Chap. 3 Instruction-Level Parallelism and Its Exploitation

• basic block—a straight-line code sequence with no branches in except to the entry and no branches out except at the exit

• loop-level parallelism

• • loop unrolling
• • SIMD

Data Dependences and Hazards

Data Dependences

• data dependences (also called true data dependences)
• name dependences
• control dependences

A data dependence conveys three things: (1) the possibility of a hazard (2) the order in which results must be calculated (3) an upper bound on how much parallelism can possibly be exploited

A dependence can be overcome in two different ways: (1) maintaining the dependence but avoiding a hazard (2) eliminating a dependence by transforming the code.

Scheduling

Name Dependences

A name dependence occurs when two instructions use the same register or memory location, called a name, but there is no flow of data between the instructions associated with that name.

1. An antidependence between instruction i and instruction j occurs when instruction j writes a register or memory location that instruction i reads. The original ordering must be preserved to ensure that i reads the correct value.
2. An output dependence occurs when instruction i and instruction j write the same register or memory location.

register renaming

Data Hazards

Control Dependences