병렬 처리와 멀티코어
병렬 처리와 멀티코어¶
개요¶
단일 프로세서의 성능 향상이 물리적 한계에 도달하면서, 현대 컴퓨터는 멀티코어와 병렬 처리를 통해 성능을 높이고 있습니다. 이 레슨에서는 병렬 처리의 기본 개념, 멀티프로세서/멀티코어 아키텍처, 캐시 일관성 문제, 동기화 메커니즘, 그리고 GPU를 활용한 병렬 컴퓨팅까지 학습합니다.
난이도: ⭐⭐⭐⭐
선수 지식: CPU 구조, 캐시 메모리, 메모리 계층
목차¶
- 병렬 처리의 필요성
- 플린 분류 (Flynn's Taxonomy)
- 멀티프로세서와 멀티코어
- 캐시 일관성 문제
- 스누핑 프로토콜 (MESI)
- 암달의 법칙과 구스타프슨 법칙
- 동기화와 락
- GPU와 병렬 컴퓨팅
- 연습 문제
1. 병렬 처리의 필요성¶
1.1 단일 코어의 한계¶
┌─────────────────────────────────────────────────────────────┐
│ CPU 클럭 속도 발전 추이 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 클럭 │
│ (GHz) │
│ │ ●──────● (정체) │
│ 5 │ ●────● │
│ │ ●──── │
│ 4 │ ●──── │
│ │ ●──── │
│ 3 │ ●──── │
│ │ ●──── │
│ 2 │ ●──── │
│ │ ● │
│ 1 │● │
│ │ │
│ └──────────────────────────────────────────────────── │
│ 1995 2000 2005 2010 2015 2020 │
│ │
│ 2005년 이후 클럭 속도 정체: │
│ - 전력 장벽 (Power Wall) │
│ - 발열 문제 │
│ - 메모리 장벽 (Memory Wall) │
│ - ILP 장벽 │
│ │
└─────────────────────────────────────────────────────────────┘
1.2 무어의 법칙과 데나드 스케일링¶
무어의 법칙 (Moore's Law):
- 트랜지스터 수 2년마다 2배 증가
- 아직 유효 (둔화 중)
데나드 스케일링 (Dennard Scaling):
- 트랜지스터 크기 감소 → 전력 밀도 일정
- 2006년경 붕괴
┌─────────────────────────────────────────────────────────────┐
│ │
│ 데나드 스케일링 종료 후: │
│ │
│ 트랜지스터 수 ↑ + 클럭 속도 정체 → 어떻게 활용? │
│ │
│ 해결책: 멀티코어 │
│ │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ 2005년 이전: 2005년 이후: │ │
│ │ │ │
│ │ ┌─────────────┐ ┌─────┐ ┌─────┐ ┌─────┐ │ │
│ │ │ │ │Core1│ │Core2│ │Core3│ ... │ │
│ │ │ 단일 고성능 │ │ │ │ │ │ │ │ │
│ │ │ 코어 │ └─────┘ └─────┘ └─────┘ │ │
│ │ │ │ │ │
│ │ └─────────────┘ 여러 개의 효율적인 코어 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘
1.3 병렬 처리의 이점¶
성능 향상:
- 동시에 여러 작업 처리
- 큰 문제를 작은 부분으로 나눠 병렬 해결
에너지 효율:
- 낮은 클럭의 여러 코어가 높은 클럭의 단일 코어보다 효율적
- 전력 ∝ 전압² × 주파수
신뢰성:
- 한 코어 고장 시 다른 코어로 계속 동작
- 결함 허용(Fault Tolerance)
확장성:
- 코어 수 증가로 성능 확장 가능
- 수직 확장(코어 추가) + 수평 확장(노드 추가)
2. 플린 분류 (Flynn's Taxonomy)¶
2.1 분류 체계¶
┌─────────────────────────────────────────────────────────────┐
│ Flynn's Taxonomy │
├─────────────────────────────────────────────────────────────┤
│ │
│ │ Single Data │ Multiple Data │
│ │ (SD) │ (MD) │
│ ────────────┼─────────────────────┼────────────────────────│
│ │ │ │
│ Single │ SISD │ SIMD │
│ Instruction │ (단일 명령어 │ (단일 명령어 │
│ (SI) │ 단일 데이터) │ 다중 데이터) │
│ │ │ │
│ ────────────┼─────────────────────┼────────────────────────│
│ │ │ │
│ Multiple │ MISD │ MIMD │
│ Instruction │ (다중 명령어 │ (다중 명령어 │
│ (MI) │ 단일 데이터) │ 다중 데이터) │
│ │ │ │
│ │ (거의 없음) │ │
│ │
└─────────────────────────────────────────────────────────────┘
2.2 SISD (Single Instruction, Single Data)¶
전통적인 폰 노이만 컴퓨터:
┌─────────────────────────────────────────────────────────────┐
│ │
│ Instruction Stream Data Stream │
│ │ │ │
│ ▼ ▼ │
│ ┌───────────┐ ┌───────────┐ │
│ │ I1 │ │ D1 │ │
│ │ I2 │ │ D2 │ │
│ │ I3 │ │ D3 │ │
│ │ ... │ │ ... │ │
│ └─────┬─────┘ └─────┬─────┘ │
│ │ │ │
│ └───────────┬─────────────┘ │
│ │ │
│ ▼ │
│ ┌───────────────┐ │
│ │ CPU │ │
│ │ (단일 코어) │ │
│ └───────────────┘ │
│ │
│ 예시: 초기 마이크로프로세서, 임베디드 시스템 │
│ │
└─────────────────────────────────────────────────────────────┘
2.3 SIMD (Single Instruction, Multiple Data)¶
같은 연산을 여러 데이터에 동시 적용:
┌─────────────────────────────────────────────────────────────┐
│ │
│ Single Instruction Multiple Data │
│ │ ┌──────┬──────┬──────┐ │
│ │ │ D1 │ D2 │ D3 │ │
│ ▼ └──┬───┴──┬───┴──┬───┘ │
│ ┌───────────┐ │ │ │ │
│ │ ADD │ ▼ ▼ ▼ │
│ └─────┬─────┘ ┌────────────────────────┐ │
│ │ │ Processing Units │ │
│ │ │ ┌────┐┌────┐┌────┐ │ │
│ └─────────────────▶│ │ PU1││ PU2││ PU3│ │ │
│ │ └────┘└────┘└────┘ │ │
│ └──────────┬─────────────┘ │
│ │ │
│ ┌──────────┴──────────┐ │
│ │ R1 │ R2 │ R3 │ │
│ └──────┴──────┴──────┘ │
│ │
│ 예시: │
│ - Intel SSE, AVX (256/512비트 벡터) │
│ - GPU의 워프/웨이브 │
│ - 이미지 처리, 과학 계산 │
│ │
│ 코드 예시 (AVX): │
│ __m256 a = _mm256_load_ps(arr1); │
│ __m256 b = _mm256_load_ps(arr2); │
│ __m256 c = _mm256_add_ps(a, b); // 8개 float 동시 덧셈 │
│ │
└─────────────────────────────────────────────────────────────┘
2.4 MISD (Multiple Instruction, Single Data)¶
여러 명령어가 같은 데이터 스트림 처리:
┌─────────────────────────────────────────────────────────────┐
│ │
│ Multiple Instructions Single Data │
│ ┌────────────────┐ │ │
│ │ I1: Encrypt │ │ │
│ │ I2: Compress │ ▼ │
│ │ I3: Checksum │ ┌─────────┐ │
│ └───────┬────────┘ │ Data │ │
│ │ └────┬────┘ │
│ │ │ │
│ ▼ │ │
│ ┌────────────┐ │ │
│ │ Pipeline │◀────────────────────┘ │
│ │ of Units │ │
│ └────────────┘ │
│ │
│ 실제 사용 예: │
│ - 시스톨릭 어레이 (일부) │
│ - 결함 허용 시스템 (같은 계산 여러 번) │
│ - 매우 드물게 사용됨 │
│ │
└─────────────────────────────────────────────────────────────┘
2.5 MIMD (Multiple Instruction, Multiple Data)¶
가장 일반적인 병렬 컴퓨터 형태:
┌─────────────────────────────────────────────────────────────┐
│ │
│ Multiple Instructions Multiple Data │
│ ┌────────────────┐ ┌────────────────────┐ │
│ │ I1: func_A() │ │ D1, D2, D3, D4 │ │
│ │ I2: func_B() │ │ D5, D6, D7, D8 │ │
│ │ I3: func_C() │ │ ... │ │
│ │ I4: func_D() │ │ │ │
│ └───────┬────────┘ └─────────┬─────────┘ │
│ │ │ │
│ ▼ ▼ │
│ ┌───────────────────────────────────────────────────┐ │
│ │ Multiple Processors │ │
│ │ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ │ │
│ │ │ CPU 1 │ │ CPU 2 │ │ CPU 3 │ │ CPU 4 │ │ │
│ │ │ func_A()│ │ func_B()│ │ func_C()│ │ func_D()│ │ │
│ │ │ D1 │ │ D5 │ │ D2 │ │ D8 │ │ │
│ │ └─────────┘ └─────────┘ └─────────┘ └─────────┘ │ │
│ └───────────────────────────────────────────────────┘ │
│ │
│ 예시: │
│ - 멀티코어 프로세서 │
│ - 멀티프로세서 서버 │
│ - 클러스터, 슈퍼컴퓨터 │
│ │
│ MIMD 분류: │
│ - 공유 메모리 (Shared Memory): SMP, NUMA │
│ - 분산 메모리 (Distributed Memory): 클러스터 │
│ │
└─────────────────────────────────────────────────────────────┘
3. 멀티프로세서와 멀티코어¶
3.1 SMP (Symmetric Multi-Processing)¶
┌─────────────────────────────────────────────────────────────┐
│ SMP (대칭 다중 처리) │
├─────────────────────────────────────────────────────────────┤
│ │
│ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ │
│ │ CPU 0 │ │ CPU 1 │ │ CPU 2 │ │ CPU 3 │ │
│ │┌───────┐│ │┌───────┐│ │┌───────┐│ │┌───────┐│ │
│ ││ Cache ││ ││ Cache ││ ││ Cache ││ ││ Cache ││ │
│ │└───────┘│ │└───────┘│ │└───────┘│ │└───────┘│ │
│ └────┬────┘ └────┬────┘ └────┬────┘ └────┬────┘ │
│ │ │ │ │ │
│ └───────────┴─────┬─────┴───────────┘ │
│ │ │
│ System Bus │
│ │ │
│ ┌──────────────────────┴──────────────────────┐ │
│ │ │ │
│ │ Shared Memory │ │
│ │ (모든 CPU 동등 접근) │ │
│ │ │ │
│ └─────────────────────────────────────────────┘ │
│ │
│ 특징: │
│ - 모든 프로세서가 메모리에 동등하게 접근 (UMA) │
│ - 어떤 CPU에서든 같은 코드 실행 가능 │
│ - 확장성 제한 (버스 경합) │
│ - 일반적으로 2-8 CPU │
│ │
└─────────────────────────────────────────────────────────────┘
3.2 NUMA (Non-Uniform Memory Access)¶
┌─────────────────────────────────────────────────────────────┐
│ NUMA 아키텍처 │
├─────────────────────────────────────────────────────────────┤
│ │
│ Node 0 Node 1 │
│ ┌──────────────────┐ ┌──────────────────┐ │
│ │ CPU0 CPU1 │ │ CPU2 CPU3 │ │
│ │ ┌───┐ ┌───┐ │ │ ┌───┐ ┌───┐ │ │
│ │ │ $ │ │ $ │ │ │ │ $ │ │ $ │ │ │
│ │ └─┬─┘ └─┬─┘ │ │ └─┬─┘ └─┬─┘ │ │
│ │ └───┬───┘ │ │ └───┬───┘ │ │
│ │ │ │ │ │ │ │
│ │ ┌─────┴─────┐ │ │ ┌─────┴─────┐ │ │
│ │ │ Local Mem │ │◀════════▶│ │ Local Mem │ │ │
│ │ │ (빠름) │ │Interconn│ │ (빠름) │ │ │
│ │ └───────────┘ │ │ └───────────┘ │ │
│ └──────────────────┘ └──────────────────┘ │
│ │
│ 메모리 접근 시간: │
│ ┌────────────────────────────────────────────────────────┐│
│ │ Local Memory (같은 노드): ~100 사이클 ││
│ │ Remote Memory (다른 노드): ~300 사이클 (3배 느림) ││
│ └────────────────────────────────────────────────────────┘│
│ │
│ 특징: │
│ - 로컬 메모리 접근이 원격 메모리보다 빠름 │
│ - 확장성 우수 (수백 CPU 가능) │
│ - NUMA-aware 프로그래밍 필요 │
│ - 최신 서버의 표준 구조 │
│ │
└─────────────────────────────────────────────────────────────┘
3.3 멀티코어 프로세서¶
┌─────────────────────────────────────────────────────────────┐
│ 현대 멀티코어 CPU │
├─────────────────────────────────────────────────────────────┤
│ │
│ ┌───────────────────────────────────────────────────────┐ │
│ │ CPU Die │ │
│ │ ┌─────────────────────────────────────────────────┐ │ │
│ │ │ Core 0 Core 1 Core 2 │ │ │
│ │ │ ┌─────────┐ ┌─────────┐ ┌─────────┐ │ │ │
│ │ │ │L1-I│L1-D│ │L1-I│L1-D│ │L1-I│L1-D│ │ │ │
│ │ │ └────┴────┘ └────┴────┘ └────┴────┘ │ │ │
│ │ │ ┌─────────┐ ┌─────────┐ ┌─────────┐ │ │ │
│ │ │ │ L2 │ │ L2 │ │ L2 │ │ │ │
│ │ │ └─────────┘ └─────────┘ └─────────┘ │ │ │
│ │ └─────────────────────────────────────────────────┘ │ │
│ │ │ │ │
│ │ ┌───────────────────────┴───────────────────────┐ │ │
│ │ │ Shared L3 Cache │ │ │
│ │ │ (8-64 MB) │ │ │
│ │ └───────────────────────┬───────────────────────┘ │ │
│ │ │ │ │
│ │ ┌───────────────────────┴───────────────────────┐ │ │
│ │ │ Memory Controller │ │ │
│ │ │ + PCIe Controller │ │ │
│ │ └───────────────────────────────────────────────┘ │ │
│ └───────────────────────────────────────────────────────┘ │
│ │
│ 장점: │
│ - 코어 간 통신 빠름 (온칩) │
│ - 전력 효율적 │
│ - 공유 캐시로 데이터 공유 효율적 │
│ │
└─────────────────────────────────────────────────────────────┘
3.4 하이퍼스레딩 (SMT)¶
┌─────────────────────────────────────────────────────────────┐
│ Simultaneous Multi-Threading (SMT) │
├─────────────────────────────────────────────────────────────┤
│ │
│ 하나의 물리 코어에서 여러 스레드를 동시 실행: │
│ │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ Physical Core │ │
│ │ ┌─────────────────────────────────────────────────┐│ │
│ │ │ Thread 0 State │ Thread 1 State ││ │
│ │ │ ┌───────────┐ │ ┌───────────┐ ││ │
│ │ │ │Registers │ │ │Registers │ ← 복제됨 ││ │
│ │ │ │PC, Stack │ │ │PC, Stack │ ││ │
│ │ │ └───────────┘ │ └───────────┘ ││ │
│ │ └─────────────────────────────────────────────────┘│ │
│ │ │ │
│ │ ┌─────────────────────────────────────────────────┐│ │
│ │ │ Shared Resources ││ │
│ │ │ ┌─────────┐ ┌─────────┐ ┌─────────┐ ││ │
│ │ │ │ ALU │ │ Cache │ │ Branch │ ← 공유 ││ │
│ │ │ │ │ │ │ │Predictor│ ││ │
│ │ │ └─────────┘ └─────────┘ └─────────┘ ││ │
│ │ └─────────────────────────────────────────────────┘│ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ 동작 원리: │
│ - Thread 0가 메모리 대기 중 → Thread 1 실행 │
│ - 실행 유닛 활용도 향상 │
│ - 일반적으로 15-30% 성능 향상 │
│ │
│ OS에서의 표시: │
│ - 4코어 8스레드 = 8개의 논리 CPU로 인식 │
│ │
└─────────────────────────────────────────────────────────────┘
4. 캐시 일관성 문제¶
4.1 캐시 일관성이란?¶
문제 상황:
┌─────────────────────────────────────────────────────────────┐
│ │
│ Core 0 Core 1 │
│ Cache Cache │
│ ┌─────────┐ ┌─────────┐ │
│ │ X = 10 │ │ X = 10 │ │
│ └─────────┘ └─────────┘ │
│ │ │ │
│ └─────────────┬───────────────────┘ │
│ │ │
│ ┌──────┴──────┐ │
│ │ Main Memory │ │
│ │ X = 10 │ │
│ └─────────────┘ │
│ │
│ 1. 초기 상태: X = 10 (모두 동일) │
│ │
│ 2. Core 0이 X = 20으로 수정: │
│ │
│ Core 0 Core 1 │
│ Cache Cache │
│ ┌─────────┐ ┌─────────┐ │
│ │ X = 20 │ ← 수정됨 │ X = 10 │ ← 구버전! │
│ └─────────┘ └─────────┘ │
│ │
│ 3. Core 1이 X를 읽으면 어떤 값? │
│ - 10 (자신의 캐시) → 오래된 값! (일관성 위반) │
│ - 20 (Core 0의 값) → 일관성 유지 │
│ │
└─────────────────────────────────────────────────────────────┘
4.2 일관성 정의¶
캐시 일관성 (Cache Coherence) 조건:
1. 프로그램 순서 보존:
- 같은 프로세서에서 쓰기 후 읽기는 쓴 값 반환
2. 일관된 읽기 값:
- 다른 프로세서의 쓰기가 최종적으로 모든 프로세서에 보임
3. 쓰기 직렬화:
- 같은 주소에 대한 쓰기는 모든 프로세서에 같은 순서로 보임
┌─────────────────────────────────────────────────────────────┐
│ 예시: │
│ │
│ 초기: X = 0 │
│ │
│ Core 0: X = 1 │
│ Core 1: X = 2 │
│ │
│ 모든 프로세서가 본 X 값의 순서는 같아야 함: │
│ - 모두 0 → 1 → 2 순서로 봄, 또는 │
│ - 모두 0 → 2 → 1 순서로 봄 │
│ │
│ 어떤 프로세서가 1 → 2 보고 다른 프로세서가 2 → 1 보면 안 됨 │
│ │
└─────────────────────────────────────────────────────────────┘
4.3 일관성 프로토콜 개요¶
일관성 유지 방법:
1. 스누핑 (Snooping) 프로토콜:
┌─────────────────────────────────────────────────────────────┐
│ │
│ - 버스 기반 시스템에 적합 │
│ - 각 캐시가 버스 트래픽 감시 (스누핑) │
│ - 관련 주소 발견 시 적절한 조치 │
│ - MESI, MOESI 등 │
│ │
│ ┌─────┐ ┌─────┐ ┌─────┐ │
│ │Cache│ │Cache│ │Cache│ ← 모두 버스 감시 │
│ └──┬──┘ └──┬──┘ └──┬──┘ │
│ │ │ │ │
│ ═══╪═══════════╪═══════════╪═════ (Shared Bus) │
│ │ │
│ ┌──────┴──────┐ │
│ │ Memory │ │
│ └─────────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘
2. 디렉토리 (Directory) 프로토콜:
┌─────────────────────────────────────────────────────────────┐
│ │
│ - 확장성 좋음 (NUMA에 적합) │
│ - 중앙 디렉토리가 캐시 상태 추적 │
│ - 해당 캐시에만 메시지 전송 │
│ │
│ ┌─────┐ ┌─────┐ ┌─────┐ │
│ │Cache│ │Cache│ │Cache│ │
│ └──┬──┘ └──┬──┘ └──┬──┘ │
│ │ │ │ │
│ └────────┬────────┴────────┬────────┘ │
│ │ │ │
│ ┌─────┴─────┐ ┌──────┴──────┐ │
│ │ Directory │ │ Memory │ │
│ │ (상태 추적)│ │ │ │
│ └───────────┘ └─────────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘
5. 스누핑 프로토콜 (MESI)¶
5.1 MESI 상태¶
┌─────────────────────────────────────────────────────────────┐
│ MESI 프로토콜 상태 │
├─────────────────────────────────────────────────────────────┤
│ │
│ M (Modified): │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ - 이 캐시만 복사본 보유 │ │
│ │ - 수정됨 (메모리와 불일치) │ │
│ │ - 다른 캐시 접근 시 Write-back 필요 │ │
│ │ - 쓰기 가능 │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ E (Exclusive): │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ - 이 캐시만 복사본 보유 │ │
│ │ - 수정 안 됨 (메모리와 일치) │ │
│ │ - 쓰기 시 M 상태로 전이 (무효화 불필요) │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ S (Shared): │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ - 여러 캐시가 복사본 보유 가능 │ │
│ │ - 메모리와 일치 │ │
│ │ - 쓰기 시 다른 캐시 무효화 필요 → M 상태 │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ I (Invalid): │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ - 유효한 데이터 없음 │ │
│ │ - 캐시 라인 비어있음 │ │
│ │ - 접근 시 캐시 미스 │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘
5.2 MESI 상태 전이¶
┌─────────────────────────────────────────────────────────────┐
│ MESI 상태 전이 다이어그램 │
├─────────────────────────────────────────────────────────────┤
│ │
│ ┌─────────┐ │
│ Read miss │ │ Read miss │
│ (exclusive)│ I │ (shared) │
│ ┌────────│ Invalid │────────┐ │
│ │ │ │ │ │
│ │ └────┬────┘ │ │
│ │ │ │ │
│ │ Write│ │ │
│ │ miss │ │ │
│ │ │ │ │
│ ▼ │ ▼ │
│ ┌──────────┐ │ ┌──────────┐ │
│ │ E │ │ │ S │ │
│ │Exclusive │ │ │ Shared │ │
│ └────┬─────┘ │ └────┬─────┘ │
│ │ │ │ │
│ Local│ │ Local│ │
│ Write│ │ Write│ │
│ │ │ │ │
│ ▼ ▼ ▼ │
│ ┌─────────────────────────────────┐ │
│ │ M │ │
│ │ Modified │ │
│ └─────────────────────────────────┘ │
│ │
│ 주요 전이: │
│ - I → E: Read miss, 다른 캐시에 없음 │
│ - I → S: Read miss, 다른 캐시에 있음 (Shared 상태) │
│ - E → M: Local write (무효화 브로드캐스트 불필요) │
│ - S → M: Local write + 다른 캐시 무효화 │
│ - M/E/S → I: 다른 캐시의 쓰기로 무효화됨 │
│ │
└─────────────────────────────────────────────────────────────┘
5.3 MESI 동작 예시¶
┌─────────────────────────────────────────────────────────────┐
│ MESI 프로토콜 동작 예시 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 초기: 변수 X는 어떤 캐시에도 없음 (메모리에만 X=0) │
│ │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ Step 1: Core 0이 X 읽기 │ │
│ │ │ │
│ │ Core 0 Cache Core 1 Cache Memory │ │
│ │ ┌─────────┐ ┌─────────┐ ┌─────────┐ │ │
│ │ │ X=0 (E) │ │ X (I) │ │ X = 0 │ │ │
│ │ └─────────┘ └─────────┘ └─────────┘ │ │
│ │ Exclusive (다른 캐시에 없음) │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ Step 2: Core 1이 X 읽기 │ │
│ │ │ │
│ │ Core 0 Cache Core 1 Cache Memory │ │
│ │ ┌─────────┐ ┌─────────┐ ┌─────────┐ │ │
│ │ │ X=0 (S) │ │ X=0 (S) │ │ X = 0 │ │ │
│ │ └─────────┘ └─────────┘ └─────────┘ │ │
│ │ E→S 전이 (다른 캐시에서 읽음) │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ Step 3: Core 0이 X = 10 쓰기 │ │
│ │ │ │
│ │ Core 0: 무효화 메시지 브로드캐스트 │ │
│ │ Core 1: X를 Invalid로 변경 │ │
│ │ │ │
│ │ Core 0 Cache Core 1 Cache Memory │ │
│ │ ┌─────────┐ ┌─────────┐ ┌─────────┐ │ │
│ │ │ X=10(M) │ │ X (I) │ │ X = 0 │ │ │
│ │ └─────────┘ └─────────┘ └─────────┘ │ │
│ │ Modified (메모리와 불일치) │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ Step 4: Core 1이 X 읽기 │ │
│ │ │ │
│ │ Core 1: Read miss, Core 0이 데이터 제공 │ │
│ │ Core 0: Write-back to memory, S로 전이 │ │
│ │ │ │
│ │ Core 0 Cache Core 1 Cache Memory │ │
│ │ ┌─────────┐ ┌─────────┐ ┌─────────┐ │ │
│ │ │ X=10(S) │ │ X=10(S) │ │ X = 10 │ │ │
│ │ └─────────┘ └─────────┘ └─────────┘ │ │
│ │ M→S 전이, 메모리 갱신됨 │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘
5.4 MOESI 프로토콜¶
MOESI = MESI + Owner 상태:
O (Owner):
- 수정된 데이터의 유일한 소유자
- 다른 캐시도 Shared 복사본 가질 수 있음
- 메모리와 불일치 (Owner가 최신)
- 다른 캐시 요청 시 Owner가 응답
┌─────────────────────────────────────────────────────────────┐
│ MOESI 장점: │
│ - Cache-to-Cache 전송 효율 증가 │
│ - Write-back 지연 가능 │
│ - AMD 프로세서에서 주로 사용 │
└─────────────────────────────────────────────────────────────┘
6. 암달의 법칙과 구스타프슨 법칙¶
6.1 암달의 법칙 (Amdahl's Law)¶
병렬화의 한계를 보여주는 법칙:
┌─────────────────────────────────────────────────────────────┐
│ Amdahl's Law │
├─────────────────────────────────────────────────────────────┤
│ │
│ 1 │
│ Speedup = ───────────────────────── │
│ (1 - P) + P/N │
│ │
│ P: 병렬화 가능한 비율 │
│ N: 프로세서 수 │
│ │
│ 예시: P = 90% (90% 병렬화 가능) │
│ │
│ N=2: Speedup = 1/(0.1 + 0.45) = 1.82x │
│ N=4: Speedup = 1/(0.1 + 0.225) = 3.08x │
│ N=8: Speedup = 1/(0.1 + 0.1125) = 4.71x │
│ N=∞: Speedup = 1/0.1 = 10x ← 최대 한계! │
│ │
│ 90%를 병렬화해도 최대 10배 성능 향상만 가능 │
│ │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ Speedup │ │
│ │ │ _______ P=99% │ │
│ │ 100│ _____/ │ │
│ │ │ ____/ │ │
│ │ 80 │ ____/ │ │
│ │ │ ____/ _______ P=95% │ │
│ │ 60 │ ____/ ____/ │ │
│ │ │___/ ____/ │ │
│ │ 40 │ ____/ _______ P=90% │ │
│ │ │ ____/ ____/ │ │
│ │ 20 │ ____/ ____/ │ │
│ │ │__/ ____/_______________________ P=75% │ │
│ │ │ ____/___________________________ │ │
│ │ └──────────────────────────────────────────── │ │
│ │ 1 10 100 1000 10000 프로세서 수 │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘
6.2 구스타프슨 법칙 (Gustafson's Law)¶
문제 크기를 확장하면 더 많은 병렬화 가능:
┌─────────────────────────────────────────────────────────────┐
│ Gustafson's Law │
├─────────────────────────────────────────────────────────────┤
│ │
│ Scaled Speedup = N + (1 - N) × S │
│ │
│ 또는: │
│ │
│ Speedup = N - S × (N - 1) │
│ │
│ N: 프로세서 수 │
│ S: 순차 부분의 비율 (고정된 시간) │
│ │
│ 핵심 아이디어: │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ 암달: "문제 크기 고정, 프로세서 추가" │ │
│ │ → 순차 부분이 병목 │ │
│ │ │ │
│ │ 구스타프슨: "시간 고정, 문제 크기 확장" │ │
│ │ → 더 큰 문제를 같은 시간에 해결 │ │
│ │ → 병렬 부분 비율 증가 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ 예시: │
│ - 1시간 안에 시뮬레이션 실행 │
│ - 프로세서 추가하면 더 정밀한 시뮬레이션 가능 │
│ - 순차 부분(초기화 등)은 일정, 병렬 계산량 증가 │
│ │
└─────────────────────────────────────────────────────────────┘
6.3 실제 병렬화 효율¶
┌─────────────────────────────────────────────────────────────┐
│ 병렬화 효율 계산 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 효율 = Speedup / N │
│ │
│ 이상적: 효율 = 1 (100%) │
│ 현실적: 오버헤드로 인해 1보다 작음 │
│ │
│ 오버헤드 요인: │
│ - 통신 시간 (프로세서 간 데이터 전송) │
│ - 동기화 대기 시간 │
│ - 로드 불균형 (작업 불균등 분배) │
│ - 캐시 일관성 트래픽 │
│ - 메모리 경합 │
│ │
│ 효율성 그래프: │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ 효율 │ │
│ │ 100%│────┐ │ │
│ │ │ └────┐ │ │
│ │ 80% │ └────┐ │ │
│ │ │ └────┐ │ │
│ │ 60% │ └────┐ │ │
│ │ │ └────┐ │ │
│ │ 40% │ └────┐ │ │
│ │ │ └──── │ │
│ │ 20% │ │ │
│ │ └───────────────────────────────────────── │ │
│ │ 1 2 4 8 16 32 64 128 프로세서 수 │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ 일반적으로 프로세서 수 증가 시 효율 감소 │
│ (수확 체감의 법칙) │
│ │
└─────────────────────────────────────────────────────────────┘
7. 동기화와 락¶
7.1 동기화의 필요성¶
Race Condition 예시:
┌─────────────────────────────────────────────────────────────┐
│ 공유 변수: counter = 0 │
│ │
│ Thread 0 Thread 1 │
│ ───────────────── ───────────────── │
│ load counter load counter // 둘 다 0 │
│ add 1 add 1 // 둘 다 1 │
│ store counter store counter // 둘 다 1 저장│
│ │
│ 기대 결과: counter = 2 │
│ 실제 결과: counter = 1 ← 하나의 증가가 손실됨! │
│ │
└─────────────────────────────────────────────────────────────┘
7.2 원자적 연산¶
하드웨어 지원 원자적 연산:
┌─────────────────────────────────────────────────────────────┐
│ │
│ Test-and-Set (TAS): │
│ ┌───────────────────────────────────────────────────┐ │
│ │ int TAS(int *lock) { │ │
│ │ int old = *lock; // 읽기 │ │
│ │ *lock = 1; // 쓰기 원자적으로 │ │
│ │ return old; // 반환 실행됨 │ │
│ │ } │ │
│ └───────────────────────────────────────────────────┘ │
│ │
│ Compare-and-Swap (CAS): │
│ ┌───────────────────────────────────────────────────┐ │
│ │ bool CAS(int *addr, int expected, int new) { │ │
│ │ if (*addr == expected) { │ │
│ │ *addr = new; 원자적으로 │ │
│ │ return true; 실행됨 │ │
│ │ } │ │
│ │ return false; │ │
│ │ } │ │
│ └───────────────────────────────────────────────────┘ │
│ │
│ Fetch-and-Add: │
│ ┌───────────────────────────────────────────────────┐ │
│ │ int FAA(int *addr, int val) { │ │
│ │ int old = *addr; 원자적으로 │ │
│ │ *addr = old + val; 실행됨 │ │
│ │ return old; │ │
│ │ } │ │
│ └───────────────────────────────────────────────────┘ │
│ │
│ x86 명령어 예시: │
│ - LOCK XCHG (Test-and-Set) │
│ - LOCK CMPXCHG (Compare-and-Swap) │
│ - LOCK XADD (Fetch-and-Add) │
│ │
└─────────────────────────────────────────────────────────────┘
7.3 스핀락 (Spinlock)¶
┌─────────────────────────────────────────────────────────────┐
│ 스핀락 구현 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 단순 스핀락 (Test-and-Set): │
│ ┌───────────────────────────────────────────────────┐ │
│ │ void lock(int *lock) { │ │
│ │ while (TAS(lock) == 1) { │ │
│ │ // 스핀 (바쁜 대기) │ │
│ │ } │ │
│ │ } │ │
│ │ │ │
│ │ void unlock(int *lock) { │ │
│ │ *lock = 0; │ │
│ │ } │ │
│ └───────────────────────────────────────────────────┘ │
│ 문제: TAS마다 버스 트래픽 발생 │
│ │
│ Test-and-Test-and-Set (TTAS): │
│ ┌───────────────────────────────────────────────────┐ │
│ │ void lock(int *lock) { │ │
│ │ while (1) { │ │
│ │ while (*lock == 1) { │ │
│ │ // 로컬 캐시에서 스핀 (버스 트래픽 없음)│ │
│ │ } │ │
│ │ if (TAS(lock) == 0) { │ │
│ │ return; // 락 획득 성공 │ │
│ │ } │ │
│ │ } │ │
│ │ } │ │
│ └───────────────────────────────────────────────────┘ │
│ 개선: 락이 해제될 때까지 로컬 캐시에서 대기 │
│ │
└─────────────────────────────────────────────────────────────┘
7.4 뮤텍스와 세마포어¶
┌─────────────────────────────────────────────────────────────┐
│ 동기화 프리미티브 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 뮤텍스 (Mutex): │
│ - Mutual Exclusion (상호 배제) │
│ - 한 번에 하나의 스레드만 진입 │
│ - 소유권 있음 (획득한 스레드만 해제) │
│ │
│ ┌───────────────────────────────────────────────────┐ │
│ │ pthread_mutex_t mutex; │ │
│ │ pthread_mutex_init(&mutex, NULL); │ │
│ │ │ │
│ │ pthread_mutex_lock(&mutex); │ │
│ │ // Critical Section │ │
│ │ pthread_mutex_unlock(&mutex); │ │
│ └───────────────────────────────────────────────────┘ │
│ │
│ 세마포어 (Semaphore): │
│ - 카운터 기반 동기화 │
│ - N개 스레드 동시 접근 허용 가능 │
│ - 소유권 없음 │
│ │
│ ┌───────────────────────────────────────────────────┐ │
│ │ sem_t sem; │ │
│ │ sem_init(&sem, 0, 3); // 최대 3개 동시 접근 │ │
│ │ │ │
│ │ sem_wait(&sem); // 카운터 감소, 0이면 대기 │ │
│ │ // Critical Section │ │
│ │ sem_post(&sem); // 카운터 증가, 대기자 깨움 │ │
│ └───────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘
7.5 Lock-Free 알고리즘¶
┌─────────────────────────────────────────────────────────────┐
│ Lock-Free 카운터 예시 │
├─────────────────────────────────────────────────────────────┤
│ │
│ void increment(atomic_int *counter) { │
│ int old, new; │
│ do { │
│ old = atomic_load(counter); │
│ new = old + 1; │
│ } while (!atomic_compare_exchange(counter, &old, new));│
│ } │
│ │
│ 동작: │
│ 1. 현재 값 읽기 │
│ 2. 새 값 계산 │
│ 3. CAS로 원자적 갱신 시도 │
│ 4. 실패하면 다시 시도 (다른 스레드가 수정함) │
│ │
│ 장점: │
│ - 락 대기 없음 │
│ - 데드락 불가능 │
│ - 우선순위 역전 없음 │
│ │
│ 단점: │
│ - 구현 복잡 │
│ - ABA 문제 주의 필요 │
│ │
└─────────────────────────────────────────────────────────────┘
8. GPU와 병렬 컴퓨팅¶
8.1 GPU 아키텍처¶
┌─────────────────────────────────────────────────────────────┐
│ GPU vs CPU 구조 │
├─────────────────────────────────────────────────────────────┤
│ │
│ CPU (Latency Optimized): │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ ┌─────────────────────────────────────────────┐ │ │
│ │ │ Large Cache │ │ │
│ │ └─────────────────────────────────────────────┘ │ │
│ │ ┌─────────────┐ ┌─────────────┐ │ │
│ │ │ Complex │ │ Complex │ │ │
│ │ │ Core 0 │ │ Core 1 │ (4-16 코어) │ │
│ │ │ (OoO, BP) │ │ (OoO, BP) │ │ │
│ │ └─────────────┘ └─────────────┘ │ │
│ └─────────────────────────────────────────────────────┘ │
│ 특징: 복잡한 코어, 큰 캐시, 낮은 지연시간 │
│ │
│ GPU (Throughput Optimized): │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐│ │
│ │ │ S │ S │ S │ S │ S │ S │ S │ S │ S │ S │ S │ S ││ │
│ │ │ M │ M │ M │ M │ M │ M │ M │ M │ M │ M │ M │ M ││ │
│ │ └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘│ │
│ │ (수천 개의 단순 코어/CUDA Core) │ │
│ │ ┌─────────────────────────────────────────────┐ │ │
│ │ │ Small Cache per SM │ │ │
│ │ └─────────────────────────────────────────────┘ │ │
│ └─────────────────────────────────────────────────────┘ │
│ 특징: 단순한 코어 수천 개, 작은 캐시, 높은 처리량 │
│ │
│ SM (Streaming Multiprocessor) 구조: │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ ┌─────────────────────────────────────────────┐ │ │
│ │ │ 32 CUDA Cores (1 Warp = 32 threads) │ │ │
│ │ │ 각 코어는 동일 명령어 실행 (SIMT) │ │ │
│ │ └─────────────────────────────────────────────┘ │ │
│ │ + Shared Memory (48KB) │ │
│ │ + Register File (65536 × 32bit) │ │
│ │ + Warp Scheduler │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘
8.2 CUDA 프로그래밍 모델¶
┌─────────────────────────────────────────────────────────────┐
│ CUDA 실행 모델 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 계층 구조: │
│ │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ Grid │ │
│ │ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ │ │
│ │ │ Block │ │ Block │ │ Block │ │ Block │ │ │
│ │ │ (0,0) │ │ (1,0) │ │ (2,0) │ │ (3,0) │ │ │
│ │ └─────────┘ └─────────┘ └─────────┘ └─────────┘ │ │
│ │ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ │ │
│ │ │ Block │ │ Block │ │ Block │ │ Block │ │ │
│ │ │ (0,1) │ │ (1,1) │ │ (2,1) │ │ (3,1) │ │ │
│ │ └─────────┘ └─────────┘ └─────────┘ └─────────┘ │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ Block 내부: │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐│ │
│ │ │ T0 │ T1 │ T2 │ T3 │ T4 │ T5 │ ... │T255 ││ │
│ │ └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘│ │
│ │ │ │
│ │ 256 Threads sharing Shared Memory │ │
│ │ 동기화: __syncthreads() │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ 메모리 계층: │
│ - Global Memory: 모든 스레드 접근, 느림 (~500 cycles) │
│ - Shared Memory: 블록 내 공유, 빠름 (~5 cycles) │
│ - Register: 스레드 전용, 가장 빠름 │
│ - Constant Memory: 읽기 전용, 캐시됨 │
│ │
└─────────────────────────────────────────────────────────────┘
8.3 CUDA 코드 예시¶
// 벡터 덧셈 CUDA 커널
__global__ void vectorAdd(float *A, float *B, float *C, int N) {
// 전역 스레드 인덱스 계산
int idx = blockIdx.x * blockDim.x + threadIdx.x;
if (idx < N) {
C[idx] = A[idx] + B[idx];
}
}
int main() {
int N = 1000000;
size_t size = N * sizeof(float);
// 호스트 메모리 할당
float *h_A = (float*)malloc(size);
float *h_B = (float*)malloc(size);
float *h_C = (float*)malloc(size);
// 디바이스 메모리 할당
float *d_A, *d_B, *d_C;
cudaMalloc(&d_A, size);
cudaMalloc(&d_B, size);
cudaMalloc(&d_C, size);
// 데이터 복사 (Host → Device)
cudaMemcpy(d_A, h_A, size, cudaMemcpyHostToDevice);
cudaMemcpy(d_B, h_B, size, cudaMemcpyHostToDevice);
// 커널 실행 설정
int threadsPerBlock = 256;
int blocksPerGrid = (N + threadsPerBlock - 1) / threadsPerBlock;
// 커널 실행
vectorAdd<<<blocksPerGrid, threadsPerBlock>>>(d_A, d_B, d_C, N);
// 결과 복사 (Device → Host)
cudaMemcpy(h_C, d_C, size, cudaMemcpyDeviceToHost);
// 메모리 해제
cudaFree(d_A); cudaFree(d_B); cudaFree(d_C);
free(h_A); free(h_B); free(h_C);
return 0;
}
8.4 GPU vs CPU 사용 사례¶
┌─────────────────────────────────────────────────────────────┐
│ GPU vs CPU 적합한 작업 │
├─────────────────────────────────────────────────────────────┤
│ │
│ GPU 적합 (데이터 병렬): │
│ - 행렬 연산 │
│ - 이미지/비디오 처리 │
│ - 딥러닝 학습/추론 │
│ - 물리 시뮬레이션 │
│ - 암호화폐 마이닝 │
│ - 과학 계산 (유체역학, 분자동역학) │
│ │
│ CPU 적합 (태스크 병렬, 복잡한 제어 흐름): │
│ - 운영체제 │
│ - 데이터베이스 │
│ - 웹 서버 │
│ - 컴파일러 │
│ - 일반 응용 프로그램 │
│ │
│ 성능 비교 (대략적): │
│ ┌────────────────────────────────────────────────────┐ │
│ │ 작업 │ CPU │ GPU │ 비율 │ │
│ ├────────────────────────────────────────────────────┤ │
│ │ 행렬 곱셈 (4K×4K) │ 10초 │ 0.1초 │ 100x │ │
│ │ 이미지 필터 │ 2초 │ 0.05초 │ 40x │ │
│ │ 신경망 학습 │ 100초 │ 2초 │ 50x │ │
│ │ 정렬 알고리즘 │ 5초 │ 4초 │ 1.25x │ │
│ │ 분기 많은 코드 │ 1초 │ 10초 │ 0.1x │ │
│ └────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘
9. 연습 문제¶
기초 문제¶
-
Flynn's Taxonomy의 4가지 분류를 설명하시오.
-
SMP와 NUMA의 차이점은?
-
MESI 프로토콜의 4가지 상태를 설명하시오.
중급 문제¶
-
프로그램의 80%가 병렬화 가능할 때, 암달의 법칙에 따른 8코어 시스템의 최대 성능 향상은?
-
다음 코드에서 발생할 수 있는 Race Condition을 설명하고 해결책을 제시하시오:
c int counter = 0; void increment() { counter++; } -
Test-and-Set과 Compare-and-Swap의 차이를 설명하시오.
심화 문제¶
- MESI 프로토콜에서 다음 시나리오의 상태 전이를 추적하시오:
- Core 0이 X 읽기 (메모리에서)
- Core 1이 X 읽기
- Core 0이 X 쓰기
-
Core 1이 X 읽기
-
GPU가 CPU보다 행렬 곱셈에서 빠른 이유를 설명하시오.
-
Lock-Free 알고리즘의 장단점과 ABA 문제를 설명하시오.
정답
1. Flynn's Taxonomy: - SISD: 단일 명령어 단일 데이터 (전통적 CPU) - SIMD: 단일 명령어 다중 데이터 (벡터 연산, GPU) - MISD: 다중 명령어 단일 데이터 (거의 없음) - MIMD: 다중 명령어 다중 데이터 (멀티코어) 2. SMP vs NUMA: - SMP: 모든 CPU가 메모리에 균일하게 접근 (UMA) - NUMA: 로컬 메모리 접근이 원격보다 빠름, 확장성 우수 3. MESI 상태: - Modified: 수정됨, 유일한 복사본 - Exclusive: 수정 안 됨, 유일한 복사본 - Shared: 수정 안 됨, 여러 복사본 가능 - Invalid: 유효하지 않음 4. 암달의 법칙 계산: Speedup = 1 / (0.2 + 0.8/8) = 1 / (0.2 + 0.1) = 1/0.3 = 3.33배 5. Race Condition 해결: - 문제: counter++ 은 원자적이지 않음 (read-modify-write) - 해결: 뮤텍스 사용, 또는 원자적 연산 사용 (atomic_fetch_add) 6. TAS vs CAS: - TAS: 항상 1로 설정, 이전 값 반환 - CAS: 예상 값과 일치할 때만 새 값으로 설정 7. MESI 상태 전이: - Core 0 읽기: Core0=E, Core1=I - Core 1 읽기: Core0=S, Core1=S - Core 0 쓰기: Core0=M, Core1=I (무효화) - Core 1 읽기: Core0=S, Core1=S (Core0이 데이터 제공) 8. GPU가 행렬 곱셈에서 빠른 이유: - 높은 데이터 병렬성 (각 원소 독립 계산) - 수천 개의 코어가 동시 실행 - 높은 메모리 대역폭 - 행렬 곱셈이 GPU 아키텍처에 최적화됨 9. Lock-Free 알고리즘: - 장점: 락 대기 없음, 데드락 불가능 - 단점: 구현 복잡, 디버깅 어려움 - ABA 문제: 값이 A→B→A로 변해도 CAS가 성공 - 해결: 태그/버전 카운터 사용, Hazard Pointers참고 자료¶
- Computer Architecture: A Quantitative Approach (Hennessy & Patterson)
- The Art of Multiprocessor Programming (Herlihy & Shavit)
- NVIDIA CUDA Programming Guide
- Intel Optimization Manual
- Memory Consistency Models