如何使用 SIMD 优化单元宽度测量（找到 8x8 字节块中具有非零字节的第一列）

Question

我有一个算法，通过计算从单元格起始位置到其中仅包含零的第一列的距离来测量位图 (

8x8

) 中每个单元格 (

128x128

) 的宽度。如果没有这样的列，则为该单元格分配宽度 8。

这是该程序的源代码：

#include <stdint.h>

uint8_t bitmap[128][128];  // all 8 bits are used, so 0..255
int widths[16][16];        // any integer type is fine, like uint8_t

void measure_cell(int i, int j)
{
    int x = i * 8;
    int x_end = x + 8;

    /* Horizontal sweep */
    while (x < x_end) {
        int y = j * 8;
        int y_end = y + 8;

        /* Vertical sweep */
        while (y < y_end && !bitmap[y][x])
            ++y;

        /* All-zero column? */
        if (y == y_end)
            break;

        ++x;
    }

    widths[j][i] = 8 - (x_end - x);
}

int main()
{
    /* Load bitmap from file */
    // ...

    /* Calculate widths for each cell */
    for (int j = 0; j < 16; ++j)
        for (int i = 0; i < 16; ++i)
            measure_cell(i, j);

    /* Print widths to stdout */
    // ...

    return 0;
}

有什么方法可以使用 SIMD 来加快速度吗？假设我的目标是 x86-64。

Answer 1

• 垂直或 8 个行数据向量（因此，如果列中的所有字节均为零，则结果的一个字节仅为 0）。
  

  _mm256_loadu_si256

  和

  _mm256_or_si256

  。
  （或者如果您在阵列上使用

  load

  ，则对齐

  alignas(32)

  。）

  如果有用，您可以使用

  pmaxub

  (

  _mm_max_epu8

  ) 来获取单元格该列中的最大值，仅当每列都为 0 时才为 0。但是如果您不打算使用最大值任何值，只需使用按位或即可。

• 比较/移动掩码以获取哪些列全为零的位掩码。
  

  _mm256_cmpeq_epi8(v, _mm256_setzero_si256())

  /

  _mm256_movemask_epi8

• 将该位掩码拆分为 8 位块（单元边界）并进行位扫描 (

  tzcnt

  / C++20

  std::countr_zero()

  / C23

  stdc_trailing_zeros

  ) 以查找第一个（最低）零的位置。
  因为你想将结果限制为

  8

  ，所以实际上是

  stdc_trailing_zeros(mask | (1<<8))

  ，或者我猜是

  stdc_trailing_zeros_uc

  ，因为

  unsigned char

  在 x86 上是 8 位宽。

_mm256_cmpeq_epi8

是

__m256i

向量的 AVX2，生成 32 位位掩码（4 个单元格宽）。
同样的事情仅适用于带有

__m128i

向量的 SSE2（16 位掩码 = 2 个单元）。

---

如果您有 AVX-512，您也可以对位扫描部分进行矢量化。如果您使用 bithack 来隔离最低设置位，则

63 - vplzcntq

可以用作 tzcnt。 （我猜特殊情况是得到 64 而不是 -1？）。 您不需要布尔化为向量掩码（这会将您限制为 256 位向量，因为 AVX-512 只能与掩码寄存器进行比较）。 相反，只需找到 64 位元素中最低设置位的位置，然后右移 3 即可获得最低非零字节的索引。 这应该可以方便地清除字节内位索引中含有不需要的垃圾的低 3 位。

或者将掩码存储到临时存储中的某个地方（可能是

width

数组，然后用计数替换它）。 然后稍后重新加载向量以获得每个字节的向量化

tzcnt

。 没有

vplzcntb

，但也许一个 bithack 可以有效地设置

vpopcntb

（Ice Lake 及更高版本中的 AVX512BITALG）。 我们希望将尾随的

0

转换为

1

并清除其他所有内容。 这就像

blsmsk

(x-1) ^ x

，只不过这是一个掩码，直到包括最低的

1

位。

我不知道有什么方法可以制作掩模，但不包括最低的

1

位。 我猜有

(-x) & x

(

blsi

) 减 1。 https://catonmat.net/low-level-bit-hacks 不包含这一点。 https://web.archive.org/web/20231120194321/https://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightLinear有一些直接计算尾随位的bithacks，而不是输入popcnt，这当缩小到 8 位时，需要更少的步骤。