12장. 명령어 스케줄링

파이프라인 hazard 피하기 — List 스케줄링, trace 스케줄링, software pipelining.

원서 범위: pp. 639–678 키워드: instruction scheduling, list scheduling, trace scheduling, software pipelining, dependence graph

12.1 들어가며: 같은 명령어, 다른 줄세우기

같은 코드라도 명령어를 어떤 순서로 늘어놓느냐에 따라 실행 시간이 크게 달라진다. 정수 덧셈은 한 사이클이면 끝나지만, 정수 곱셈은 세 사이클, 부동소수점 나눗셈은 12~18 사이클, 정수 나눗셈은 20~40 사이클씩 잡아먹는다. 메모리 로드(load)는 더 변덕스럽다 — 캐시 가까이에 값이 있으면 한두 사이클, 메모리 끝까지 다녀와야 하면 수백 사이클이 걸린다.

명령어 스케줄링(instruction scheduling)이란 이렇게 지연 시간이 제각각인 명령어들을 잘 줄세워서 프로세서의 함수 유닛(functional unit)들이 놀지 않도록 만드는 일이다. 입력은 부분적으로 순서가 정해진 어셈블리 명령어 목록, 출력은 같은 명령어들을 더 좋은 순서로 다시 정렬한 목록. 스케줄러는 코드를 다시 쓰지 않는다 — nop을 끼워 넣는 것 정도가 전부고, 레지스터 할당도 건드리지 않는다. 그저 비어 있는 사이클과 발행 슬롯에 명령어를 빽빽하게 끼워 넣는 게 일이다.

스톨(stall)이 뭔가? 곱셈 결과가 아직 나오지 않았는데 그걸 사용하는 명령어가 발행되면, 하드웨어가 "잠깐, 피연산자 안 익었어"라고 멈춰 세운다. 이 강제 대기를 stall이라 하고, 이걸 감지·처리하는 메커니즘을 인터록(interlock)이라 한다. 정적 스케줄(statically scheduled) 머신은 컴파일러가 nop으로 빈 칸을 채워 정확성을 보장하고, 동적 스케줄(dynamically scheduled) 머신은 하드웨어가 인터록으로 알아서 처리한다.

왜 이게 어려운가

현대 프로세서의 대부분은 한 사이클에 여러 명령어를 발행한다. 이런 슈퍼스칼라(superscalar) 프로세서는 명령어 수준 병렬성(instruction-level parallelism, ILP) — 동시에 실행 가능한 독립 연산들 — 을 뽑아내야 성능이 나온다. 정수 유닛 하나, 부동소수점 유닛 하나가 있는 머신에 정수 100개와 부동소수점 100개짜리 루프가 있다고 치자. 컴파일러가 정수 75개를 먼저 줄세우면 부동소수점 유닛은 그동안 손가락만 빨고 있다. 두 종류를 번갈아 배치해야 두 유닛이 동시에 일한다.

12.2 명령어 스케줄링 문제 정의하기

책의 1.3절에서 본 작은 예제를 다시 가져오자. 한 함수 유닛, load/store 3사이클, mult 2사이클, 나머지는 1사이클이라 가정한다.

(a) 원래 코드 — 22 사이클        (b) 스케줄된 코드 — 13 사이클
Start  Operations               Start  Operations
  1    loadAI rarp,@a => r1       1    loadAI rarp,@a => r1
  4    add    r1,r1   => r1       2    loadAI rarp,@b => r2
  5    loadAI rarp,@b => r2       3    loadAI rarp,@c => r3
  8    mult   r1,r2   => r1       4    add    r1,r1   => r1
 10    loadAI rarp,@c => r2       5    mult   r1,r2   => r1
 13    mult   r1,r2   => r1       6    loadAI rarp,@d => r2
 15    loadAI rarp,@d => r2       7    mult   r1,r3   => r1
 18    mult   r1,r2   => r1       8    mult   r1,r2   => r1
 20    storeAI r1      => rarp,@a 9    storeAI r1      => rarp,@a

스케줄된 버전은 load 세 개를 첫 세 사이클에 몰아넣었다. 이 작은 재배치만으로 22 사이클이 13 사이클로 줄었다 — 41% 단축이다. 핵심 트릭은 "오래 걸리는 명령어"와 "그 결과를 쓰는 명령어"를 떨어뜨려 놓고, 그 사이의 빈 사이클에 다른 독립 작업을 끼워 넣는 것이다.

