Optimizing throughput and resource utilization using pipelining: Transformation based approach

A simple formulation of pipelining: Pipelining withN stages is equivalent to retiming where the number of delays on all inputs or all outputs, but not both, is increased byN is used as the basis for a convenient and efficient treatment of pipelining in the design of application specific computers.Pipelining according to the objective function (throughput or resource utilization) and the latency is introduced. For two polynomial complexity pipelining classes, optimal algorithms are presented. For two other classes both proofs of NP-completeness and efficient probabilistic algorithms are presented. Both theoretical and experimental properties of pipelining are discussed and a relationship with other transformations is explored. Due to similar formulations for both software pipelining and the pipelining presented here, all results can be easily modified for use in compilers for general purpose computers. We have also developed a polynomial complexity algorithm for determining the iteration bound.This work was done while the first author was at the University of California, Berkeley.