3

我想知道我应该如何存储 N 个小维度的向量（比如说 X、Y、Z）以提高效率。

出于缓存局部性的原因，我期望将向量一个接一个地打包 [N][3]（行主要）会比布局 [3][N] （其中放置维度 X、Y 然后 Z连续输出）在使用 OpenMP 进行矢量运算时。

但是，将每个向量乘以一个 3x3 矩阵，并使用英特尔 MKL BLAS，我发现布局 [3][N] 的速度是原来的两倍。

我猜缓存局部性与 SSE 指令适用于非跨步数据的事实相抵消。这让我想知道人们（例如在计算机图形学中）如何存储他们的向量以及是否有其他优点和缺点。

4

1 回答 1

1

常用的数据布局有两种：结构数组 (AoS) 和数组结构 (SoA)。

服务端：

struct
{
   float x;
   float y;
   float z;
} points[N];

索阿：

struct
{
   float x[N];
   float y[N];
   float z[N];
} points;

为了将 AoS 案例中的每个点与 3x3 矩阵相乘M，循环体如下所示：

r[i].x = M[0][0]*points[i].x +
         M[0][1]*points[i].y +
         M[0][2]*points[i].z;
// ditto for r[i].y and r[i].z

SSE 可以一次乘以 4 个浮点数（AVX 可以乘以 8 个浮点数），它还提供点积运算，但问题是在向量寄存器中加载 3 个浮点数是非常低效的操作。可以添加一个额外的float字段来填充结构，但仍然会损失 1/4 的计算能力，因为两个向量操作数中的第 4 个浮点数未使用（或不包含有用信息）。您也不能对这些点进行矢量化，例如一次处理 4 个点，因为一次加载points[i].x需要points[i+3].x收集负载，这在 x86 上（尚）不受支持（尽管一旦支持 AVX2 的 CPU 可用，这将改变）。

在 SoA 案例中，内部循环是：

r.x[i] = M[0][0]*points.x[i] +
         M[0][1]*points.y[i] +
         M[0][2]*points.z[i];
// ditto for r.y[i] and r.z[i]

它基本上看起来相同，但有一个非常关键的区别。现在编译器可以使用向量指令一次处理 4 个点（甚至 AVX 的 8 个点）。例如，它可以展开循环并将其转换为以下等效向量：

<r.x[i], r.x[i+1], r.x[i+2], r.x[i+3]> =
    M[0][0]*<x[i], x[i+1], x[i+2], x[i+3]> +
    M[0][1]*<y[i], y[i+1], y[i+2], y[i+3]> +
    M[0][2]*<z[i], z[i+1], z[i+2], z[i+3]>

这里有三个向量加载、三个标量向量乘法、三个向量加法和一个向量存储。它们都 100% 地利用了 SSE 的向量能力。唯一的问题是点的数量不能被 4 整除，但可以轻松填充数组，或者编译器可能会生成标量代码以串行执行剩余的迭代。无论哪种方式，如果您有很多点，那么仅在剩余的 1 到 3 个点上损失一些性能要比在每个点上不断地利用硬件要好得多。

另一方面，如果您经常需要访问(x,y,z)随机点的元组，那么 SoA 实现将导致三个缓存行读取（如果数据不适合缓存），而 AoS 实现将需要一个或两个（带有填充可以避免需要两个负载的情况）。所以答案是——数据结构取决于什么样的操作主导算法。

于 2012-12-13T11:28:46.850 回答