Computer System Structure: The CPU

Computer System Structure - The Central Processing Unit (CPU)

• The CPU is a crucial component of computer systems.
• Solutions for hazards include scoreboard method, Tomasulo's method, and branch prediction.

Scoreboard Method

• First used in the CDC 6600 computer (1966).
• Used for dynamically scheduling pipeline instructions, allowing out-of-order execution when no conflicts exist and hardware resources are available (no structural hazard).
• Logs data dependencies between instructions.
• Releases instructions only when no conflicts exist with previously issued, incomplete instructions.
• Monitors executing instructions until dependencies are resolved before permitting stalled instructions.
• Instructions go through four stages: Issue (ID1), Decode instructions, check for structural and WAW hazards, stall until structural and WAW hazards are resolved. Read operands (ID2), wait until no RAW hazards, execute operands, may be multiple cycles, notify scoreboard when done. Write result (WB), finish execution, stall if WAR hazard.
• Scoreboard structure includes: Instruction status (indicates instruction stage: ID1, ID2, EX, or WB), Functional unit status (indicates the FU's state), Busy (indicates if the unit is busy or not), Op (operation to perform, e.g., + or -), Fi (destination register), Fj and Fk (source register numbers), Qj and Qk (functional units producing source registers), Rj and Rk (flags indicating when source registers are ready), Register result status (indicates which functional unit writes each register).
• Speedup from scoreboard: 1.7 for Fortran programs, 2.5 for hand-coded assembly language programs.
• Hardware: Scoreboard hardware is approximately equal to one FPU; main cost is buses (four times the normal amount). Hardware implementation might be more complex for modern processors.
• Issues: does not solve structural hazards, no forwarding logic, and introduces stalls when a required functional unit is busy.

Tomasulo's Method

• Avoids structural hazards and resolves WAR and WAW hazards using register renaming and a common data bus (CDB).
• First used in the IBM 360/91 computer (1969).
• Register renaming: Keeps multiple copies of the same physical register, preventing data dependencies that arise from limited register availability; this only matters if registers/allocation are limited and the dependency isn't due to data dependencies.
• Common data bus (CDB): A data is put on a common bus as soon as it's available; prevents unnecessary stalls.
• Instruction stages: Issue; issues an instruction if the functional unit and operands are available, otherwise stalls; considers a virtual value until the real value becomes available; renames registers to avoid hazards, Execute - carries out instructions as long as necessary operands are available or present on the CDB; special care for load and stores, and Write result - result is written to the destination register with memory operations (see commit stage).
• Reservation stations: Buffers that fetch and store instruction operands as they're available; reservation stations hold instruction data and results; points to registers or other reservation stations with necessary data as soon as it's available (before it's written back into a register).
• To avoid structural hazard, redundant functional units are used, including multiple integer ALUs, floating-point ALUs, or address computing ALUs.
• Example: Pentium II and III architectures with multiple ALUs (2 integer unit executions, 1 floating-point execution, 1 MMX, 3 address generation units). Functional unit buffers store requests/instructions destined for that unit (e.g., Netburst architecture, Pentium IV reservation stations).
• Commit: An extra stage in the instruction execution sequence; data is written to re-order buffers instead of directly to destination registers or memory; enables data to be used by other instructions; enables avoidance of some stalls.

Branch Prediction

• A method for solving control hazards in pipelines.
• Problem: a branch in the program disturbs pipeline execution; if the branch is taken, pipeline must be flushed and reinitialized.
• Principle: Predicts the direction of a branch instruction (mainly conditional branches) to load the pipeline with instructions from the correct branch.
• Methods: Static prediction (nature of the branch instruction):
  • Cases: Procedure calls (taken), Unconditional jumps (taken), Backward branches (taken), Forward branches (not taken). Advantage: simple, fast, and works well for programs with many loops. Drawback: does not work well for programs with many conditional jumps.
• Methods: Dynamic prediction (considering the history of branch instructions): methods include Next line predictor, stores pointer to next instruction; stores decision and target; saturating counters store decisions in bits (1 or 2), such as strongly not taken, weakly not taken, weakly taken, and strongly taken; every occurrence of the branch updates state of counter.
• Dynamic prediction methods (cont.): Local branch prediction (a separate history buffer for each jump). Global branch prediction (keeps a shared history of all conditional jumps). Two-level adaptive predictor (necessary for alternating/imbedded conditional jumps; memorizes patterns of taken/not taken branches).
• Correlated prediction: predictor between local and global prediction. Global branch predictor: XOR (Exclusive-OR) between global-history buffer and jump's address in BHT. Gshare Predictor. Gselect Predictor. Hybrid Predictor(combines local & global predictors, such as Pentium IV).
• Branch Target Buffer (BTB): Contains target of taken branches, an associative access memory, jump instruction address, target address, and prediction state

Misprediction Statistics

• Data presented on misprediction rates for various branch prediction methods using various test cases. Graphs showing how misprediction rates correlate to predictor size.

Tournament Predictor

• Combines local and global predictors with a selector, aiming to pick the correct predictor for a branch or context.