명령어 수준 병렬성

명령어 수준 병렬성(ILP)은 한 프로그램의 명령어들 사이에서 동시에 처리할 수 있는 일을 찾아내는 기술입니다. 프로그래머는 대체로 한 줄씩 쓰지만, 하드웨어는 속으로 묻습니다. “이 두 줄, 사실 서로 기다릴 필요 없지 않나?” 이 장의 핵심은 그 질문을 매우 공격적으로, 그러나 결과는 정확하게 유지하며 던지는 방법입니다.

파이프라인과 해저드

파이프라인은 세탁소 컨베이어벨트와 비슷합니다. 한 벌을 세탁하고 말리고 다림질하고 포장할 때까지 기다린 뒤 다음 옷을 받는 대신, 단계마다 다른 옷을 올려 전체 처리량을 높입니다. CPU도 명령어 인출, 해독, 실행, 메모리 접근, 기록 같은 단계를 겹쳐서 처리합니다. 이상적인 파이프라인은 매 사이클 명령어 하나를 끝냅니다.

문제는 명령어들이 얌전히 줄 서 있지 않다는 점입니다. 앞 명령어의 결과가 뒤 명령어에 필요하거나, 같은 하드웨어를 동시에 쓰려 하거나, 분기 때문에 다음 명령어 주소가 불확실해집니다. 이런 방해물을 해저드(hazard)라고 부릅니다.

정적 ILP와 컴파일러의 몫

ILP를 찾는 가장 조용한 방법은 컴파일러가 미리 명령어 순서를 바꾸는 것입니다. 결과가 달라지지 않는 범위에서 독립적인 명령어를 앞으로 당기고, 오래 걸리는 load 뒤에는 그 결과와 무관한 일을 끼워 넣습니다. 루프 언롤링은 반복문의 제어 오버헤드를 줄이고, 서로 다른 반복의 독립성을 드러내 ILP를 더 잘 보이게 합니다.

for (i = 0; i < n; i += 4) {
  y[i]   = a * x[i]   + y[i];
  y[i+1] = a * x[i+1] + y[i+1];
  y[i+2] = a * x[i+2] + y[i+2];
  y[i+3] = a * x[i+3] + y[i+3];
}

하지만 컴파일러는 실행 시점의 캐시 미스, 실제 분기 방향, 동적 의존성을 모두 알 수 없습니다. 그래서 고성능 프로세서는 실행 중에도 계속 재배치합니다. 프로그램 순서는 계약서이고, 내부 실행 순서는 작업반장 마음입니다. 단, 퇴근 보고서는 반드시 계약서 순서대로 올라가야 합니다.

동적 스케줄링

동적 스케줄링은 준비된 명령어부터 먼저 실행하는 방식입니다. 앞 명령어가 캐시 미스로 오래 기다리더라도, 그 결과와 상관없는 뒤 명령어가 있다면 놀리지 않습니다. 이를 위해 프로세서는 명령어를 발행하고, 피연산자가 준비될 때까지 대기시키고, 실행 유닛이 비면 내보내는 작은 교통 관제소를 둡니다.

여기서 중요한 구분은 in-order issue, out-of-order execution, in-order commit입니다. 앞에서 받아들이고, 중간에서는 순서를 바꿔 실행하되, 바깥에서 보이는 완료는 원래 순서대로 맞추는 구조가 현대 OOO 코어의 기본 감각입니다.

Tomasulo와 레지스터 리네이밍

Tomasulo 알고리즘의 핵심은 피연산자를 레지스터 이름으로만 추적하지 않고, “누가 이 값을 만들어 줄 예정인가”라는 태그로 추적하는 것입니다. 명령어는 예약 스테이션(reservation station)에 들어가고, 필요한 값이 도착하면 태그가 실제 값으로 바뀝니다. 준비가 끝난 명령어는 실행 유닛으로 나갑니다.

