병렬계산 1. Basics

Serial과 Parallel의 차이는 간단히, serial computing은 하나의 코어에서 명령을 순차적으로 실행하는 것. 한 번에 하나의 task를 처리함. Parallel은 작업 (instruction or data)을 여러 부분으로 나눠서 여러 코어에서 동시에 처리하는 방식.

Parallel을 쓰는 가장 큰 이유는 계산 시간을 줄이는 것. 2005년 이후로 물리적 한계로 인해 CPU의 클럭을 높이는 것이 매우 어려워져서, 코어 여러 개를 쓰는 것으로 발전해왔다. 또 다른 이유는 여러 작업이 동시에 진행되고 동시에 끝나도록 하는 concurrency를 병렬 계산을 통해 구현할 수 있다. 그리고 대량의 데이터에 대한 작업을 하는 경우에, 컴퓨터의 메모리에 제한이 있을 경우 데이터를 여러 컴퓨터에 나눠서 병렬계산을 하면 메모리 사용량을 여러 컴퓨터로 분산할 수 있다.

Von Neumann 구조는 메모리에 프로그램이랑 데이터를 저장해놓고, 필요할 때마다 CPU로 가져와서 계산을 하는 것을 말한다.

멀티 코어 CPU에는 여러 개의 코어가 있고 코어마다 L1 캐시가 있고 보통 L2 캐시는 코어 두 개당 하나가 있다. L3 캐시는 보통 컴퓨터마다 하나씩. 캐시보다 메인 메모리는 보통 access 시간이 10배정도 느리고, 캐시보다 10배 빠른 레지스터는 CPU의 일부이다.

Flynn’s classical taxonomy에 따르면 instruction과 data가 single인지 multiple인지에 따라서 병렬 컴퓨터를 네 개로 구분할 수 있다. SISD는 serial computer이고, SIMD는 벡터 파이프라인이나 GPU에서 사용되는 것이고 MIMD가 가장 일반적인 병렬 컴퓨터의 유형.

컴퓨터가 일을 하는 최소 단위, 즉 병렬로 나눴을 때 나눠지는 최소 단위를 task라고 한다.

Pipelining은 한 unit이 일을 마치고 다음 unit에 넘겨주면 그 unit은 넘겨진 것에 대해 일을 하고 또 다음으로 넘겨주는 것이 이어지는 컨베이어벨트 같은 방식. 동시에 unit들이 일을 하긴 하는 거. Vector processor는 pipeline이 하나인데 array processor나 GPU는 pipeline이 여러 개라서 효율이 좋음.

Shared memory에서는 모든 task가 같은 메모리에 직접 연결돼 있음. Symmetric multi-processor (SMP)는 모든 코어가 메인 메모리랑 IO를 공유하고 그것을 엉키지 않게 bus가 조절해주는 하드웨어 구조.

Distributed memory는 코어마다 메모리가 따로 있거나, 컴퓨터 여러 개를 붙여놨을 때 메모리를 따로 쓰는 것. 다른 메모리에 있는 데이터를 주고받을 때는 network를 쓰는데, 이거는 버스보다 훨씬 느림.

한 캐시에서 그 데이터를 바꾼다면 데이터가 바뀌었다는 것을 메인 메모리나 다른 캐시에서는 모르는데, 이 데이터를 동일하게 유지하는 게 캐시 coherence. 공유 메모리 구조에서는 중요한 의미가 있다.

공유 메모리 구조 중에서 uniform memory access (UMA)는 모든 CPU가 메모리 접근에 대해서 동등한 위치에 있음. 이 예시가 SMP. Non-uniform memory access (NUMA)는 CPU와 메모리의 위치에 따라서 접근 시간이 차이나는 것. SMP 여러 개를 물리적으로 연결한 게 대표적 예시이다. 그런데 이거는 여전히 한 컴퓨에 안에 여러 CPU와 메모리가 있는 거라서 데이터 통신은 네트워크가 아니라 버스로 한다. 그리고 NUMA를 구성하는 여러 노드의 캐시 간에 cache coherence를 유지해주는 것이 CC-NUMA이고, 클러스터를 이용해 미니 슈퍼 컴퓨터를 만들 때 CC-NUMA를 많이 쓴다.

Distributed memory 구조에서는 각 CPU가 독립적인 local 메모리를 갖기 때문에, 메모리 간의 통신을 위해서는 네트워크가 필요하다.

하이브리드 메모리 구조는 노드 하나는 cache coherent SMP와 같은 shared memory 구조이고, 이 노드들을 붙여놔서 전체적으로는 distributed memory인 구조. 슈퍼컴퓨터나 클러스터에 갖아 많이 쓰이는 구조.

