Инструкцияларды динамикалық жоспарлау және орындау: Scoreboarding әдісі

Scoreboarding is a centralized method, first used in the CDC 6600 computer, for dynamically scheduling instructions so that they can execute out of order when there are no conflicts and the hardware is available. In a scoreboard, the data dependencies of every instruction are logged, tracked and strictly observed at all times. Instructions are released only when the scoreboard determines that there are no conflicts with previously issued ("in flight") instructions. If an instruction is stalled because it is unsafe to issue (or there are insufficient resources), the scoreboard monitors the flow of executing instructions until all dependencies have been resolved before the stalled instruction is issued. In essence: reads proceed on the absence of write hazards, and writes proceed in the absence of read hazards. Scoreboarding is essentially a hardware implementation of the same underlying algorithm seen in dataflow languages, creating a Directed Acyclic Graph, where the same logic is applied in the programming language runtime.

Instructions are decoded in order and go through the following four stages. Issue: The system checks which registers will be read and written by this instruction and where conflicts WAR and RAW and WAW are detected. RAW and WAR hazards are recorded using a Dependency Matrix (constructed from SR NOR latches in the original 6600 design) as it will be needed in the following stages. Simultaneously, an entry is recorded in a second Matrix, which records the instruction order as a Directed Acyclic Graph. In order to avoid output dependencies (WAW – Write after Write) the instruction is stalled until instructions intending to write to the same register are completed. The instruction is also stalled when required functional units are currently busy. No instruction is ever issued unless it is fully trackable from start to finish. Read operands: After an instruction has been issued and correctly allocated to the required hardware module (named a Computation Unit in Thornton's book), the Unit waits until all operands become available. The read only proceeds when write dependencies (RAW – Read after Write) have been dropped from all other Units. To avoid Register File Port contention, a Priority Picker selects one Computational Unit (in the case where several Units are clear of hazards). Execution: When all operands have been fetched, the Computation Unit starts its execution. After the result is ready, the scoreboard is notified. Write Result: In this stage the result is ready but has not yet been written to its destination register. The write may not proceed until the Unit is clear of all (WAR – Write after Read) hazards. The only additional delays here are based on availability of register file ports: in the 6600 a Priority Picker was used to select one result per write port. Once written the unit is marked as no longer busy, and all hazards and state is dropped. Note that only in advanced (augmented, precise) scoreboards with "Shadow" capability will the Write Result phase be prevented (delayed). The original 6600 did not have this capability. It is critical to note above that Reads only proceed in the absence of write hazards, and that writes proceed in the absence of Read hazards. This is logical but contraindicative to expectations. In particular, note that Writes must wait to write after read in order to give other units the opportunity to read the current value in a register, before overwriting it with the new one. Hence why writes must wait until the absence of WAR hazards.

Thornton's book pre dates modern computing terminology. Function Units (pipelines) were called "Computation Units". "First Order Conflict" covered both stall due to all Units being busy and also covered WAW conflict. "Second Order Conflict" was the term used for RAW conflict. "Third Order Conflict" covered WAR conflict. Stalling only occurred at the issue stage, when "First Order" conflicts were detected. Some other techniques like Tomasulo algorithm additionally resolve WAW dependencies with register renaming. The original CDC 6600 likely did not have WAW hazard tracking simply because its designers had to deliver product, and then moved on to the 7600: stalling instead was the most expedient option. There is no technical reason why Register renaming should not be added to Scoreboards. An analysis of both algorithms was carried out by Luke Leighton and a transformation process outlined which shows equivalence between the Tomasulo algorithm and the 6600 Scoreboard algorithm. WAW hazards resolution is indeed missing from the original algorithm: the 6600 would stall at the first occurrence of a Write Hazard.