Many students find Hennessy & Patterson's Computer Architecture A Quantitative Approach, overwhelming at times. An example of this is found in their discussion of Scoreboard and Tomasulo's algorithm. To address this issue we have provided a brief overview, example problems, and also have searched through numerous sources on the internet and have collected links to some of the premire sites that deal with this subject. We hope these will help future students as they embark on the long and exhausting journey of preparing for Dr. Hugue's exam.
Register scoreboarding maintains register coherency by preventing parallel execution units from accessing registers for which there is an outstanding operation. When an instruction that targets a destination register or group of registers executes, the processor sets a register-scoreboard bit to indicate that this register or group of registers is being used in an operation. When the instructions that follow do not require data from registers already in use, the processor can execute those instructions before the prior instruction completes execution are essentially equivalent for the purposes of pipeline control. Scoreboarding is a technique for allowing instructions to execute out of order when there are sufficient resources and no data dependencies; it is named after the CDC-6600 scoreboard, which developed this capability. The goal of the scoreboard is to maintain an execution rate of one instruction per clock cycle( when there are no structural hazards) by executing an instruction as early as possible. Thus, when the next instruction to execute is stalled, other instructions can be issued and executed if they do not depend on any active or stalled instruction. The scoreboard takes full responsibility for instruction issue and execution, including all hazard detection. Taking advantage of out-of order execution requires multiple instructions to be in their Execute stage simultaneously. This can be achieved with multiple functional units, with pipelined functional units, or with both. Notice that these two capabilities --pipelined functional units and multiple functional units--are essentially equivalent for the purposes of pipeline control.
Another approach to allow execution to proceed in the presence of hazards was used by the IBM 360/91 FP unit. Tomasulo's scheme combines key elements of the scoreboarding scheme with the introduction of register renaming. There are many variations on this scheme, though the key concept of renaming registers to avoid WAR and WAW hazards is the most common characteristic.
