Abstract
Recent programmable accelerators are faster and more energy efficient than general purpose processors, but expose complex hardware/software abstractions for compilers. A key problem is instruction scheduling, which requires sophisticated algorithms for mapping instructions to distributed processing elements, routing of operand dependences, and timing the arrival of operands to enable high throughput. The complex dependences between mapping, communication and timing make prior scheduling techniques insufficient. Optimization-based approaches are too slow, and heuristic-based approaches cannot achieve high quality. Our first insight is that the algorithm can be solved in a series of phases with overlapping responsibilities to reduce complexity. Second, it is possible to combine optimization-based and stochastic-heuristic based search strategies, to exploit the best features of both. This leads to the two primary techniques we explore, phase overlapping and hybridization. In this work we explore the codesign of scheduling algorithms with a challenging-to-schedule programmable accelerator. We show we can improve its area by 35% by trimming its scheduling-friendly structures, using a scheduling algorithm that is 5× faster than the state-of-the-art optimizationbased scheduler, with up to 2× better throughput.
Original language | English (US) |
---|---|
Title of host publication | Proceedings - 27th International Conference on Parallel Architectures and Compilation Techniques, PACT 2018 |
Publisher | Institute of Electrical and Electronics Engineers Inc. |
ISBN (Electronic) | 9781450359863 |
DOIs | |
State | Published - Nov 1 2018 |
Event | 27th International Conference on Parallel Architectures and Compilation Techniques, PACT 2018 - Limassol, Cyprus Duration: Nov 1 2018 → Nov 4 2018 |
Publication series
Name | Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT |
---|---|
ISSN (Print) | 1089-795X |
Conference
Conference | 27th International Conference on Parallel Architectures and Compilation Techniques, PACT 2018 |
---|---|
Country/Territory | Cyprus |
City | Limassol |
Period | 11/1/18 → 11/4/18 |
Bibliographical note
Publisher Copyright:© 2018 Association for Computing Machinery.
ASJC Scopus subject areas
- Software
- Theoretical Computer Science
- Hardware and Architecture