Instruction Set Principles and Dependences

note

• Take advantage of parallelism
• Programs have high locality
  • Sped 90% runtime in 10% of code
• Focus on common case

• Tradeoffs to consider when designing an instruction set
  • Complexity
  • Code Size
  • Can it be implemented?
  • Does it fit well with the intended application?

Four Types of Machines

• Stack: Operands are registers at the top of the stack
• Accumulator: One register for an operand and the other operand comes from memory
• Register-memory: One register operand and one memory operand
• Register-register/load-store: Both operands come from registers, load/store to copy to/from memory

Addressing Modes

Name	Example	Comment
Register	ADD r5, r4, r2	can put register name in instruction
Immediate	ADD r5, r4, 500	can put number in instruction
Register Indirect	ADD r5, r4, (r2)	r2 contains the address of the register to add
Displacement	ADD r5, r4, 4(r2)	r2 contains the base address, then you add the displacement to it (in this case, that is 4)

In the last example, the number 4 is called the offset or displacement.

Static instruction: Instrictions in program binary

Dynamic Instructions: Instrictions when running the program.

Control Flow Instructions

• Branches
• Jumps
• Returns
• Function Call

Instruction-Level Parallelism (ILP)

Definition

Parallel execution of instructions in a code sequence

Pipelining is a technique that uses ILP because multiple instructions are in the pipeline at the same time

Approaches to Obtaining ILP

• Hardware
  • Design CPU hardware that can detect when instructions are parallel
• Software
  • Have the compiler flag which instructions are independent

Data Dependences

• Parallelism is limited by data dependences

lw R1, 0(R2)

add R4, R1, R3

lw R1, 4(R3)

and R5, R2, R1

• Which instructions have dependencies?
  • lw R1, _(__) (frist lw) and add __, R1, __ (True Dependence)
  • lw R1, _(__) (second lw) and and __, __, R1 (True Dependence)
  • add __, R1, __ and lw R1, _(__) (Antidependence)
  • lw R1, _(__) (frist lw) and lw R1, _(__) (second lw) (Output Dependence)

True data dependences are when an instruction uses a result produced by another instruction.

• Name dependences

  • Antidependence: an instruction writes a register that a previous instruction reads

  • Output dependence: an instruction writes a register that a previous instruction writes

The reason there are name and true dependences is that you can get rid of the name dependences and you can run instructions in parallel. By changing the second lw and the second add to use R10 instead of R1, you can run the first and second lw and and in parallel.

Control Dependence

• Instructions are dependent on branches
  • You may run some instructions depending on a branch outcome

Data Hazards

• RAW: Read after Write (True data dependence)
• WAW:: Write after Write (Output-dependence)
• WAR:: Write after Read (Anti-dependence)