Algorithm 898 Efficient multiplication of dense matrices over GF(2)
Algorithm 898 Efficient multiplication of dense matrices over GF(2)
复制标题
算法 898 GF(2) 上稠密矩阵的高效乘法
DOI：
10.1145/1644001.1644010
复制
发表时间：
2010
影响因子：
2.7
通讯作者：
Albrecht M
中科院分区：
文献类型：
--
作者：
Albrecht M
我们描述了一个有效的实现算法的层次结构的乘法稠密矩阵在域上的两个元素（GF（2））。特别是，我们提出了我们的实现-在M4 RI库-的Strassen-Winograd矩阵乘法和“四个俄罗斯人的方法”乘法（M4 RM），并将其与其他可用的实现进行比较。良好的性能表现在AMD的Opteron上，特别是在英特尔的Core 2 Duo上。开源M4 RI库可以独立使用，也可以作为Sage数学软件的一部分使用。在机器术语中，GF（2）中的加法是逻辑异或，乘法是逻辑与，因此64位的机器字允许对GF（2）的64个元素并行操作：最多一个CPU周期用于64个并行加法或乘法。因此，GF（2）上的逐元素运算相对便宜。事实上，在本文中，我们得出的结论是，实际的瓶颈是内存读写和数据局部性问题。我们提出了我们的实证研究结果，最大限度地减少这些，并给出了分析。
We describe an efficient implementation of a hierarchy of algorithms for multiplication of dense matrices over the field with two elements (GF(2)). In particular we present our implementation -- in the M4RI library -- of Strassen-Winograd matrix multiplication and the "Method of the Four Russians" multiplication (M4RM) and compare it against other available implementations. Good performance is demonstrated on on AMD's Opteron and particulary good performance on Intel's Core 2 Duo. The open-source M4RI library is available stand-alone as well as part of the Sage mathematics software. In machine terms, addition in GF(2) is logical-XOR, and multiplication is logical-AND, thus a machine word of 64-bits allows one to operate on 64 elements of GF(2) in parallel: at most one CPU cycle for 64 parallel additions or multiplications. As such, element-wise operations over GF(2) are relatively cheap. In fact, in this paper, we conclude that the actual bottlenecks are memory reads and writes and issues of data locality. We present our empirical findings in relation to minimizing these and give an analysis thereof.