arch · 13

비순차 실행

CPU파이프라인비순차실행

CPU가 명령어를 적힌 순서대로만 실행하면, 앞 명령어 하나가 오래 걸릴 때 뒤의 명령어가 모두 함께 멈춥니다. 대표적인 경우가 캐시 미스입니다. 메모리에서 데이터를 가져오는 동안 수십에서 수백 사이클이 흐르는데, 그 사이 뒤쪽에 그 데이터와 상관없는 계산이 있어도 순차 실행 CPU는 기다릴 수밖에 없습니다. 비순차 실행(Out-of-Order Execution)은 명령어 사이의 데이터 의존성을 하드웨어가 추적해, 피연산자가 준비된 명령어부터 먼저 실행합니다. 실행 순서는 뒤섞이지만 결과는 리오더 버퍼(ROB)를 거쳐 원래 프로그램 순서대로 확정되므로, 프로그램 입장에서는 순서대로 실행한 것과 똑같이 보입니다.

스마트폰부터 서버까지 오늘날 대부분의 고성능 CPU 코어가 이 방식을 씁니다. 1964년 CDC 6600의 스코어보드가 동적 스케줄링을 처음 선보였고, 1967년 IBM System/360 Model 91의 부동소수점 장치에 쓰인 토마술로 알고리즘이 하드웨어 레지스터 리네이밍을 더해 오늘날 비순차 실행의 뿌리가 됐습니다. 결과를 순서대로 확정하는 리오더 버퍼는 1985년 정밀 예외를 위해 제안됐고, 1990년대 중반 이후 범용 프로세서로 널리 퍼졌습니다. 컴파일러가 명령어 순서를 미리 바꿔 두는 정적 스케줄링과 달리, 비순차 실행은 프로그램이 돌아가는 중에 실제로 어떤 데이터가 늦게 도착하는지 보고 순서를 정하는 동적 스케줄링입니다.

핵심 개념

명령어 수준 병렬성(ILP)

서로 결과를 주고받지 않는 명령어는 동시에 실행하거나 순서를 바꿔 실행해도 결과가 같습니다. 프로그램 안에 이런 독립 명령어가 얼마나 있는지가 비순차 실행으로 얻을 수 있는 성능의 상한입니다.

핵심 개념

진짜 의존성(RAW)

앞 명령어가 쓴 레지스터를 뒤 명령어가 읽는 관계(Read After Write)입니다. 값이 만들어지기 전에는 계산할 수 없으므로 비순차 실행으로도 없앨 수 없고, 값이 나올 때까지 기다려야 합니다.

핵심 개념

가짜 의존성과 레지스터 리네이밍

WAR(Write After Read)과 WAW(Write After Write)는 값을 주고받아서가 아니라 같은 레지스터 이름을 다시 써서 생기는 충돌입니다. CPU는 프로그램의 레지스터 이름을 내부의 더 많은 물리 레지스터에 매번 새로 연결해(리네이밍) 이 충돌을 없앱니다.

핵심 개념

예약 스테이션(발행 대기열)

해독된 명령어는 실행 유닛 앞의 대기열에서 피연산자를 기다립니다. 필요한 값이 모두 준비되면 원래 순서와 상관없이 비어 있는 실행 유닛으로 발행(issue)됩니다. 교재에 따라 이 단계를 dispatch라 부르고, 대기열에 넣는 단계를 issue라 부르기도 합니다(Hennessy & Patterson의 토마술로 설명).

핵심 개념

리오더 버퍼(ROB)

명령어가 들어온 순서대로 한 칸씩 자리를 잡는 원형 버퍼입니다. 실행이 먼저 끝난 명령어도 결과를 여기에 보관한 채, 앞선 명령어가 모두 끝나기를 기다립니다.

핵심 개념

순서대로 확정과 정밀 예외

ROB 맨 앞(head)의 명령어가 완료돼야 그 결과를 레지스터와 메모리에 반영(commit, retire)합니다. 그래서 예외가 나면 그 지점 이전 명령어의 결과만 반영된 깔끔한 상태로 멈출 수 있습니다(정밀 예외).

가장 큰 이득은 메모리 지연을 숨기는 것입니다 — 캐시 미스 한 번이 수백 사이클에 이를 수 있는데, 그동안 뒤쪽의 독립 명령어와 다른 로드 명령어를 미리 처리합니다. 여러 캐시 미스를 동시에 기다리게 만드는 효과(메모리 수준 병렬성)도 큽니다.

