A bubble propagation model for pipeline performance

Abstract

Pipelining is a very commonly used implementation technique whereby multiple operations are overlapped in their successive phases of execution. 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 stage is considered stalled or frozen, and during this period, instead of transmitting some intermediate result to the following stage, the stalled stage is said to be transmitting bubbles. This paper proposes an analytical model for predicting pipeline performance based on reception, generation, and transmission of these bubbles. The model proposed is shown to be an effective tool for estimating overall performance of small pipelines (5 to 6 stages deep) using the delay distributions of individual stages. The proposed model is an order of magnitude faster than the corresponding simulations. It provides the complete delay distribution (instead of just the average) of the overall performance. Also, the model is considerably less computationally complex than alternative exact analytical approaches such as the discrete-time Markov model. © 1994 Academic Press, Inc.