TY - GEN
T1 - Piecewise linear schedules for recurrence equations
AU - Rajopadhye, Sanjay
AU - Mui, Lap
AU - Kiaei, Sayfe
N1 - Funding Information:
‘This research is supported by the NSF-RIA grant MIP-9011227.
Publisher Copyright:
© 1992 IEEE.
PY - 1992
Y1 - 1992
N2 - The scheduling problem for a system of affine recurrence equations (SARE) has been studied by many researchers. The emphasis has been on an important class of timing functions called linear or affine schedules. For many SAREs, linear schedules may not exist, although the SARE is computable. It will be shown that it is possible to find piecewise linear schedules (PLS) for many practical algorithms expressed in terms of SAREs. PLS have different slopes for different variables in the algorithm. For each variable, the computation domain is partitioned into finitely many "pieces" in which the schedule is different for each subdomain. The main focus of this paper is to introduce PLS and develop a synthesis procedure to find PLS for the given SARE.
AB - The scheduling problem for a system of affine recurrence equations (SARE) has been studied by many researchers. The emphasis has been on an important class of timing functions called linear or affine schedules. For many SAREs, linear schedules may not exist, although the SARE is computable. It will be shown that it is possible to find piecewise linear schedules (PLS) for many practical algorithms expressed in terms of SAREs. PLS have different slopes for different variables in the algorithm. For each variable, the computation domain is partitioned into finitely many "pieces" in which the schedule is different for each subdomain. The main focus of this paper is to introduce PLS and develop a synthesis procedure to find PLS for the given SARE.
UR - http://www.scopus.com/inward/record.url?scp=0012524474&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0012524474&partnerID=8YFLogxK
U2 - 10.1109/VLSISP.1992.641069
DO - 10.1109/VLSISP.1992.641069
M3 - Conference contribution
AN - SCOPUS:0012524474
T3 - Workshop on VLSI Signal Processing 1992
SP - 375
EP - 384
BT - Workshop on VLSI Signal Processing 1992
A2 - Przytula, Wojtek
A2 - Yao, Kung
A2 - Jain, Rajeev
A2 - Rabaey, Jan
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 6th IEEE Workshop on VLSI Signal Processing
Y2 - 28 October 1992 through 30 October 1992
ER -