분기 예측과 함께 동작합니다 — 분기 결과가 나오기 전에 예측한 방향의 명령어까지 미리 실행합니다(추측 실행). 예측이 틀리면 ROB에서 그 뒤의 명령어를 모두 버리면 되므로, 확정 전의 결과는 프로그램에 영향을 주지 않습니다.

의존성 사슬과 창 크기가 한계입니다 — 모든 명령어가 바로 앞 결과를 기다리는 사슬(예: 연결 리스트 따라가기)에서는 앞당길 명령어가 없습니다. 또 ROB와 대기열 크기만큼만 앞을 내다볼 수 있어, 아주 긴 캐시 미스 동안에는 창이 가득 차 결국 멈춥니다.

공짜가 아닙니다 — 의존성 추적, 리네이밍, ROB 하드웨어는 칩 면적과 전력을 많이 씁니다. 그래서 저전력 코어는 순차 실행을 유지하기도 합니다. 또 확정되지 못하고 버려진 일시적 실행(transient execution)이 캐시에 흔적을 남기는 점을 이용한 공격이 Spectre(분기 예측을 악용)와 Meltdown(권한 예외가 확정 시점까지 미뤄지는 점을 악용)입니다.

이 시각화에서 확인할 것 — "순차 vs 비순차" 탭에서 같은 명령어 5개의 총 사이클 차이를, "의존성과 발행" 탭에서 사이클마다 어떤 명령어가 준비돼 먼저 실행되는지를, "리오더 버퍼" 탭에서 실행은 뒤섞여도 확정은 순서대로 이뤄지는 과정을 STEP으로 확인하세요.

비순차 실행의 역사

비순차 실행의 핵심 아이디어는 1967년 IBM System/360 Model 91의 부동소수점 장치에서 로버트 토마술로(Robert Tomasulo)가 쓴 알고리즘에서 나온 것으로 알려져 있습니다. 순서대로 확정하는 구조(리오더 버퍼)는 스미스(Smith)와 플레스쿤(Pleszkun)이 정밀 예외(논문 용어로 precise interrupt)를 위한 여러 해법 중 하나로 다룬 연구(1985년 ISCA)로 소개됩니다. 이후 일반 프로세서의 표준 기법이 되었습니다.

숫자로 확인하기

이 시각화의 5개 명령어 — 순차 실행은 12사이클, 비순차 실행은 7사이클에 끝납니다. I1(LOAD)이 6사이클 걸리는 동안 I3(MUL, 3사이클)과 I5(ADD)가 먼저 실행되고, 발행 순서는 I1 → I3 → I5 → I4 → I2입니다.

확정은 순서대로 — 같은 예에서 확정(commit)은 I1이 사이클 7, I2와 I3이 사이클 8, I4와 I5가 사이클 9입니다. 한 사이클에 2개까지 확정하는 설정입니다. 실행 순서가 뒤섞여도 결과가 반영되는 순서는 프로그램 순서 그대로입니다.

창 크기의 한계(가정한 예) — ROB가 200개이고 한 사이클에 4개씩 처리한다고 가정하면 창이 채워지기까지 약 50사이클입니다. 메모리 지연이 300사이클이면 그 뒤로는 앞당길 명령어가 없어 멈춥니다.

자주 하는 오해

비순차 실행이면 프로그램 결과가 달라질 수 있다 — 한 스레드가 보기에는 프로그램 순서대로 실행한 것과 같은 결과를 내도록 확정이 순서대로 이뤄집니다. 달라지는 것은 내부 실행 순서입니다.

비순차 실행이면 항상 빠르다 — 모든 명령어가 앞 결과를 기다리는 의존성 사슬(연결 리스트 따라가기)에서는 앞당길 명령어가 없습니다. 이득은 독립 명령어가 있을 때 생깁니다.

다른 코어도 내 코드를 프로그램 순서로 본다 — 한 코어 안의 결과는 순서대로 보이지만 멀티스레드에서 다른 코어가 메모리 쓰기를 관찰하는 순서는 아키텍처의 메모리 모델에 달려 있습니다. 그래서 동기화나 메모리 배리어가 필요합니다.

가짜 의존성은 컴파일러가 모두 해결한다 — 컴파일러도 줄이지만 레지스터 개수가 정해져 있어서, CPU가 물리 레지스터로 이름을 바꿔 주는 리네이밍을 따로 둡니다.

