Cost Sensitive Modulo Scheduling in a Loop Accelerator Synthesis System
Kevin Fan, Manjunath Kudlur, Hyunchul Park et al. · Proceedings of the ... annual International Symposium on Microarchitecture/Proceedings of the annual International Symposium on Microarchitecture · 2006
Scheduling algorithms used in compilers traditionally focus on goals such as reducing schedule length and register pressure or producing compact code. In the context of a hardware synthesis system where the schedule is used to determine various components of the hardware, including datapath, storage, and interconnect, the goals of a scheduler change drastically. In addition to achieving the traditional goals, the scheduler must proactively make decisions to ensure efficient hardware is produced. This paper proposes two exact solutions for cost sensitive modulo scheduling, one based on an integer linear programming formulation and another based on branch-and-bound search. To achieve reasonable compilation times, decomposition techniques to break down the complex scheduling problem into phase ordered sub-problems are proposed. The decomposition techniques work either by partitioning the dataflow graph into smaller subgraphs and optimally scheduling the subgraphs, or by splitting the scheduling problem into two phases, time slot and resource assignment. The effectiveness of cost sensitive modulo scheduling in minimizing the costs of function units, register structures, and interconnection wires are evaluated within a fully automatic synthesis system for loop accelerators. The cost sensitive modulo scheduler increases the efficiency of the resulting hardware significantly compared to both traditional cost unaware and greedy cost aware modulo schedulers.
Cited by 34 works. doi:10.1109/micro.2005.17
Authors
References
- Force-directed scheduling for the behavioral synthesis of ASICs
- METIS: A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices
- Sehwa: a software package for synthesis of pipelines from behavioral specifications
- Iterative modulo scheduling
- PRISM-II compiler and architecture
- The Garp architecture and C compiler
- NAPA C: compiling for a hybrid RISC/FPGA architecture
- Facet: A Procedure for the Automated Synthesis of Digital Systems
- Lifetime-sensitive modulo scheduling
- Parallelizing applications into silicon