具有列优先布局的 int8 x uint8 矩阵向量乘积

Question

我希望使用 AVX-1 或更早的指令来加速这个矩阵向量乘积：

    // a is an array N columns of length M each
    // b is length N
    // c is length M
    //
    // M % 32 == N % 32 == 0
    // all memory is nicely aligned and unaliased
    
    void mat_vec_prod(const int8_t** a, const uint8_t* b, int16_t* c) {
        for(int i = 0; i < M; ++i) {
            c[i] = 0;
            for(int j = 0; j < N; ++j)
                c[i] += int16_t(a[j][i]) * int16_t(b[j]);
        }
    }

（我知道交换循环是值得考虑的）

内在函数 _mm_maddubs_epi16 和 _mm_maddubs_pi16 可以帮助 uint8 x int8 点积，但是，在我的例子中，矩阵的布局很尴尬，它是一个指针数组列（而不是行）。

一种可能性是加载 a 的 8x8 块，然后将它们转置并乘以 b 的片段。（我在 8x8 字节矩阵转置上发现）。但是，这将不得不使用 _mm_maddubs_pi16，它的吞吐量只有 _mm_maddubs_epi16.

的一半

我的问题是：是否值得尝试加载和转置 16x16 补丁，或者我会运行出 xmm 寄存器？我的策略应该是什么？

Answer 1

我会采用 chtz 建议的交错方法。

从两行中读取 32 或 64 字节（又名完整缓存行），然后交错。

至少 32 个字节，因为每行的宽度 % 32 == 0，最好是 64 个字节，因为这是一个完整的缓存行，它会占用 16 个寄存器中的 8 个累加器。

另外我猜想将输入处理为块（8、16 或 32 行）乘以（32 或 64 列）会比处理所有行更好；您处理的行越多，将累加器溢出到内存的需求就越少，以非线性顺序处理的行越多，从缓存中逐出即将需要的行的可能性就越高。 4 行应该绝对安全。

交织 b 由

很自然地完成

auto b0to7 = _mm_unpacklo_epi16(b,b);
auto b8tof = _mm_unpackhi_epi16(b,b);
auto b01 = _mm_shuffle_epi32(b0to7, 0x00);
auto b23 = _mm_shuffle_epi32(b0to7, 0x55);
...
auto bef = _mm_shuffle_epi32(b8tof, 0xff);

将输入拆分为 even/odd 序列的另一种可能性是每 16 字节需要 4 条算术指令，或者每 32 字节需要 8 条指令：

// common terms
auto b_even = _mm_set1_epi16(b[j] & 0x00ff);
auto b_odd = _mm_set1_epi16(b[j] * 256);
// per 16 input bytes in `a`
auto mul_even = _mm_maddubs_epi16(row_j, b_even);
auto mul_odd = _mm_maddubs_epi16(row_j, b_odd);
sum_even = _mm_add_epi16(sum_even, mul_even);
sum_odd = _mm_add_epi16(mul_odd, mul_even);

这显然不像

那么紧

auto prod_lo = _mm_unpacklo_epi8(row_j, row_jplus1);
auto prod_hi = _mm_unpackhi_epi8(row_j, row_jplus1);
prod_lo = _mm_maddubs_epi16(prod_lo, b01);
prod_hi = _mm_maddubs_epi16(prod_hi, b01);
sum_lo = _mm_add_epi16(sum_lo, prod_lo);
sum_hi = _mm_add_epi16(sum_hi, prod_hi);

但是洗牌只能在端口 5 上执行，因为 2 mul/adds 可以在每个周期开始。它们的性能可能非常接近。

具有列优先布局的 int8 x uint8 矩阵向量乘积

int8 x uint8 matrix-vector product with column-major layout

assembly

x86

simd

sse

avx