컴퓨터 구조(9), Control Dependence Handling: Predicated Execution and Loop Unrolling

Control Dependence

---

1. Predicated Excution

- control dependence는 브랜치때문에 발생한다.

- 타겟 어드레스를 보고 Backward, Forward를 하는 방법이 있었다.

- branch prediction도 사용한다.

- 위의 내용을 모두 사용해서 성능을 높이기 위해 노력한다. 이때 control-flow instructions을 제거하는 방법이 있다. 이는 MIPS ISA에는 없다.

 

 

 

- ARM은 ISA를 다음과 같이 디자인했다. condition에 4비트를 사용해서 브랜치 명령어를 줄인다.

 

예제)

- 브랜치를 없애고 이를 condition으로 바꿔서 실행할 것인지 말 것인지를 확인한다. 이를 통해 원래는 control 디팬던시가 있었지만 이를 데이터 디팬던시 문제로 바꿔서 브랜치를 제거해줄 수 있다. 

- ARM은 브랜치를 없애는 대신 다음과 같이 Condition 4비트를 줬다.

 

- 위와 같이 ISA를 정의했다.

 

 

- x86이나 Alpha는 이를 적용해서 사용했다.

- 다시 정리해서 컨트롤 디팬던시를 없애고 이를 데이터 디팬던시로 바꿨다. 

 

- 높은 성능과 에너지 효율을 얻을수도 있다.

- branch prediction을 하고 틀리면 뒤에 있는 것들을 모두 버려야하지만 Predicated execution을 사용하는 경우에는 하나만 없애면 된다.

- 만약 C나 B에서 실행해야하는 명령어가 엄청 많은 경우에는 오히려 더 많은 시간이 걸릴수도 있다. 이에 따라 브랜치 예측이 어렵거나 C나 B를 모두 돌렸을 때 실패해서 얻게될 비용이 적다면 Predicated execution을 사용하는 것이 좋다.

- 예제는 C가 맞을 때이다.

- Control 디팬던시가 데이터 디팬던시로 바뀐 것이다.

 

Predicated Execution 장단점

- 브랜치 예측이 어려우면 Predicated Execution을 하는게 더 유리하다. 

- 잘못 예측했을 때의 비용이 Predicated Execution의 비용보다 작다면 이를 하는 것이 더 좋다. 

- 하지만 Predicated Execution은 useless가 있기에 예측이 쉽다면 이를 사용하는 것이 더 손해일수도 있다. 또한 스태틱한 예측이기에 브랜치 특성을 반영하기 어렵다. 또한 추가적인 ISA의 지원이 필요하다. MIPS에서는 못한다.

 

Conditional Execution in ARM ISA

- 직전에 실행된 명령어에서의 ALU의 결과값이 0인 경우 ADDEQ를 실행하는 등의 방법도 사용할 수 있다.

---

2. Loop Unrolling

- for문을 돌리는데 이는 매번 브랜치가 존재한다. 이를 unrolling해서 반복문을 풀어서 브랜치의 횟수를 줄일 수 있다. 직접 코드를 작성하는 것이 아니라 unrolling을 해준다. 실행 속도가 훨씬 빠르지만 프로세서가 unrolling할 수 있는 것을 unrolling을 해준다. while문이나 for문은 unrolling을 하면 실행 속도가 더 빠르다.

 

- 반복(루프)의 개수를 줄여준다.

 

- 굉장히 효율적이며, loop도 줄여주고, 동작 시간이 매우 효율적이게 된다.

- 이에 따라 브랜치 예측에 발생한 오버헤드도 줄여주고 빠르며, 풀어낸 코드들은 디팬던시가 없기에 병렬적으로 실행할 수 있다.

- 하지만 명령어의 개수가 늘어난다. 또한 레지스터 사용이 늘어나며 간단한 코드가 복잡해질 수 있다.