면접에서 이렇게 물어요

면접 질문

비순차 실행은 어떤 문제를 푸나요?

캐시 미스 같은 긴 지연 동안 뒤에 있는 독립 명령어를 먼저 실행해 파이프라인이 멈추는 시간을 줄입니다. 의존성이 없는 명령어의 순서를 바꿔도 결과가 같다는 점을 이용합니다.

면접 질문

리오더 버퍼(ROB)는 왜 필요한가요?

실행은 뒤섞여도 결과는 프로그램 순서대로 확정해야 합니다. ROB는 실행이 끝난 결과를 보관하다 맨 앞부터 순서대로 반영해 정밀 예외와 분기 예측 실패 복구를 가능하게 합니다.

면접 질문

레지스터 리네이밍이 없으면 어떻게 되나요?

WAR와 WAW 같은 가짜 의존성 때문에 독립적인 명령어도 같은 레지스터 이름을 쓰면 순서를 지켜야 해서 병렬성이 줄어듭니다.

면접 질문

슈퍼스칼라와 비순차 실행은 같은 말인가요?

다릅니다. 슈퍼스칼라는 한 사이클에 여러 명령어를 발행하는 폭에 대한 개념이고, 비순차 실행은 발행 순서를 프로그램 순서와 다르게 하는 개념입니다. 순차 실행하는 이중 발행 코어(예: Arm Cortex-A53)도 있습니다.

실제 시스템에서는

메모리 모델 — 인텔 64 및 IA-32 개발자 매뉴얼(Vol.3A)의 Memory Ordering 절은 메모리 접근 순서에 대한 규칙(메모리 순서 모델)을 따로 정의하고, 로드와 저장이 어떤 경우에 다른 프로세서에서 다른 순서로 관찰될 수 있는지 설명합니다. 자바 언어 명세는 이를 언어 수준의 happens-before 규칙으로 감쌉니다.

추측 실행 취약점 — Spectre와 Meltdown은 확정되지 못한 추측 실행이 남긴 캐시 흔적을 이용한 공격입니다. 리눅스 커널 문서는 Spectre에 대한 완화 방법을, 별도 문서에서 Meltdown에 대한 대응(커널 페이지 테이블 격리)을 설명합니다.

캐시와의 관계 — 비순차 실행이 숨기려는 지연의 대표가 캐시 미스입니다. 캐시 메모리 토픽에서 미스가 왜 비싼지 봅니다.

함께 보면 좋은 토픽

파이프라이닝 — 비순차 실행의 바탕이 되는 파이프라인과 해저드를 봅니다.

분기 예측 — 추측 실행과 예측 실패 복구를 봅니다.

캐시 메모리 — 비순차 실행이 숨기는 메모리 지연을 봅니다.

명령어 사이클 — 한 명령어가 처리되는 기본 단계를 봅니다.

프로세스 동기화 — 메모리 순서가 동기화에서 중요한 이유를 봅니다.

참고 자료

Linux Spectre — Spectre Side Channels — The Linux Kernel documentation, Page Table Isolation (PTI) — The Linux Kernel documentation

자바 메모리 모델 — Java Language Specification — Chapter 17. Threads and Locks

원 논문 — Tomasulo, "An Efficient Algorithm for Exploiting Multiple Arithmetic Units", IBM Journal of Research and Development 11(1), 1967

논문 — Kocher 외, "Spectre Attacks: Exploiting Speculative Execution", 2018 / Lipp 외, "Meltdown: Reading Kernel Memory from User Space", USENIX Security Symposium, 2018

교재 — Hennessy, Patterson, "Computer Architecture: A Quantitative Approach", "Instruction-Level Parallelism and Its Exploitation" 장

의존성 사슬 끊기 — 누산기 나누기

// 누산기 하나: 매 덧셈이 직전 덧셈의 결과를 기다림 (하나의 긴 의존성 사슬)
double sum = 0;
for (int i = 0; i < n; i++) sum += a[i];

// 누산기 넷: 서로 독립인 사슬 4개라 덧셈 여러 개가 겹쳐 진행될 수 있음
double s0 = 0, s1 = 0, s2 = 0, s3 = 0;
int i = 0;
for (; i + 3 < n; i += 4) {
    s0 += a[i];     s1 += a[i + 1];
    s2 += a[i + 2]; s3 += a[i + 3];
}
for (; i < n; i++) s0 += a[i]; // 4로 나누어떨어지지 않는 나머지
double total = s0 + s1 + s2 + s3;

