12. Other Ways for Handling Control Dependency

생성일: 2021년 11월 5일 오후 2:58

• Potential solutions if the instruction is a control-flow instruction:
  • Stall the pipeline until we know the next fetch address
  • Backward Taken Forward Not Taken
  • Guess the next fetch address (branch prediction)
  • Do something else (fine-grained multithreading)
  • Employ delayed branching (branch delay slot)
  • Eliminate control-flow instructions (predicated execution, Loop Unroll)
  • Fetch from both possible paths (if you know the addresses of both
    possible paths) (multipath execution)

Delayed Branching

• Change the semantics of a branch instruction
• Problem : How do you find instructions to fill the delay slots?
  • Conditional Branch

Delayed branch 를 이용하여 cycle 수를 줄였다. B는 독립적인 instruction 이기 때문에 실행 순서를 바꾸어도 지장이 없다 ⇒ BC X (브랜치)를 먼저 실행 시켜서 비는 시간이 없도록 한다.

• Delayed branch with squashing

  • 브랜치가 not taken 일때 delay slot instruction 은 실행되지 않는다.

    

• 장점
  • Keeps the pipeline full with useful instructions in a simple way assuming
• 단점
  • Not easy to fill the delay slots (even with a 2-stage pipeline)
  • Ties ISA semantics to hardware implementation

Predication (Predicated Execution)

• Compiler converts control dependence into data dependence ⇒ branch is eliminated
  

• Predicated execution can be high performance and energy-efficient

1번은 일단 다 실행해보고 나중에 필요 없는 부분을 not operation 으로 날리기

• 장점
  • 손해보는 정도가 정해져 있음, 예측이 어려운 브랜치에 좋음, 잘못 예측되는 일이 없음, 브랜치를 사실상 없애는 것이기에 컴파일러가 더 자유롭게 코드 최적화 가능
• 단점
  • 엄청나게 큰 반복문과 같은 경우를 실행해야한다면 그냥 예측해서 하나만 실행시키는 것이 더 이득
  • 예측이 쉬운 브랜치일 경우 쓸모 없는 일을 한 꼴

2번은 예측해서 필요할 것 같은 것만 실행

• 장점
  • 실행 시간이 큰 두가지 선택지 중에 하나를 예측해서 실행하므로 예측 성공시 메리트가 큼
• 단점
  • 예측 실패시 실행시킨 것이 의미없게 되고 새로 다시 반대 것을 실행 시켜야 함

따라서, 1번과 2번을 잘 선택해서 사용해야 한다.

Loop Unrolling

• program transformation that trades code size for execution speed

반복문 branch의 수를 줄여서 실행 시간을 단축시킨다.

• 장점
  • Increases program efficiency
  • Reduces loop overhead
  • If statements in loop are not dependent on each other, they can be executed in parallel
• 단점
  • Increased program code size, which can be undesirable
  • Possible increased usage of register in a single iteration to store temporary variables which may reduce performance
  • Apart from very small and simple codes, unrolled loops that contain branches are even slower than recursions