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.2x over state-of-the-art CGRA CDFG compilation with modulo scheduling and loop unrolling.

arXiv commentAccepted for publication in ACM Transactions on Architecture and Code Optimization (ACM TACO). This version incorporates revisions made during peer review and a minor change to the title