高效實現間接DAXPY操作

for i = 1:n 
    a[i] = a[i]-$\alpha$ b[i]

一個BLAS水平一個操作有可通過各種BLAS庫如MKL高效執行這種定期DAXPY的。

在我的情況下，我想實現以下使用間接尋址的daxpy操作的變體。

for i = 1:n 
    a[ind1[i]] = a[ind1[i]]-$\alpha$ b[i]

其中ind1包含需要更新的向量A的元素的索引。我得到的信息是ind1是一個單調的數組，即$ ind1 [i]> ind [j] \ forall i> j $。

我假設這樣的計算經常出現在稀疏線性代數中。有沒有人知道基於SSE/AVX的這種例程的有效實現。

2013-12-19 zimbra314

如果'ind1'數組包含連續運行，您可能可以做些事情來加速操作。如果'ind1'基本上是任意的，那麼幾乎沒有什麼可以優化它（除了可能用於預取）。 SSE/AVX根本沒有辦法進行必要的收集/分散操作。 –

它確實包含連續運行，但可能是10-30的小長度。我的猜測是prefetching可能會工作，但我已經被警告過，手動預取可能會造成更多的傷害，而不是任何優勢 – zimbra314

你可以做movss，然後3 insrps，直到你填充一個向量，然後做數學。然後分散回地點？如果索引是16位或32位，則可以將多個索引一次加載到64位GP寄存器中，並移位+ movzx以獲取數組索引。

參見例如https://github.com/pcordes/par2-asm-experiments/blob/master/asm-pinsrw.s。該功能基於16位字的高低兩位查找16位GF16長處的組件。所以我的索引是8位的，所以我可以在一個64位的負載中獲得很多。

如果您的索引中有足夠多的連續數據值得大量分支預測失敗，那麼正如@StephenCanon所說，只需要尋找運行並使用SIMD執行每個連續的數據塊即可。

2015-07-09 20:30:20

回答