Algorithms and Parallel Computing

7.9 PIPELINING

We showed in Chapter 2 how pipelining enhanced the performance of uniprocessors. Pipelining was used in the arithmetic and logic unit (ALU) to increase the amount of computations to be performed per clock cycle. Pipelining was also used in the control unit to increase the number of instructions to be processed per clock cycle.

In general, pipelining is a very effective technique for improving system throughput, which is defined as the rate of task completion per unit time. This technique requires two conditions to be effective:

1. There should be many instances of the task and all of them must be completed at a high rate.

2. Each task should be divisible into several serial or parallel subtasks.

A pipeline executes a task in successive stages by breaking it up into smaller tasks. It is safe to assume that a smaller task will complete in a shorter time compared with the original task.

Examples of using pipelining to speed up the high-performance coordinate rotation digital computer (HCORDIC) algorithm, which is a very powerful algorithm for evaluating elementary functions such as trigonometric, hyperbolic, logarithmic, square root, and division operations [5–8]. Evaluating elementary functions is required in many engineering applications such as adaptive filters, telecommunications, scientific computing, and so on. Figure 7.4 shows a schematic of the data and control inputs of the HCORDIC algorithm and the resulting outputs. HCORDIC accepts four input data.