부동소수점 덧셈은 결과가 나오기까지 여러 사이클이 걸립니다. 누산기가 하나면 매 반복이 직전 덧셈을 기다려야 해서 비순차 실행이 앞당길 명령어가 없습니다. 누산기를 넷으로 나누면 독립된 사슬이 4개가 되어 덧셈이 겹쳐 진행됩니다. 단, 부동소수점은 더하는 순서에 따라 결과가 아주 조금 달라질 수 있어서 컴파일러가 이렇게 자동으로 바꾸지 않는 경우가 많습니다.

메모리 지연을 숨길 수 있는 코드와 없는 코드

// 배열: 다음 원소의 주소를 이전 로드 결과 없이 계산할 수 있음 → 여러 로드를 겹쳐 실행
long total = 0;
for (int i = 0; i < n; i++) total += values[i];

// 연결 리스트: 다음 노드 주소가 이번 로드의 결과(p.next)에 들어 있음 → 로드끼리 사슬
for (Node p = head; p != null; p = p.next) total += p.value;

배열은 i번째 주소를 계산하는 데 앞선 로드의 결과가 필요 없어서, CPU가 캐시 미스 여러 개를 동시에 기다릴 수 있습니다(하드웨어 프리페치도 잘 동작합니다). 연결 리스트는 p.next를 읽어야 다음 주소를 알 수 있으므로 캐시 미스가 하나씩 차례로 일어나고, 비순차 실행도 그 사이에 할 일을 찾지 못합니다. 같은 개수의 원소를 더해도 리스트가 크게 느려질 수 있는 이유입니다.

레지스터 리네이밍 — 가짜 의존성 없애기

// 원래 명령어: r1이라는 이름을 두 번 사용
I1: r1 ← [a]         // 캐시 미스로 오래 걸림
I2: r2 ← r1 + 1       // I1의 결과를 읽음 (진짜 의존, RAW)
I3: r1 ← r5 × r6     // r1을 다시 씀: I2가 옛 r1을 읽기 전에 덮으면 안 됨 (WAR), I1과는 WAW
I4: r7 ← r1 - r8     // I3이 쓴 새 r1을 읽음 (진짜 의존, RAW)

// 리네이밍 후: 같은 r1이라도 쓸 때마다 다른 물리 레지스터(p1, p9)를 배정
I1: p1  ← [a]
I2: p2  ← p1 + 1
I3: p9  ← p5 × p6    // 이름이 달라져 I1, I2를 기다릴 필요가 없음
I4: p10 ← p9 - p8

프로그램에서 쓸 수 있는 레지스터 이름은 몇 개 되지 않아서 같은 이름이 계속 재사용됩니다. 리네이밍이 없으면 I3은 I2가 옛 r1을 읽을 때까지 기다려야 하지만, 새 물리 레지스터 p9에 쓰면 I1의 캐시 미스와 상관없이 바로 실행할 수 있습니다. 진짜 의존성(I1 → I2, I3 → I4)은 그대로 남습니다.

비순차 실행(Out-of-Order Execution)의 핵심 아이디어는?

기다리는 동안 CPU가 놀지 않게 하려는 기법입니다.

비순차 실행은 앞 명령어가 메모리 응답 등을 기다리는 동안, 서로 의존하지 않는 뒤쪽 명령어를 먼저 실행해 실행 유닛이 노는 시간을 줄이는 기법입니다.

비순차 실행 CPU에서도 프로그램 결과가 순차 실행과 같게 보이도록 보장하는 장치는?

실행은 뒤섞여도 "완료 확정"은 순서를 지킵니다.

명령어는 순서와 상관없이 실행되더라도, 리오더 버퍼(ROB)가 결과를 원래 프로그램 순서대로 확정(commit)하기 때문에 소프트웨어에는 순차 실행처럼 보입니다. 예외 발생 시에도 정확한 지점으로 복귀할 수 있습니다.

다음 중 앞선 명령어보다 먼저 실행할 수 없는 경우는?

결과를 만들어내는 명령어가 끝나야 그 값을 쓸 수 있습니다.

앞 명령어의 결과를 읽어야 하는 명령어(RAW 데이터 의존성)는 그 결과가 나오기 전에 실행할 수 없습니다. 의존성이 없는 명령어들만 순서를 바꿔 먼저 실행할 수 있습니다.