A BUBBLE PROPAGATION MODEL FOR PIPELINE PERFORMANCE

Pipelining is a very commonly used implementation technique whereby mu ltiple operations are overlapped in their successive phases of executi on. An identifiable phase of an operation execution constitutes a pipe stage. Ideally, the time required to complete any of the phases does not exceed 1 clock cycle. In practice, quite often one or more of the pipeline stages take longer than 1 cycle to process the data. Such a s tage is considered stalled or frozen, and during this period, instead of transmitting some intermediate result to the following stage, the s talled stage is said to be transmitting bubbles. This paper proposes a n analytical model for predicting pipeline performance based on recept ion, generation, and transmission of these bubbles. The model proposed is shown to be an effective tool for estimating overall performance o f small pipelines (5 to 6 stages deep) using the delay distributions o f individual stages. The proposed model is an order of magnitude faste r than the corresponding simulations. It provides the complete delay d istribution (instead of just the average) of the overall performance. Also, the model is considerably less computationally complex than alte rnative exact analytical approaches such as the discrete-time Markov m odel. (C) 1994 Academic Press, Inc.