병렬처리와 Flynn 분류

사진 100장의 밝기를 모두 올리는 작업은 사진끼리 서로 상관이 없으므로, 여러 코어에 나누어 맡기면 빨리 끝납니다. 반면 다음 계산이 바로 앞 계산의 결과를 기다려야 하는 작업은 코어가 아무리 많아도 마음대로 나눌 수 없습니다. 여러 처리를 같은 시간에 실제로 겹쳐 실행하는 것을 병렬 처리(parallel processing)라고 하며, 무엇을 나눌 수 있는지는 작업 사이의 의존 관계와 함께 쓰는 자원이 정합니다. 이 글에서는 병렬 처리를 하는 컴퓨터의 종류를 나누고, 작업을 나눌 때 생기는 문제를 다룹니다.

명령어 흐름과 데이터 흐름으로 나누기

Flynn 분류(Flynn's taxonomy)는 1966년 Michael Flynn이 제안한 방법으로, 컴퓨터를 동시에 처리하는 명령어 흐름의 수와 데이터 흐름의 수로 네 가지로 나눕니다. 여기서 흐름은 프로그램 파일의 수가 아니라, 동시에 진행되는 명령어의 줄기와 그 명령어가 다루는 데이터의 줄기를 말합니다.

SIMD의 대표적인 예는 CPU 안의 벡터 명령어로, 한 명령어로 8개나 16개의 수에 같은 덧셈을 한꺼번에 합니다. GPU는 수많은 스레드가 같은 명령어를 함께 실행하는 SIMT(single instruction, multiple threads)라는 방식으로 설명하는데, 스레드마다 분기가 갈리는 경우를 다루는 방법까지 있어서 SIMD라는 이름 하나로는 다 설명되지 않습니다.

더 깊이: 벡터 길이를 고정하지 않은 RISC-V 벡터 확장

앞의 예처럼 벡터 명령어 하나가 다루는 원소 수가 정해져 있으면, 레지스터가 더 넓은 CPU의 이점을 쓰려면 코드를 다시 짜야 합니다. RISC-V의 벡터 확장은 이 폭을 구현에 맡깁니다. RISC-V 벡터 규격에 따르면 벡터 레지스터 하나의 비트 수 VLEN은 구현이 정하는 상수로, 8 이상인 2의 거듭제곱이면서 $2^{16}$을 넘지 않으면 됩니다. 응용 프로세서용 V 확장은 여기에 128비트 이상이라는 조건을 더합니다.

그래서 프로그램은 한 번에 처리할 원소 수를 미리 정하지 않습니다. 처리할 전체 원소 수를 vsetvli 같은 설정 명령에 알려 주면, 하드웨어가 이번 반복에서 처리할 원소 수를 정해 vl과 목적 레지스터에 돌려주고, 프로그램은 그만큼 처리한 뒤 남은 수로 다시 반복합니다. 규격은 이렇게 원소를 몇 개씩 나누어 반복하는 스트립 마이닝(strip mining)을 이식성 있게 지원한다고 설명하며, 정해진 조건을 지키면 같은 바이너리가 VLEN이 다른 하드웨어 스레드에서도 실행된다고 밝힙니다. 다만 벡터 상태가 살아 있는 실행 문맥을 VLEN이나 ELEN이 다른 하드웨어 스레드로 옮겨 실행을 이어 갈 수는 없습니다.

파이프라인, SIMD, 멀티코어는 서로 다른 질문이다

파이프라인은 한 명령어 흐름 안에서 여러 명령어의 단계를 겹칩니다. SIMD는 명령어 하나를 여러 데이터에 적용하고, 멀티코어는 서로 다른 명령어 흐름을 동시에 실행합니다. 이 세 가지는 하나만 고르는 선택지가 아니라서, 오늘날의 CPU는 코어마다 파이프라인과 SIMD 장치를 갖추고, 그런 코어를 여러 개 넣은 멀티코어입니다.

동시성(concurrency)과 병렬성(parallelism)도 구별해야 합니다. 동시성은 여러 작업이 함께 진행 중인 상태를 다루는 설계로, 코어 하나가 작업들을 번갈아 실행해도 성립합니다. 병렬성은 여러 작업이 실제로 같은 순간에 실행되는 것입니다. 코어가 둘이라고 해서 프로그램 하나가 저절로 두 배 빨라지지 않는 것은, 프로그램이 작업을 나누어 두 코어에 맡기도록 만들어져 있어야 하기 때문입니다.

작업을 나눌 수 있는가

길이 8인 배열의 모든 원소에 3을 더하는 작업은 원소마다 따로 할 수 있으므로, 두 작업자가 앞 네 개와 뒤 네 개를 나누어 맡으면 됩니다. 모든 원소의 합은 조금 다릅니다. 각 작업자가 자기 몫의 부분 합을 구할 수는 있지만, 마지막에 두 부분 합을 하나로 합치는 단계가 따로 필요합니다. 그런데 두 작업자가 하나의 합계 변수에 각자 바로 더하려고 하면 문제가 생깁니다.

data = [1, 2, 3, 4, 5, 6, 7, 8]
print([x + 3 for x in data])
left, right = data[:4], data[4:]
partial = [sum(left), sum(right)]
print(partial, sum(partial))

total = 0
a_read = total
b_read = total
total = a_read + partial[0]
total = b_read + partial[1]
print(total)

[4, 5, 6, 7, 8, 9, 10, 11]
[10, 26] 36
26

첫 줄은 원소마다 따로 3을 더한 결과이고, 둘째 줄은 두 작업자가 각자 구한 부분 합 10과 26을 마지막에 더한 36입니다. 셋째 부분은 두 작업자가 공유 변수 total에 "읽기, 더하기, 쓰기"를 각자 하는데, 그 순서가 A가 읽고, B가 읽고, A가 쓰고, B가 쓰는 차례로 섞인 경우를 코드로 그대로 옮긴 것입니다. 두 작업자 모두 0을 읽었으므로, A가 쓴 10은 B가 쓴 26에 덮여 사라지고 결과는 36이 아니라 26입니다. 이렇게 한쪽의 갱신이 다른 쪽에 덮여 없어지는 것을 갱신 손실(lost update)이라고 합니다.

실제 스레드라면 이 섞임은 실행할 때마다 다르게 일어나므로, 같은 프로그램이 어떤 때는 맞고 어떤 때는 틀립니다. 그래서 공유 변수를 함께 고칠 때는 한 번에 한 작업자만 고치도록 잠그거나, 읽기와 쓰기를 쪼갤 수 없는 하나의 동작으로 하는 원자적(atomic) 연산을 쓰거나, 처음부터 각자의 부분 합을 따로 두었다가 마지막에 합칩니다. 여러 작업자가 같은 메모리 위치에 동기화 없이 접근하고 그 가운데 적어도 하나가 쓰는 앞의 상황을 데이터 경쟁(data race)이라고 하며, 운영체제 교재의 동기화 문제의 본질에서 자세히 다룹니다. Flynn 분류는 컴퓨터의 구조를 나누는 말일 뿐, 이런 데이터 경쟁을 해결해 주지는 않습니다.

정리

• Flynn 분류는 명령어 흐름과 데이터 흐름의 수로 SISD, SIMD, MISD, MIMD를 나누며, 흐름은 프로그램 파일의 수가 아닙니다.
• SIMD는 같은 연산을 여러 데이터에 한꺼번에 하고, MIMD는 서로 다른 명령어 흐름을 함께 실행하며, GPU는 SIMT로 따로 설명합니다.
• 파이프라인, SIMD, 멀티코어는 함께 쓰이는 서로 다른 기법이고, 동시성은 여러 작업이 함께 진행 중인 것, 병렬성은 실제로 같은 순간에 실행되는 것입니다.
• 원소마다 따로 하는 작업은 쉽게 나눌 수 있고, 합계처럼 결과를 모으는 작업은 부분 결과를 합치는 단계가 필요합니다.
• 공유 변수를 여러 작업자가 동시에 고치면 갱신을 잃을 수 있으므로, 잠금, 원자적 연산, 따로 모았다가 합치기 같은 방법이 필요합니다.

연습 문제

1. 분류와 안전한 합치기

장치 A는 연산 하나를 원소 8개에 한꺼번에 적용하고, 장치 B는 코어 두 개가 서로 다른 프로그램을 실행합니다. 두 장치를 Flynn 분류로 나누세요. 두 작업자가 합계를 구하면서 각자의 결과를 하나의 변수에 잠금 없이 더하는 것이 안전한지 판단하고, 안전한 방법을 설명하세요.

2. 앞의 결과에 의존하는 계산

x[i] = x[i-1] + a[i]처럼 앞에서부터 누적하는 합, 곧 누적 합을 두 작업자가 배열의 앞 절반과 뒤 절반으로 나누어 그대로 계산하면 왜 틀리나요? 나누어 계산할 방법이 있나요?

3. 파이프라인이 있는 코어 하나

파이프라인으로 여러 명령어를 겹쳐 실행하는 코어 하나는 Flynn 분류에서 무엇에 속하나요?

작업을 병렬로 나누기 전에는 작업끼리 서로의 결과를 기다리는지, 같은 데이터를 함께 고치는지를 먼저 적어 보세요. 다음 글 공유 메모리·NUMA·일관성에서는 여러 코어가 같은 메모리를 쓸 때 거리와 값이 어떻게 문제가 되는지 다룹니다.