의존 그래프(dependence graph): 스케줄링의 지도

스케줄링 문제는 블록의 의존 그래프 D = (N, E) 위에서 정의된다. 각 노드 n은 한 명령어, 각 엣지 (n1, n2)는 "n2가 n1의 결과를 사용함"을 뜻한다. 노드마다 연산 타입(operation type)과 지연(delay) 두 속성이 붙는다.

위 예제의 의존 그래프 (지연시간을 윗첨자로 붙이면)

         a¹³ — leaf, loadAI
          |
         b¹⁰         c¹²       e¹⁰     g⁸
          \         /  \      /
           \       /    \    /
            d⁹             f⁷
             \             /
              \           /
               \         /
                  h⁵
                   |
                  i³ — root, storeAI

예제에서 a, c, e, g처럼 선행 노드가 없는 노드를 잎(leaf)이라 부른다. 잎은 누구도 기다릴 필요가 없으니 가장 먼저 스케줄될 수 있다. 후행 노드가 없는 노드(여기서는 i)는 뿌리(root)다. 모든 조상이 끝나야 실행할 수 있으니 그래프상 가장 제약이 심하다. (책의 다른 트리들과 달리 그림에서는 잎을 위에, 뿌리를 아래에 그린다 — 위쪽이 먼저, 아래쪽이 나중이라 시간 흐름과 맞아 떨어진다.)

스케줄과 그 품질 측정

스케줄 S는 각 노드에 "몇 번째 사이클에 발행되는지"를 나타내는 음이 아닌 정수를 매긴다. 올바른 스케줄은 세 가지 제약을 지켜야 한다.

시작 제약: S(n) ≥ 1 (코드가 시작도 안 했는데 발행되면 곤란하다)
의존성 제약: 엣지 (n1, n2)가 있으면 S(n1) + delay(n1) ≤ S(n2) — 피연산자가 익기 전엔 못 쓴다
자원 제약: 한 사이클에 같은 종류의 명령어가 머신이 발행 가능한 수보다 많으면 안 된다

스케줄의 길이는 L(S) = max(S(n) + delay(n))이다. 시간 최적(time-optimal) 스케줄이란 같은 명령어 집합으로 만들 수 있는 가장 짧은 스케줄을 말한다.

의존 그래프에서 가장 중요한 양은 임계 경로(critical path) — 누적 지연이 가장 긴 경로 — 다. 위 예제에서는 a-b-d-f-h-i 경로가 13으로 가장 길고, 그게 곧 전체 실행 시간의 하한이다. 모든 명령어를 그것보다 빨리 끝낼 방법은 없다.

스케줄링이 못 고치는 것: a를 16번 곱하기 위해 mult를 5개 직렬로 늘어놓은 코드는, 의존 사슬이 한 줄로 길어서 스케줄러가 손쓸 게 없다. 하지만 (a²)² × (a²)² 형태로 코드 자체를 재구성하면 곱셈 두 개가 병렬로 돌 수 있다 — 이건 스케줄러의 일이 아니라 그 앞 단계 옵티마이저의 일이다.

안티의존(antidependence)과 이름 바꾸기

위 예제에서 c와 e가 모두 r2에 값을 쓰고, d는 c가 쓴 r2를 읽는다. 스케줄러가 e를 d 앞으로 옮기면 d는 잘못된 값을 읽게 된다. 이걸 안티의존이라 한다 — 데이터 흐름 때문이 아니라 이름 충돌 때문에 생기는 제약이다. 표기는 e→d.

해결책은 두 가지. 안티의존을 그대로 존중하거나, 값을 새 이름으로 다시 명명(rename)하거나. 단순한 명명 전략은 모든 정의에 새 가상 레지스터를 부여하는 것이다. 그러면 위 예제는 c는 r3로, e는 r5로 가는 식으로 충돌이 사라지고 스케줄러는 자유로워진다. 다만 명명을 늘리면 동시에 살아 있는 값이 많아져 레지스터 할당기가 스필(spill)을 더 많이 만들 수 있다 — 트레이드오프다.

왜 어렵나, 한 줄로

지역 명령어 스케줄링은 가장 단순한 아키텍처를 빼고는 모두 NP-완전이다. 그래서 실무 컴파일러는 최적해를 포기하고 탐욕 휴리스틱 — 그중에서도 list scheduling — 으로 좋은 근사해를 얻는다.

