SplitMS: Split Modulo-Scheduling for Accelerating Loops Onto CGRAs

Christie Sajitha Sajan (1, 2, 3) , Kevin J M Martin (1, 2) , Satyajit Das (3) , Philippe Coussy (1, 2)

1 Lab-STICC_ARCAD - Equipe Hardware ARchitectures and CAD tools
2 UBS Lorient - Université de Bretagne Sud - Lorient
3 ITT Palakkad - Indian Institute of Technology [Palakkad]

Coarse-Grained Reconfigurable Array (CGRA) architectures are popular for accelerating loop kernels due to a good balance between energy efficiency and flexibility. Modulo scheduling (MS) is the preferred solution for efficiently mapping loops onto CGRAs. Existing CGRA MS algorithms suffer from low resource utilization if the number of operation nodes in the Data Flow Graph (DFG) is less than the number of Processing Elements (PEs) in the CGRA. To improve instruction level parallelism (ILP), the common approaches unroll the loop before applying MS. However, finding valid MS solutions for larger DFGs becomes difficult for CGRAs with resource constraints. This paper proposes a novel Split Modulo-Scheduling (SplitMS) technique to improve the ILP by segmenting the target CGRA into clusters and mapping loop chunks. We also present a lightweight hardware approach to support the cluster execution. Experiments show that SplitMS for a 4×[2×2] CGRA cluster achieves an average speedup of 2.8× over MS for a 4×4 target CGRA with 8 Load-Store Units (LSUs). SplitMS increases an average of 2.9× the PE utilization and 3× the energy efficiency over the conventional MS approach.

Mots clés: CGRA; Loop Splitting; Loop Unrolling; Modulo Scheduling

Domaines: Architectures Matérielles [cs.AR]

Christie Sajitha Sajan, Kevin J M Martin, Satyajit Das, Philippe Coussy. SplitMS: Split Modulo-Scheduling for Accelerating Loops Onto CGRAs. 2024 27th Euromicro Conference on Digital System Design (DSD), Aug 2024, Paris, France. pp.242 - 249, ⟨10.1109/dsd64264.2024.00040⟩. ⟨hal-04777325⟩