Modulo graph embedding
Hyunchul Park, Kevin Fan, Manjunath Kudlur et al. · International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES) · 2006
Coarse-grained reconfigurable architectures (CGRAs) present an appealing hardware platform by providing the potential for high computation throughput, scalability, low cost and energy efficiency. CGRAs consist of an array of function units and register files generally organized as a two dimensional grid. The most difficult challenge with deploying CGRAs is compiler scheduling technology that can map software implementations of compute intensive loops onto the array. Traditional schedulers are not suitable because they do not take into account the explicit routing of operand values that is necessary. In essence, the problem of binding operations to time slots and resources is extended to also include explicit routing of operands from producers to consumers. To tackle this problem, this paper introduces a software pipelining technique for mapping loop bodies onto CGRAs, referred to as modulo graph embedding. We leverage graph embedding from graph theory, which is used to draw graphs onto a target space. The loop body is essentially drawn onto the CGRA mesh, subject to modulo resource usage constraints. Modulo graph embedding is effective because it can take into account the communication structure of the loop body during mapping. On average, a compute utilization of 56-68% is achieved for a set of loop kernels across three 4x4 CGRA designs.
Cited by 87 works. doi:10.1145/1176760.1176778
Authors
References
- An algorithm for drawing general undirected graphs
- A Heuristic for Graph Drawing
- Bulldog: A Compiler for VLIW Architectures
- The Raw microprocessor: a computational fabric for software circuits and general-purpose programs
- Drawing graphs nicely using simulated annealing
- Iterative modulo scheduling
- PipeRench: a co/processor for streaming multimedia acceleration
- The Garp architecture and C compiler
- Space-time scheduling of instruction-level parallelism on a raw machine
- Exploiting loop-level parallelism on coarse-grained reconfigurable architectures using modulo scheduling