Transitive Array: An Efficient GEMM Accelerator with Result Reuse Conference: Proceedings of the 52nd Annual International Symposium on Computer Architecture; June 21–25, 2025; Tokyo, Japan Proceedings of the 52nd Annual International Symposium on Computer Architecture (ISCA ’25), June 21–25, 2025,

Cong Guo, Chiyue Wei, Jiaming Tang, Bowen Duan, Song Han, Hai Li, Yiran Chen · 2025

Read Transitive Array: An Efficient GEMM Accelerator with Result Reuse Conference: Proceedings of the 52nd Annual International Symposium on Computer Architecture; June 21–25, 2025; Tokyo, Japan Proceedings of the 52nd Annual International Symposium on Computer Architecture (ISCA ’25), June 21–25, 2025, by Cong Guo, Chiyue Wei, Jiaming Tang, Bowen Duan, Song Han, Hai Li, Yiran Chen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-16339.txt.

Introduction

Cong Guo and co-authors build a chip accelerator that reuses its own past answers, in a 2025 paper. Matrix multiplication dominates the cost of running neural networks. Cutting number precision helped, but memory and compute demands still strain small devices. The team noticed a different kind of waste: many partial results repeat across the computation.

They call the pattern transitive sparsity and chart it as a directed graph without cycles. The graph yields an execution order that reuses stored results instead of recomputing them. Their Transitive Array hardware balances work across parallel lanes without any multipliers. Tests showed several-fold speedups and large energy savings over leading accelerators. The design targets efficient artificial intelligence on constrained hardware.

Catalog record

