Exposing Embedded Matrix Multiplication with polyhedral transformations for CGRA compilation
Matrix-matrix multiplication ( mmul ) is a dominant computing pattern in edge workloads, but in real applications it is often embedded within larger affine programs and intertwined with other operations. Coarse-Grained Reconfigurable Arrays (CGRAs) can flexibly and efficiently support it, since they combine operation-level reconfigurability and high energy efficiency. However, mapping computational kernels that include mmul with state-of-the-art compilation strategies often leads to suboptimal results, since its multi-dimensional structure hampers the uncovering of its inherent parallelism and, ultimately, runtime performance. This article presents Kernel-CGRA, a compiler flow that uses polyhedral transformations to expose legal affine mmul subspaces, lower each accepted region to a back-end-independent operation, and preserve the surrounding computation in the generic CDFG path. For CGRA execution, the operation is instantiated as a parametric output-stationary kernel, while residual regions are reconnected through context generation and live-value preservation. The matcher is intentionally strict: only regions proven to match the supported affine mmul form are rewritten. Across canonical, fused, and application-level benchmarks, Kernel-CGRA achieves runtime speedups of up to 10.2× over state-of-the-art CGRA CDFG compilation with modulo scheduling and loop unrolling.
Authors
- María José Belda (ORCID: https://orcid.org/0000-0002-2870-7679)
- Giovanni Ansaloni (ORCID: https://orcid.org/0000-0002-8940-3775)
- Fernando Castro (ORCID: https://orcid.org/0000-0002-2773-3023)
- David Atienza (ORCID: https://orcid.org/0000-0001-9536-4947)
- Katzalin Olcoz (ORCID: https://orcid.org/0000-0002-1821-124X)
- Yuxuan Wang (ORCID: https://orcid.org/0009-0008-4281-2388)
Institutions
- Universidad Complutense de Madrid (ES)
- Embedded Systems (United States) (US)
- École Polytechnique Fédérale de Lausanne (CH)
Publication Details
- Journal
- ACM Transactions on Architecture and Code Optimization
- Published
- 2026-11-18
- DOI
- https://doi.org/10.1145/3859886
- Citations
- 1
- Primary Topic
- Embedded Systems Design Techniques
- Type
- article
- Field-Weighted Citation Impact
- 2.07
Funders
- National Science Foundation
- Innovation and Technology Commission
- Agencia Estatal de Investigación