6. Multicore Programming

[ MIT OpenCourseWare : Multicore Programming ]
 
https://youtu.be/dx98pqJvZVk?si=2cdZid4RgwTfai_u

 
 

Part 1. 왜 멀티코어 프로세서가 등장했는가

1. Multicore processor의 기본 구조

멀티코어 프로세서에서는 여러 개의 core가 같은 chip 위에 배치되어 있고, 이 core들은 shared memory에 접근할 수 있습니다.
보통 각 core는 private cache를 가지고 있고, 여러 core가 공유하는 last-level cache도 있습니다. 예를 들어 L3 cache가 여기에 해당합니다. 또한 모든 core는 동일한 memory controller를 통해 메인 메모리에 접근하고, I/O에도 접근할 수 있습니다.
하지만 오랫동안 chip에는 core가 하나뿐이었습니다. 그렇다면 왜 오늘날에는 multicore processor가 일반적일까요? 왜 반도체 회사들은 여러 processor core를 한 chip에 넣기 시작했을까요?
답은 크게 두 가지입니다.

1. Moore's Law
2. Clock frequency scaling의 종료

2. Moore’s Law와 clock frequency scaling의 한계

Moore’s Law는 chip에 넣을 수 있는 트랜지스터 개수가 시간이 지남에 따라 증가한다는 관찰입니다. 대략 2년마다 chip에 들어갈 수 있는 트랜지스터 개수가 두 배가 된다는 것입니다.
동시에 과거에는 single core의 clock frequency를 계속 높일 수 있었습니다. 하지만 2004년에서 2005년 즈음부터 더 이상 clock frequency를 계속 올리기 어려워졌습니다.

슬라이드에는 시간에 따른 트랜지스터 개수와 processor clock frequency가 함께 그려져 있습니다. y축은 log scale입니다. 파란 선은 Moore’s Law를 나타냅니다. chip에 넣을 수 있는 트랜지스터 개수는 약 2년마다 두 배씩 늘어났고, 이 추세는 꽤 오랫동안 지속되었습니다.
반면 clock frequency는 2000년대 초반까지 꾸준히 증가하다가, 그 이후 거의 평평해졌습니다. 대략 4GHz 부근에서 한계에 도달했습니다. 오늘날 processor를 사더라도 보통 clock speed는 4GHz 근처, 혹은 그보다 조금 낮은 수준입니다.
 
Q) 그렇다면 2004년에서 2005년 사이에 무슨 일이 있었을까요?
 
Moore’s Law가 가능했던 이유는 transistor가 점점 작아졌기 때문입니다. transistor가 작아지면, transistor를 동작시키는 데 필요한 voltage도 낮출 수 있습니다. voltage를 낮출 수 있으면 같은 power density를 유지하면서 clock frequency를 높일 수 있습니다.
반도체 제조사들은 2004년 무렵까지 이 방식으로 clock frequency를 계속 높였습니다.
하지만 transistor가 충분히 작아지고 동작 voltage가 충분히 낮아지자, leakage current 문제가 커졌습니다. 전류가 새어나가기 시작했고, reliable switching을 유지하면서 voltage를 더 낮추기 어려워졌습니다.
voltage를 더 이상 낮출 수 없다면, 같은 power density를 유지한 채 clock frequency를 높일 수 없습니다.

Intel이 2004년 multicore processor를 만들기 시작할 때의 power density 그래프를 보면 이 문제를 직관적으로 볼 수 있습니다. 만약 clock frequency를 계속 매년 25~30%씩 올렸다면 power density가 계속 증가했을 것입니다.
그 결과 power density는 원자로 수준에 도달하고, rocket nozzle 수준까지 올라가며, 결국 태양 표면의 power density에 가까워집니다. 물론 chip의 power density가 태양 표면과 같아진다면, 그것은 더 이상 chip이 아니라 불덩어리에 가깝습니다.
즉, clock frequency를 계속 높이는 길은 막혔습니다.

하지만 Moore’s Law 덕분에 transistor 수는 계속 늘어나고 있었습니다. 그래서 반도체 회사들은 남는 transistor를 single core의 frequency를 높이는 데 쓰는 대신, 여러 core를 chip에 넣는 데 사용하기 시작했습니다.
2004년 즈음부터 chip당 core 수가 1보다 커지기 시작했고, 이후 Moore’s Law 세대가 지날 때마다 chip에 들어가는 core 수도 증가할 수 있었습니다.

Part 2. Abstract Multicore Architecture

3. Chip Multiprocessor, CMP