여기서 내 컴퓨터는 어떤 구조일까? 먼저 shared memory인지 distributed memory인지는 쉽게 판단할 수 있다. 내가 쓰고 있는 데스크탑은 컴퓨터 여러 개를 네트워크로 연결시켜놓지도 않았고, 램 여러 개를 CPU마다 연결해서 그 램을 네트워크로 연결해놓지도 않았다. 그러면 일단 당연히 shared memory이다. 그리고 UMA인지 NUMA인지는 리눅스에서 lscpu 명령어를 통해 얻은 다음과 같은 내용으로 확인할 수 있다.

Architecture:                         x86_64

CPU op-mode(s):                       32-bit, 64-bit

Byte Order:                           Little Endian

Address sizes:                        46 bits physical, 48 bits virtual

CPU(s):                               20

On-line CPU(s) list:                  0-19

Thread(s) per core:                   2

Core(s) per socket:                   10

Socket(s):                            1

NUMA node(s):                         1

NUMA 노드가 하나인 걸 봐서, 메모리 자체가 하나이고, 그러면 반드시 UMA인 것이다.

그런데 내가 쓰는 계산용 클러스터 컴퓨터에서는 다음으로 구성되어있다.

Architecture:        x86_64

CPU op-mode(s):      32-bit, 64-bit

Byte Order:          Little Endian

CPU(s):              192

On-line CPU(s) list: 0-191

Thread(s) per core:  1

Core(s) per socket:  96

Socket(s):           2

NUMA node(s):        2

Vendor ID:           AuthenticAMD

CPU family:          25

Model:               17

Model name:          AMD EPYC 9654 96-Core Processor

Stepping:            1

CPU MHz:             2400.008

BogoMIPS:            4800.01

Virtualization:      AMD-V

L1d cache:           32K

L1i cache:           32K

L2 cache:            1024K

L3 cache:            32768K

NUMA node0 CPU(s):   0-95

NUMA node1 CPU(s):   96-191

일단 NUMA고, 192개의 코어 중 96개의 코어씩 다른 메모리에 연결돼 있다는 것이다. 그러면 병렬계산을 할 때, 다른 코어에 연결된 메모리에 접근할 일이 없도록 한 메모리에 연결된 코어만 쓰는 것이 속도는 빠르겠다. 이거는 처음 알았다. 컴퓨터를 쓰면서도 뭔가 그렇지 않을까 라는 생각은 해봤는데, 내용을 배우고 나니까 역시 아는 만큼 보인다. 그런데 사실 어차피 UMA든 NUMA든 버스로 통신하는 거라서 그렇게까지 속도 차이가 나려나 싶긴 하다.

이러한 병렬계산을 할 때 중요한 것이 결국 speed-up이다. 정의는 serial로 계산했을 때 걸린 시간을 parallel로 계산했을 때 걸린 시간으로 나눈 것이다. 그리고 Efficiency는 speedup을 프로세서의 개수로 나눈 값이다. Speedup과 efficiency에 관련된 여러 요소들이 있다.

먼저 granularity는 한 task의 계산 시간과 통신 시간의 비율이라고 정의된다. 전체 일을 작은 task 여러 개로 나누면 한 task의 계산 시간을 줄어들겠지만 통신 시간은 늘어난다. 따라서 이는 granularity가 작은 것이고, 이처럼 small tasks가 여러 개 있는 경우를 fine-grained라고 한다. 반대로 large tasks가 적은 개수만큼 있는 경우를 coarse-grained라고 한다.

또 speedup에 영향을 미치는 요소 중 하나는 parallel overhead이다. 병렬계산을 하지 않았다면 발생하지 않았을 시간이 overhead인 것이다. 이론상 overhead가 전혀 없다면 efficiency는 1이어야겠지만 이는 당연히 불가능하다. Overhead의 예시는 task start and termination, communication, synchronization, software overhead by libraries or OS 등이 있다. 이 중 synchronization은 여러 task가 서로 시간을 맞추기 위해 기다리면서 발생하는 시간이다. 그리고 embarrassingly parallel problems라는 것이 있는데, 문제 자체가 본질적으로 parallel하고 문제를 구성하는 모든 task가 독립적이어서 task 간의 통신이 없거나 매우 적은 것을 말한다. 그런데 이름이 당황스럽게 병렬인 문제인 것이 당황스럽다.

