你会如何转置二进制矩阵？

Question

我在C++中有二进制矩阵,我用8位值向量重复.

例如,以下矩阵:

1 0 1 0 1 0 1
0 1 1 0 0 1 1
0 0 0 1 1 1 1

表示为:

const uint8_t matrix[] = {
    0b01010101,
    0b00110011,
    0b00001111,
};

我这样做的原因是因为然后计算这样的矩阵和8位向量的乘积变得非常简单和有效(每行只有一个按位AND和奇偶校验计算),这比单独计算每个位.

我现在正在寻找一种有效的方法来转置这样的矩阵,但是我无法弄清楚如何在不必手动计算每个位的情况下进行转换.

只是为了澄清一下,对于上面的例子,我想从转置中得到以下结果:

const uint8_t transposed[] = {
    0b00000000,
    0b00000100,
    0b00000010,
    0b00000110,
    0b00000001,
    0b00000101,
    0b00000011,
    0b00000111,
};

注意:我更喜欢一种算法,它可以用任意大小的矩阵来计算,但我也对只能处理某些大小的算法感兴趣.

Answer 1

我花了更多的时间寻找解决方案,而且我找到了一些好的解决方案.

SSE2的方式

在现代的x86 CPU上,使用SSE2指令可以非常有效地转换二进制矩阵.使用这样的指令可以处理16×8矩阵.

这个解决方案的灵感来自mischasan的博客文章,远远优于我迄今为止对这个问题的每一个建议.

这个想法很简单:

• #include <emmintrin.h>
• 将16个uint8_t变量打包成一个__m128i
• 使用_mm_movemask_epi8得到每个字节的MSB,产生uint16_t
• 用于_mm_slli_epi64将128位寄存器移位1
• 重复,直到你有所有8 uint16_t秒

通用的32位解决方案

不幸的是,我还需要在ARM上完成这项工作.在实现SSE2版本之后,很容易找到NEON等价物,但Cortex-M CPU(与Cortex-A相反)没有SIMD功能,因此NEON对我来说不是很有用.时刻.

注意:因为Cortex-M 没有原生的64位算术,所以我不能在任何建议的答案中使用这些想法,将8x8块视为一个uint64_t.大多数具有Cortex-M CPU的微控制器也没有太多内存,所以我更喜欢在没有查找表的情况下完成所有这些操作.

经过一番思考后,可以使用普通的32位算术和一些聪明的编码来实现相同的算法.这样,我一次可以使用4×8块.它是由一个同事建议的,神奇之处在于32位乘法的工作原理:你可以找到一个32位的数字,你可以用它来乘法,然后每个字节的MSB在高32位中相互接近.结果.

• uint8_t以32位变量打包4
• 屏蔽每个字节的第1位(使用0x80808080)
• 乘以它 0x02040810
• 取乘法的高32位的4个LSB
• 通常,您可以屏蔽每个字节中的第N位(将屏蔽右移N位)并乘以幻数,向左移位N位.这里的优点是,如果您的编译器足够智能以展开循环,则掩码和"幻数"都将成为编译时常量,因此移位它们不会产生任何性能损失.最后一个4位系列有一些问题,因为那时一个LSB​​丢失,所以在这种情况下我需要将输入左移8位并使用与第一个4位系列相同的方法.

如果使用两个4×8块执行此操作,则可以完成8x8块并排列结果位,以便一切都进入正确的位置.

Answer 2

我的建议是,你不进行换位,而是将一位信息添加到矩阵数据中,指示矩阵是否转置.

现在,如果要将转置矩阵与向量相乘,它将与向量乘以左边的矩阵(然后转置)相同.这很简单:只需xor8位数字的一些操作.

然而,这使得一些其他操作变得复杂(例如,添加两个矩阵).但是在评论中你说乘法正是你想要优化的.

Answer 3

这是 Jay Foad 给我的关于快速布尔矩阵转置的电子邮件文本：

布尔转置算法的核心是一个我将调用的函数transpose8x8，它将一个 8x8 布尔矩阵转置成一个 64 位字（按行主顺序从 MSB 到 LSB）。要转置任何宽度和高度为 8 的倍数的矩形矩阵，请将其分解为 8x8 块，单独转置每个块并将它们存储在输出中的适当位置。要加载 8x8 块，您必须加载 8 个单独的字节并将它们移位和或转换为 64 位字。同样的东西用于存储。

一个简单的 C 实现transpose8x8依赖于这样一个事实，即平行于前导对角线的任何对角线上的所有位向上/向下和向左/向右移动相同的距离。例如，前导对角线上方的所有位必须向左移动一位，向下移动一位，即在打包的 64 位字中向右移动 7 位。这导致了这样的算法：

transpose8x8(word) {

  return
    (word & 0x0100000000000000) >> 49 // top right corner

  | (word & 0x0201000000000000) >> 42

  | ...

  | (word & 0x4020100804020100) >> 7 // just above diagonal

  | (word & 0x8040201008040201) // leading diagonal

  | (word & 0x0080402010080402) << 7 // just below diagonal

  | ...
  | (word & 0x0000000000008040) << 42

  | (word & 0x0000000000000080) << 49; // bottom left corner

}

这比之前的实现快了大约 10 倍，后者从内存中的源字节单独复制每个位并将其合并到内存中的目标字节中。

或者，如果您有 PDEP 和 PEXT 指令，您可以实现完美的 shuffle，并使用它来执行 Hacker's Delight 中提到的转置。这明显更快（但我没有时间方便）：

shuffle(word) {
    return pdep(word >> 32, 0xaaaaaaaaaaaaaaaa) | pdep(word, 0x5555555555555555);
} // outer perfect shuffle

transpose8x8(word) { return shuffle(shuffle(shuffle(word))); }

POWER 的vgbbd指令transpose8x8在单个指令中有效地实现了全部（并且由于它是一条 128 位向量指令，因此它在低 64 位和高 64 位上独立地执行了两次）。这比普通的 C 实现提高了大约 15% 的速度。（只有 15%，因为虽然位旋转要快得多，但现在总体运行时间主要由加载 8 个字节并将它们组装到 的参数中transpose8x8，以及获取结果并将其存储为 8 个单独的字节.)