12.3 지역 List Scheduling

List scheduling은 1970년대 후반 등장한 이후 명령어 스케줄링의 사실상 표준이 되어왔다. 알고리즘 하나라기보다 방법론에 가깝다 — 우선순위 매기는 방식, 동점 처리, 진행 방향 등 변형이 무수히 많다.

네 단계 작전

안티의존 제거를 위한 이름 바꾸기: 모든 정의에 고유한 이름을 부여 (선택사항이지만 거의 필수)
의존 그래프 D 구축: 블록을 끝에서부터 거꾸로 훑으며 노드와 엣지를 만든다. 엣지에는 시작 노드의 지연시간을 라벨로 붙인다
각 노드에 우선순위 부여: 가장 흔한 방식은 그 노드에서 뿌리까지의 최장 지연 가중 경로 길이 — 즉 임계 경로 기여도
반복적으로 골라 스케줄: 첫 사이클부터 시작해 발행 가능한 후보 중 우선순위 높은 것을 고르고, 사이클을 증가시키며 반복

알고리즘의 심장: Ready-Active 두 큐 구조

Cycle  <- 1
Ready  <- D의 잎들 (선행 노드 없는 노드들)
Active <- ∅

while (Ready ∪ Active ≠ ∅)
    for each op ∈ Active
        if S(op) + delay(op) < Cycle then
            Active에서 op 제거
            for each successor s of op
                if s가 ready 이면
                    Ready에 s 추가
    if Ready ≠ ∅ then
        Ready에서 한 op 꺼내기 (우선순위 최고)
        S(op) <- Cycle
        Active에 op 추가
    Cycle <- Cycle + 1

Ready는 "지금 당장 실행 가능한 후보"들의 큐, Active는 "이미 발행되었지만 아직 안 끝난" 명령어들이다. 매 사이클마다: 끝난 명령어들을 Active에서 빼고 그 후행자를 Ready로 옮기고, Ready에서 가장 가치 있는 놈 하나 꺼내서 발행. 사이클을 1 증가. 단순한 시뮬레이션 시계 위에서 도는 탐욕 알고리즘이다.

Ready에 후보가 단 하나뿐이라면 알고리즘은 자동으로 최적이다. 둘 이상이 동시에 ready일 때 어떤 걸 먼저 고르느냐 — 거기서 우선순위 휴리스틱의 진가가 드러난다.

가변 지연시간(variable delay) 다루기

load는 캐시에 따라 1~수백 사이클로 들쭉날쭉하다. 최악을 가정하면 평소엔 프로세서가 놀고, 최선을 가정하면 캐시 미스 때 stall이 길어진다. 절충책이 균형 스케줄링(balanced scheduling)이다 — 블록 안에서 각 load 주변에 사용 가능한 독립 연산이 얼마나 있는지 보고, 그 만큼을 load의 가상 지연시간으로 잡는다. 가용한 ILP를 모든 load에 골고루 나눠 분산시켜 캐시 미스의 충격을 흡수하는 전략이다.

우선순위 깨기 — 동점 휴리스틱

List scheduling의 품질은 결국 동점일 때 누구를 먼저 뽑느냐에 좌우된다. 흔히 쓰이는 보조 우선순위들이다.

직속 후행자 수: 후행자가 많은 노드를 먼저 → 그래프를 폭우선으로 펼쳐 Ready 큐를 두텁게 유지
전체 후손 수: 더 많은 노드의 임계값에 영향 주는 노드를 먼저
delay 값: 오래 걸리는 명령어를 먼저 발행 → 그 지연을 가릴 시간이 더 많음
마지막 사용 횟수: 어떤 값의 마지막 사용인 노드를 우선 → 정의와 가까이 붙어 레지스터 압박 감소

안타깝게도 어느 한 우선순위도 늘 이기진 못한다. 어떤 코드엔 A가 좋고 어떤 코드엔 B가 좋다. 그래서 똑똑한 컴파일러는 여러 조합을 돌려보고 가장 짧은 결과를 채택하기도 한다.

전방향 vs 후방향 스케줄링

위 알고리즘은 잎에서 뿌리로 — 코드 시작에서 끝으로 — 전방향(forward) 진행한다. 거꾸로 뿌리에서 잎으로 가는 후방향(backward) 변형도 있다. 마지막 발행되는 명령어부터 거꾸로 채워 나가는 식.