그리고 speedup에 대한 Amdahl’s law라는 것이 있다. 코드에서 병렬화 가능한 부분의 비율이 P이고 프로세서가 n개일 때 overhead를 무시하면 speedup S=1/(P/n+1-P)라는 것이다. 그런데 overhead는 반드시 있으니까 S<(1(P/n+1-P)라고 쓰기도 한다. 여기서 n이 무한이 되면 maximum speedup S는 1/(1-P)가 된다. 그런데 n이 무한일 수는 없으니까, maximum speedup의 99%가 언제 되는지를 보려면 다음의 식을 고려하면 된다. 1/(P/n+1-p)=99/(100(1-P)). 이걸 정리하면 n은 99P(1-P)에서 이론상 최대 speedup의 99%를 달성할 수 있다. Embarrassingly parallel problem에서는 이론상 S=n이 된다.

그런데 embarrassingly parallel problem에서도, parallel overhead를 무시하더라도 S<n이다. 그 이유는 load imbalance인데, 이상적으로는 모든 task가 모든 코어에서 동시에 끝나야 하겠지만, 소프트웨어적인 이유든 하드웨어적인 이유든 그렇지 않기 때문이다.

또 speedup과 관련된 개념으로 scalability라는 것이 있다. 이는 계산 자원을 늘렸을 때 speedup을 증가시키는 능력이다. 이론상 코어의 개수가 증가하면 speedup이 계속 증가해야겠지만, 실제로는 maximum speedup에 도달하고 나서 speedup을 오히려 감소한다. 이러한 현상의 이유는 알고리즘도 있고 병렬계산에 필요한 라이브러리도 있지만, 하드웨어적인 원인이 중요하다. 하드웨어적인 원인이란 통신, 메모리, CPU frequency 등을 말하는 것이다. 스케일링은 두 가지가 있는데, 먼저 strong scaling은 전체 문제의 크기가 고정된 상태에서 빠른 속도로 계산을 하는 것을 목표로 하는 것이고 weak scaling은 코어당 문제의 크기를 고정한 상태에서 같은 시간 동안 더 큰 문제를 푸는 것을 목표로 하는 것이다.

Weak scaling의 경우에, 같은 시간 안에 최대한 많은 문제를 푸는 것이 목표이기 때문에 전체 실행 시간을 1로 고정하면 serial로 실행하는 시간은 1-P이고 parallel로 실행하는 시간이 P인데, 이 parallel로 실행하는 것을 serial로 실행한다면 걸리는 시간이 nP이다. 따라서 speedup은 S=1-P+nP=1+(n-1)P가 된다.

이러한 parallel programming의 실제 모델은 몇 가지가 있는데, 먼저 한 프로세서에서 하나의 task를 실행시키는 shared memory without threads가 있다. 이 경우에는 메모리에 asynchronous하게 접근하고 예시는 POSIX shared memory API가 있다. 또한 shared memory 구조에서 사용하는 것 중 하나의 thread에서 하나의 task를 실행하지만, 하나의 코어가 여러 개의 thread를 가질 수 있는 multi-threading이 있다. OpenMP가 대표적 예시이다. Distributed memory에서 사용하는 것은 task들이 데이터를 서로 공유하는 Message passing이 있고 MPI가 대표적 예시이다. Data parallel model은 동일 연산을 데이터를 분할해서 수행하는 것이다. Hybrid는 이 중 두 개 이상을 함께 사용하는 것을 말한다.

마지막으로 실제 병렬 프로그램을 쓸 때는, 먼저 문제를 이해하고 serial program을 써본다. 그리고 그 serial program이 병렬화 가능한지 아닌지를 판단하고, 가장 시간이 많이 소모되는 hot spot을 찾는다. 그리고 병렬화될 수 없는 느린 부분인 bottleneck을 찾고, 병렬 알고리즘을 선택한다. 실행하고 디버깅한 후 성능을 평가하고 최적화하면 된다.

이 과정에서 데이터를 병렬화할 것인지, 기능을 병렬화할 것인지를 선택해야 한다. 또한 동기화 타입을 선택해야 하는데, barrier는 먼저 끝난 task가 다른 task들을 기다리는 방식이고, lock/block은 특정 데이터를 잠시동안 하나의 task만 사용하도록 제한하는 것이다. Synchronous 통신은 MPI에서 사용되는 것이다.

병렬 프로그램을 작성하는 과정에서 data dependencies를 고려해야 한다. 두 개의 계산이 같은 메모리를 공유하는데, 하나는 데이터를 write하고 다른 하나다 read하든 write하든 데이터에 접근하면 두 연산은 data dependency가 있다. 연산들 사이에 data dependencies가 없는 경우에 병렬화될 수 있다.

그리고 load balance를 얻기 위한 방법 중, 모든 코어에 같은 양을 분배하는 equal partition이 있고, 계산 시간을 예상하고 다시 분배하는 dynamic redistribution이 있고, 스케줄러에 작업을 올려놓고, 어떤 코어에서 task가 끝나면 스케줄러가 그 코어에 작업을 주는 scheduler 기반 방법이 있다. 또한 load balance는 granularity와도 관련이 있는데, fine-grained 된 경우에 load balance를 얻기 쉽지만 overhead가 크다. 반면 coarse grained 된 경우에 통신이 적지만 synchronization으로 인한 overhead가 발생한다.