[CS311] 7. 명령어 수준 병렬성과 멀티프로세서

KAIST CS311 전산기조직 (Spring 2023) 교재: Computer Organization and Design: The Hardware/Software Interface (Patterson & Hennessy, MIPS Edition)

ILP (Instruction-Level Parallelism)

ILP(Instruction-Level Parallelism)란 하나의 프로그램 내에서 동시에 실행할 수 있는 명령어의 평균 수를 의미한다. 다시 말해, 하나의 프로그램에 포함된 여러 명령어를 얼마나 동시에 실행할 수 있는지를 나타내는 척도이다. 가능한 한 많은 명령어를 동시에 실행(execute)하기 위한 다양한 기법들이 연구되어 왔다.

Multiple Issue

지금까지 살펴본 파이프라인 프로세서는 한 사이클에 하나의 명령어만 issue하는 Single Issue 방식이었다. Multiple Issue는 한 사이클에 여러 개의 명령어를 CPU가 issue하여 처리하도록 하는 아키텍처 설계 기법이다.

Multiple Issue는 구현 방식에 따라 크게 두 가지로 나뉜다:

Multiple Issue
├── Static Multiple-Issue (VLIW)
│     → Compiler가 Compile-Time에 병렬 명령어 결정
│     → 하드웨어가 단순
└── Dynamic Multiple-Issue (Superscalar)
      → CPU가 Run-Time에 병렬 명령어 결정
      → 하드웨어가 복잡

VLIW (Static Multiple-Issue)

VLIW(Very Long Instruction Word)는 컴파일 타임에 컴파일러가 코드를 분석하여 병렬로 실행 가능한 명령어를 찾아내는 방식이다.

Issue Packet

Issue Packet이란 한 사이클에서 함께 issue되는 명령어들의 묶음(bundle)이다. 컴파일러가 병렬로 실행해도 문제없는 명령어들을 하나의 패킷으로 묶으며, 이 패킷을 하나의 “매우 긴 명령어(Very Long Instruction Word)“로 간주할 수 있다.

2-Issue MIPS 예시

2-issue MIPS에서는 하나의 Issue Packet이 두 개의 명령어로 구성된다:

Issue Packet (64-bit)
┌──────────────────────┬──────────────────────┐
│   ALU Op / Branch    │    Load / Store       │
│      (32-bit)        │      (32-bit)         │
└──────────────────────┴──────────────────────┘

이를 지원하기 위해 하드웨어에는 다음과 같은 변경이 필요하다:

Register File의 포트 수를 2배로 확장 (동시에 두 명령어가 레지스터를 읽고 써야 하므로)
EX 스테이지에 ALU 유닛을 추가

VLIW에서의 Hazard 처리

EX Data Hazard는 Single-Issue와 동일하게 Forwarding으로 해결한다. 단, 같은 Issue Packet 내의 명령어 간에는 Forwarding이 불가능하다.

Load-Use Hazard의 경우 여전히 1 사이클 stall이 발생한다. 하지만 이제 stall 시 2개의 명령어가 함께 지연된다는 점이 다르다.

┌──────────┬──────────┬──────────┐
│  Cycle 1 │  Cycle 2 │  Cycle 3 │
├──────────┼──────────┼──────────┤
│ lw $t0,… │  stall   │          │
│ add $t1,…│  stall   │          │  ← 2개 instr이 함께 stall
│          │          │ ...      │
└──────────┴──────────┴──────────┘

Loop Unrolling

Loop Unrolling은 루프 본문을 반복 복제하여 병렬로 실행할 수 있는 명령어 수를 늘리는 최적화 기법이다. 루프를 펼치면(unroll) 루프 오버헤드(branch, counter 업데이트)가 줄어들고, 독립적인 명령어들을 하나의 Issue Packet에 묶을 기회가 늘어난다.

이때 컴파일러는 Register Renaming을 사용하여 이름 의존성(name dependency)을 해결한다. 예를 들어, 원래 루프가 같은 레지스터를 재사용하는 경우, 다른 레지스터로 바꿔 할당하면 의존성이 사라진다.

VLIW의 장단점

장점	단점
하드웨어가 단순 (Simpler Hardware)	하위 호환성 부족 (Backward Incompatibility)
잠재적으로 더 높은 확장성	프로그래머 및 컴파일러 복잡도 증가
	Code Bloat (NOP 패딩으로 코드 크기 증가)

