A Framework for Practical Parallel Fast Matrix Multiplication
A Framework for Practical Parallel Fast Matrix Multiplication
复制标题
DOI：
10.1145/2688500.2688513
复制
发表时间：
2015-08-01
影响因子：
--
通讯作者：
Ballard, Grey
中科院分区：
文献类型：
--
作者：
Benson, Austin R.;Ballard, Grey
矩阵乘法是许多科学学科中的一种基本计算。在这篇文章中，我们证明了新的快速矩阵乘法算法在中等大小和形状的问题上可以显著优于经典算法和Strassen的快速算法的供应商实现。此外，我们还证明了快速算法的最佳选择不仅取决于矩阵的大小，还取决于矩阵的形状。我们开发了一个代码生成工具来自动实现每个快速算法的多个顺序和共享内存并行变体，包括我们新的并行化方案。这使我们能够对几个问题大小的20多个快速算法进行快速基准测试。此外，我们还讨论了这些算法在共享内存机器上的一些实际实现问题，这些问题可以指导进一步的快速算法实用化的研究。
Matrix multiplication is a fundamental computation in many scientific disciplines. In this paper, we show that novel fast matrix multiplication algorithms can significantly outperform vendor implementations of the classical algorithm and Strassen's fast algorithm on modest problem sizes and shapes. Furthermore, we show that the best choice of fast algorithm depends not only on the size of the matrices but also the shape. We develop a code generation tool to automatically implement multiple sequential and shared-memory parallel variants of each fast algorithm, including our novel parallelization scheme. This allows us to rapidly benchmark over 20 fast algorithms on several problem sizes. Furthermore, we discuss a number of practical implementation issues for these algorithms on shared-memory machines that can direct further research on making fast algorithms practical.