Chapter 8Pipelining Design TechniquesGeneral ConceptsInstruction PipelineArithmetic pipelineChapter SummaryIn this chapter, we have considered the basic principles involved in designing pipeline architectures. Our coverage started with a discussion on a number of metrics that can be used to assess the goodness of a pipeline. We then moved to present a generalExercisesReferences and Further ReadingChapter 8 Pipelining Design Techniques There exists two basic techniques to increase the instruction execution rate of a processor. These are to increase the closk rate, thus decreasing instruction execution time or alternatively to increase the number of instructions that can be executed simultaneously. Pipelining and instruction-level parallelism are examples of the latter technique. Pipelining ows its origin to car assembly lines. The idea is to have more than one instruction being processed by the processor at the same time. Similar to the assembly line, the success of a pipeline depends upon dividing the execution of an instruction among a number of sub-units (stages), each performing part of the required operations. A possible divison is to consider instruction fetch (IF), instruction decode (ID), operand fetch (OF), instruction execution (IE), and store of results (IS) as the sub-tasks needed for the execution of an instruction. In this case, it is possible to have up to five instructions in the pipeline at the same time, thus reducing instruction execution latency. In this chapter, we discuss the basic concepts involved in designing instruction pipelines. Performance measures of a pipeline are introduced. The main issues contributing to an instruction pipeline hazards are discussed and some possible solutions are introduced. In addition, we introduce the concept of data pipelining together with the problems involved in designing such piepline. Our coverage concludes with a review of a recent pipeline processor. 8.1. General Concepts Pipelining refers to the technique in which a given task is divided into a number of subtasks that need to be performed in sequence. Each subtask is performed by a given functional unit. The units are connected in a serial fashion and all of them operate simultaneously. The use of Pipelining improves the performance as compared to the traditional sequential execution of tasks. Fig. 8.1 shows an illustration of the basic difference between executing four sub-tasks of a given instruction (in this case fetching F, decoding D, execution E, and writing the results W) using pipelining and sequential processing. 1I2I3I F1 D1 O1 W1 F2 D2 O2 W2 F3 D3 O3 W3 (a) Sequential Processing 1I F1 D1 O1 W1 1I F2 D2 O2 W2 F3 D3 O3 W3 1I Time 1 2 3 4 5 6 7 8 9 10 11 12 (b) Pipelining Fig. 8.1: Pipelining versus sequential processingIt is clear from the figure that the total time required to process three instruction ( ) is only six time units if pipelining is used as compared to twelve time units if sequential processing is used. A possible saving of up to 50% in the execution time of these three instructions. In order to formulate some performance measures for the goodness of a pipeline in processing a series of tasks, a space time chart (called the Gantt's Chart) is used. The chart shows the succession of the sub-tasks in the pipe with respect to time. Fig. 8.2 shows an example Gantt's chart for the example shown in Fig. 8.1. In this chart, the vertical axis represents the sub-units (four in this case) and the horizontal axis represents time (measured in terms of the time unit required for each sub-unit to perform its task). In developing the Gantt's chart, we assume that the time (T) taken by each sub-unit to perform its task is the same, we call this the unit time. 321,, III 4U 1I 2I 3I 4I 5I 6I 7I 8I 9I 10I 3U 1I 2I 3I 4I 5I 6I 7I 8I 9I 10I 2U 1I 2I 3I 4I 5I 6I 7I 8I 9I 10I 1U 1I 2I 3I 4I 5I 6I 7I 8I 9I 10I 1 2 3 4 5 6 7 8 9 10 11 12 13 Time Fig. 8.2: The Space-time Chart (Gantt Chart) As can be seen from the figure, 13 time units are needed to finish executing 10 instructions ( to ). This is to be compared to 40 time units, if sequential processing is used (ten instructions each requires four time units). 1I10I In the following analysis, we provide two performance measures for the goodness of a pipeline. These are the Speed-up S(n) and the Throughput U(n). It should be noted that in this analysis, we assume that the unit time T =1. (1) Speed-up S(n) Consider the execution of m tasks (instructions) using n-segments (units) pipeline. As can be seen n+m-1 time units are required to complete m tasks. possibleally theoreticis speedin increase fold-n i.e.n = S(n) 1processing pipeline using Timeprocessing sequential using Time= S(n) ∞→−+×=−mLimmnnmupSpeed (2) Throughput U(n)\ 1 = U(n)mLim 1)-m+(nm =unit timeper executed tasks# = )( ∞→nUThroughput 28.2. Instruction Pipeline The simple analysis made in Section 8.1 ignores an important aspect that can affect the performance of a pipeline, i.e., pipeline stall. A Pipeline operation is said to have been stalled if one unit (stage) requires more time to perform its function, thus forcing other stages to become idle. Consider, for example, the case of an instruction fetch that incurs a cache miss. Assume also that a cache miss requires three extra time units. Fig. 8.3 illustrates the effect of having instruction incurring a cache miss (assuming the execution of ten instructions to ). 2I1I10I 4U 1I 2I 3I 4I 5I 6I 7I 8I 9I 10I 3U 1I 2I 3I 4I 5I 6I 7I 8I 9I 10I 2U 1I 2I3I 4I 5I 6I 7I 8I 9I 10I 1U 1I 2I 3I 4I 5I 6I 7I 8I 9I 10I 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Fig. 8.3: The effects of a cache miss on the pipeline The figure shows that due to the extra time units needed for instruction to be fetched, the pipeline stalls, i.e., fetching of instruction and subsequent instructions are delayed. Such situations create what is known as pipeline bubble (or pipeline hazards). The creation of a pipeline bubble leads to wasted unit times, thus leading to an overall increase in the number of time units