| Constructing and exploiting linear schedules with prescribed parallelism (2002) | |||||||||||||||
Abstract | |||||||||||||||
| systolic array, multicluster VLIW, linear schedule 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. | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||