Exposing Embedded Matrix Multiplication with polyhedral transformations for CGRA compilation

Abstract

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 paper 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.

The authors' abstract, as published at the source. ACM Transactions on Architecture and Code Optimization, 2026 · DOI ↗