이 과정에서 레지스터 리네이밍이 매우 중요합니다. 프로그램에는 같은 레지스터 이름이 반복해서 등장하지만, 그중 상당수는 이름만 같은 서로 다른 값입니다. 이름 때문에 생기는 가짜 의존성(WAR, WAW)을 없애면 더 많은 명령어를 동시에 움직일 수 있습니다.

F2 = F0 + F4
F2 = F6 * F8
F10 = F2 - F12

위 코드에서 첫 번째와 두 번째 명령어는 둘 다 F2에 씁니다. 물리 레지스터를 따로 배정하면 두 결과는 서로 다른 이름표를 달 수 있습니다. 세 번째 명령어가 어떤 F2를 읽어야 하는지만 정확히 연결하면 됩니다. 이름 충돌을 없애는 순간, 하드웨어의 어깨가 조금 내려갑니다.

Reorder buffer와 정확한 예외

순서를 마음껏 바꿔 실행하면 성능은 좋아지지만, 예외와 인터럽트가 난 순간이 골치 아픕니다. 뒤 명령어가 먼저 결과를 써버린 뒤 앞 명령어에서 페이지 폴트가 나면, 운영체제는 “방금 어디까지 실행된 건데요?”라고 물을 수밖에 없습니다. 이 질문에 깔끔히 답하기 위해 reorder buffer(ROB)가 등장합니다.

ROB는 명령어의 결과를 임시로 붙잡아 두었다가, 프로그램 순서상 앞선 명령어들이 모두 문제없이 끝났을 때만 건축물 준공 승인처럼 커밋합니다. 그래서 내부에서는 뒤죽박죽 실행되더라도 외부에서 보면 순서대로 한 줄씩 실행된 것처럼 보입니다. 이것이 정확한 예외(precise exception)의 바탕입니다.

분기 예측

파이프라인이 깊고 명령어 창이 넓을수록 분기는 더 무섭습니다. 다음 PC를 모르면 앞단이 멈추고, 잘못 짚으면 이미 가져온 명령어들을 버려야 합니다. 그래서 프로세서는 분기가 어디로 갈지 예측합니다. 반복문 뒤로 돌아가는 분기는 대체로 taken, 에러 처리 분기는 대체로 not taken 같은 단순 규칙에서 출발해, 실행 이력을 저장하는 동적 예측기로 발전했습니다.

prediction accuracy = correct predictions / total branches
misprediction cost  = flushed work + lost fetch bandwidth

좋은 예측기는 방향뿐 아니라 목적지 주소도 빨리 알아야 합니다. 방향을 맞혔는데 목적지를 늦게 알면 프런트엔드는 여전히 허공을 봅니다. 분기 대상 버퍼(BTB), 반환 주소 스택, 전역/지역 이력 기반 예측은 모두 이 빈칸을 줄이기 위한 장치입니다.

추측 실행

분기를 예측했다면 그 길로 실제 실행까지 밀고 나갈 수 있습니다. 이것이 추측 실행입니다. 맞으면 시간을 벌고, 틀리면 ROB와 체크포인트를 이용해 흔적을 지웁니다. 말하자면 하드웨어가 “일단 해보고 아니면 접자”를 나노초 단위로 반복하는 셈입니다.

추측 실행은 ILP를 크게 늘리지만, 보안과 전력 측면의 비용도 남깁니다. 잘못된 경로의 결과는 커밋되지 않아야 하지만, 캐시나 예측기 같은 미세한 상태에는 흔적이 남을 수 있습니다. 성능을 위해 미래를 미리 살아봤더니, 발자국 관리가 새 숙제가 된 셈입니다.

ILP의 한계

ILP는 강력하지만 무한하지 않습니다. 프로그램에는 진짜 데이터 의존성이 있고, 메모리 주소는 늦게 밝혀지며, 분기는 완벽히 예측되지 않습니다. 명령어 창을 키우면 더 멀리 볼 수 있지만, 비교해야 할 태그와 전력도 같이 커집니다. 폭을 넓히면 한 사이클에 더 많이 발행할 수 있지만, 실행 유닛과 포트와 바이패스 네트워크가 복잡해집니다.