Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1109/MICRO.2005.17 | Barcelona |
Keywords | Field | DocType |
cost sensitive modulo scheduling,loop accelerator synthesis system,traditional cost,aware modulo schedulers,cost sensitive modulo scheduler,decomposition technique,hardware synthesis system,greedy cost,complex scheduling problem,efficient hardware,scheduling problem,integer programming,linear programming,branch and bound,scheduling algorithm,exact solution,functional unit,resource allocation,scheduling algorithms,resource management,vliw,compilers | Fixed-priority pre-emptive scheduling,Job shop scheduling,Fair-share scheduling,Computer science,Scheduling (computing),Modulo,Parallel computing,Real-time computing,Two-level scheduling,Resource allocation,Dynamic priority scheduling | Conference |
ISSN | ISBN | Citations |
1072-4451 | 0-7695-2440-0 | 14 |
PageRank | References | Authors |
0.86 | 24 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kevin Fan | 1 | 335 | 20.29 |
| Manjunath Kudlur | 2 | 1997 | 71.21 |
| Hyunchul Park | 3 | 341 | 17.56 |
| Scott Mahlke | 4 | 4811 | 312.08 |