이제 multicore architecture를 단순화한 모델을 봅시다.
여러 processor가 있고, 각각 cache를 가지고 있습니다. 슬라이드에서는 cache를 달러로 표시했습니다. 보통 각 processor에는 private cache(L1, L2)가 있고, 여러 processor가 공유하는 last-level cache(L3)도 있습니다.
processor들은 network에 연결되어 있고, 이 network를 통해 main memory에 접근합니다. 모든 processor는 동일한 shared memory에 접근할 수 있습니다. I/O를 위한 별도 network가 있을 수도 있지만, 슬라이드에서는 단순화를 위해 하나의 network처럼 그려져 있습니다.
또한 이 network는 같은 system 안의 다른 multiprocessor와 연결될 수도 있습니다.
이런 추상적인 multicore architecture를 Chip Multiprocessor, 줄여서 CMP라고 합니다. 오늘 살펴볼 architecture가 바로 이 CMP입니다.

Outline

오늘 강의의 구성은 다음과 같습니다.
먼저 shared-memory multicore machine에서 발생하는 hardware challenge를 봅니다. 특히 cache coherence protocol을 살펴봅니다. 그다음 software solution을 봅니다. 여러 core를 활용해서 parallel program을 작성하기 위한 concurrency platform을 살펴봅니다.
오늘 다룰 concurrency platform은 다음과 같습니다.

1. Pthreads
2. Intel Threading Building Blocks, TBB
3. OpenMP
4. Cilk Plus

 

Pthreads는 병렬 실행을 위한 low-level API입니다. Microsoft 환경에서는 Win API threads가 비슷한 역할을 합니다.
TBB는 concurrency를 위한 library solution입니다.
OpenMP와 Cilk Plus는 언어 확장에 가까운 linguistic solution입니다.
이 수업에서는 주로 Cilk Plus 계열의 concurrency platform을 사용할 것입니다.

Part 3. Shared memory와 cache coherence

4. Cache가 동작하는 방식

먼저 cache가 어떻게 동작하는지 봅시다.
main memory의 어떤 위치에 x = 3이라는 값이 있다고 합시다. 어떤 processor가 x를 load하려고 하면, 그 processor는 main memory에서 값을 읽어 자기 cache로 가져옵니다. 동시에 register에도 값을 load합니다.
이 값을 cache에 보관하는 이유는, 가까운 미래에 다시 x에 접근할 때 main memory까지 가지 않고 자기 cache에서 빠르게 읽기 위해서입니다.
다른 processor가 x를 load하면 어떻게 될까요? 그 processor도 main memory에서 값을 읽어 자기 cache에 가져오고, register에 load합니다.
사실 항상 main memory까지 갈 필요는 없습니다. 값이 다른 processor의 cache에 있다면, main memory 대신 다른 processor의 cache에서 가져올 수도 있습니다. 때로는 그것이 main memory에 접근하는 것보다 더 저렴합니다.
 
이제 두 번째 processor가 다시 x를 load한다고 합시다. 이미 자기 cache에 값이 있으므로 main memory나 다른 processor의 cache에 갈 필요가 없습니다.

그런데 어떤 processor가 x를 store해서 값을 바꾸면 어떻게 될까요? 예를 들어 한 processor가 x = 5를 저장한다고 합시다. 그러면 그 processor는 자기 cache에 x = 5를 씁니다.
이제 첫 번째 processor가 다시 x를 load하려고 합니다. 첫 번째 processor의 cache에는 아직 x = 3이 있습니다. 그래서 cache에서 값을 읽으면 3을 얻습니다.
 
Q) 문제가 무엇일까요?
A) cache is stale.
첫 번째 processor의 cache에 들어 있는 x = 3은 stale value입니다. 다른 processor가 이미 x를 5로 업데이트했기 때문입니다. 따라서 첫 번째 processor의 cache에 있던 x 값은 invalid입니다.
이 문제가 cache coherence 문제입니다.
멀티코어 하드웨어의 중요한 과제 중 하나는 여러 processor의 cache에 있는 값들이 update 이후에도 일관성을 유지하도록 보장하는 것입니다.
 

MSI Protocol

Cache coherence 문제를 해결하는 기본 protocol 중 하나가 MSI protocol입니다.
MSI protocol에서는 각 cache line에 state를 붙입니다. 가능한 state는 세 가지입니다.

M: Modified
S: Shared
I: Invalid

 

이 state는 memory location 단위가 아니라 cache line 단위로 관리됩니다. 모든 memory location마다 state를 저장하는 것은 너무 비싸기 때문에, cache line 단위로 관리.
이 수업에서 사용하는 cache line 크기는 64 바이트로 가정.
이 값은 성능 추정을 할 때 중요한데, 어림잡은 계산을 할 때 cache line 크기를 알아야 더 정확한 추정이 가능하기 때문입니다.
 

