previous | contents | next

Fig. 12. Data part for 8-stage pipeline multiplier.

transfers data and of setting the flags of stage i to 1 after its computation is complete. Each stage operates as soon as its input data is available and its just- computed outputs have been used. Thus, the whole pipeline moves as fast as possible, compatible with not mixing up the computations.

The alert reader will have noticed that since the flag outputs are positive logic and the Ke control flow outputs are negative logic, the complements of the named flag outputs are the ones that must enter the K(parallel merge)'s. Even so, there are some problems in using Kflag's to enable ((parallel merge)'s. Chapter 7 must be read to discover why. After reading Chapter 7, return to this example and, if necessary, alter it so that the K(parallel merge)'s are enabled properly.

The pipeline structure is considerably more complicated than the array case from a control viewpoint. The limit to the parallelism is set by the structure of the algorithm -- here, 8 stages -- rather than by the size of the data array being processed. The time to perform a given stage is 2.7 microseconds, computed from the control sequence of Figure 13, so that the time to get an answer is 8 * 2.7 = 21.6 microseconds. However, providing the data. is fed into the pipeline rapidly enough, the system will finish a multiplication every 2.7 microseconds.

The pipeline makes clear that one must always consider two distinct performance measures for a process. One is the time taken to produce a result, measured from the time at which the input., is presented -- this is the operation time. The other is the rate at which results are produced -- this is the operation rate. In ideal serial systems the operation rate is simply the reciprocal of the time for each operation: 1/operation-time. But in general the two can vary independently. In parallel systems, as we have seen, the operation rate can be increased many fold. To do so usually implies an appropriate organization of the input data. But also, systems sometimes produce their outputs prior to the time they are prepared to accept the next input, thus reducing the operation rate



previous | contents | next