실무 사례 하나 — SPEC95의 go 벤치마크에 나오는 블록을 보자. 이 블록은 store 다섯 개가 시간을 먹는데, 임계 명령어들이 뿌리 근처에 몰려 있다. 전방향 스케줄러는 잎부터 시작해 store들에 도착할 즈음엔 결정의 폭이 좁아진 상태다. 결과는 13 사이클. 반면 후방향 스케줄러는 store와 cbr부터 배치하기 시작하니 임계부를 함께 보고 결정한다 — 결과는 12 사이클로 한 사이클 절약. 임계가 어느 쪽에 몰렸느냐가 방향 선택을 좌우한다. 그래서 많은 컴파일러가 두 방향 모두 돌려보고 더 짧은 쪽을 채택한다.

비순서 실행(out-of-order)이면 스케줄링 안 해도 되는 거 아냐? OoO 프로세서는 런타임에 의존 그래프 일부를 직접 만들고, 가능한 명령어를 일찍 발행한다. 하지만 들여다보는 창(lookahead window)이 50~100 명령어 정도로 유한하다. 그 창보다 길게 정수 100개 + 부동소수점 100개를 한 덩어리씩 나란히 놓아둔 코드는 OoO도 풀어내지 못한다. 결국 OoO는 좋은 스케줄을 더 좋게 만들지, 나쁜 스케줄을 좋게 바꾸지는 못한다.

효율 향상

Ready를 단순 리스트로 두면 매번 선형 검색이라 O(n²)가 든다. 우선순위 큐(힙)로 바꾸면 O(n log n). Active도 비슷하게 우선순위 큐로 바꾸면 "이번 사이클에 끝나는 놈"을 빠르게 뽑아낼 수 있다. 더 적극적으로는 WorkList[]를 cycle mod MaxLatency 인덱스로 두는 순환 버퍼를 써서, 사이클별로 끝나는 명령어를 분리 보관하는 방법도 있다.

12.4 지역(Region) 스케줄링: 블록 너머로 시야 넓히기

한 블록 안에서만 명령어를 옮기면 ILP를 충분히 뽑아내기 어렵다. 더 큰 영역을 함께 보면 더 좋은 스케줄이 나온다. 핵심 아이디어 셋이 있다.

12.4.1 확장 기본 블록(EBB) 스케줄링

확장 기본 블록(extended basic block, EBB)이란 진입점을 하나만 가지는 블록들의 집합 B1, B2, …, Bn — 즉 B1으로만 들어올 수 있고, 나머지 Bi는 EBB 내부의 단 한 개 선행자를 갖는 구조다. EBB는 분기 없이 쭉 이어지는 "긴 직선 코드의 트리"라고 보면 된다.

      B1: a, b, c, d
       /  \
      B2   B3: g
     e,f
     /  \
    B4   B5: j, k
   h,i
    |
    B6: l

이 EBB에서 ⟨B1, B2, B4⟩는 "한 개의 긴 블록처럼" 함께 스케줄될 수 있다. 단, ⟨B1, B3⟩ 같은 다른 경로와 B1을 공유하니 이동에는 조건이 붙는다.

보상 코드(compensation code): B1의 c 명령어를 B2로 미루는 게 좋아 보인다고 하자. 그러면 ⟨B1, B3⟩ 경로에서 c가 사라진다. c가 그 경로에서도 살아 있는 값이라면, B3에 c의 복사본을 끼워넣어야 정확성을 유지할 수 있다. 반대로 B2의 f를 B1으로 당기면 ⟨B1, B3⟩ 경로에 안 쓰던 f가 끼게 되어 부수효과가 있을 경우 이를 되돌리는 보상 코드를 B3에 넣어야 한다.

실무에선 자주 실행되는 경로(hot path)를 먼저 스케줄링하고, 거기서 발생한 보상 코드는 덜 자주 실행되는 경로에 떠넘긴다 — profile 정보를 활용한 절충이다.

12.4.2 Trace 스케줄링

EBB는 단일 진입을 요구하지만, trace는 그 제약을 풀고 CFG를 가로지르는 가장 자주 실행되는 비순환 경로를 통째로 잡아 스케줄링한다. profile에서 가장 무거운 엣지를 골라 시작점을 정하고, 그 엣지를 따라 가장 빈번한 출입 엣지를 따라 trace를 키워 나간다.

     B1
      \3                각 엣지의 숫자는
   7   \                실행 빈도(프로파일)
  B2 ----- B3
   5\  2\   \3
    \    \   \
    B4    B5
     \5    \5
      \    /
       B6

