University:
California State University, Northridge
Course:
COMP 222 | Computer Organization
Academic year:

2024
Views:

439

Pages:

23
Author:

vykolsinaigr

Chapter 12 Processor Structure and Function Part 3 Pipeline Hazards • Pipeline, or some portion of pipeline, must stall • Also called pipeline bubble • Types of hazards —Resource —Data —Control Resource Hazards • • • • Two (or more) instructions in pipeline need same resource Executed in serial rather than parallel for part of pipeline Also called structural hazard E.g. Assume simplified five-stage pipeline — Each stage takes one clock cycle • Ideal case is new instruction enters pipeline each clock cycle • Assume main memory has single port • Assume instruction fetches and data reads and writes performed one at a time • Ignore the cache • Operand read or write cannot be performed in parallel with instruction fetch • Fetch instruction stage must idle for one cycle fetching I3 • E.g. multiple instructions ready to enter execute instruction phase • Single ALU • One solution: increase available resources — Multiple main memory ports — Multiple ALUs Data Hazards • • • • • Conflict in access of an operand location Two instructions to be executed in sequence Both access a particular memory or register operand If in strict sequence, no problem occurs If in a pipeline, operand value could be updated so as to produce different result from strict sequential execution • E.g. x86 machine instruction sequence: • ADD EAX, EBX • SUB ECX, EAX /* EAX = EAX + EBX /* ECX = ECX – EAX • ADD instruction does not update EAX until end of stage 5, at clock cycle 5 • SUB instruction needs value at beginning of its stage 2, at clock cycle 4 • Pipeline must stall for two clocks cycles • Without special hardware and specific avoidance algorithms, results in inefficient pipeline usage Data Hazard Diagram Types of Data Hazard • Read after write (RAW), or true dependency — An instruction modifies a register or memory location — Succeeding instruction reads data in that location — Hazard if read takes place before write complete • Write after read (RAW), or antidependency — An instruction reads a register or memory location — Succeeding instruction writes to location — Hazard if write completes before read takes place • Write after write (RAW), or output dependency — Two instructions both write to same location — Hazard if writes take place in reverse of order intended sequence • Previous example is RAW hazard • See also Chapter 14 Resource Hazard Diagram Control Hazard • Also known as branch hazard • Pipeline makes wrong decision on branch prediction • Brings instructions into pipeline that must subsequently be discarded • Dealing with Branches —Multiple Streams —Prefetch Branch Target —Loop buffer —Branch prediction —Delayed branching Multiple Streams • Have two pipelines • Prefetch each branch into a separate pipeline • Use appropriate pipeline • Leads to bus & register contention • Multiple branches lead to further pipelines being needed Prefetch Branch Target • Target of branch is prefetched in addition to instructions following branch • Keep target until branch is executed • Used by IBM 360/91 Loop Buffer • Very fast memory • Maintained by fetch stage of pipeline • Check buffer before fetching from memory • Very good for small loops or jumps • c.f. cache • Used by CRAY-1 Loop Buffer Diagram Branch Prediction (1) • Predict never taken —Assume that jump will not happen —Always fetch next instruction —68020 & VAX 11/780 —VAX will not prefetch after branch if a page fault would result (O/S v CPU design) • Predict always taken —Assume that jump will happen —Always fetch target instruction Branch Prediction (2) • Predict by Opcode —Some instructions are more likely to result in a jump than thers —Can get up to 75% success • Taken/Not taken switch —Based on previous history —Good for loops —Refined by two-level or correlation-based branch history • Correlation-based —In loop-closing branches, history is good predictor —In more complex structures, branch direction correlates with that of related branches – Use recent branch history as well Branch Prediction (3) • Delayed Branch —Do not take jump until you have to —Rearrange instructions Branch Prediction Flowchart Branch Prediction State Diagram Dealing With Branches Intel 80486 Pipelining • Fetch — From cache or external memory — Put in one of two 16-byte prefetch buffers — Fill buffer with new data as soon as old data consumed — Average 5 instructions fetched per load — Independent of other stages to keep buffers full • Decode stage 1 — Opcode & address-mode info — At most first 3 bytes of instruction — Can direct D2 stage to get rest of instruction • Decode stage 2 — Expand opcode into control signals — Computation of complex address modes • Execute — ALU operations, cache access, register update • Writeback — Update registers & flags — Results sent to cache & bus interface write buffers 80486 Instruction Pipeline Examples Pentium 4 Registers EFLAGS Register Control Registers