Constructing and Exploiting Linear Schedules with Prescribed Parallelism

Darte, Alain ; Schreiber, Robert ; Rau, B. Ramakrishna ; Vivien, Frederic

HP Development Company

关键词: systolic array;    multicluster VLIW;    linear schedule;   

RP-ID  :  HPL-2001-238

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

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