MSI의 세 가지 state를 살펴봅시다.
 
M, Modified
해당 cache block이 수정되었음을 의미합니다. 어떤 cache가 block을 Modified 상태로 가지고 있다면, 다른 cache들은 그 block을 M이나 S 상태로 가지고 있을 수 없습니다.
 
S, Shared
해당 block이 공유되어 있음을 의미합니다. 다른 cache들도 같은 block을 Shared 상태로 가지고 있을 수 있습니다.
 
I, Invalid
해당 cache block이 유효하지 않음을 의미합니다. 사실상 cache에 없는 것과 같습니다.
 
Cache coherence 문제를 해결하려면, 어떤 cache가 memory location을 수정할 때 다른 cache들에게 그 값이 이제 stale하다고 알려야 합니다. 즉 다른 cache에 있는 해당 cache line의 복사본을 invalid로 바꿔야 합니다.
 

Store

2번째 프로세서가 y=5로 store.
1, 4번 프로세서의 해당 값은 I(Invalid) state로 변경됨.
 
Q) 어차피 다른 cache들에게 invalid로 바꾸라고 알려야 한다면, 그냥 새 값 y = 5를 보내주면 안 되나요?
A) 실제로 그렇게 하는 protocol도 있습니다. 하지만 여기서 설명하는 MSI는 가장 기본적인 protocol이며, 이 protocol에서는 단순히 invalidation을 보냅니다.
 

Load

값을 load할 때는 먼저 자기 cache line이 M 또는 S 상태인지 확인합니다. M이나 S 상태라면 그 값을 바로 읽을 수 있습니다. 하지만 I 상태이거나 cache에 없으면, 다른 processor의 cache나 main memory에서 block을 가져와야 합니다.
실제 machine에는 MSI 외에도 여러 protocol이 있습니다. 예를 들어 MESI, MOESI 같은 protocol이 있고, 그 중에는 상표권이 있는 프로토콜도 있습니다. 이 protocol들은 매우 복잡하며, 올바르게 구현하기 매우 어렵습니다.
흥미롭게도 formal verification의 초기 성공 사례 중 하나가 cache coherence protocol의 correctness를 증명하는 것이었습니다.
 
Q) 두 processor가 동시에 같은 값을 수정하려고 하면 어떻게 되나요?
A) 하드웨어는 둘 중 하나가 먼저 일어나도록 처리합니다. 먼저 값을 수정한 processor는 다른 cache의 복사본을 invalidate합니다. 그다음 두 번째 processor가 값을 수정하면 다시 다른 복사본들을 invalidate합니다.
많은 processor가 같은 값을 수정하려고 하면 invalidation storm이 발생합니다. 하드웨어 전체에 invalidation message가 대량으로 돌아다니게 됩니다. 이는 큰 성능 병목이 될 수 있습니다.
각 processor가 값을 수정할 때마다 다른 processor들에게 알려야 하기 때문에, 여러 processor가 같은 값을 계속 수정하면 거의 quadratic behavior을 하게 됩니다.
하드웨어는 여전히 correctness를 보장합니다. 즉 최종적으로 어떤 processor의 write가 적용될지는 정해집니다. 하지만 parallel code를 작성할 때 이런 성능 문제를 알고 있어야 합니다.
 
Q) 이 protocol들은 전부 hardware에서 동작하나요?
A) 네. cache coherence protocol은 hardware에서 구현됩니다. 컴퓨터 구조 과목을 들으면 이런 protocol의 상세한 variant들을 더 많이 배우게 됩니다. 이 수업에서는 세부 구현을 모두 알 필요는 없습니다. 다만 높은 수준에서 무엇이 일어나는지 이해하면, parallel program에서 왜 성능 병목이 생기는지 설명할 수 있습니다.
 

Part 5. Pthreads

Pthreads는 threading을 위한 표준 API이며, Unix 기반 machine에서 지원됩니다. Microsoft 환경의 대응물은 Win API threads입니다.
Pthreads는 ANSI와 IEEE 표준으로 정의되어 있지만, 오늘날에는 그냥 Pthreads라고 부릅니다.
Pthreads는 일종의 do-it-yourself concurrency platform입니다. 병렬 프로그래밍의 assembly language 같은 존재입니다.
 
Pthreads는 특수한 non-C semantics를 가진 함수 library로 구성됩니다. 순수 C 코드만으로는 어떤 부분을 병렬로 실행해야 하는지 표현하기 어렵기 때문에, Pthreads는 concurrency를 표현하기 위한 함수들을 제공합니다.
 
