An analytical model for a synchronous pipeline subject to stochastic input and output is presented. We find a nonlinear discrete-time equation that describes the time evolution of the occupancy probabilities in the pipeline and then solve a special case of the equation where the input and output are stationary Bernoulli processes. For this case, the two commonly used steady-state performance measures—latency and throughput—are obtained. The results obtained in this paper are applicable to pipelined computer systems such as network processors and media processors.

Keywords