| This paper presents both a serial and parallel general purpose scheduling algorithm which ensures 100% utilization of at least one stage in a statically configured pipeline processing architecture with less than quadratic computational complexity. This maximized utilization is accomplished through a greedy delay insertion strategy intended to allow any static reservation table to utilize a constant perfect latency cycle without necessarily removing all spatial parallelism present in the initial reservation table. The parallel version requires a multi-function pipeline, but achieves a near-ideal linear relative speedup. The increased utilization, results in decreased total computation time for reservation tables with a sufficiently large number of iterations. In addition, the length of the reservation table experiences, at most, quadratic growth.;Index Terms: Algorithms, Computation Time, Computer Performance, Pipeline Processing, Pipelines, Processor Scheduling... |
