슈퍼스칼라와 비순차 실행
슈퍼스칼라와 비순차 실행¶
개요¶
현대 고성능 프로세서는 단순히 클럭 속도를 높이는 것만으로는 성능 향상에 한계가 있습니다. 슈퍼스칼라(Superscalar)와 비순차 실행(Out-of-Order Execution)은 명령어 수준 병렬성(ILP)을 활용하여 한 사이클에 여러 명령어를 동시에 실행하는 기술입니다. 이 레슨에서는 ILP의 개념, 슈퍼스칼라 아키텍처, 비순차 실행의 원리와 구현 방법을 학습합니다.
난이도: ⭐⭐⭐⭐
선수 지식: 파이프라이닝, 분기 예측, CPU 구조 기초
목차¶
- 명령어 수준 병렬성 (ILP)
- 슈퍼스칼라 프로세서
- 비순차 실행의 필요성
- 레지스터 리네이밍
- Tomasulo 알고리즘
- Reorder Buffer (ROB)
- 현대 프로세서의 실제 구현
- 연습 문제
1. 명령어 수준 병렬성 (ILP)¶
1.1 ILP의 개념¶
명령어 수준 병렬성(Instruction-Level Parallelism, ILP)은 프로그램 내에서 동시에 실행 가능한 명령어들의 잠재적 병렬성을 의미합니다.
순차 실행 vs 병렬 실행:
순차 실행:
시간 →
t1 t2 t3 t4 t5 t6
├─────┼─────┼─────┼─────┼─────┼─────┤
│ I1 │ I2 │ I3 │ I4 │ I5 │ I6 │
└─────┴─────┴─────┴─────┴─────┴─────┘
총 6사이클
병렬 실행 (ILP = 2):
시간 →
t1 t2 t3
├─────┼─────┼─────┤
│ I1 │ I3 │ I5 │
│ I2 │ I4 │ I6 │
└─────┴─────┴─────┘
총 3사이클
1.2 데이터 의존성 (Data Dependence)¶
ILP를 제한하는 가장 중요한 요소는 데이터 의존성입니다.
RAW (Read After Write) - 진정한 의존성¶
I1: ADD R1, R2, R3 ; R1 = R2 + R3
I2: SUB R4, R1, R5 ; R4 = R1 - R5 (R1 사용, I1 결과 필요)
I1 ────────→ I2
R1 의존성
I2는 I1이 R1에 쓴 후에만 실행 가능
WAR (Write After Read) - 반의존성¶
I1: ADD R1, R2, R3 ; R2 읽기
I2: SUB R2, R4, R5 ; R2 쓰기 (I1이 R2를 읽은 후에 써야 함)
I1이 R2를 읽기 전에 I2가 R2를 덮어쓰면 안 됨
→ 레지스터 리네이밍으로 해결 가능
WAW (Write After Write) - 출력 의존성¶
I1: ADD R1, R2, R3 ; R1 쓰기
I2: SUB R1, R4, R5 ; R1 쓰기 (같은 레지스터에 쓰기)
I2가 I1보다 먼저 완료되면 최종 R1 값이 틀려짐
→ 레지스터 리네이밍으로 해결 가능
1.3 의존성 그래프¶
프로그램:
I1: LD R1, 0(R10) ; 메모리에서 로드
I2: ADD R2, R1, R3 ; RAW on R1
I3: LD R4, 8(R10) ; 독립적
I4: MUL R5, R4, R6 ; RAW on R4
I5: ADD R7, R2, R5 ; RAW on R2, R5
I6: ST R7, 16(R10) ; RAW on R7
의존성 그래프:
I1 I3
│ │
▼ ▼
I2 I4
│ │
└─────┬─────┘
│
▼
I5
│
▼
I6
병렬 실행 가능한 그룹:
- 레벨 1: I1, I3 (동시 실행 가능)
- 레벨 2: I2, I4 (동시 실행 가능)
- 레벨 3: I5
- 레벨 4: I6
최소 실행 시간: 4 레벨 (4사이클) vs 순차 실행: 6사이클
ILP = 6/4 = 1.5
1.4 제어 의존성¶
BEQ R1, R2, LABEL ; 분기 명령어
ADD R3, R4, R5 ; 분기 안 취할 때 실행
...
LABEL:
SUB R6, R7, R8 ; 분기 취할 때 실행
분기 결과가 나오기 전에는 어떤 명령어를 실행할지 모름
→ 분기 예측으로 해결
2. 슈퍼스칼라 프로세서¶
2.1 슈퍼스칼라의 개념¶
슈퍼스칼라 프로세서는 매 사이클마다 여러 개의 명령어를 페치, 디코드, 실행할 수 있는 프로세서입니다.
스칼라 vs 슈퍼스칼라:
스칼라 파이프라인 (IPC ≤ 1):
┌─────┬─────┬─────┬─────┬─────┐
│ IF │ ID │ EX │ MEM │ WB │ I1
└─────┴─────┴─────┴─────┴─────┘
┌─────┬─────┬─────┬─────┬─────┐
│ IF │ ID │ EX │ MEM │ WB │ I2
└─────┴─────┴─────┴─────┴─────┘
2-way 슈퍼스칼라 (IPC ≤ 2):
┌─────┬─────┬─────┬─────┬─────┐
│ IF │ ID │ EX │ MEM │ WB │ I1
├─────┼─────┼─────┼─────┼─────┤
│ IF │ ID │ EX │ MEM │ WB │ I2
└─────┴─────┴─────┴─────┴─────┘
┌─────┬─────┬─────┬─────┬─────┐
│ IF │ ID │ EX │ MEM │ WB │ I3
├─────┼─────┼─────┼─────┼─────┤
│ IF │ ID │ EX │ MEM │ WB │ I4
└─────┴─────┴─────┴─────┴─────┘
2.2 슈퍼스칼라 구조¶
┌─────────────────────────────────────────────────────────────────┐
│ 4-way 슈퍼스칼라 프로세서 │
├─────────────────────────────────────────────────────────────────┤
│ ┌──────────────────────────────────────────────────────────┐ │
│ │ Instruction Fetch Unit │ │
│ │ ┌──────────┐ ┌──────────────────────────────────┐ │ │
│ │ │ PC │───→│ Instruction Cache (I-Cache) │ │ │
│ │ └──────────┘ └──────────────────────────────────┘ │ │
│ │ │ │ │
│ │ 4개 명령어/사이클 │ │
│ └──────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌──────────────────────────────────────────────────────────┐ │
│ │ Instruction Decode Unit │ │
│ │ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ │
│ │ │Decoder1│ │Decoder2│ │Decoder3│ │Decoder4│ │ │
│ │ └────────┘ └────────┘ └────────┘ └────────┘ │ │
│ └──────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌──────────────────────────────────────────────────────────┐ │
│ │ Issue Unit │ │
│ │ (의존성 검사 및 실행 유닛 할당) │ │
│ └──────────────────────────────────────────────────────────┘ │
│ │ │
│ ┌───────────┬──────────┼──────────┬───────────┐ │
│ ▼ ▼ ▼ ▼ ▼ │
│ ┌──────────┐┌──────────┐┌──────────┐┌──────────┐┌──────────┐ │
│ │ ALU 1 ││ ALU 2 ││ FPU ││ Load ││ Store │ │
│ │ ││ ││ ││ Unit ││ Unit │ │
│ └──────────┘└──────────┘└──────────┘└──────────┘└──────────┘ │
│ │ │ │ │ │ │
│ └───────────┴──────────┴──────────┴───────────┘ │
│ │ │
│ ▼ │
│ ┌──────────────────────────────────────────────────────────┐ │
│ │ Write-back / Commit │ │
│ └──────────────────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────────────────┘
2.3 Issue 정책¶
In-Order Issue¶
명령어가 프로그램 순서대로 실행 유닛에 발행됨
프로그램:
I1: ADD R1, R2, R3
I2: MUL R4, R1, R5 ; I1 의존 (stall)
I3: SUB R6, R7, R8 ; 독립적이지만 I2 뒤에 대기
시간 흐름:
사이클 1: Issue I1
사이클 2: I1 실행 중, I2 대기 (RAW hazard)
사이클 3: Issue I2 (I1 완료 후)
사이클 4: Issue I3
문제: I3는 독립적인데 I2 때문에 지연
Out-of-Order Issue¶
의존성이 없는 명령어는 순서에 관계없이 발행
프로그램:
I1: ADD R1, R2, R3
I2: MUL R4, R1, R5 ; I1 의존
I3: SUB R6, R7, R8 ; 독립적
시간 흐름:
사이클 1: Issue I1, I3 (동시 발행)
사이클 2: I1 완료, Issue I2
사이클 3: I2 실행
성능 향상: I3가 I2를 기다리지 않음
2.4 실행 유닛의 다양화¶
현대 프로세서의 실행 유닛 예시:
┌─────────────────────────────────────────────────┐
│ Execution Units (Intel Core) │
├────────────────┬────────────────────────────────┤
│ Port 0 │ ALU, FP MUL, FP DIV, Branch │
├────────────────┼────────────────────────────────┤
│ Port 1 │ ALU, FP ADD, LEA │
├────────────────┼────────────────────────────────┤
│ Port 2 │ Load (Address Gen) │
├────────────────┼────────────────────────────────┤
│ Port 3 │ Load (Address Gen) │
├────────────────┼────────────────────────────────┤
│ Port 4 │ Store Data │
├────────────────┼────────────────────────────────┤
│ Port 5 │ ALU, Vector Shuffle, Branch │
├────────────────┼────────────────────────────────┤
│ Port 6 │ ALU, Branch │
├────────────────┼────────────────────────────────┤
│ Port 7 │ Store (Address Gen) │
└────────────────┴────────────────────────────────┘
총: 8개 포트, 사이클당 최대 8개 마이크로 연산 실행 가능
3. 비순차 실행의 필요성¶
3.1 순차 실행의 한계¶
프로그램:
I1: LD R1, 0(R10) ; 캐시 미스 - 100 사이클 소요
I2: ADD R2, R1, R3 ; I1 의존
I3: LD R4, 8(R10) ; 독립적 - 캐시 히트 4 사이클
I4: MUL R5, R4, R6 ; I3 의존
I5: ADD R7, R8, R9 ; 완전히 독립적
순차 실행 (In-Order):
사이클 1-100: I1 실행 (캐시 미스 대기)
사이클 101: I2 실행
사이클 102-105: I3 실행
사이클 106: I4 실행
사이클 107: I5 실행
총: 107 사이클
비순차 실행 (Out-of-Order):
사이클 1: I1 시작 (캐시 미스)
사이클 2-5: I3 실행 (I1과 병렬)
사이클 6: I4 실행
사이클 7: I5 실행
...
사이클 100: I1 완료
사이클 101: I2 실행
총: 101 사이클
성능 향상: 107/101 = 1.06x (단순 예시)
실제로는 더 큰 차이 발생
3.2 OoO 실행의 3단계¶
┌─────────────────────────────────────────────────────────────┐
│ Out-of-Order Execution Pipeline │
├─────────────────────────────────────────────────────────────┤
│ │
│ In-Order Out-of-Order In-Order │
│ Front-end Execution Back-end │
│ │
│ ┌─────────┐ ┌─────────────┐ ┌─────────────┐ │
│ │ Fetch │ │ Issue/ │ │ Commit/ │ │
│ │ Decode │───→│ Execute │───→│ Retire │ │
│ │ Rename │ │ (비순차) │ │ (순차) │ │
│ └─────────┘ └─────────────┘ └─────────────┘ │
│ │
│ 프로그램 순서 데이터 흐름 순서 프로그램 순서 │
│ │
└─────────────────────────────────────────────────────────────┘
1단계: Front-end (In-Order)
- 명령어 페치, 디코드
- 레지스터 리네이밍
- 명령어를 Issue Queue에 삽입
2단계: Execution (Out-of-Order)
- 피연산자가 준비된 명령어부터 실행
- 데이터 의존성에 따라 실행 순서 결정
- 여러 실행 유닛에서 병렬 실행
3단계: Back-end (In-Order)
- 프로그램 순서대로 결과 커밋
- 정확한 예외 처리 보장
- 아키텍처 레지스터 갱신
4. 레지스터 리네이밍¶
4.1 리네이밍의 필요성¶
프로그램:
I1: ADD R1, R2, R3 ; R1 쓰기
I2: MUL R4, R1, R5 ; R1 읽기 (RAW)
I3: ADD R1, R6, R7 ; R1 쓰기 (WAW with I1)
I4: SUB R8, R1, R9 ; R1 읽기 (RAW with I3)
문제:
- I3는 I1, I2와 독립적으로 실행 가능해야 함
- 하지만 R1을 공유하므로 WAW 의존성 발생
- I3가 I1보다 먼저 완료되면 I2가 잘못된 값 읽음
4.2 리네이밍 동작¶
Architectural Registers: R1-R8 (프로그래머가 보는 레지스터)
Physical Registers: P1-P64 (실제 하드웨어 레지스터)
리네이밍 전:
I1: ADD R1, R2, R3
I2: MUL R4, R1, R5
I3: ADD R1, R6, R7
I4: SUB R8, R1, R9
리네이밍 후:
I1: ADD P10, P2, P3 ; R1 → P10
I2: MUL P11, P10, P5 ; R4 → P11, R1 → P10
I3: ADD P12, P6, P7 ; R1 → P12 (새로운 물리 레지스터!)
I4: SUB P13, P12, P9 ; R8 → P13, R1 → P12
결과:
- I1과 I3의 WAW 의존성 제거 (다른 물리 레지스터 사용)
- I2는 P10 읽음 (I1의 결과)
- I4는 P12 읽음 (I3의 결과)
- I1과 I3는 병렬 실행 가능!
4.3 Register Alias Table (RAT)¶
┌─────────────────────────────────────────────────────────┐
│ Register Alias Table (RAT) │
├─────────────────────────────────────────────────────────┤
│ Architectural Reg │ Physical Reg │ Valid │
├─────────────────────┼────────────────┼──────────────────┤
│ R0 │ P0 │ 1 │
│ R1 │ P12 │ 0 (pending) │
│ R2 │ P2 │ 1 │
│ R3 │ P3 │ 1 │
│ R4 │ P11 │ 0 (pending) │
│ R5 │ P5 │ 1 │
│ R6 │ P6 │ 1 │
│ R7 │ P7 │ 1 │
│ R8 │ P13 │ 0 (pending) │
│ ... │ ... │ ... │
└─────────────────────┴────────────────┴──────────────────┘
Free List: P14, P15, P16, ... (사용 가능한 물리 레지스터)
4.4 리네이밍 알고리즘¶
리네이밍 과정 (명령어: ADD Rd, Rs1, Rs2):
1. 소스 레지스터 리네이밍:
- RAT에서 Rs1, Rs2에 대응하는 물리 레지스터 조회
2. 목적지 레지스터 리네이밍:
- Free List에서 새로운 물리 레지스터 할당
- RAT에서 Rd의 매핑을 새 물리 레지스터로 갱신
3. 의존성 정보 기록:
- 소스 물리 레지스터가 아직 생성 중인지 확인
- 생산자 명령어에 대한 링크 설정
예시:
명령어: ADD R1, R2, R3
Before:
RAT[R1] = P5, RAT[R2] = P2, RAT[R3] = P3
Free List: P10, P11, P12, ...
리네이밍:
1. Rs1(R2) → P2, Rs2(R3) → P3
2. Rd(R1) → P10 (새 할당)
3. RAT[R1] = P10
After:
RAT[R1] = P10, RAT[R2] = P2, RAT[R3] = P3
Free List: P11, P12, ...
리네이밍된 명령어: ADD P10, P2, P3
5. Tomasulo 알고리즘¶
5.1 배경¶
1967년 IBM 360/91의 부동소수점 유닛을 위해 Robert Tomasulo가 개발한 알고리즘입니다. 현대 비순차 실행 프로세서의 기초가 됩니다.
5.2 핵심 구성 요소¶
┌─────────────────────────────────────────────────────────────────┐
│ Tomasulo Architecture │
├─────────────────────────────────────────────────────────────────┤
│ │
│ ┌──────────────────────────────────────────────────────────┐ │
│ │ Instruction Queue │ │
│ └──────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌──────────────────────────────────────────────────────────┐ │
│ │ Issue Logic │ │
│ │ (Reservation Station 할당) │ │
│ └──────────────────────────────────────────────────────────┘ │
│ │ │
│ ┌─────────────────┴─────────────────┐ │
│ ▼ ▼ │
│ ┌──────────────────────┐ ┌──────────────────────┐ │
│ │ Reservation Stations │ │ Reservation Stations│ │
│ │ (Add/Sub) │ │ (Mul/Div) │ │
│ ├──────────────────────┤ ├──────────────────────┤ │
│ │ RS1: Op Vj Vk Qj Qk │ │ RS4: Op Vj Vk Qj Qk │ │
│ │ RS2: Op Vj Vk Qj Qk │ │ RS5: Op Vj Vk Qj Qk │ │
│ │ RS3: Op Vj Vk Qj Qk │ │ RS6: Op Vj Vk Qj Qk │ │
│ └──────────┬───────────┘ └──────────┬───────────┘ │
│ │ │ │
│ ▼ ▼ │
│ ┌──────────────────────┐ ┌──────────────────────┐ │
│ │ FP Adder │ │ FP Multiplier │ │
│ │ (2 cycles) │ │ (10 cycles) │ │
│ └──────────┬───────────┘ └──────────┬───────────┘ │
│ │ │ │
│ └─────────────────┬────────────────┘ │
│ │ │
│ ▼ │
│ ┌──────────────────────────────────────────────────────────┐ │
│ │ Common Data Bus (CDB) │ │
│ │ (결과 브로드캐스트) │ │
│ └──────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌──────────────────────────────────────────────────────────┐ │
│ │ Register File │ │
│ └──────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────┘
5.3 Reservation Station 구조¶
┌─────────────────────────────────────────────────────────────┐
│ Reservation Station Entry │
├──────┬──────┬──────┬──────┬──────┬──────┬──────┬───────────┤
│ Busy │ Op │ Vj │ Vk │ Qj │ Qk │ A │ Dest │
├──────┼──────┼──────┼──────┼──────┼──────┼──────┼───────────┤
│ 1 │ ADD │ 3.5 │ - │ - │ RS4 │ - │ F2 │
└──────┴──────┴──────┴──────┴──────┴──────┴──────┴───────────┘
필드 설명:
- Busy: 엔트리 사용 중 여부
- Op: 수행할 연산
- Vj, Vk: 소스 피연산자 값 (이미 사용 가능한 경우)
- Qj, Qk: 값을 생산할 Reservation Station (아직 준비 안 된 경우)
- A: 메모리 주소 (Load/Store용)
- Dest: 결과가 저장될 레지스터
5.4 동작 과정¶
3단계 처리:
1. Issue (발행)
- Instruction Queue에서 명령어 가져옴
- 적절한 Reservation Station 할당
- 피연산자 값 또는 생산자 RS 태그 기록
2. Execute (실행)
- 모든 피연산자가 준비되면 실행 시작
- Qj = 0 AND Qk = 0 일 때 실행 가능
- 실행 유닛에서 연산 수행
3. Write Result (결과 쓰기)
- CDB를 통해 결과 브로드캐스트
- 대기 중인 RS들이 결과 수신
- Register File 갱신
5.5 예제: Tomasulo 실행 추적¶
프로그램:
I1: LD F6, 34(R2)
I2: LD F2, 45(R3)
I3: MUL F0, F2, F4
I4: SUB F8, F6, F2
I5: DIV F10, F0, F6
I6: ADD F6, F8, F2
초기 상태:
F4 = 2.5 (사용 가능)
Load: 2사이클, Mul: 10사이클, Add/Sub: 2사이클, Div: 40사이클
=== 사이클 1 ===
Issue I1: LD F6, 34(R2)
Load1: Busy=1, A=34+R2, Dest=F6
Register[F6]: Qi=Load1
=== 사이클 2 ===
Issue I2: LD F2, 45(R3)
Load2: Busy=1, A=45+R3, Dest=F2
Register[F2]: Qi=Load2
Execute I1: 메모리 접근 시작
=== 사이클 3 ===
Issue I3: MUL F0, F2, F4
Mult1: Busy=1, Op=MUL, Vk=2.5, Qj=Load2, Dest=F0
Register[F0]: Qi=Mult1
Execute I2: 메모리 접근 시작
Write I1: CDB에 F6 값 브로드캐스트
Load1: Busy=0
Register[F6]: Qi=0, Value=M[34+R2]
=== 사이클 4 ===
Issue I4: SUB F8, F6, F2
Add1: Busy=1, Op=SUB, Vj=M[34+R2], Qk=Load2, Dest=F8
Write I2: CDB에 F2 값 브로드캐스트
Mult1: Vj=M[45+R3], Qj=0 (값 수신)
Add1: Vk=M[45+R3], Qk=0 (값 수신)
=== 사이클 5 ===
Issue I5: DIV F10, F0, F6
Mult2: Busy=1, Op=DIV, Vk=M[34+R2], Qj=Mult1, Dest=F10
Execute I3: MUL 시작 (Vj, Vk 준비됨)
Execute I4: SUB 시작 (Vj, Vk 준비됨)
=== 사이클 6 ===
Issue I6: ADD F6, F8, F2
Add2: Busy=1, Op=ADD, Vk=M[45+R3], Qj=Add1, Dest=F6
Register[F6]: Qi=Add2
=== 사이클 7 ===
Write I4: CDB에 F8 값 브로드캐스트
Add2: Vj=(F6-F2), Qj=0 (값 수신)
=== 사이클 8 ===
Execute I6: ADD 시작
... (계속)
=== 사이클 15 ===
Write I3: MUL 완료 (사이클 5+10)
Mult2: Vj=(F2*F4), Qj=0 (값 수신)
=== 사이클 16 ===
Execute I5: DIV 시작
=== 사이클 56 ===
Write I5: DIV 완료 (사이클 16+40)
6. Reorder Buffer (ROB)¶
6.1 ROB의 필요성¶
문제: 비순차 실행 시 정확한 예외 처리 불가
예시:
I1: LD R1, 0(R2) ; 페이지 폴트 발생 가능
I2: ADD R3, R4, R5 ; I1보다 먼저 완료
만약 I2가 먼저 완료되고 I1에서 페이지 폴트:
- I2의 결과가 이미 R3에 기록됨
- 예외 처리 후 프로그램 재시작 시 상태 불일치
해결: Reorder Buffer
- 결과를 임시 저장
- 프로그램 순서대로 커밋
- 예외 시 커밋되지 않은 결과 폐기
6.2 ROB 구조¶
┌─────────────────────────────────────────────────────────────┐
│ Reorder Buffer │
├─────┬─────────┬──────────┬─────────┬────────┬──────────────┤
│Entry│ Busy │ State │ Dest │ Value │ Instruction │
├─────┼─────────┼──────────┼─────────┼────────┼──────────────┤
│ 1 │ 1 │ Commit │ F6 │ 10.5 │ LD F6,34(R2) │
│ 2 │ 1 │ Commit │ F2 │ 5.0 │ LD F2,45(R3) │
│ 3 │ 1 │ Execute │ F0 │ - │ MUL F0,F2,F4 │
│ 4 │ 1 │ Write │ F8 │ 5.5 │ SUB F8,F6,F2 │
│ 5 │ 1 │ Issue │ F10 │ - │ DIV F10,F0,F6│
│ 6 │ 1 │ Issue │ F6 │ - │ ADD F6,F8,F2 │
│ 7 │ 0 │ - │ - │ - │ - │
│ 8 │ 0 │ - │ - │ - │ - │
└─────┴─────────┴──────────┴─────────┴────────┴──────────────┘
↑ ↑
Head Tail
(Commit) (Issue)
State:
- Issue: 발행됨, 실행 대기
- Execute: 실행 중
- Write: 실행 완료, 결과 기록됨
- Commit: 커밋 준비 완료
6.3 ROB와 Tomasulo 통합¶
┌─────────────────────────────────────────────────────────────────┐
│ Modern Out-of-Order Processor │
├─────────────────────────────────────────────────────────────────┤
│ │
│ ┌────────────────────────────────────────────────────────────┐ │
│ │ Instruction Fetch/Decode │ │
│ └────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌────────────────────────────────────────────────────────────┐ │
│ │ Register Rename │ │
│ │ (RAT + Physical Register File) │ │
│ └────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌────────────────────────────────────────────────────────────┐ │
│ │ Reorder Buffer (ROB) Allocation │ │
│ │ (Entry 할당, 순서 추적) │ │
│ └────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌────────────────────────────────────────────────────────────┐ │
│ │ Issue Queue / Reservation Stations │ │
│ │ (의존성 대기, 발행 제어) │ │
│ └────────────────────────────────────────────────────────────┘ │
│ │ │
│ ┌────────────────────┼────────────────────┐ │
│ ▼ ▼ ▼ │
│ ┌────────────┐ ┌────────────┐ ┌────────────┐ │
│ │ Execution │ │ Execution │ │ Memory │ │
│ │ Unit 1 │ │ Unit 2 │ │ Unit │ │
│ └─────┬──────┘ └─────┬──────┘ └─────┬──────┘ │
│ │ │ │ │
│ └───────────────────┼───────────────────┘ │
│ │ │
│ ▼ │
│ ┌────────────────────────────────────────────────────────────┐ │
│ │ Write Back to ROB │ │
│ │ (결과를 ROB에 기록) │ │
│ └────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌────────────────────────────────────────────────────────────┐ │
│ │ Commit (In-Order) │ │
│ │ (ROB Head부터 순서대로 아키텍처 레지스터 갱신) │ │
│ └────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────┘
6.4 커밋 과정¶
Commit 규칙:
1. ROB Head의 명령어만 커밋 가능
2. 명령어가 완료 상태여야 함
3. 이전 명령어가 모두 커밋되어야 함
4. 예외가 없어야 함
예외 발생 시:
┌──────────────────────────────────────────────────┐
│ I1 │ I2 │ I3 │ I4 │ I5 │ I6 │ │
│ Done │ Done │ Done │ Exc! │ Done │ Done │ │
└──────────────────────────────────────────────────┘
↑
Head
I4에서 예외 발생:
1. I1, I2, I3 커밋 완료
2. I4에서 예외 감지
3. I5, I6 결과 폐기 (아직 커밋 안 됨)
4. I4 주소에서 예외 핸들러로 점프
5. 정확한 예외 상태 유지
6.5 분기 예측 실패 복구¶
분기 예측 실패 시 복구:
ROB 상태:
┌────────────────────────────────────────────────────┐
│ I1 │ I2 │ BR │ I4 │ I5 │ I6 │ │
│ Done │ Done │Mis-P│ Done │ Done │ Done │ │
└────────────────────────────────────────────────────┘
↑ ↑
Head 분기
BR에서 분기 예측 실패 확인:
1. I1, I2 커밋
2. BR에서 예측 실패 감지
3. I4, I5, I6 플러시 (투기적 실행 결과)
4. RAT를 BR 시점으로 복원 (체크포인트 또는 ROB 역순회)
5. 올바른 분기 대상으로 페치 재시작
복구 메커니즘:
- 체크포인트: 분기마다 RAT 스냅샷 저장
- 점진적 복구: ROB를 역순회하며 RAT 복원
7. 현대 프로세서의 실제 구현¶
7.1 Intel Core 아키텍처 (Skylake 기준)¶
┌─────────────────────────────────────────────────────────────────┐
│ Intel Skylake Microarchitecture │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Front-end (In-Order) │
│ ┌────────────────────────────────────────────────────────────┐ │
│ │ - 분기 예측: 32KB 방향 예측기, 약 4K 항목 BTB │ │
│ │ - L1 I-Cache: 32KB, 8-way │ │
│ │ - Decode: 4-wide (복잡한 명령어는 micro-op으로 분해) │ │
│ │ - Micro-op Cache: ~1.5K micro-ops │ │
│ │ - 할당: 4 micro-ops/cycle │ │
│ └────────────────────────────────────────────────────────────┘ │
│ │
│ Out-of-Order Engine │
│ ┌────────────────────────────────────────────────────────────┐ │
│ │ - ROB: 224 entries │ │
│ │ - 스케줄러: 97 entries │ │
│ │ - Physical Registers: 180 정수 + 168 벡터 │ │
│ │ - Load Buffer: 72 entries │ │
│ │ - Store Buffer: 56 entries │ │
│ └────────────────────────────────────────────────────────────┘ │
│ │
│ Execution Units (8 Ports) │
│ ┌────────────────────────────────────────────────────────────┐ │
│ │ Port 0: ALU, FMA, FP Div/Sqrt, Branch │ │
│ │ Port 1: ALU, FMA, AES │ │
│ │ Port 2: Load AGU │ │
│ │ Port 3: Load AGU │ │
│ │ Port 4: Store Data │ │
│ │ Port 5: ALU, Shuffle, Branch │ │
│ │ Port 6: ALU, Branch │ │
│ │ Port 7: Store AGU │ │
│ └────────────────────────────────────────────────────────────┘ │
│ │
│ Memory Subsystem │
│ ┌────────────────────────────────────────────────────────────┐ │
│ │ - L1 D-Cache: 32KB, 8-way, 4 cycles │ │
│ │ - L2 Cache: 256KB, 4-way, 12 cycles │ │
│ │ - L3 Cache: 2MB/core, 16-way, ~40 cycles │ │
│ └────────────────────────────────────────────────────────────┘ │
│ │
│ 성능 지표 │
│ ┌────────────────────────────────────────────────────────────┐ │
│ │ - 이론적 최대: 6 micro-ops 실행/cycle │ │
│ │ - 실제 IPC: 워크로드에 따라 2-4 │ │
│ │ - 파이프라인 깊이: 14-19 단계 │ │
│ └────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────┘
7.2 ARM Cortex-A77 아키텍처¶
┌─────────────────────────────────────────────────────────────────┐
│ ARM Cortex-A77 Microarchitecture │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Front-end │
│ ┌────────────────────────────────────────────────────────────┐ │
│ │ - Fetch: 4 instructions/cycle │ │
│ │ - Decode: 4-wide │ │
│ │ - Macro-op Cache: 1.5K entries │ │
│ │ - 분기 예측: TAGE 기반 │ │
│ └────────────────────────────────────────────────────────────┘ │
│ │
│ Out-of-Order Engine │
│ ┌────────────────────────────────────────────────────────────┐ │
│ │ - ROB: 160 entries │ │
│ │ - Dispatch: 6 micro-ops/cycle │ │
│ │ - Issue Queue: 120 entries │ │
│ └────────────────────────────────────────────────────────────┘ │
│ │
│ Execution Units (10 pipelines) │
│ ┌────────────────────────────────────────────────────────────┐ │
│ │ - 2x Branch │ │
│ │ - 3x Integer ALU │ │
│ │ - 2x Integer Multi-Cycle │ │
│ │ - 2x FP/NEON │ │
│ │ - 2x Load + 1x Store │ │
│ └────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────┘
7.3 성능 비교¶
┌──────────────────────────────────────────────────────────────────┐
│ 현대 고성능 프로세서 비교 (2024년 기준) │
├───────────────┬────────────────┬────────────────┬────────────────┤
│ 특성 │ Intel Golden │ AMD Zen 4 │ Apple M2 P-core│
│ │ Cove │ │ │
├───────────────┼────────────────┼────────────────┼────────────────┤
│ Decode Width │ 6-wide │ 4-wide │ 8-wide │
├───────────────┼────────────────┼────────────────┼────────────────┤
│ ROB Size │ 512 entry │ 320 entry │ ~600 entry │
├───────────────┼────────────────┼────────────────┼────────────────┤
│ Issue Width │ 12 ports │ 10 ports │ ~13 ports │
├───────────────┼────────────────┼────────────────┼────────────────┤
│ L1 I-Cache │ 32KB │ 32KB │ 192KB │
├───────────────┼────────────────┼────────────────┼────────────────┤
│ L1 D-Cache │ 48KB │ 32KB │ 128KB │
├───────────────┼────────────────┼────────────────┼────────────────┤
│ L2 Cache │ 1.25MB │ 1MB │ 16MB │
├───────────────┼────────────────┼────────────────┼────────────────┤
│ 실제 IPC (avg)│ ~3-4 │ ~3-4 │ ~4-5 │
└───────────────┴────────────────┴────────────────┴────────────────┘
7.4 ILP의 한계¶
ILP 활용의 제한 요소:
1. 진정한 데이터 의존성 (RAW)
- 리네이밍으로 해결 불가
- 실행 시간이 길어지면 의존 체인이 성능 결정
2. 제어 의존성
- 분기 예측 정확도 한계 (~95-97%)
- 예측 실패 시 파이프라인 플러시
3. 메모리 의존성
- Load-Store 의존성 탐지 어려움
- 메모리 명령어 재정렬 제한
4. 윈도우 크기 제한
- ROB, Issue Queue 크기 한계
- 멀리 떨어진 ILP 활용 불가
실제 프로그램의 ILP:
┌────────────────────────────────────────────────────┐
│ 프로그램 유형 │ 평균 ILP │ 제한 요소 │
├────────────────────────────────────────────────────┤
│ 정수 연산 (SPEC INT)│ 1.5-2.5 │ 의존성 체인 │
│ 부동소수점 (SPEC FP)│ 2.0-4.0 │ 메모리 대역폭 │
│ 미디어 처리 │ 3.0-6.0 │ SIMD 활용도 │
│ 데이터베이스 │ 1.0-2.0 │ 분기 예측 │
│ 웹 브라우저 │ 1.5-2.5 │ 제어 흐름 │
└────────────────────────────────────────────────────┘
8. 연습 문제¶
기초 문제¶
-
다음 데이터 의존성의 유형을 분류하시오:
assembly I1: ADD R1, R2, R3 I2: SUB R4, R1, R5 I3: MUL R1, R6, R7 I4: DIV R8, R1, R9 -
3-way 슈퍼스칼라 프로세서에서 이론적 최대 IPC는 얼마인가?
-
레지스터 리네이밍이 해결할 수 있는 의존성 유형은?
- (a) RAW
- (b) WAR
- (c) WAW
- (d) Control
중급 문제¶
-
다음 프로그램에 레지스터 리네이밍을 적용하시오:
assembly I1: ADD R1, R2, R3 I2: MUL R4, R1, R5 I3: ADD R1, R6, R7 I4: SUB R8, R1, R4(물리 레지스터 P10부터 사용) -
ROB가 필요한 이유 3가지를 설명하시오.
-
Tomasulo 알고리즘에서 CDB(Common Data Bus)의 역할은?
심화 문제¶
-
다음 상황에서 Tomasulo 알고리즘의 Reservation Station 상태를 추적하시오:
assembly I1: LD F2, 0(R1) ; 3 사이클 I2: MUL F4, F2, F0 ; 5 사이클 I3: ADD F6, F4, F2 ; 2 사이클(초기: F0 = 2.0, RS 3개 (Load1, Mult1, Add1), 사이클 1~10 추적) -
분기 예측 실패 시 ROB를 사용한 복구 과정을 설명하시오.
-
Intel Skylake의 ROB가 224 엔트리인 이유는 무엇일까요? 더 크거나 작으면 어떤 영향이 있을까요?
정답
1. 의존성 분류: - I1→I2: RAW (R1) - I1→I3: WAW (R1) - I2→I3: WAR (R1 - I2가 읽고 I3가 씀) - I3→I4: RAW (R1) 2. 3-way 슈퍼스칼라의 이론적 최대 IPC = 3 3. (b) WAR, (c) WAW - RAW는 진정한 의존성이므로 해결 불가 - Control은 분기 예측으로 해결 4. 레지스터 리네이밍: ```assembly I1: ADD P10, P2, P3 ; R1 → P10 I2: MUL P11, P10, P5 ; R4 → P11 I3: ADD P12, P6, P7 ; R1 → P12 (새 레지스터) I4: SUB P13, P12, P11 ; R8 → P13 ``` I1과 I3는 이제 병렬 실행 가능 5. ROB 필요 이유: - 정확한 예외 처리 (순서대로 커밋) - 분기 예측 실패 복구 - 정확한 인터럽트 처리 6. CDB 역할: - 실행 완료된 결과를 모든 RS에 브로드캐스트 - 대기 중인 명령어들이 피연산자 수신 - 레지스터 파일 갱신 7. Tomasulo 실행 추적: ``` 사이클 1: Issue I1 → Load1 사이클 2: Execute I1, Issue I2 → Mult1 (Qj=Load1) 사이클 3: Execute I1 계속, Issue I3 → Add1 (Qj=Mult1, Qk=Load1) 사이클 4: Write I1, Mult1: Vj 업데이트, Add1: Vk 업데이트 사이클 5: Execute I2 시작 ... 사이클 9: Write I2, Add1: Vj 업데이트 사이클 10: Execute I3 시작 사이클 11-12: Execute I3 완료 ``` 8. 분기 예측 실패 복구: - ROB에서 분기 이후 명령어들의 결과 무효화 - RAT를 분기 시점 상태로 복원 - 올바른 분기 대상으로 페치 재시작 - 파이프라인 플러시 9. ROB 크기 트레이드오프: - 더 크면: 더 많은 ILP 활용 가능, 긴 메모리 지연 허용 - 더 작으면: 면적/전력 감소, 복구 시간 단축 - 224는 메모리 지연(~100사이클)과 6-wide 발행의 균형점다음 단계¶
- 14_Memory_Hierarchy.md - 메모리 시스템의 계층 구조와 지역성 원리
참고 자료¶
- Computer Architecture: A Quantitative Approach (Hennessy & Patterson)
- Intel Optimization Manual
- WikiChip - Microarchitectures
- Agner Fog's microarchitecture
- Tomasulo, R.M. "An Efficient Algorithm for Exploiting Multiple Arithmetic Units" (1967)