arXiv:2501.08889cs.ARcs.AI2025-01中稿 · publication in IEE…被引 5

将卡氏乘法拓展至矩阵乘法,提升硬件效率。

Karatsuba Matrix Multiplication and its Efficient Custom Hardware Implementations

  • 将卡氏算法扩展到矩阵乘法,减少额外加法开销。
  • 相比传统方法,面积或执行时间降低20%以上。
  • 适合深度学习加速器等定制硬件场景使用。

尽管卡氏算法能降低大整数乘法的复杂度,但其额外加法操作在常用位宽的小整数上削弱了优势。本文提出将标量卡氏乘法算法扩展至矩阵乘法,保持原始卡氏算法的乘法复杂度降低,同时减少额外加法复杂度。此外,设计了高效利用该扩展算法的定制硬件架构。结果表明,所提算法与硬件架构在整数矩阵乘法中相比标量卡氏或传统方法,在面积或执行时间上均有实际提升;且支持通过可验证的流水线阵列和常规乘法器架构实现。通过算法与架构的复杂度分析,并在端到端深度学习加速器系统中与基线及先进方案对比,验证了其在性能/面积比上的优势。

原文摘要 · Abstract (English)

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.

矩阵乘法硬件加速卡氏算法

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。