비순차 실행(1편)

본 포스팅은 "프로그래머가 몰랐던 멀티코어 CPU 이야기" 를 읽고 주인장의 생각을 정리한 게시글 입니다.

책정보, 프로그래머가 몰랐던 멀티코어 CPU 이야기 : 네이버 책 (naver.com)

프로그래머가 몰랐던 멀티코어 CPU 이야기

1. 비순차 실행(Out Of Order Execution)

비순차 실행은 일을 순서 바꿔 실행하면서, 성능을 향상시키는 방법 입니다.

 

예를들어, Code의 실행 순서가 명령어1 → 2 → 3 → 4 순서로 되어 있다면,

 

최적의 성능을 위해서 명령어 1 → 3 → 4 → 2 등으로  바꾸는 것을 의미합니다.

 

지난 포스팅의 파이프라인 최적화를 위해서, 명령어 비동기 처리도 비순차 실행에 해당됩니다.

 

2. 비순차 실행이 왜 필요한가?

아래 예시를 보겠습니다.

1: x = data[10];
   ↑---↓  #x의 결과가 y에 영향을 줌
2: y = x + 10;
3: a = b / c;
4: d = e * f;

1번 코드를 실행할 때, 캐시에 데이터가 없다면 RAM까지 데이터를 찾게 되고, 이는 100clock 이상이 소요되게 됩니다.

 

이때, 1번 코드의 작업이 10clock이 걸리고, 나머지 코드들은 모두 1clock안에 처리된다고 가정해 보겠습니다.

 

그럼 순차적으로 실행할 경우, 10(명령어1) + 3(명령어2 + 3 + 4) = 13clock

 

하지만, 명령어의 실행을 1->3->4->2로 진행한다면 10(명령어1, 이때 명령어 3, 4 도 실행됨) + 1(명령어2) = 11clock

 

시간 순서로 보면 아래와 같습니다.

[ ] <= 1clock동안 실행됨

명령어 1  [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
명령어 2                                [ ]
명령어 3     [ ]
명령어 4        [ ]

위 예시처럼, 명령어의 순서를 바꾸는것 만으로도 성능 향상을 야기할 수 있으며, 이렇게 명령어의 순서를 바꿔서 실행하는 것을 ILP(Instruction Level Parallelism, 명령어 수준 병렬성) 이라고 합니다.

(명령어 비순차 처리 = 명령어 수준의 병렬처리)

(Thread를 동시에 실행하는 방법은 ILP와 별개로 TLP(Thread Level Parallelism. 쓰레드 수준 병렬성) 이라고 부릅니다.)

 

ILP는 약어이자 수치로 사용됩니다. 아래 예시를 보시죠.

1: x = data[10];         3: a = b/c;           4:d = e*f;
     |
     ↓
2: y = x + 10;

만약 모든 명령어가 1clock을 소모한다고 하면, 
일반적으로 실행하면 4clock(1하고 2하고 3하고 4)

명령어 비동기 처리를 하면 2clock(1, 3, 4는 동시에, 그다음 2)

위 경우, ILP = 일반처리 / 비순차 처리 = 4/2 = 2 가 나옵니다.

 

ILP는 실행하는 프로그램에 따라 바뀌지만, 최악의 경우 1이 나오고, 이상적인 경우 명령어 개수만큼 나옵니다.

 

ILP는 잘 생각해보면, 단일 쓰레드 CPU가 가질 수 있는 최대의 IPC라고 할 수 있습니다.

(어떻게 되었던, 1Clock당 완료되는 명령어의 수가 되기 때문입니다.)

 

3. 어떻게 비순차로 실행하는가?

일단, 한번에 관리할 수 있는 명령어의 수 만큼 명령어 윈도우를 갖습니다.

 

명령어 윈도우가 128이면, 한번에 128개의 명령어에 대해서 ILP를 찾을수 있다는 뜻입니다.

(128개의 명령어에 대해서 ILP가능 여부를 판단하고, 최적화된 명령어 순서를 찾는다는 의미같습니다)

(인텔 코어2 프로세서는 96, 네할램은 128개의 명령어 윈도우를 사용)

 

명령어 윈도우 내에 들어온 명령어들을 in-Flight 명령어 라고 하며,

 

이 명령어들은 ROB라고 불리는 Queue에 들어가서 순서대로 체크됩니다.

 

자신의 피연산자가 준비 되었는지를 체크하여, 피연산자가 준비된 명령어를 실행하게 됩니다.

 

위와같은 알고리즘을 토미슐로 알고리즘 이라고 부릅니다.

 

이때, ROB 버퍼에 들어가 있는 명령어 중 실행되지 않은 명령어의 피연산자 준비를 확인할때, Resevation Station(RS)를 사용합니다.

 

RS는 ROB의 미실행된 명령어의 피연산자가 준비되었는지를 확인하고, 피연산자가 준비되었을 경우 Wake-up을 시키고, 해당 명령어를 Select합니다.

 

이 RS같은경우 인텔 네할렘 에서 36개까지 카바가 가능합니다.

 

RS의 크기를 늘려야지 많은 명령어를 비순차 처리할 수 있지만, RS의 크게를 늘린 만큼 구현 복잡도가 크게 증가하여 고성능 프로세서의 병목이 된다고 합니다.

 

4. ROB

ROB는 Re-Order Buffer의 약자 입니다.

 

명령어를 효율을 위해서 비 순차적으로 실행 하더라도, 명령어의 완료는 순차성이 유지되어야 합니다.

 

ROB의 크기 = 명령어 윈도우의 크기 라고 볼 수 있으며, RS의 크기는 ROB보다 작을수 밖에 없습니다.

(명령어 윈도우 내의 명령어가 ROB로 들어가고, ROB에 있는 실행되지 않은 명령어들이 RS에서 관리하기 때문이죠)

 

ROB는 각 명령어들의 Status(Ex. 실행중, 실행 대기중, 완료)로 관리하고, 가장 오래된 명령어가 완료되었을 경우 Commit을 하게 됩니다.

---------------------
명령어     |   Status
---------------------
a = b + c  |    대기
e = f * e  |    완료
z = z + 1  |    처리
 ...            ...

 

 

따라서, 개발자는 명령어의 비순차 실행과 관계없이, 최종적으로 순차적으로 완료되는 실행 결과를 기대할 수가 있습니다.