While the Karatsuba algorithm reduces the complexity of large integer multiplication, the extra additions required minimize its benefits for smaller integers of more commonly-used bitwidths. In this work, we propose the extension of the scalar Karatsuba multiplication algorithm to matrix multiplication, showing how this maintains the reduction in multiplication complexity of the original Karatsuba algorithm while reducing the complexity of the extra additions. Furthermore, we propose new matrix multiplication hardware architectures for efficiently exploiting this extension of the Karatsuba algorithm in custom hardware. We show that the proposed algorithm and hardware architectures can provide real area or execution time improvements for integer matrix multiplication compared to scalar Karatsuba or conventional matrix multiplication algorithms, while also supporting implementation through proven systolic array and conventional multiplier architectures at the core. We provide a complexity analysis of the algorithm and architectures and evaluate the proposed designs both in isolation and in an end-to-end deep learning accelerator system compared to baseline designs and prior state-of-the-art works implemented on the same type of compute platform, demonstrating their ability to increase the performance-per-area of matrix multiplication hardware.

本研究解决了大型整数乘法中卡拉茨巴算法在小整数乘法中效益减低的问题。我们提出将标量卡拉茨巴乘法算法扩展到矩阵乘法，并设计了高效的硬件架构以实现这一扩展，显著降低了额外加法的复杂度。研究表明，所提出的算法和硬件架构在矩阵乘法中相较于传统方法提供了更好的面积和执行时间效率，这对深度学习加速器系统的性能提升具有重要意义。

卡拉茨巴矩阵乘法及其高效定制硬件实现