Effective Pipelining of Digital Systems

Abstract

This paper presents quantitative techniques for the evaluation and comparison of pipelined digital systems. They are based on three measures of effectiveness: delay, average time/operation, and average cost/operation. Moreover, the techniques do not assume that there is an unbounded stream of operations to be performed, although this case is considered. The use of the analysis methods to compare different ways of pipelining a given algorithm is illustrated by an investigation of the pipelining of general four-neighbor cellular arrays. The methods can also be used to evaluate different algorithms for performing the same operation. This is illustrated by comparing three array algorithns for integer multiplication.