Click here for full text:
Constructing and Exploiting Linear Schedules with Prescribed Parallelism
Darte, Alain; Schreiber, Robert; Rau, B. Ramakrishna; Vivien, Frederic
HPL-2001-238
Keyword(s): systolic array; multicluster VLIW; linear schedule
Abstract: We present two new results of importance in code generation for and synthesis of synchronously scheduled parallel processor arrays and multicluster VLIWs. The first is a new, practical method for constructing a linear schedule for the iterations of a loop nest that schedules precisely one iteration per cycle on each of a prescribed set of processors. While this problem goes back to the era in which systolic computation was in vogue, it has defied practical solution until now. We provide a closed form solution that enables the enumeration of all such schedules. The second result is a new technique that reduces the cost of code or hardware whose function is to control the flow of data, predicate operations, and generate memory addresses. The key idea is that by using the mathematical structure of any of the conflict-free schedules we construct, a very shallow recurrence can be developed to inexpensively update these qualities. Notes: Copyright 2001 by Association for Computing Machinery To be published in the ACM Transactions on Design Automation of Electronic Systems
13 Pages
Back to Index
| 
printable version
