N向量的內存佈局

我想知道爲了提高效率，我應該如何存儲小尺寸的N個向量（比如X，Y，Z）。對於緩存局部性的原因，我期望一個接一個地排列向量[N] [3]（行主）會比佈局[3] [N]產生更好的結果（其中維X，Y那麼當使用OpenMP進行向量操作時，Z會連續佈局）。N向量的內存佈局

但是，將每個向量乘以3x3矩陣，並使用Intel MKL BLAS，我發現佈局[3] [N]的速度是其兩倍。

我猜測緩存區域是通過SSE指令適用於非分步數據這一事實進行平衡的。這讓我想知道人們（例如計算機圖形學）如何存儲它們的向量，以及是否存在其他利弊。

來源

2012-12-12 pch

有兩種常用的數據佈局：結構數組（AoS）和數組結構（SoA）。

AOS：

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

SoA的：

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

爲了乘以在AOS情況下，每個點具有一個3×3矩陣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個浮點數），它還提供點積o但是問題在於向向量寄存器中加載3個浮點數是非常低效的操作。可以添加額外的float字段來填充結構，但是由於兩個向量操作數中的第4個浮點未使用（或不包含有用信息），所以仍然會損失1/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]>

有三種載體負載，三標量矢量乘法，三次向量加法，在這裏一個矢量店。它們都利用了SSE的100％的矢量功能。唯一的問題是當點的數量不能被4整除時，但是可以輕鬆地填充數組，或者編譯器可以生成標量代碼來執行剩餘的串行迭代。無論哪種方式，如果你有很多點，那麼在剩下的1到3個點上只失去一些性能比在每個點上不斷利用硬件更有利。另一方面，如果您經常需要訪問隨機點的元組，則SoA實現會導致三個緩存行讀取（如果數據不適合緩存），而AoS實現將需要一個緩存行讀取或兩個（填充可以避免需要兩個負載的情況）。所以答案是 - 數據結構取決於哪種操作主導了算法。

來源

2012-12-13 11:28:46

N向量的內存佈局

回答

相關問題