OPTIMIZING THROUGHPUT AND RESOURCE UTILIZATION USING PIPELINING - TRANSFORMATION BASED APPROACH

A simple formulation of pipelining: ''Pipelining with N stages is equi valent to retiming where the number of delays on all inputs or all out puts, but not both, if increased by N'' is used as the basis for a con venient and efficient treatment of pipelining in the design of applica tion specific computers. Pipelining according to the objective functio n (throughput or resource utilization) and the latency is introduced. For two polynomial complexity pipelining classes, optimal algorithms a re presented. For two other classes both proofs of NP-completeness and efficient probabilistic algorithms are presented. Both theoretical an d experimental properties of pipelining are discussed and a relationsh ip with other transformations is explored. Due to similar formulations for both software pipelining and the pipelining presented here, ail r esults can be easily modified for use in compilers for general purpose computers. We have also developed a polynomial complexity algorithm f or determining the iteration bound.