高效实施间接操作

Question

_axpy 是一个 blas 一级操作，它实现如下

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

可以通过各种blas库（如MKL）有效地实现这种常规daxpy。

就我而言，我想实现以下使用间接寻址的 daxpy 操作变体。

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

其中 ind1 包含向量 A 的元素索引，需要更新。我得到的信息是 ind1 是一个单调数组，即 $ind 1[i]>ind[j] \forall i>j$。

我认为这种计算经常出现在稀疏线性代数中。有谁知道基于SSE/AVX的任何有效实现这样的例程。

Answer 1

你可以

做movss，然后做3 insrps，直到你填充一个向量，然后做数学运算。 然后分散回地点？ 如果索引为 16 位或 32 位，则可以一次将多个索引加载到 64 位 GP 寄存器中，然后 shift + movzx 获取数组索引。

例如，请参阅 https://github.com/pcordes/par2-asm-experiments/blob/master/asm-pinsrw.s。 该函数根据 16 位字的高半部分和低半部分查找 16 位 GF16 长乘分量。 所以我的索引是 8 位的，所以我可以在单个 64 位加载中获得很多。

如果索引中有足够的连续数据值得进行大量分支错误预测查找，那么正如@StephenCanon所说，可能值得仅查找运行并使用 SIMD 执行每个连续块。