In this blog post, we’ll explore the principles of pipelined processing—one of the key methods that allowed computers to efficiently process multiple instructions and boost performance—along with structural, data, and control issues, and how they were resolved.
Have you ever tried to handle multiple tasks at once in your daily life? For example, imagine doing household chores all at the same time: putting clothes in the washing machine, heating food in the microwave, sweeping the floor with a broom, mopping the floor with a mop, and setting the table. You might first put the clothes in the washing machine and set it for 30 minutes, then put the food in the microwave to heat it for about a minute, sweep the floor in the meantime, take out the heated food, mop the floor, and then, while doing that, go get the clothes that have finished washing. While people can sometimes juggle multiple tasks in this frantic manner, computers use a method called “pipelining” to overlap the processing stages of multiple instructions in a similar way. Let’s take a look at what pipelining is—the mechanism that makes this processing possible—and what problems arise from it.
When a computer performs a task, it processes instructions—represented by 0s and 1s—in sequence. Here, an instruction is the most basic operation a computer can perform; for example, it can execute complex tasks using simple operations such as adding or subtracting two values, or copying a value to another location. Now, suppose the instructions a computer must execute are A, B, C, and D, in that order. In sequential processing, the computer reads A, calculates A, outputs the result of A, and only then reads B—executing the next command only after the previous one is complete. This is called sequential processing. While it has the advantage of ensuring accurate results, it cannot efficiently overlap the processing of multiple commands, which limits its ability to increase overall throughput. For example, consider someone doing household chores: rather than simply loading clothes into the washing machine and then doing nothing while waiting for the cycle to finish, they use their hands to load the clothes while simultaneously checking with their eyes what the next task is and thinking through how to handle it. Just as the eyes, mind, and hands each perform different tasks simultaneously, a computer can also divide the processing steps: reading the next instruction in one part, preparing the values needed for that instruction in another, performing the calculation with the prepared values in yet another, and finally writing the calculated result in the last part. In other words, a single instruction is broken down into multiple stages of work. This is called pipelined processing.
However, while pipelined processing can achieve higher throughput than sequential processing, it comes with three major issues: structural hazards, data hazards, and control hazards. These issues arise because, even when a computer processes instructions using pipelined processing, it must produce the same results as it would if the instructions were executed sequentially. In other words, from the user’s perspective, the results should appear as if B is processed only after A is completed; however, since the processing stages of multiple instructions proceed simultaneously in a pipeline, situations where they conflict or depend on one another can arise. Let’s examine what these three issues are and how each is resolved.
The first issue is a structural problem that arises when multiple instructions attempt to access the same hardware resource simultaneously. Here, “resource” typically refers to hardware shared by multiple instructions, such as a computer’s storage or arithmetic units. For example, situations may arise where the process of reading the next instruction and the process of preparing the values required for that instruction simultaneously access the same memory resource, or where the process of preparing an instruction and the process of storing the calculated result simultaneously use the same register or hardware resource. Such situations rarely occur in sequential processing because multiple stages do not overlap at the same moment; however, in a pipeline, resource conflicts can arise because multiple instructions execute different stages simultaneously. This problem can be resolved during pipeline design by separating resources or adding the necessary hardware resources.
The second issue is a data problem, which occurs when a subsequent instruction attempts to read a result before the preceding instruction has finished storing it. For example, suppose instruction A adds the values 3 and 4 and stores the result in `a`, and the next instruction, B, adds 5 to `a` and stores the result in `b`. A situation may arise where instruction B needs to read `a`—a value required during its preparation—even though the result of instruction A’s addition is still being computed and has not yet been produced. This scenario, where a subsequent instruction requires a result generated by a preceding instruction but that result is not yet ready, is a classic example of a data hazard. A simple solution is to temporarily pause the pipeline—that is, to use a “stall”—until the preceding instruction stores its result. This involves waiting until the result of Instruction A is stored, just as in sequential processing, before proceeding to Instruction B. However, this approach fails to fully leverage the advantages of pipelined processing. Therefore, another solution is to use “data forwarding,” or internal forwarding. Since the result of instruction A is sometimes determined during the computation process before it is finally stored, instead of writing that result to a storage location and then reading it back, it can be passed directly to the required instruction B within the pipeline. In other words, the value is passed through a path within the pipeline rather than being retrieved via a storage location. However, forwarding alone cannot solve all data-related issues. For example, in situations where the result is not ready until later—such as when a value must be used by the next instruction immediately after being read from memory—stall must be used in conjunction with forwarding.
The third issue is the control problem. In addition to performing calculations or transferring values, instructions include branch instructions that, based on the calculation results, determine which instruction to execute next, move forward, or skip the next instruction to execute one from a different location. In other words, there are cases where it is impossible to know for certain which instruction to fetch and execute next until the preceding instruction has been executed. One way to address this is to predict one of two possible paths and continue pipeline processing; if the prediction is incorrect, the instructions fetched or executed on the wrong path are discarded, and the instructions from the correct path are re-executed. The purpose of this approach is to reduce pipeline stalls by pre-processing the next instruction before the branch outcome is determined. In modern processors, this is implemented through techniques such as branch prediction and speculative execution; however, since the pipeline must be flushed and restarted from the correct path in the event of an incorrect prediction, a certain amount of performance loss occurs.
Some might argue that abandoning the predicted path in favor of another could result in significant overhead. Indeed, if the branch prediction is incorrect, performance is lost because instructions that have already been fetched and processed must be discarded. However, the reason branch prediction is used is that, even with this overhead, it increases overall throughput compared to halting the pipeline each time while waiting for the branch result. There are several methods for predicting a single path. A simple approach is static prediction, which selects one path by exploiting the tendency for branch instructions to repeat in a specific direction. A more sophisticated method involves recording the outcomes of identical branch instructions in the past and using that history to predict the next path when the same instruction is encountered again. Modern processors use more sophisticated methods, such as dynamic branch prediction—which utilizes past branch results and patterns—to minimize the overhead caused by incorrect predictions.
To date, computers have become capable of performing increasingly more computations and storing more data through the continuous increase in semiconductor integration density, epitomized by Moore’s Law, and the development of various computer architectures. However, Moore’s Law did not originally refer to a rule stating that “performance doubles every 18 months”; rather, it is a concept derived from the observation and prediction that the number of transistors integrated onto a semiconductor chip would double approximately every two years. While the increase in transistor density has served as a crucial foundation for enhancing computing performance and efficiency, it does not mean that an increase in the number of transistors directly translates to a proportional increase in the performance of all computers.
In the process of improving computer performance, it was important not only to advance materials and manufacturing processes but also to develop computer architectures—such as pipelines—that enable computers to process more work in the same amount of time. In particular, pipelining is a key method for increasing instruction throughput by dividing a single instruction into multiple stages and overlapping the processing stages of different instructions. While advancements in semiconductor materials and manufacturing technologies will continue in the future, various physical and engineering limitations may emerge as technology progresses. Therefore, when designing computers, it is important not only to develop new technologies but also to efficiently utilize existing hardware and processing methods. Pipeline processing is a prime example of increasing a computer’s throughput by dividing existing processing steps into multiple stages and executing them in parallel.
