[컴파일러 이론] 14. Instruction Scheduling

명령어(instruction)의 순서를 바꿔 성능을 더 좋게 만들 수 있는 경우가 있다.

이번 글은 명령어 스케줄링을 알아보자.

 

순서를 바꾸더라도 기능이 달라지면 안된다.

순서를 마음대로는 바꿀 수 없고, dependency 때문에 제약이 발생한다.

 

어떤 명령어를 옮겨야 하드웨어적으로 성능이 좋을까?

옮겨도 기능적으로 문제가 없을까?

 

이 두가지를 고려해야한다.

 

컴퓨터 구조론을 학습했다면 아래 그림이 어느정도 익숙할 것이다.

 

코드를 짤 때 하나씩 실행될 것이라고 생각하고 짜지만,

실제로 명령어는 여러 명령어에 대해 병렬 실행이 된다.

이렇게 cpu의 병렬 구조에 맞는 스케줄링을 해야한다.

 

또는 동시에 같은 레지스터에 값을 쓰는 것도 불가능하다.

이런 식으로 여러가지 동시에 실행이 불가능한 경우들이 있다.

 

따라서 constraint가 발생한다.

이 제약은 자원과 관련된 제약과, 프로그램과 관련된 제약으로 나뉘다.

 

---

Resource Constraints

Finite Issue Width

한 사이클에 실행할 수 있는 명령어의 개수가 유한하기 때문에 무한히 많은 명령어를 동시에 실행할 수 없다.

 

Limited Functional Unit per Instruction type

아무리 동시 실행이 가능한 많은 명령어를 가지고 있어도, 한번에 4개의 연산까지만 가능한 cpu가 있다고 해보자.

int형 연산기 2개, 메모리 연산기 1개, float형 연산기 1개 라고 하자.

 

아래 그림에서 왼쪽의 첫 4개의 명령어는 2,1,1개씩 잘 실행된다.

그 다음 4개를 보면 노랑(float)연산 2개는 동시에 실행이 불가능하다.

연산기가 하나밖에 없기 때문이다.

 따라서 int나 mem연산에서 빈 시간이 발생한다.

이런 경우 연산 자원을 최대한 사용할 수 없다.

 

---

Program Constraints

Data Dependency와 Control dependency로 나눌 수 있다.

 

<Data Dependency>

아래 그림의 왼쪽처럼 w연산에 x값이 필요한 경우 동시 실행이 불가능하다.

이전 연산의 결과를 기다려야 다음 명령을 실행할 수 있다.

이런 경우를 data dependency가 있다고 한다.

 

<Control Dependency>

오른쪽처럼 data dependency가 없더라도 if문의 실행을 기다려야 내부 코드를 실행할 수 있을 때도 있다.

이런 경우는 control dependency이다.

 

---

<control Dependency 해결 방법 - speculative code motion>

이건 if문의 조건이 참이던 거짓이던 미리 내부 내용을 실행하고,

실제로 실행이 안될 것이었다면 계산 값을 버리는 것이다.

만약 adder 2개 ,multiplyer 2개, Copy 1개(각 2,2,1사이클)라면

control denendency 때문에 주황 부분은 조건부로 실행되기 때문에 원래는 끌어올려서 같이 실행할 수 없다.

근데 이 cpu는 mul연산기가 2개라서 최대한 쓰고 싶기 때문에 연산기를 놀게 할 바에 실행될지 안될지 모르는 애들 일단 실행한다.

branch이후에 b가 사용되지 않는다면 if문이 실행되지 않을 경우였더라도 코드를 올려 미리 계산한 값이 결과에 영향을 미치지 않는다.

 

 

이번에는 b가 live한 경우이다.

a<t인 경우 원래 b값이 이용되어야 하는데, 맘대로 올려서 실행하면 달라질 수 있다.

이럴 경우를 위해 b' 이라는 레지스터를 만든다.