각 thread는 processor의 abstraction처럼 동작합니다. 이 thread들은 실제 machine resource 위에 multiplex됩니다. 즉 생성한 thread 수가 실제 processor 수와 같을 필요는 없습니다. processor 수보다 thread가 많으면 time-sharing으로 실행됩니다. single core에서도 여러 Pthreads thread를 실행할 수 있습니다.
 
모든 thread는 shared memory(공유 메모리)를 통해 통신합니다. 모든 thread는 같은 memory view에 접근합니다.
Pthreads library function은 inter-thread coordination protocol을 감춰주는 것을 제공합니다. 이런 protocol을 직접 올바르게 구현하기는 매우 어렵기 때문에 프로그래머가 직접할 필요는 없습니다.
 

Coarsening

병렬 프로그램에서는 parallelism을 너무 잘게 쪼개면 overhead가 커집니다. 입력이 충분히 작으면 병렬로 실행하지 않고 sequential하게 실행하는 편이 좋습니다.
→ Task의 n이 적다면 sequential하게 수행하는 것이 오히려 더 빠를 수 있음. 따라서 병렬화로 성능 상 이점을 볼 수 있는 값인 n을 넘겼을 때 병렬화하도록 하자.
 

Pthreads의 문제

Pthreads 구현의 주요 문제는 다음과 같습니다.

1) thread 생성 overhead가 큽니다. thread 생성에는 보통 10^4 cycles 이상이 듭니다. 따라서 thread 하나가 충분히 많은 일을 해야 overhead를 amortize할 수 있습니다. 이 때문에 Pthreads는 coarse-grained concurrency에 적합합니다.
이를 완화하는 기법으로 thread pool이 있습니다. 여러 thread를 미리 만들어두고, 작업이 필요할 때 그 thread를 가져다 쓰는 방식입니다. thread pool 안의 thread들은 일을 기다리고 있습니다.
 
2) scalability 문제가 있습니다. 앞의 Fibonacci Pthreads 코드는 두 core에서도 최대 약 1.5배 speedup 정도만 얻습니다. 왜 2배가 아니라 1.5배일까요? 두 병렬 call의 작업량이 다르기 때문입니다. 하나는 fib(n-1)이고 다른 하나는 fib(n-2)입니다. 이 둘의 비율은 황금비, 약 1.6입니다. overhead까지 고려하면 실제 speedup은 약 1.5 정도가 됩니다.
더 많은 core를 활용하려면 코드를 다시 작성해야 하고, 코드가 더 복잡해집니다.
 
3) modularity가 나쁩니다. Fibonacci logic이 하나의 함수 안에 깔끔하게 encapsulate되어 있지 않습니다. 일부 logic은 왼쪽의 fib 함수에 있고, 일부는 오른쪽 main function에 흩어져 있습니다. 이렇게 되면 유지보수가 어렵습니다. Fibonacci logic을 조금 바꾸려면 여러 위치를 함께 수정해야 합니다.
 
4) argument marshaling이 복잡합니다. n-1을 args.input에 넣고, 결과를 args.output에서 꺼내야 합니다. 이런 코드는 지저분하고 error-prone합니다.
 
→ Pthreads는 병렬 프로그래밍의 어셈블리같은 존재. 스레드를 생성할 때마다 마샬링을 수동으로 해줘야 하는데, 이는 프로그래밍에서 컴파일러가 없던 시절 어셈블리어를 다룰 때와 비슷하다. 함수를 호출할 때마다 argument marshaling을 수동으로 줬기 때문이다.
이런 방식은 에러가 발생하기도 쉽고, 런타임에 스레드 생성 오버헤드도 있는 등 위 문제를 해결하기 위해선 멀티코어 프로그래밍을 위한 플랫폼을 쓰는 것이 낫다.

Part 6. Intel Threading Building Blocks, TBB

TBB Overview

다음은 Threading Building Blocks, 줄여서 TBB입니다.
TBB는 library solution입니다. Intel이 개발했으며, native threads 위에서 동작하는 C++ library입니다.
내부 구현은 thread를 사용하지만, programmer는 thread를 직접 다루지 않습니다. 대신 programmer는 task를 지정합니다. 그리고 이 task들은 MIT의 Charles Leiserson 연구에서 영감을 받은 work-stealing algorithm을 사용해 thread들 사이에 자동으로 load-balanced됩니다.
TBB의 초점은 performance입니다. Pthreads로 작성해야 하는 코드보다 TBB 코드가 더 단순합니다.