CREATORCong Guo, Chiyue Wei, Jiaming Tang, Bowen Duan, Song Han, Hai Li, Yiran Chen
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE64 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-16339

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Transitive Array: An Efficient GEMM Accelerator with Result Reuse Conference: Proceedings of the 52nd Annual International Symposium on Computer Architecture; June 21–25, 2025; Tokyo, Japan Proceedings of the 52nd Annual International Symposium on Computer Architecture (ISCA ’25), June 21–25, 2025, Tokyo, Japan DOI: 10.1145/3695053.3731043 ISBN: 979-8-4007-1261-6/2025/06 CCS: Computer systems organization Single instruction, multiple data CCS: Computer systems organization Systolic arrays Cong Guo, Chiyue Wei, Jiaming Tang, Bowen Duan, Song Han, Hai Li, Yiran Chen Abstract . Deep Neural Networks (DNNs) and Large Language Models (LLMs) have revolutionized artificial intelligence, yet their deployment faces significant memory and computational challenges, especially in resource-constrained environments. Quantization techniques have mitigated some of these issues by reducing data precision, primarily focusing on General Matrix Multiplication (GEMM). This study introduces a novel sparsity paradigm, transitive sparsity , which leverages the reuse of previously computed results to substantially minimize computational overhead in GEMM operations. By representing transitive relations using a directed acyclic graph, we develop an efficient strategy for determining optimal execution orders, thereby overcoming inherent challenges related to execution dependencies and parallelism. Building on this foundation, we present the Transitive Array , a multiplication-free accelerator designed to exploit transitive sparsity in GEMM. Our architecture effectively balances computational workloads across multiple parallel lanes, ensuring high efficiency and optimal resource utilization. Comprehensive evaluations demonstrate that the Transitive Array achieves approximately 7.46 × \times and 3.97 × \times speedup and 2.31 × \times and 1.65 × \times energy reduction compared to state-of-the-art accelerators such as Olive and BitVert while maintaining comparable model accuracy on LLaMA models. † † cc-license: by 1. Introduction Deep neural networks (DNNs) ( LeCun et al. 2015 ; Goodfellow 2016 ) have become foundational to modern artificial intelligence, demonstrating transformative potential across various applications. Among these, large language models (LLMs) ( Devlin 2018 ; Brown et al. 2020 ) stand out for their ability to generate human-like text, understand complex language, and perform advanced reasoning, making them crucial in natural language processing ( Vaswani 2017 ; Brown 2020 ) . However, as DNNs scale, they introduce substantial memory and computational overheads that challenge their deployment efficiency, particularly in resource-constrained environments ( Shoeybi et al. 2020 ; Kaplan et al. 2020 ) . Quantization ( Jacob et al. 2017 ) has thus emerged as a critical research avenue, offering methods to reduce model size and computational load by representing parameters with lower precision while aiming to retain model accuracy. Most quantization approaches aim to reduce the data precision of general matrix multiplication (GEMM) operations, which are fundamental to DNNs ( Chetlur et al. 2014 ; Jouppi et al. 2017 ) , as they represent the core computational workload in both training and inference. Recently, quantization has regained popularity in LLMs. AWQ ( Lin et al. 2024a ) achieves a 4-bit compression of weights with negligible accuracy loss. Additional advanced algorithms (e.g., BitNet1.58 ( Wang et al. 2023 ) ) push the limits further by targeting 1-bit weight quantization. Through such innovations, quantization significantly enhances LLM efficiency and deployability. Building on quantization, this study explores novel opportunities to accelerate GEMM operations. Bit-slicing has proven to be an effective technique in DNN accelerators ( Lu et al. 2021 ; Shi et al. 2024 ; Chen et al. 2024b ; Albericio et al. 2017 ) . It decomposes each bit of a quantized matrix into multiple binary 1-bit matrices, as illustrated in Fig. 2 . By leveraging bit-slicing, we transform quantized integer-based GEMM into binary GEMM, as shown in Fig. 1 . Bit-slice accelerators exploit bit-level sparsity, achieving computational reductions of up to 50–60% ( Chen et al. 2024b ) . However, our analysis reveals even greater sparsity potential beyond bit sparsity, highlighting further opportunities for optimization. This study introduces a novel sparsity paradigm termed transitive sparsity , which leverages previously computed results to minimize overall computations. As illustrated in Fig. 1 , consider Row-0 of the binary matrix, represented by the bit pattern 1011 , which requires the accumulation of values 6 , -2 , and 4 , and Row-2, represented by 0011 , which involves the accumulation of -2 and 4 . Since both rows share the accumulation of -2 and 4 , we can reuse the computed result of Row-2 for Row-0, significantly reducing the accumulation operations in GEMM. In the example shown in Fig. 1 , transitive sparsity enables a 2.5-fold reduction in operations (from 10 to 4) compared to bit sparsity and a 4-fold decrease over dense GEMM. Furthermore, it is worth noting that transitive sparsity is algorithm-agnostic and lossless, preserving the computational accuracy of quantized GEMM operations. Our evaluation demonstrates that transitive sparsity theoretically reduces overall computations by 8\times (i.e., 87.5\% sparsity) for the LLaMA-7B ( Touvron et al. 2023a ) compared to dense GEMM without accuracy loss after the quantization. Figure 1. Comparison of bit sparsity and transitive sparsity (Ours) on the binary general matrix multiplication. To harness the benefits of transitive sparsity, we propose a novel computer architecture called the transitive array . However, we encountered several challenges in efficiently implementing transitive sparsity. First, transitive sparsity imposes strict requirements on execution order. For example, if Row-0 is computed before Row-2, it prevents reuse of Row-2’s results. For weight tensors, we can precompute an optimal execution order offline. However, attention operations ( Vaswani et al. 2023 ) in LLM present a complication, as they involve dynamically generated activations (e.g., the Query and Key tensors). This dynamic nature makes it challenging to determine execution order on the fly without incurring significant overhead. This dynamic limitation is also observed in most existing accelerators ( Chen et al. 2024b ; Guo et al. 2023 ; Lu et al. 2021 ) , which consequently lack adequate support for attention layers in their designs. Instead, these accelerators predominantly focus on fully connected (FC) layers with pre-processed weights. Second, even with an optimized execution order, the strict dependencies within transitive sparsity result in inherently serial execution, greatly restricting parallelism. Additionally, the irregularity of sparsity patterns makes it difficult to balance workloads across multiple parallel lanes, as varying sparsity levels lead to inconsistent computational loads and underutilization. Fortunately, we identified certain properties within transitive sparsity that help address these challenges. Leveraging these insights, we can represent the transitive relations of the transitive sparsity using a directed acyclic graph, precisely a Hasse graph ( contributors [n. d.] ; Hasse 1967 ) . This representation enables us to reduce the overhead of generating an optimal execution order, achieving linear complexity compared to the cubic complexity typically associated with GEMM. Following this, we assign rows of the bit-sliced matrix across multiple parallel lanes and have proven that this approach eliminates dependencies among parallel lanes. Additionally, to address workload imbalance, we introduce a simple yet effective method to ensure balanced distribution across multiple lanes before execution, making sparse execution more regular and highly efficient. This work presents a comprehensive solution and novel architecture to enable transitive sparsity in GEMM operations. This work provides a new perspective on transitive sparsity and insights for future designs of more versatile GEMM accelerators. Compared to state-of-the-art accelerators like Olive ( Guo et al. 2023 ) , which leverages outlier-aware quantization, and BitVert ( Chen et al. 2024a

Read the complete text