VLIW는 하드웨어의 복잡도를 컴파일러에게 전가하는 접근법이다. 하드웨어가 단순해지는 대신, 컴파일러가 병렬 실행 가능한 명령어를 정확히 찾아내야 하므로 컴파일러의 부담이 커진다.

Superscalar (Dynamic Multiple-Issue)

Superscalar 프로세서는 **실행 시간(Run-Time)**에 CPU가 매 사이클마다 어떤 명령어를 issue할지 동적으로 결정한다. Structural Hazard와 Data Hazard를 피하면서 가능한 많은 명령어를 동시에 issue한다.

Out-of-Order Execution

Superscalar의 핵심 특징은 **비순차 실행(Out-of-Order Execution)**이다. 명령어의 실행 순서를 프로그램 순서와 다르게 재배치하여 파이프라인의 활용도를 극대화한다.

Superscalar Processor의 3 영역

Superscalar 프로세서는 크게 세 부분으로 나뉜다:

┌─────────────────────────────────────────────────────────────┐
│                    Superscalar Processor                     │
│                                                              │
│  ┌──────────────┐   ┌──────────────────┐   ┌─────────────┐  │
│  │  Front End   │──▶│ Execution Engine  │──▶│  Back End   │  │
│  │  (In-Order)  │   │  (Out-of-Order)   │   │  (In-Order) │  │
│  ├──────────────┤   ├──────────────────┤   ├─────────────┤  │
│  │ Fetch        │   │ Reservation      │   │ Commit Unit │  │
│  │ Decode       │   │   Station        │   │ (Reorder    │  │
│  │ Issue ──────▶│   │ Functional Units │   │  Buffer)    │  │
│  └──────────────┘   └──────────────────┘   └─────────────┘  │
└─────────────────────────────────────────────────────────────┘

Front End (In-Order Issue): Fetch → Decode → Issue 순서로 명령어를 가져와 Reservation Station으로 보낸다.
Execution Engine (Out-of-Order Execution): Reservation Station에서 피연산자가 준비된 명령어부터 Functional Unit에서 실행한다. 프로그램 순서와 무관하게 실행된다.
Back End (In-Order Commit): Commit Unit 내의 **Reorder Buffer (RoB)**를 사용하여 프로그램 순서대로 결과를 커밋한다. 비순차로 실행되더라도 최종 결과는 순서대로 반영된다.

Data Dependency

명령어 간의 데이터 의존성은 세 가지 유형으로 분류된다:

유형	이름	설명	프로그래머 의도?
RAW	True Data Dependency	쓰인 값을 읽어야 함	O
WAW	Output Dependency	나중 명령어의 결과가 나중에 쓰여야 함	X
WAR	Antidependency	읽은 후에 써야 함	X

**True Data Dependency (RAW)**만이 프로그래머가 의도한 진짜 의존성이다. Output Dependency(WAW)와 Antidependency(WAR)는 레지스터 수가 제한되어 같은 레지스터를 재사용하면서 발생하는 **거짓 의존성(False Dependency)**이다.

예시:
  add $t0, $s0, $s1    ─┐
  sub $t1, $t0, $s2     │  RAW: $t0 (True Dependency)
                         │
  add $t0, $s3, $s4    ─┘  WAW: $t0 (Output Dependency)
                            WAR: $t0 (Antidependency)

Register Renaming으로 Output Dependency와 Antidependency를 해결할 수 있다. 하드웨어가 내부적으로 물리 레지스터를 더 많이 가지고 있어서, 같은 이름의 아키텍처 레지스터를 서로 다른 물리 레지스터에 매핑하면 거짓 의존성이 사라진다.

Speculation

Superscalar 프로세서는 성능을 극대화하기 위해 **추측 실행(Speculation)**을 사용한다.

1. Branch Prediction

분기(Branch) 결과가 나오기 전에 예측(predict)하여 명령어를 계속 issue한다. 단, 분기 결과가 확정되기 전에는 commit하지 않는다. 예측이 틀렸다면 해당 명령어들의 결과를 폐기(flush)한다.

2. Load Speculation

sw와 lw 사이에 True Data Dependency가 존재할 수 있다. 이를 처리하기 위해:

