Reservation station

Reservation station as part of Intel's Nehalem microarchitecture

Reservation station, also known as unified scheduler, is a decentralized feature of the microarchitecture of a CPU that allows for register renaming, and is used by the Tomasulo algorithm for dynamic instruction scheduling.

Reservation stations permit the CPU to fetch and re-use a data value as soon as it has been computed, rather than waiting for it to be stored in a register and re-read. When instructions are issued, they can designate the reservation station from which they want their input to read. When multiple instructions need to write to the same register, all can proceed and only the (logically) last one need actually be written. It checks if the operands are available (RAW) and if execution unit is free (Structural hazard) before starting execution.

Instructions are stored with available parameters, and executed when ready. Results are identified by the unit that will execute the corresponding instruction. Implicitly register renaming solves WAR and WAW hazards. Since this is a fully associative structure, it has a very high cost in comparators (need to compare all results returned from processing units with all stored addresses).

In Tomasulo's algorithm, instructions are issued in sequence to Reservation Stations which buffer the instruction as well as the operands of the instruction. If the operand is not available, the Reservation Station listens on a Common Data Bus for the operand to become available. When the operand becomes available, the Reservation Station buffers it, and the execution of the instruction can begin.

Functional Units (such as an adder or a multiplier), each have their own corresponding Reservation Station. The output of the Functional Unit connects to the Common Data Bus, where Reservation Stations are listening for the operands they need.

Bibliography

• Computer Architecture: A Quantitative Approach, John L. Hennessy, David A. Patterson, 2012 (ISBN 9780123838728) "3.4 Overcoming Data Hazards with Dynamic Scheduling", p 172-180

External links

• The Reservation Stations, HASE Project, Institute for Computing Systems Architecture, School of Informatics, University of Edinburgh, 2003
• CS6290 Tomasulo’s Algorithm, Georgia Tech