reference: "프로그래머가 몰랐던 멀티코어 CPU 이야기" / 김민장, "Computer System A Programmers'Perspective" / 랜달 E.브라이언트
파이프라인은 명령어를 순서대로만 처리했다. 이 방법은 사이클이 낭비될 수 있다는 단점을 가진다. 비순차 실행은 이런 단점을 극복한다. 비순차 실행 프로세서는 프로그램을 적혀 있는 순서대로 실행하는 것이 아니라, 프로세서가 직접 명령어 사이의 의존성을 분석하여 먼저 실행할 수 있는 명령을 미리 실행시켜 명령어 완료 시간을 크게 단축시킨다. 비순차 실행은 명령어 수준 병렬성이라는 것을 활용한다. 비순차 실행, 그리고 이를 더욱 잘 작동할 수 있도록 하는 슈퍼 스칼라 처리에 대해 알아본다.
슈퍼 스칼라: "프로세서 내에 pipeline 된 ALU를 여러개 포함, 매 사이클마다 다수의 명령어들이 동시에 실행되는 기술"
비순차 슈퍼스칼라 프로세서가 필요한 이유
프로그래머는 자신의 프로그램이 '순서'대로 프로세서가 실행해 줄 것으로 당연히 믿고 있다. 파이프라인은 프로그래머의 믿음처럼 주어진 명령어를 순서대로 처리했다. 이런 프로세서를 순차(in-order) 프로세서라고 부른다.
1: x = data[10];
2: y = x + 10;
3: a = b / c;
4: d = e + f;위 코드에서 1번 명령은 load 명령이다. CPU 내의 캐시에서 데이터를 찾지 못하고 메인 메모리에서 데이터를 가져온다면 보통 컴퓨터에서 이 작업은 100사이클이 훨씬 넘는 시간이 걸린다. 덧셈 같은 단순한 정수 연산이 한 사이클마다 완료될 수 있다는 것을 상기하면 매우 긴 시간이다. 따라서 2번 명령은 1번 명령이 완료될 때까지 기다려야 한다. 하지만 3번과 4번 명령은 아무런 관련이 없다.
1번 명령이 완료되지 못하고 기다리는 상황에서 3번 나눗셈 명령을 처리할 수 있다면 프로그램 완료 시간을 단축할 수 있다. 비순차 실행(Out-of-Order Execution, OOO)에선 이것이 가능하다.
이것을 구현하려면 3번 명령이 1, 2번과 무관하다는 사실을 알아내야 한다. 또 1번 명령이 멈춰있을 때와 같은 상황에 3번 명령어가 실행될 수 있게 스케줄링할 수 있어야 한다.
여기서 또 하나 명령어 처리율을 높일 수 있는 기회가 있다. 살펴보면, 4번 명령 역시 1~3번과 무관하다. 이상적으로 1번 명령이 캐시 미스를 겪는 동안 3, 4번 두 명령어를 동시에 처리할 수 있다면 더욱 좋을 것이다. 지금까지 알아본 파이프라인 구조는 파이프라인이 오직 하나만 있었기에 명령어를 한 사이클에 하나만 투입할 수 있었고, 또 하나씩만 완료가 가능했다. 즉 최대 IPC(Instruction per Cycle)가 1이었다. 그런데 만약 파이프라인이 두 개로 복제되어 있다면 3, 4번 명령은 병렬로 처리가 가능할 것이다. 이런 구조를 슈퍼 스칼라(superscalar) 프로세서라 부른다. 슈퍼스칼라는 파이프라인이 여러 개 있어 여러 명령어를 동시에 처리(투입)하는 구조를 뜻한다. 이 슈퍼스칼라와 비순차 실행으로 프로세서의 명령어 처리 성능을 크게 높일 수 있다.
1: x = data[10];
2: y = x + 10;
3: a = b / c;
4: d = e + f;위 코드를 다시 보면서 완료되는데 걸리는 사이클을 비교해보자면,
캐시 미스가 났을 때 메모리 load는 100사이클이 소요된다고 가정한다. 또한 덧셈, 곱셈, 나눗셈은 각각 1, 4, 10사이클이 걸린다고 가정한다. 비슈퍼스칼라 및 순차 프로세서는 주어진 명려어를 최대 하나씩만 순서대로 처리하기에 100 + 1 + 10 + 4 = 115 사이클이 필요하다. 그러나 이상적인 슈퍼스칼라 및 비순차 프로세서라면 1번 명령이 캐시 미스를 겪는 동안 3, 4번 명령을 동시에 처리할 수 있어, 101 사이클만이 걸린다. 여기서는 캐시 미스가 이미 100사이클이나 필요하기 때문에 큰 차이가 안 나는 것 같지만 비순차 프로세서는 순차 프로세서에 비해 명령어 완료 시간을 몇 배 이상까지도 단축시킬 수 있다.
슈퍼스칼라 및 비순차 실행 역시 소프트웨어 알고리즘으로 컴퓨터 소프트웨어 어디에나 적용 가능한 일반적인 알고리즘이다.
비순차 실행의 원리: 명령어 수준 병렬성
비순차 실행은 명령어 수준 병렬성(Instruction Level Parallelism, ILP)을 찾아 프로그램에 적혀 있는 순서가 아닌 데이터의 흐름에 따라 명령어를 처리하는 기술이다. ILP라는 개념은 비순차 실행을 이해하는데 핵심이 된다. 병렬성이라고 하면 멀티 쓰레드나 멀티 코어를 먼저 떠올린다. 두 개의 독립적인 쓰레가 있다면 이 두 쓰레드는 '동시'에 작동한다. 보다 구체적으로 말해면, 멀티 코어에서는 정말로 두 쓰레드가 물리적으로 동시에 실행될 것이다. 싱글코어 프로세서에서도 운영체제의 시분할 멀티태스킹 기능 덕분에 논리적으로는 동시에 실행되는 것처럼 보인다. 어떤 방법이든 프로그래머는 여러 쓰레드가 동시에 실행되는 병렬성이 있다고 생각할 것이다. 이런 병렬성을 쓰레드 수준 병렬성(Thread-level parallelism, TLP)이라고 부른다. TLP는 프로그래머가 명시적으로 멀티쓰레드 프로그램을 작성했을 때 얻는 병렬성이다.
그런데 프로그래머가 멀티쓰레드로 작성하지 않은 일반적인 싱글쓰레드 프로그램에도 분명히 동시에 실행가능한 명령어를 찾을 수 있다. TLP보다 규모가 작은 병렬성이 있는 것이다. 이것을 ILP, 명령어 수준 병렬성(Instruction-level parallelism)라고 부른다.
1: x = y + 1;
2: a = b * 2;(이 코드에서 모든 변수는 포인터가 아닌 int/float 같은 스칼라 형이라 가정.) 1번과 2번 명령이 동시에 실행하다. 1번 또는 2번 명령 중 어떤 것이 먼저 수행되든 프로그램의 문맥에는 차이가 없다.(여기서 문맥이란 컴퓨터 구조적 상태(architectural state)를 가리킨다.) 이 두 명령을 순서에 상관없이 실행해도 레지스터나 메모리 내용은 같다.
엄밀히 따지면 위 문장도 오류가 있는데, 어떤 연산은 플래그 레지스터 값을 변경시킨다. 그래서 플래그 값을 변경시키는 명령어나 이 플래그 값을 이용하는 연산이 있으면 숨어있는 의존성이 있는 것이다.
달리 말하면 1, 2번을 어떤 순서대로 실행해도 이 프로그램의 의미(semantic)를 정확히 실행하는 것이다. 데이터 의존성만 지킨다면 실제 실행 순서는 바뀌어도 큰 문제가 없을 것이다. 바로 이것이 ILP이다.
주어진 프로그램에 ILP가 얼마나 되는지는 그 프로그램의 성격에 따라 매우 다르다. 일반적으로 과학 계산 프로그램의 명령어 수준 병렬성은 매우 풍부하지만 그렇지 않은 프로그램도 많다.
위 코드에서 1, 2번 명령은 변수 x에 대해 RAW 데이터 의존성을 가진다. 그러나 3, 4번은 아무런 관련이 없다.
만약 순차 방식으로 실행하면 총 4사이클에 완료될 수 있고, ILP를 찾아 병렬 수행하여 2사이클만에 완료할 수 있다면 이 프로그램의 ILP는 4/2 = 2라고 할 수 있다. 아주 극단적으로 엄청나게 많은 자언이 있고, 하나의 명령어를 1사이클만에 처리할 수 있다쳤을 때, 만일 모든 명령어가 의존성으로 묶여 있다면 ILP는 1이 될 것이며, 최대 값은 명령어 갯수가 된다.
ILP는 이론적인 프로그램의 속성으로 프로그램의 성격에 따라 ILP는 크게 다르다. ILP는 싱글쓰레드 프로그램에서 추출할 수 있는 병렬성의 이론적인 상한 값이다.
IPC(Instruction per Cycle) vs ILP(Instruction Level Parallelism) 혼동X
ILP는 프로그램에 고유한 성격이고, 사이클 당 처리할 수 있는 명령어 개수인 IPC는 프로세서 구현 방식에 따라 구현된다.
비순차 실행은 스케줄링 관점에서 볼 수 있다. 비순차 실행은 명령어를 정적으로 정해진 순서대로만 처리되도록 스케줄링하지 않고 동적으로 명령어 사이의 의존성을 파악해 스케줄링한다. 그래서 비순차 실행을 "동적 스케줄링(dynamic scheduling) 기법"이라 부른다. 그런데 ILP는 반드시 하드웨어가 찾아줄 필요는 없다. 소프트웨어(컴파일러)가 대신 찾아줄 수도 있다. 여기서는 하드웨어에 의한 ILP 탐색 방법에 대해서만 이야기한다.
한편, 컴퓨터 구조 중 데이터플로우(dataflow)라는 전통적인 컴퓨터 실행 방식과 매우 다른 처리 방식이 있다. dataflow 구조가 바로 지금 여기서 설명하는 비순차 실행 방식의 이상적인 모습이다. 비순차 실행은 제한된 형태의 dataflow 구조이다.
슈퍼스칼라 파이프라인 구조
슈퍼스칼라는 파이프라인이 여러 개 있어 동시에 명령어를 처리할 수 있는 구조를 말한다. 아래 그림은 파이프라인이 두 개 복제된 슈퍼스칼라 구조이다. 최대 12개의 명령어가 동시에 실행 가능하다.
여지껏 본 파이프라인 프로세서는 파이프라인이 하나밖에 없어 얻을 수 있는 최대 1사이클에 하나의 명령어만 완료할 수 있었다. 다시 말해 IPC가 1이었는데 이 값을 높이려면 파이프라인을 여러 개 두어 명령어를 동시에 실행시켜야 한다.
위 그림처럼 파이프라인이 두 개라면 이상적으로 사이클마다 최대 두 개의 명령어가 투입(issue)과 완료(graduation, retirement) 가능하여 IPC = 2가 된다.
보통 슈퍼스칼라 프로세서는 동시에 투입/완료가 가능한 명령어 개수에 따라 N-이슈, N-와이드, N-웨이 슈퍼스칼라로 표현한다. 이상적으로는 N개의 명령어를 읽어 파이프라인에 넣을 수 있지만(fetch), 실제로는 명령어 캐시의 제약, 명령어 사이의 의존성, 분기문 때문에 N개 보다 작은 명령어만 넣을 수 있을 때가 일반적.
슈퍼스칼라 프로세서는 오직 명령어 파이프라인이 여러 개 복제되어 있는 것만 가리킨다. 프로세서가 순차인지 비순차인지에 대해서는 무관하다. 비순차 프로세서가 슈퍼스칼라가 아닌 1-와이드 프로세서일 수도 있다. 반면, 순차 프로세서가 슈퍼스칼라 방식일 수도 있다. 그런데 비순차 프로세서가 좋은 성능을 내려면 슈퍼스칼라로 만들어져야 하기에 슈퍼스칼라를 비순차 프로세서 자체로 오해하는 경우가 종종 있다.
현대 x86 프로세서는 보통 2~4-와이드 구조를 갖는다. 최초의 펜티엄 프로세서는 파이프라인 중 일부를 두 개로 나누어(각각 u-파이프라인, v-파이프라인) 처리하여 완벽하지는 않지만(명령어는 한 사이클에 하나만 투입) 슈퍼스칼라와 비슷한 구조를 만들었다. 인텔의 네할램 구조는 기존 Core 아키텍쳐의 3-와이드에서 4-와이드 구조로 확장했다.
각종 마이크로아키텍처를 연구할 때는 8~16 와이드 같은 매우 폭 넓은 슈퍼스칼라도 고려된다. 그러나 실제로는 이보다 작은 크기의 슈퍼스칼라 프로세서를 구현하는데, 일반적인 하드웨어에서 찾을 수 있는 IPC가 보통 5를 넘지 않기 때문이다. 이상적으로는 10에서 수백에 해당하는 값도 얻을 수 있지만, 하드웨어 제약으로 그렇게까지 찾지 못하였다. (현재는 또 모름.. 오래된 책이기에)
슈퍼스칼라 프로세서의 구현은 수많은 어려움을 만든다. N-와이드 프로세서라면 최대 N개의 명령어를 읽어와야 하는데 명령어 캐시가 이를 손쉽게 해결하지는 못한다. 만일 명령어가 제대로 정렬되지 않았거나 다른 캐시 라인에 걸쳐 있다면 쉽지 않다. 또 동시에 읽은 명령어 가운데 분기문이 끼어 있다면 문제가 어려워진다. 바이패스 로직 역시 복잡해진다. 비슈퍼스칼라 프로세서는 한 명령어에만 계산 결과를 전달하면 되지만 슈퍼스칼라는 이것이 N배로 커진다.