Store-to-Load Forwarding: 아직 메모리에 쓰지 않은 store의 값을 load에게 전달
만약 이미 실행된 lw가 잘못된 데이터를 load했다면 (matching되는 sw를 뒤늦게 발견), 파이프라인을 flush하고 복구(Recover)한다

멀티프로세서 (Multiprocessor)

멀티프로세서(Multiprocessor)란 최소 2개 이상의 프로세서를 가진 컴퓨터 시스템이다. 멀티프로세서는 다양한 형태의 병렬성을 지원한다:

Thread-Level Parallelism (TLP)
Job-Level Parallelism
Process-Level Parallelism

멀티코어 프로세서 (CMP)

Multicore Processor (= Chip Multi-Processor, CMP)는 하나의 CPU 칩 내부에 여러 Core가 존재하는 프로세서를 의미한다. 하나의 마이크로프로세서(CPU chip) 안에 여러 프로세서(Core)가 있는 형태이다.

Flynn’s Taxonomy

병렬 컴퓨팅(Parallel Computing)을 분류하는 대표적인 체계이다:

Flynn's Taxonomy
┌──────────┬─────────────────────────────────────────────┐
│   SISD   │ Single Instruction, Single Data              │
│          │ → 전통적인 단일 프로세서                       │
├──────────┼─────────────────────────────────────────────┤
│   SIMD   │ Single Instruction, Multiple Data            │
│          │ → Data-Level Parallelism                      │
│          │ → Instruction Sequence는 하나지만,             │
│          │   각 instruction이 multiple data를 처리       │
├──────────┼─────────────────────────────────────────────┤
│   MIMD   │ Multiple Instruction, Multiple Data          │
│          │ → Thread-Level Parallelism                    │
│          │ → N개 프로그램 또는 1개 프로그램의 N개 Thread   │
│          │ → 많은 맥락에서 MIMD ≡ Multi-Processor        │
├──────────┼─────────────────────────────────────────────┤
│   MISD   │ Multiple Instruction, Single Data            │
│          │ → 실용적 사례 거의 없음                        │
└──────────┴─────────────────────────────────────────────┘

Communication Model

멀티프로세서에서 프로세서 간 통신 방식에 따라 두 가지 모델로 분류된다:

┌─────────────────────────────────────────────────────────┐
│           Multi-Processor Communication                  │
├───────────────────────┬─────────────────────────────────┤
│  Shared Memory Model  │    Message Passing Model         │
│  (e.g. pthread, openMP)│    (e.g. MPI)                   │
│  일상 컴퓨터용          │    슈퍼컴퓨터용                  │
├───────────────────────┼─────────────────────────────────┤
│  ┌───┐  ┌───┐        │   ┌───┐      ┌───┐              │
│  │P1 │  │P2 │        │   │P1 │─msg─▶│P2 │              │
│  └─┬─┘  └─┬─┘        │   │Mem│      │Mem│              │
│    └───┬───┘          │   └───┘      └───┘              │
│    ┌───┴───┐          │   각 프로세서가 자체 메모리 보유   │
│    │Memory │          │   메시지를 통해 데이터 교환        │
│    └───────┘          │                                  │
│  프로세서들이 메모리 공유│                                  │
└───────────────────────┴─────────────────────────────────┘

Shared Memory Multiprocessor (SMP)

메모리 구조

공유 메모리 멀티프로세서에서 메모리 접근 시간에 따라 두 가지로 나뉜다:

UMA (Uniform Memory Access): 모든 프로세서가 메모리에 동일한 시간에 접근. 일상 컴퓨터에서 사용.
NUMA (Non-Uniform Memory Access): 프로세서마다 가까운 메모리와 먼 메모리가 있어 접근 시간이 다름. Multi-Socket 시스템에서 사용.

Cache Coherence Problem

SMP에서 발생하는 핵심 문제가 바로 캐시 일관성(Cache Coherence) 문제이다.

같은 주소의 데이터가 여러 캐시에 복제되어 존재할 수 있다. 특정 프로세서가 자신의 캐시에 Write하면 이 사실을 다른 캐시에도 전파(Propagate)해야 한다.

