How does Tomasulo’s Algorithm work?

A fundamental restriction in MIPS 5-stage pipeline is, if one instruction stalls, all instructions following it stall as well, even if they have no dependencies at all. If the stalled instruction take a long time to finish, the throughput of the CPU pipeline will suffer.

In modern CPU technology, out-of-order scheduling is an important technique to address the restriction above. Tomasulo’s algorithm is a typical solution to CPU out-of-order scheduling.

Continue reading → How does Tomasulo’s Algorithm work?

Hazards and solutions: a case study using MIPS 5-stage pipeline

The CPU pipelining introduces throughput increasing and possible higher clock frequency, but it does not come for free. By allowing multiple instructions being executed in parallel, CPU designers need to take care of the following hazards:

Structural hazards
Data hazards
Control hazards

In this post, we will discuss these hazards in detail and use MIPS 5-stage pipeline for case study.

Continue reading → Hazards and solutions: a case study using MIPS 5-stage pipeline