Podcast
Questions and Answers
What is the main purpose of a two-level adaptive predictor in branch prediction?
What is the main purpose of a two-level adaptive predictor in branch prediction?
Local branch predictors use a shared history buffer for all conditional jump instructions.
Local branch predictors use a shared history buffer for all conditional jump instructions.
False
What is the role of the global history buffer in a global branch predictor?
What is the role of the global history buffer in a global branch predictor?
To keep a shared history of all conditional jumps for better prediction.
A _______ predictor uses a XOR between the global history buffer and the jump address for indexing in the prediction history table.
A _______ predictor uses a XOR between the global history buffer and the jump address for indexing in the prediction history table.
Signup and view all the answers
Match the following branch prediction techniques with their descriptions:
Match the following branch prediction techniques with their descriptions:
Signup and view all the answers
What is the primary function of Tomasulo's algorithm?
What is the primary function of Tomasulo's algorithm?
Signup and view all the answers
The Scoreboard method solves structural hazards and does not introduce stall phases.
The Scoreboard method solves structural hazards and does not introduce stall phases.
Signup and view all the answers
What are reservation stations used for in Tomasulo's algorithm?
What are reservation stations used for in Tomasulo's algorithm?
Signup and view all the answers
The main cost of the Scoreboard hardware is due to the increased number of __________.
The main cost of the Scoreboard hardware is due to the increased number of __________.
Signup and view all the answers
Match the following terms with their descriptions:
Match the following terms with their descriptions:
Signup and view all the answers
What is the primary purpose of the scoreboard method in the context of CPU instruction scheduling?
What is the primary purpose of the scoreboard method in the context of CPU instruction scheduling?
Signup and view all the answers
The scoreboard method was first utilized in the CDC 6000 computer.
The scoreboard method was first utilized in the CDC 6000 computer.
Signup and view all the answers
What do the four stages of an instruction in the scoreboard method include?
What do the four stages of an instruction in the scoreboard method include?
Signup and view all the answers
In the scoreboard method, an instruction may be stalled due to a ______ hazard.
In the scoreboard method, an instruction may be stalled due to a ______ hazard.
Signup and view all the answers
Match the following stages of the scoreboard method with their descriptions:
Match the following stages of the scoreboard method with their descriptions:
Signup and view all the answers
What is the main purpose of the re-order buffer (ROB) in Tomasulo's algorithm?
What is the main purpose of the re-order buffer (ROB) in Tomasulo's algorithm?
Signup and view all the answers
Dynamic branch prediction is based solely on the nature of the branch instruction.
Dynamic branch prediction is based solely on the nature of the branch instruction.
Signup and view all the answers
What are the two types of methods used in branch prediction?
What are the two types of methods used in branch prediction?
Signup and view all the answers
In dynamic prediction, the __________ stores the decision and target address for executed conditional jumps.
In dynamic prediction, the __________ stores the decision and target address for executed conditional jumps.
Signup and view all the answers
Match the following branch prediction methods with their descriptions:
Match the following branch prediction methods with their descriptions:
Signup and view all the answers
Study Notes
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.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Related Documents
Description
Explore the vital role of the Central Processing Unit (CPU) in computer systems and understand the mechanisms like the scoreboard method and Tomasulo's method for handling hazards. This quiz will guide you through CPU instruction scheduling and execution techniques essential for efficient computing.
