二进制矩阵向量乘法

Question

7

我希望能够将一个8x8的二进制矩阵，表示为一个无符号64位整数，乘以一个由无符号字符表示的8位向量。然而，由于其他问题，矩阵必须按列排序，因此没有简单的匹配字节以进行易于计算的乘法。

有什么办法可以加快这样的计算速度吗？每个操作都很重要，因为我需要进行数十亿次这样的计算。

这些乘法在2元域（F-2）上进行。

- Kornel Kisielewicz

你能举个（慢）代码的例子吗？你目前的速度是多少？你的目标是现代的x86/x86_64吗？ - osgx

运行在64位架构上--慢速代码是从F-7直接翻译过来的，因此它逐位相乘。 - Kornel Kisielewicz

1

操作是result= vector*matrix还是result= matrix*vector？发布原始版本会有所帮助，因为我认为您可以将其简化为output[bit]= vector[bit] && matrix_row[bit]!=0。 - MSN

@MSN，整个意图是避免使用 [bit] 索引。 - Kornel Kisielewicz

@Kornel，没错，但如果你只是这样做的话，你可以使用SWAR技术来并行进行位操作。（在寄存器内的单指令流多数据流）这就是Peter G.所做的。 - MSN

@MSN，不用了，我已经做完计算了（这是为一篇数学论文检查一组图表）-- 不过还是谢谢你 :) - Kornel Kisielewicz

2个回答

6

你只有256个向量！使用查找表生成正确的位掩码，然后你的逻辑将类似于：

output_bit_n = bool (matrix [n] & lookup [vector])

换句话说，您的查找表可以将8位值转换为64位世界。

如果编译器没有足够智能地优化(value<<=1)|=result，您可以使用带进位旋转指令高效地将其打包到结果中。

- spraff

虽然这是有帮助的建议，但是那个基于列的乘法是最有影响力的，仍然非常感谢！ - Kornel Kisielewicz

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter G. · Accepted Answer

使用矩阵和向量表示法，可以通过以下方式进行矩阵乘法：

(col₁ ... col₈) * (v₁ ... v₈)^T = col₁ * v₁ + ... + col₈ * v₈ 其中矩阵 A = (col₁ ... col₈)，列向量 v = (v₁ ... v₈)^T。

进一步思考，如果将 8 位向量通过重复每个位 8 次扩展为 64 位向量，就可以一次性完成所有乘法，并计算 P = A & v_inflated。然后只需要进行加法（即异或）操作即可得到乘积的结果。

对于异或乘积的简单方法如下。

uint64_t P = calculated products from text above;
uint64_t sum = 0;
for( int i = 8; i; --i )
{
   sum ^= P & 0xFF;
   P >> 8;  
}