가장 hot한 trace: ⟨B1, B2, B4, B6⟩

이 hot trace를 한 덩어리로 list scheduling한 뒤, 다음으로 자주 실행되는 trace를 잡고 — 단, 이전에 정한 스케줄을 존중하면서 — 또 스케줄링한다. 모든 블록이 처리될 때까지 반복. 중간 진입점(trace 한가운데로 다른 곳에서 들어오는 엣지)이 있으면 EBB 때와 비슷한 보상 코드 처리가 추가로 필요하다.

EBB 스케줄링은 trace 스케줄링의 특수 케이스 — "중간 진입을 금지한 trace"라고 볼 수 있다.

12.4.3 컨텍스트를 위한 클로닝

CFG의 합류 지점(join point) — 여러 경로가 한 블록으로 합쳐지는 곳 — 은 스케줄러를 답답하게 만든다. 합류 지점에 들어가는 블록은 어느 쪽에서 왔는지 모르니 최악을 가정해야 한다. 슈퍼블록 클로닝(superblock cloning)은 이런 블록을 복제해 합류를 없애 버린다.

클로닝 전:                     클로닝 후:
     B1                           B1
    /  \                         /  \
   B2   B3                      B2   B3
   |     |                      |     |
   B4   B5                      B4   B5  B5'  ← 복사
    \   /                        \   |   /
     B6                           B6  B6' B6''  ← 두 번 복사

이렇게 하면 ⟨B1, B2, B4, B6⟩, ⟨B1, B2, B4, B6'⟩ 같은 경로가 모두 EBB가 된다. 코드 크기는 늘지만 더 긴 직선 코드가 생겨 list scheduling에 유리한 환경이 만들어진다. 꼬리 재귀(tail-recursive) 루틴에서 진입 블록을 클로닝해 스케줄러에 더 정확한 컨텍스트를 주는 패턴도 흔하다.

12.5 고급 주제: Software Pipelining

루프 안 코드는 루프 밖 코드보다 훨씬 자주 실행되니, 루프를 짧게 만드는 게 가장 효율적이다. 가장 널리 쓰이는 루프 최적화 스케줄링이 소프트웨어 파이프라이닝(software pipelining)이다.

12.5.1 비유: 반복을 비스듬히 겹쳐 돌리기

하드웨어 파이프라인이 한 명령어를 fetch / decode / execute / writeback 단계로 쪼개 동시에 처리하듯이, 소프트웨어 파이프라인은 루프 반복(iteration) 자체를 단계로 쪼개 겹쳐서 실행한다. iteration 1의 후반부가 끝나는 동안 iteration 2의 중반부가 돌고, 동시에 iteration 3의 전반부가 시작된다.

일반 루프:           파이프라인 루프:
 [Iter 1]            [Iter 1 전반]
 [Iter 1]            [Iter 1 중반 | Iter 2 전반]
 [Iter 2]            [Iter 1 후반 | Iter 2 중반 | Iter 3 전반]  ← kernel
 [Iter 2]                                                          (정상 상태)
 [Iter 3]            [Iter 2 후반 | Iter 3 중반 | Iter 4 전반]
 [Iter 3]            ...
                      비스듬히 겹쳐 흐름

이렇게 만들어진 루프는 세 부분으로 구성된다.

프롤로그(prologue): 파이프라인을 채우는 도입부 (iteration 1의 전반부, iteration 2의 시작)
커널(kernel): 정상 상태로, 한 번의 iteration씩 처리하지만 내부에서는 여러 iteration이 겹쳐 돌아감
에필로그(epilogue): 마지막에 파이프라인을 비우는 마무리

예제: for (i=1; i<200; i++) z[i] = x[i] * y[i]; 같은 단순 루프를 단일 함수 유닛 머신에 스케줄링하면 9 사이클짜리 루프 본문이 나온다. 그러나 두 함수 유닛 머신에서 단순히 list scheduling만 적용하면 6 사이클까지만 줄어든다. 소프트웨어 파이프라이닝을 적용하면 iteration당 5 사이클까지 떨어진다 — 두 iteration의 load와 다른 iteration의 mult, store가 한 사이클에 동시에 발행되도록 직조하기 때문이다.

12.5.2 알고리즘 — 세 단계