Cache Coherence Problem:

    CPU 0         CPU 1         CPU 2
  ┌──────┐     ┌──────┐     ┌──────┐
  │Cache │     │Cache │     │Cache │
  │ X=5  │     │ X=5  │     │ X=5  │
  └──┬───┘     └──┬───┘     └──┬───┘
     └─────────┬──┴────────────┘
          ┌────┴────┐
          │ Memory  │
          │  X=5    │
          └─────────┘

  CPU 0이 X=10으로 Write → 다른 캐시는 아직 X=5!
  → 일관성(Coherence) 깨짐 → Propagate 필요

변경 사항을 전파하는 방식은 두 가지이다:

Update-based Protocol (Write Through): Write 시 해당 데이터를 가진 모든 캐시의 값을 업데이트
Invalidation-based Protocol: Write 시 다른 캐시의 해당 라인을 무효화(Invalidate)

False Sharing Problem: 서로 다른 데이터가 같은 캐시 라인에 위치하면, 한 프로세서가 자신의 데이터만 수정해도 다른 프로세서의 캐시 라인이 무효화된다. 이를 방지하려면 데이터 구조를 캐시 라인 경계에 맞춰 정렬(align)해야 한다.

Propagation 대상: Snoop vs Directory

변경 사항을 누구에게 전파할 것인가?

Snoop-based Protocol

각 캐시가 버스(bus)를 감시(snoop)하여 다른 프로세서의 Write를 감지
Extended Cache State를 사용 → MSI Protocol:
- M (Modified): 이 캐시만 최신 값을 가짐, 메모리와 불일치
- S (Shared): 여러 캐시에 동일한 값 존재, 메모리와 일치
- I (Invalid): 이 캐시 라인은 무효
Broadcast medium: UMA에서는 Bus, NUMA에서는 Point-to-Point Network
Serialization: UMA에서는 Bus, NUMA에서는 Home Node

Directory-based Protocol

중앙 디렉토리(Home Node)가 각 캐시 라인의 상태를 추적
대규모 시스템에서 Snoop-based보다 확장성이 좋음

동기화 (Synchronization)

SMP 환경에서는 상호 배제(Mutual Exclusion) 문제가 발생한다. 여러 프로세서가 공유 데이터에 안전하게 접근하기 위해서는 동기화 메커니즘이 필요하다.

해결 방법:

Software 자원: Semaphore, Monitor, Mutex
Barrier: 모든 프로세서가 특정 지점에 도달할 때까지 대기
Lock: 공유 데이터에 대한 접근을 규제하는 Low-level primitive

Lock

Lock Variable은 메모리 공간의 일부에 Lock 여부를 저장한다 (0: 비사용 / 1: 사용중). 이 메모리 공간은 모든 Thread가 공유(Shared)하는 영역이어야 한다.

acquire operation: 화장실에 가서 비었으면 들어가서 사용중으로 바꾸기, 사용중이면 확인하며 기다리기
release operation: 사용중이었던 것을 다 쓰고 나와서 비사용으로 바꾸기
Critical Section: acquire와 release 사이의 코드 영역. 하나의 프로세서만 critical section에 진입 가능

Atomic Exchange

Lock을 구현하려면 “읽기와 쓰기"가 원자적(Atomic)으로 수행되어야 한다. 그렇지 않으면 두 프로세서가 동시에 Lock이 비었다고 판단할 수 있다.

Atomic Exchange는 Register와 Memory의 값을 원자적으로 교환하는 연산이다:

Lock 변수 읽기와 사용중(1)으로 설정을 동시에 수행
읽어온 값이 0이면 Lock 획득 성공, 1이면 이미 다른 프로세서가 사용중

Load Linked / Store Conditional (LL/SC)

MIPS에서는 Atomic Exchange 대신 LL/SC 쌍을 사용한다:

ll  R2, 0(R1)    # R2에 Mem[R1] 값을 Load & 해당 address 기억
sc  R3, 0(R1)    # Store 성공하면 R3 = 1, 실패하면 R3 = 0

ll (Load Linked): 메모리에서 값을 읽으면서 해당 주소를 예약(reservation)한다.

sc (Store Conditional): 예약한 주소에 Store를 시도한다.

성공 (return 1): ll 이후 해당 주소에 다른 프로세서가 값을 쓰지 않았을 경우
실패 (return 0): ll 이후 다른 프로세서가 해당 주소에 Write했을 경우 → 값을 덮어쓰지 않고 실패 반환

sc 성공 조건:

