[Parallel Computing] (19) Register Allocation

Register는 CPU나 GPU에 속해있는 저장공간으로 연산 동작 중에 저장이 필요한 데이터를 저장해두는 용도로 사용된다. 연산 장치에 가장 가까이 있는 저장공간으로 접근 속도가 상당히 중요하다. 그러므로 빠른 접근 속도를 가지는 메모리를 사용하였고, 비용 및 공간의 문제로 많은 Register를 두기 어렵다.  물론 사용할 수 없는 Register가 없다고 저장이 필요한 연산을 수행하지 못하는 건 아니다. Main memory를 활용하면 연산을 수행할 수 있지만, Main memory는 매우 느리기 때문에 성능에 악영향을 줄 수 있다. 그렇기 때문에 이런 한정된 Register를 가지고 연산을 효율적으로 하기 위한 방법이 필요하다.
가장 널리 알려진 방법이 Chaitin's algorithm이다.
이 알고리즘을 소개하기 전에 그 전에 관련 용어들에 대해서 정리하고 시작하겠다.
여담이지만 Allocation 과 assignment의 차이를 이야기하자면, Allocation(할당)은 어떤 값들을 Register들에 저장할 지 정하는 것이고, Assignment(배정,배치)는 값을 저장하기 위한 Register를 고르는 것을 말한다.
Interference는 두 개의 값이 서로 Live할 때, 두 값은 절대 같은 레지스터에 할당되면 안된다는 것을 말한다. Interference graph는 이 관계를 graph로 표현한 것을 말한다.
변수 𝑎가 point 𝑝에서 "live"라고 하려면 프로그램의 flow graph에서 point  𝑝 에서 시작하여 𝑎의 값을 사용하는 지점에서 끝나는 경로가 있어야 한다. 이 경로를 따라서 𝑎 의 값은 보존되어야 하며, 즉 사용되기 전에 덮어쓰이거나 변경되어서는 안 된다.
이 때, live해야하는 구간을 live range라고 표현한다.
Spilling은 특정 값을 레지스터에서 메모리로 저장하는 것을 말한다. Spilling을 수행할 경우, 해당 Register는 free 상태가 되므로 다른 값을 저장할 수 있다.

일반적으로 Register allocation을 수행할 때 사용하는 것이 graph-colouring paradiam이다.
처음으로 값들의 interference graph를 만든 다음, graph 내에서 k개의 color로 색칠이 가능한 graph를 찾는 것이다. (k는 Register의 개수)그런데 너무 많은 경우수가 존재하므로 NP-Complete가 된다.

이를 찾기 위한 방법이 Chaitin's algorithm이다,
interference graph에서 어떤 노드는 연결되어 있는 다른 노드와 같은 색으로 칠해질 수 없다. 이를 주시하면서, 각 노드별로 몇 개의 노드와 연결되어 있는 지를 체크한다. Graph 내에 노드의 연결 횟수가 만약 존재하는 Register의 개수보다 많다면, Spill을 통해서 연결을 끊어서 노드간 연결 횟수를 줄인다.
Register 개수보다 작아진다면, 충분히 색칠이 가능해진다.

아래는 Chaitins' algorithm의 예시이다.

Chaitin's algorithm example [1]

Stack에 하나씩 넣어 가면서 노드 간의 연결을 끊고, 모든 노드가 Stack에 담기면 다시 하나씩 꺼내면서 색칠을 한다.

위의 예제에서는 Spilling이 발생하지 않았다. 만약 아래와 같이 모든 노드가 사용할 수 있는 Register 개수 만큼 이웃노드를 가진다면, Spilling을 수행해야 한다.

Spilling이 필요한 Graph

이런 경우 하나의 노드를 정해서 Spiling을 수행한 다음, 아래와 같이 Graph를 만들어 다시 시작해야 한다.

spilling이 수행된 Graph

이 경우, t8, t4, t7부터 다시 Stack에 넣고 진행될 수 있다.




*Reference
[1]: https://www.inf.ed.ac.uk/teaching/courses/copt/lecture-7.pdf