슈퍼스칼라 & 비순차 실행

파이프라이닝만으로는 부족하다 — 한 클럭에 여러 개, 그리고 순서 무시하고 준비된 것부터

1. 복습 — 파이프라이닝의 한계

CPU 파이프라이닝 페이지에서 본 5단계 파이프라인은 IF·ID·EX·MEM·WB를 겹쳐 실행해서 이상적으로는 매 클럭 새 명령어 하나를 투입할 수 있었다. CPI(사이클당 명령어 수)가 1에 가까워지는 것이 목표였다.

그런데 여기서 질문 하나. CPI가 1이 파이프라이닝의 한계라면, 그다음은 없을까? 만약 CPU 안에 ALU가 하나가 아니라 두세 개라면? 메모리에 접근하는 유닛이 두 개라면? 서로 상관없는 명령어들을 굳이 한 클럭에 하나씩만 처리할 이유가 없지 않을까 — 라는 발상에서 슈퍼스칼라(superscalar)가 나온다. 그리고 "어차피 여러 개를 볼 수 있다면, 꼭 프로그램에 적힌 순서대로 처리해야 하나?"라는 다음 질문에서 비순차 실행(OoO)이 나온다.

2. 슈퍼스칼라(Superscalar)란

슈퍼스칼라는 CPU 내부에 실행 유닛(ALU, 곱셈기, Load/Store 유닛 등)을 여러 개 두고, 같은 클럭 사이클에 서로 의존성이 없는 명령어 여러 개를 동시에 발행(issue)하는 설계다. 한 클럭에 명령어를 몇 개까지 발행할 수 있는지를 이슈 폭(issue width)이라 부른다 (2-way, 4-way 슈퍼스칼라처럼 표현).

단, 아래 프로그램처럼 뒤 명령어가 앞 명령어의 결과(레지스터)를 필요로 하면, 그 결과가 나올 때까지는 같이 발행할 수 없다 — 이건 순서대로 발행하는 슈퍼스칼라라도 마찬가지다.

# 6개 명령어 — 화살표는 데이터 의존관계
I1  ADD  r1, r2, r3
I2  SUB  r4, r5, r6      # I1과 독립적
I3  MUL  r7, r1, r8      # r1 필요 → I1에 의존
I4  XOR  r9, r10, r11    # 독립적
I5  ADD  r12, r7, r7     # r7 필요 → I3에 의존
I6  OR   r13, r14, r15   # 독립적

3. 비순차 실행(Out-of-Order Execution)이란

슈퍼스칼라도 보통 명령어를 프로그램에 적힌 순서대로 발행하려고 한다(in-order issue). 문제는 앞 명령어가 오래 걸리는 작업으로 멈춰 있으면, 그 뒤에 있는 명령어들이 설령 지금 당장 실행할 준비가 끝났어도 순서를 지키느라 같이 멈춰버린다는 점이다. 특히 메모리 접근(LOAD)은 캐시 미스라도 나면 수십~수백 사이클이 걸릴 수 있는데, 그동안 CPU 전체가 손을 놓고 있는 건 엄청난 낭비다.

비순차 실행(OoO)은 이 문제를 뒤집는다. 명령어들을 일단 예약 스테이션(reservation station)에 쌓아두고, 프로그램 순서와 상관없이 피연산자가 준비된 명령어부터 실행 유닛에 넣는다. 다만 이렇게 뒤죽박죽 실행된 결과를 레지스터/메모리 같은 "진짜" 상태에 반영할 때는 반드시 프로그램 순서를 지켜야 한다 — 그래야 프로그램 입장에서는 마치 순서대로 실행된 것처럼 보인다(이걸 정밀 예외(precise exception) 보장이라 부른다). 이 순서를 맞춰주는 하드웨어 구조가 재정렬 버퍼(Reorder Buffer, ROB)다 — 명령어가 실행은 먼저 끝나도 ROB 안에서 자기 차례를 기다렸다가 순서대로 커밋(commit)된다.

4. 핵심 인터랙티브 — OoO 실행 시뮬레이터

다음 세 명령어를 보자. LOAD는 메모리에서 값을 가져오는 데 3사이클이 걸리는 무거운 연산이라 하자.

L1  LOAD  R1, [mem]        # 메모리 접근, 3사이클 소요
L2  ADD   R2, R1, R3       # R1 필요 → L1이 끝나야 함
L3  MUL   R4, R5, R6       # L1·L2와 완전히 독립적!

순서대로(In-Order) 실행하면 L2는 L1의 결과를 기다려야 하고, L3는 L2보다 뒤에 있다는 이유만으로 같이 멈춰 선다 — 정작 L3는 지금 당장 실행해도 아무 문제가 없는데도. 비순차(OoO) 실행에서는 L3가 먼저 실행 유닛을 차지해 L1이 메모리를 기다리는 동안 결과를 만들어 두고, L1이 끝나 R1이 준비되면 L2가 실행된다. 마지막에 재정렬 버퍼가 L1→L2→L3 순서로 결과를 커밋해 프로그램 순서를 맞춘다.

5. 세 가지 방식 비교

6. 의존성 검사 의사코드

OoO 스케줄러가 매 사이클 "이 명령어를 지금 실행 유닛에 넣어도 되는가"를 판단하는 핵심 로직이다.

// 명령어가 지금 발행(issue) 가능한지 검사
function canIssue(instr, scoreboard) {
    // scoreboard[reg] = 그 레지스터를 마지막으로 쓴 명령어가
    // 아직도 "pending"(계산 안 끝남)인지 여부
    for (reg of instr.srcRegs) {
        if (scoreboard[reg] === "pending") {
            return false;  // 값이 아직 없음 → 대기
        }
    }
    return true;  // 모든 소스 레지스터 준비 완료
}

// 매 사이클, 비어 있는 실행 유닛마다 반복
for (unit of freeExecutionUnits) {
    // 프로그램 순서 무시하고, 준비된 것 중 "가장 오래된" 것 선택
    candidate = pickOldestReady(reservationStation, canIssue);
    if (candidate) dispatch(candidate, unit);
}

// 커밋은 반드시 프로그램 순서대로 (ROB 헤드부터)
while (rob.head.status === "done") {
    commit(rob.head);  // 레지스터/메모리에 결과 확정 반영
    rob.advance();
}

7. 관련 페이지