오른쪽 처럼 코드를 만든다면 위의 문제가 해결된다.

 

speculative code motion을 정리하면,

리소스에 여유가 있을 때,

control dependent한 코드를 branch앞으로 빼와서 실행하는 것이다.

브랜치가 실제로 실행될 것이였다면 사이클을 아낀 것이고, 아니어도 남는 리소스 쓴거라 손해는 아니다.

 

---

<data dependency 해결 방법>

data dependency는 크게 true dependency와 false dependency 두 종류로 나뉜다.

true dependency는 해결이 불가능하고, false dependency는 해결 가능하다.

<true dependency>

r1 = r4 + r5

r2 = r1 + 1

이전 계산의 결과를 다음 연산에 쓰는 경우이다.

 

<false dependency>

anti, output 두 가지 종류가 있다.

 

1. anti dependency

r1 = r2 + r3

r2 = r4 + r5

true와는 반대로 anti는 연산에 사용한 값이 다음 연산의 결과가 되는 것이다.

얼핏 보면 문제가 아닌 것 같은데 순서를 바꾸게 되면 의도와 다르게 계산이 되기 때문에 순서가 지켜져야한다.

 

2. output dependency

r1 = r2 + r3

r1 = r4 + r5

이것도 순서를 바꾸면 r1의 값이 달라진다.

---

이 3가지 상황 모두 명령어의 순서를 바꿀 수는 없지만 위에서 얘기했듯 false dependency의 경우에는 약간의 조작을 통해 가능하게 할 수 있다.

아래 그림처럼 r1' 이라는 레지스터를 하나 더 사용해 해결가능하다.

true의 경우에는 안되지만, 특이 케이스로 단순 copy의 경우 가능하다.

 

 

---

basic block scheduling

BB안의 범위에 한정되어 스케줄링하는 방법이다.

BB의 정의 때문에 BB안에서는 control dependency가 없다. 따라서 상대적으로 단순하다.

 

 

레지스터는 사이클의 시작에 read되고, write는 사이클이 끝나갈 때 된다고 가정하자.

따라서 read후 write는 한 사이클 안에서 가능하다.

 

 

---

list scheduling

list scheduling은 명령어의 순서를 짜주는 기법이다.
dependency를 위반하지 않으면서 명령어 중 우선순위가 높은 것부터 실행하여 전체 실행 시간을 줄이는 것이 목표이다.

 

입력:

1. DPG(data precedence graph) : 명령어 사이의 dependency를 나타내는 그래프이다.

2. machine parameters : 사용가능한 리소스에 대한 정보

 

출력 :

스케줄링된 instruction code

 

 

target list : 지금 실행 가능한 준비된 명령어들을 표시한 리스트이다.

이 리스트의 명령어를 실행하면 이로 인해 또 새로운 명령어들이 실행가능해질 것이다.

이렇게 반복적으로 실행하면 된다.

 

 

간단한 예시이다.

아래 그림은 마침 int 2, float 1이므로 딱 개수가 맞다.

이 명령어들이 실행하면 DPG에 의해 새로 실행가능해진 명령어들이 추가될 것이다.

 

 

하지만 리소스 보다 너무 많은 명령어가 ready상태면 문제가 어려워진다.

이것들 중 어떤 것을 실행하는게 좋을지 판단해야하기 때문이다.

 

아래는 DPG의 예시이다.

색깔은 사용하는 리소스 종류(add 연산기/mul 연산기)에 따라 다르게 표시되었다.

위 왼쪽의 그래프에서는 true, false dependency가 표현되어있지 않다.

이를 edge의 선 종류로 표현할 수 있다.

실선은 true, 점선은 false이다.

 

 

---

Priority

위에서 본 'ready한 명령어가 너무 많을 때 누구를 먼저 실행할지'를 판단하기 위해 priority개념이 있다.

아래 DPG에서 023569는 의존성이 없으므로 다 실행 가능하다.

