AVX2稀疏矩阵乘法

Question

我试图利用新的AVX2集合指令来加速稀疏矩阵向量乘法。矩阵采用CSR (或Yale)格式，有一个行指针，它指向列索引数组，该数组又保存这些列。这种mul的C代码确实如下所示：

for (int row = 0; row < n_rows - 1; row++) {
    double rowsum = 0;
    for (int col = row_ptr[row]; col < row_ptr[row + 1]; col++) {
        rowsum += values[col] * x[col_indices[col]];
    }
    result[row] = rowsum;
}

现在，我的目标是用AVX2本质加速这一过程。以下代码适用于基于https://blog.fox-toolkit.org/?p=174的最新英特尔或GCC。我在这里删除了剩下的部分，因为我的行都对齐了4个双倍(列% 4==0) (幸运的是我)。如果有人感兴趣的话，我也有处理剩余部分的代码，但重点是，代码实际上稍微慢了一些。我检查了反汇编，对于上面的版本，只生成了FP指令，对于我的AVX2代码，所有的AVX2操作都如预期的那样出现。即使有适合缓存的小矩阵，AVX2版本也是不好的。我现在很困惑..。

double* value_base = &values[0];
double* x_base = &x[0];
int*    index_base = &col_indices[0];


for (int row = 0; row < n_rows - 1; row++) {
    int col_length   = row_ptr[row + 1] - row_ptr[row];

    __m256d rowsum = _mm256_set1_pd(0.);
    for (int col4 = 0; col4 < col_length; col4 += 4) {
        // Load indices for x vector(const __m128i*)
        __m128i idxreg     = _mm_load_si128((const __m128i*)index_base);
        // Load 4 doubles from x indexed by idxreg (AVX2)
        __m256d x_     = _mm256_i32gather_pd(x_base, idxreg, 8);
        // Load 4 doubles linear from memory (value array)
        __m256d v_     = _mm256_load_pd(value_base);
        // FMA: rowsum += x_ * v_
        rowsum = _mm256_fmadd_pd(x_, v_, rowsum);

        index_base += 4;
        value_base += 4;
    }
    __m256d s = _mm256_hadd_pd(rowsum, rowsum);
    result[row] = ((double*)&s)[0] + ((double*)&s)[2];
    // Alternative (not faster):
    // Now we split the upper and lower AVX register, and do a number of horizontal adds
    //__m256d hsum = _mm256_add_pd(rowsum, _mm256_permute2f128_pd(rowsum, rowsum, 0x1));
    //_mm_store_sd(&result[row], _mm_hadd_pd( _mm256_castpd256_pd128(hsum), _mm256_castpd256_pd128(hsum) ) );
}

欢迎任何建议。

非常感谢，克里斯

Answer 1

集中在哈斯韦尔是缓慢的。我以几种不同的方式实现了16位值的8位索引LUT查找(对于GF16乘用于par2)，以找出最快的方法。在Haswell上，VPGATHERDD版本花费的时间是movd / pinsrw版本的1.7倍。(在集合之后只需要几个VPUNPCK / shift指令。) 这里的代码，如果有人想运行基准测试。

当一条指令第一次被引入时，人们通常不会投入大量的硅来使它变得超快。它只是为了获得HW的支持，所以可以编写代码来使用它。为了在所有CPU上获得理想的性能，您需要做x264对pshufb所做的事情:为CPU(如Core2 )设置一个SLOW_SHUFFLE标志，并将其考虑到最佳的例程查找函数指针设置中，而不仅仅是CPU支持的内容。

对于那些不太热衷于为每个运行的CPU调整asm版本的项目，引入一个非加速比的指令版本会让人们更快地使用它，所以当下一个设计出现并且它的速度更快的时候，更多的代码会加速。发布一个像Haswell这样的设计，其中design实际上是一个减速是有点冒险。也许他们想看看人们会如何使用它？它确实增加了代码密度，这有助于当集合不是一个紧密的循环时。

Broadwell应该有一个更快的集合实现，但我没有权限。列出指令延迟/吞吐量的英特尔手册说，布罗德韦尔的收集速度大约快了1.6倍，因此它仍然比手工制作的循环稍微慢一些，该循环将GP regs中的索引转移/解压缩，并将它们用于PINSRW向量。

如果gather可以利用多个元素具有相同索引的情况，甚至可以利用指向同一个32B提取块的索引，则可能会根据输入数据出现一些大的加速。

希望Skylake能进一步改善。我想我读到了一些东西，上面写着它会的，但经过查证，我什么也没找到。

RE:稀疏矩阵:是否有重复数据的格式，这样就可以对行或列进行连续读取？这不是我必须为之编写代码的东西，但我想我在一些答案中提到过它。