A TRANSFORMATION-BASED METHOD FOR LOOP FOLDING

We propose a transformation-based scheduling algorithm for the problem - given a loop construct, a target initiation interval and a set of re source constraints, schedule the loop in a pipelined fashion such that the iteration time of executing an iteration of the loop is minimized . The iteration time is an important quality measure of a data path de sign because it affects both storage and control costs. Our algorithm first performs an As Soon As Possible Pipelined (ASAP(P)) scheduling r egardless the resource constraint. It then resolves resource constrain t violations by rescheduling some operations. The software system impl ementing the proposed algorithm, called Theda.Fold, can deal with beha vioral loop descriptions that contain chained, multicycle and/or struc tural pipelined operations as well as those having data dependencies a cross iteration boundaries. Experiment on a number of benchmarks is re ported.