일단 모든 화살표는 true dependency로 가정하자.

이중에 뭐 실행할지 우선순위를 정해야한다.

 

우선순위는 "내가 수행되는데 걸리는 시간+내가 실행되고 다음에 실행될 것들(실선) 중 가장 높은 우선순위"로 구한다.

만약 오른쪽처럼 false(점선)의존성이 있다면, "점선으로 연결된 자식 중 가장 높은 우선순위"와 기존 값 중 큰 값을 취한다.

 

 

만약 우선순위가 같을 경우

우선적으로 선택할 정책을 설정하면 된다.

예를 들어 lower instruction number를 먼저 고른다고 하자.

 

아래그림에서 처음은 dependency가 하나도 없는 명령어들이 ready list에 있는 상태로 시작한다.

이후 1. 우선순위, 2. 우선순위 같을 때 낮은 숫자 먼저 순서에 따라 배정한다.

 

 

위에서는 3,5중 3이 숫자가 작으므로 3을 선택했지만 만약 5를 선택했다면 더 빨리 끝날 수 있었다.

 

---

다른 방법으로 거꾸로(backward) 스케줄링하는 방법이 있다.

여기서도 같은 우선순위일 때 어떤 것을 먼저 선택할지 임의로 정할 수 있다.

 

 

위 두방법은 어떤게 더 좋다고 말할 수 없다.

따라서 RBF scheduling방법이라는 것을 사용한다.

forward, backward방식을 여려번씩, 각각 다른 tie breaking전략을 사용해서 해보고 좋은것을 선택하는 방법이다.

---

global scheduling

이전글에서 알아본 list scheduling은 basic block하나의 범위에서의 스케줄링이었다.

이번에는 블럭 간 스케줄링인 global scheduling을 알아보자.

 

control equivalence, speculative

global 범위에서 scheduling을 하기 위해서는 먼저 두 가지 개념을 알아야한다.

 

control equivalence : 두 명령어/BB 중 어떤 명령어/BB 하나가 실행되면 다른 명령어/BB가 실행되는 것도 보장이 될 때를 얘기한다.

예를 들면 if문 안의 코드들은 보통 control equivalent할 것이다.

 

speculative : 위에서 한번 봤던 단어이다. 실제 실행될지 모르지만 일단 실행하는 것이다.

---

스케줄링 시에는 가장 안쪽의 loop부터 스케줄링한다.

가장 안쪽에서 빼면 반복 횟수가 많이 줄 것이기 때문이다.

 

코드를 위로 올릴 때, speculative하거나 non-speculative하게 올릴 수 있다.

speculative하게 옮긴다는 것은, 자신을 지배하는 부모 중 control equivalent한 BB로 옮기는 것이다.

이 경우는 원래 분기가 실행이 되지 않을 거였다면 올려서 계산하는 행동은 쓸모없어질 수 있다.

 

non-speculative하게 옮긴다는 것은 control equivalent한 BB로 옮기는 것이다.

 

아래 예시를 보면 더 이해가 쉬울 것이다.

위 상황에서 nop자리에 다른 코드를 가져와 병렬로 실행하므로써 효율을 높일 수 있다.

speculative하거나 non-speculative하게 코드를 올릴 수 있지만,

speculative한 것은 쓸모없는 행동이 될 수 있어 non-speculative를 먼저 올리는 게 좋다.

 

아래는 정리된 알고리즘이다.

첫 for문에서 B1이 가장 먼저 선택되고, CandInsts는 B2와 B3의 준비된 명령어를 나타낼 것이다.

non-speculative한 B3의 준비된 명령어(i5)를 먼저 처리시도한다.

i5는 B1의 nop자리로 올라올 수 있다.

아래가 이 방식으로 스케줄링한 결과이다.

 

이렇게 이번글을 끝으로 컴파일러 이론 정리는 끝낸다.