AFFINE-BY-STATEMENT SCHEDULING OF UNIFORM AND AFFINE LOOP NESTS OVER PARAMETRIC DOMAINS

This paper deals with parallel scheduling techniques for uniform and a ffine loop nests. We deal with affine-by-statement scheduling, a power ful extension of Lamport's hyperplane method where each statement with in the loop nest is scheduled by a different timing function. We prese nt a new, constructive and efficient method to determine the optimal ( i.e., with smallest latency) affine-by-statement scheduling. We also c onsider parametric loop nests, where loop limits (in addition to being affine functions of outer loops) involve program variables whose valu es may not be known at compile-time (but are runtime constants). We th en derive parameter-independent affine-by-statement schedules, and we show that these schedules are asymptotically as efficient as parameter -dependent solutions while much more regular. This theoretical result is of importance in practice, as regularity is a key factor for loop r ewriting and code generation. (C) 1995 Academic Press, Inc.