소프트웨어 파이프라이닝의 절차는 단순하다.

커널 크기(initiation interval, ii) 추정
- 자원 제약(RC) = max(⌈I_u / N_u⌉) — 타입 u의 명령어 I_u개를 함수 유닛 N_u개로 나누면 적어도 몇 사이클 필요한가
- 의존 제약(DC) = max(⌈d_r / k_r⌉) — recurrence(루프 내 사이클) r의 누적 지연 d_r를 그 사이클이 걸치는 iteration 수 k_r로 나눈 값
- 초기 ii = max(RC, DC)
커널 스케줄링: 길이 ii의 순환 시계를 가지고 list scheduling. 사이클 카운터를 ii로 나머지 연산. 슬롯이 부족하면 ii를 1 늘리고 재시도. 이 변형을 모듈로 스케줄링(modulo scheduling)이라 부른다.
프롤로그·에필로그 생성: 의존 그래프를 거슬러 위쪽으로 노출된 사용(upward exposed use)을 따라가며 프롤로그를, 아래쪽으로 노출된 사용을 따라가며 에필로그를 만든다.

한 가지 주의할 게 있다. 직선 코드의 의존 그래프와 달리 루프의 의존 그래프에는 사이클(cycle)이 있다 — 이걸 recurrence라고 한다. iteration n의 결과를 iteration n+1이 쓰는 의존(loop-carried dependence) 같은 게 그렇다. 모듈로 스케줄링은 사이클 카운터의 모듈로 연산으로 이 사이클들을 자연스럽게 다룬다.

실전 한 컷

예제 루프의 의존 그래프에서 RC = max(⌈9/2⌉, ⌈3/1⌉) = 5, DC = 1이 나오므로 ii = 5. 다섯 사이클 두 함수 유닛 커널에 모듈로 스케줄링을 적용하면 다음 같은 빽빽한 커널이 만들어진다.

Cycle  Functional Unit 0           Functional Unit 1
  1    L1: loadAO rarp.r@x => rx    addI r@x.4 => r@x
  2        loadAO rarp.r@y => ry    addI r@y.4 => r@y
  3        cmp_LT r@x.rub  => rcc   nop
  4        storeAO rz      => rarp.r@z   addI r@z.4 => r@z
  5        cbr    rcc      -> L1.L2 mult rx.ry => rz

같은 사이클에 iteration n의 store와 iteration n+1의 mult가 함께 발행된다 — 비스듬히 겹친 모습이다. 한 iteration이 진짜로는 5 사이클이 아니라 9 사이클짜리 일을 하고 있지만, 다음 iteration이 일찍 시작하므로 iteration간 거리는 5 사이클이 된다.

12.6 정리

현대 프로세서에서 그럴듯한 성능을 뽑으려면 컴파일러가 명령어를 신중히 줄세워야 한다. 거의 모든 컴파일러가 어떤 형태로든 list scheduling을 쓴다. 우선순위 휴리스틱, 동점 처리 규칙, 진행 방향만 바꿔서 같은 골격을 다양하게 변주할 수 있고, 이 알고리즘은 다양한 코드에 안정적으로 좋은 결과 — 종종 시간 최적해 — 를 낸다.

더 큰 영역으로 시야를 확장하는 변형들 — EBB 스케줄링, trace 스케줄링, 클로닝 — 은 모두 같은 list scheduling 엔진에 더 긴 코드 컨텍스트를 먹이는 작업이다. 머신이 복잡해질수록 ILP를 충분히 뽑으려면 더 큰 컨텍스트가 필요하기 때문이다.

루프에는 software pipelining이 강력한 무기다. 반복을 비스듬히 겹쳐 돌리는 이 기법은 사이클당 발행 명령어 수를 늘리고 루프 총 실행시간을 줄인다. Trace 스케줄링은 원래 VLIW 아키텍처를 위해 개발되었다 — 많은 함수 유닛을 모두 바쁘게 굴려야 하는 상황에서 컨텍스트가 절실했기 때문이다.

핵심 자료구조는 의존 그래프 한 장. 한 번 만들어 두면 우선순위 계산, 임계 경로 찾기, 보상 코드 결정까지 모두 그 위에서 돌아간다. 코드의 데이터 흐름을 한 장의 그림으로 압축한 이 그래프가 명령어 스케줄링의 알파이자 오메가다.

← 이전11장. 명령어 선택 다음 →13장. 레지스터 할당