이전에 해당 주소에 대해 ll이 실행되었는가?
ll로 값을 읽은 이후에 다른 프로세서가 해당 주소에 값을 쓰지 않았는가? (Invalid State 확인)

LL/SC를 사용한 Lock 획득 코드:

try:
    ll   R2, 0(R1)        # Lock 변수 읽기
    bnez R2, try          # 이미 사용중이면 다시 시도
    addi R2, R0, 1        # R2 = 1 (사용중 표시)
    sc   R2, 0(R1)        # 원자적으로 Store 시도
    beqz R2, try          # Store 실패하면 다시 시도
    # --- Critical Section ---
    sw   R0, 0(R1)        # Lock 해제 (0으로 설정)

Atomic Load and Store

Atomic Load and Store는 Load와 Store 사이에 다른 프로세서의 방해 없이 수행할 수 있도록 보장하는 것이다. 핵심 요구사항:

Atomic Exchange: 메모리와 레지스터의 값을 원자적으로 교환. MIPS에는 없고 ARM에는 존재.
SWP (Swap): load와 store를 한 instruction에서 처리하지만 ARM에서만 지원.
MIPS에서는 LL/SC 쌍으로 atomic operation을 구현한다.

Spin Lock

Spin Lock은 프로세서가 Lock을 획득할 때까지 계속 시도(Acquire)하는 형태의 Lock이다.

Processor A                    Processor B
──────────────                 ──────────────
spin: Read lock variable       spin: Read lock variable
      Set lock variable = 1          Set lock variable = 1
      if (read value != 0)           if (read value != 0)
        go to spin                     go to spin
      Task on shared memory          Task on shared memory
      Set lock variable = 0          Set lock variable = 0
      (unlock)                       (unlock)

Spin Lock의 특징:

Lock을 획득할 때까지 CPU가 계속 반복 검사 → Busy Waiting
Lock이 짧은 시간 안에 풀릴 것으로 예상되는 경우에 적합
하드웨어 지원(Atomic Exchange 또는 LL/SC)이 반드시 필요

Data Race가 발생하는 경우:

서로 다른 프로세서가 동일한 메모리 위치에 접근
Memory Access 중 하나 이상이 Write인 경우 (양쪽 다 Read이면 문제 없음)
Memory Access의 순서가 정해지지 않은 경우

이러한 Data Race를 방지하기 위해 Lock을 사용하며, Lock의 정확한 구현을 위해 하드웨어 수준의 원자적 연산이 필수적이다.

정리

이번 글에서는 단일 프로세서의 성능 한계를 넘기 위한 두 가지 접근법을 살펴보았다:

ILP (명령어 수준 병렬성): 하나의 프로세서 내에서 여러 명령어를 동시에 실행
- VLIW: 컴파일러가 정적으로 병렬 명령어를 결정 → 단순한 하드웨어, 복잡한 컴파일러
- Superscalar: CPU가 동적으로 병렬 명령어를 결정 → 비순차 실행, Register Renaming, Speculation
멀티프로세서: 여러 프로세서를 사용하여 Thread-Level Parallelism 달성
- 캐시 일관성(Cache Coherence)을 위한 Snoop/Directory 프로토콜
- 동기화를 위한 Lock, Atomic Exchange, LL/SC 메커니즘

단일 프로세서의 ILP에는 한계가 있으므로 (ILP Wall), 현대 컴퓨터는 멀티코어 프로세서를 통해 Thread-Level Parallelism으로 성능을 확보하는 방향으로 발전해왔다.

ILP (Instruction-Level Parallelism)#

Multiple Issue#

VLIW (Static Multiple-Issue)#

Issue Packet#

2-Issue MIPS 예시#

VLIW에서의 Hazard 처리#

Loop Unrolling#

VLIW의 장단점#

Superscalar (Dynamic Multiple-Issue)#

Out-of-Order Execution#

Superscalar Processor의 3 영역#

Data Dependency#

Speculation#

멀티프로세서 (Multiprocessor)#

멀티코어 프로세서 (CMP)#

Flynn’s Taxonomy#

Communication Model#

Shared Memory Multiprocessor (SMP)#

메모리 구조#

Cache Coherence Problem#

Propagation 대상: Snoop vs Directory#

동기화 (Synchronization)#

Lock#

Atomic Exchange#

Load Linked / Store Conditional (LL/SC)#

Atomic Load and Store#

Spin Lock#

정리#