병렬 컴퓨팅 설계의 기준: Flynn 분류와 Amdahl의 법칙

병렬성을 나누는 위치가 시스템의 성격을 바꾼다

병렬 컴퓨팅은 큰 문제를 작은 부분 문제로 분해하고, 여러 처리 유닛이 이를 함께 수행하도록 구성하는 계산 방식이다. 실행 시간을 줄이고 단위 시간당 처리 작업 수를 늘리는 데 쓰이며, 단일 프로세서로 감당하기 어려운 규모의 계산을 다룰 수 있다. 고가의 슈퍼컴퓨터 대신 저가 프로세서를 다수 활용하는 비용 효율성도 이 방식의 목적에 포함된다.

병렬성은 어느 계층에 적용하느냐에 따라 다르게 나타난다.

수준	설명	예시
비트 수준	데이터 비트를 병렬로 처리	32비트에서 64비트 ALU
명령어 수준	여러 명령어를 동시 실행	파이프라인, 슈퍼스칼라
데이터 수준	동일 연산을 다수 데이터에 적용	SIMD, 벡터 연산
태스크 수준	독립적인 태스크를 병렬 실행	멀티스레딩, 분산 처리

⤢✕

명령어와 데이터 흐름으로 구분하는 Flynn 분류

마이클 플린(Michael J. Flynn)은 1966년에 명령어 스트림과 데이터 스트림의 개수를 기준으로 컴퓨터 아키텍처를 구분하는 체계를 제안했다. 여기서 명령어 스트림은 프로세서가 실행하는 명령어의 흐름이며, 데이터 스트림은 그 명령어가 처리하는 데이터의 흐름이다. 각 스트림은 단일(Single) 또는 다중(Multiple)으로 구분된다.

분류	명령어 스트림	데이터 스트림	설명
SISD	Single	Single	단일 명령어, 단일 데이터
SIMD	Single	Multiple	단일 명령어, 다중 데이터
MISD	Multiple	Single	다중 명령어, 단일 데이터
MIMD	Multiple	Multiple	다중 명령어, 다중 데이터

⤢✕

SISD: 하나의 명령어와 하나의 데이터

SISD에서는 하나의 제어 유닛이 하나의 처리 유닛으로 명령어를 전달하고, 처리 유닛은 단일 데이터 스트림을 처리한다. 전통적인 폰 노이만 아키텍처가 이 구조에 해당한다. 명령어는 순차적으로 실행되고, 단일 ALU와 하나의 프로그램 카운터를 사용하므로 동작은 결정론적이다.

초기 마이크로프로세서, 기본 형태의 단일 코어 CPU, 전통적인 메인프레임이 구현 예시다.

명령어 스트림: I1 → I2 → I3 → I4 → ...
     ↓
[처리 유닛]
     ↓
데이터 스트림: D1 → D2 → D3 → D4 → ...

SIMD: 같은 연산을 여러 데이터에 적용하는 구조

SIMD는 하나의 명령어를 여러 처리 유닛에 동시에 전달한다. 각 처리 유닛은 서로 다른 데이터를 대상으로 같은 연산을 수행한다. 데이터 병렬성을 활용하며, 단일 제어 유닛과 다수의 ALU로 동기식 병렬 실행을 구성한다. 규칙적인 데이터 구조에서 특히 적합하다.

벡터 프로세서(Cray-1), GPU의 SIMT(Single Instruction, Multiple Thread), CPU의 SIMD 확장인 SSE·AVX·NEON, 배열 프로세서가 이 구조의 예다. 픽셀 단위 이미지 처리, 선형 대수의 행렬 연산, FFT와 필터링 같은 신호 처리, 입자 시스템 물리 시뮬레이션에도 활용된다.

명령어 스트림:      I1
             ↓  ↓  ↓  ↓
        [PU0][PU1][PU2][PU3]
             ↓  ↓  ↓  ↓
데이터 스트림: D0  D1  D2  D3

⤢✕

MISD: 하나의 데이터를 다른 명령어로 처리하는 경우

MISD에서는 여러 처리 유닛이 각각 다른 명령어를 실행하면서 동일한 데이터 스트림을 처리한다. 실용적인 구현은 드물고 주로 이론적 분류로 남아 있다. 시스톨릭 배열(Systolic Array)의 일부 형태, 내결함성을 위한 다중화 시스템, 파이프라인의 변형으로 해석할 수 있는 구조에서 제한적으로 언급된다.

명령어 스트림: I1, I2, I3, I4
             ↓   ↓   ↓   ↓
        [PU0][PU1][PU2][PU3]
             ↓   ↓   ↓   ↓
데이터 스트림:     D (단일)

MIMD: 독립적으로 실행되는 처리 유닛

MIMD는 여러 프로세서가 서로 다른 명령어 스트림을 실행하고, 각자의 데이터 스트림을 처리하는 아키텍처다. 비동기적 실행과 태스크 수준 병렬성을 지원하는 범용적이고 유연한 구조지만, 프로세서 사이의 통신이 필요하다.

메모리 구성에 따라 공유 메모리와 분산 메모리로 나뉜다.

구분	공유 메모리(Shared Memory)	분산 메모리(Distributed Memory)
메모리 구조	단일 주소 공간	프로세서별 독립 메모리
통신 방식	공유 변수	메시지 패싱
확장성	제한적	우수
프로그래밍	상대적 용이	복잡
예시	SMP, NUMA	클러스터, MPP

멀티코어 프로세서, SMP(Symmetric Multiprocessor), NUMA(Non-Uniform Memory Access), 분산 컴퓨팅 클러스터, MPP(Massively Parallel Processor)가 구현 예시다.

⤢✕

순차 구간이 정하는 성능의 상한

진 암달(Gene Amdahl)은 1967년에 병렬화로 얻을 수 있는 최대 성능 향상의 이론적 한계를 제시했다. 핵심은 간단하다. 프로그램에 남아 있는 순차적 부분이 전체 성능 향상을 제한한다.

전체 실행 시간에서 병렬화 가능한 비율을 P, 병렬화할 수 없는 순차적 비율을 S라고 하면 다음 관계가 성립한다.

P + S = 1

N개의 프로세서를 사용할 때 최대 속도 향상(Speedup)은 다음과 같다.

Speedup = 1 / (S + P/N)

N이 무한대로 증가할 때의 최대 속도 향상은 순차 구간에 의해 결정된다.

Speedup_max = 1 / S

예를 들어 프로그램의 80%가 병렬화 가능하면(P = 0.8, S = 0.2), 프로세서 수를 늘려도 속도 향상과 효율은 다음처럼 변한다.

프로세서 수(N)	Speedup	효율(Speedup/N)
1	1.00	100%
2	1.67	83%
4	2.50	63%
8	3.33	42%
16	4.00	25%
64	4.71	7%
무한대	5.00	0%

⤢✕

이 법칙은 프로세서 수를 늘리는 것만으로는 이상적인 선형 확장에 도달할 수 없음을 보여 준다. 설계에서는 알고리즘의 순차 구간을 줄이고, 효율성(Efficiency)과 비용 대비 성능을 함께 판단해야 한다.

문제 크기와 시스템 비용까지 포함해 해석하기

Amdahl의 법칙은 문제 크기가 고정되어 있다고 가정하며, 통신 오버헤드와 메모리 대역폭 제한, 로드 밸런싱 이슈를 반영하지 않는다. 이 한계를 다른 관점에서 다루는 모델이 Gustafson의 법칙이다. 이 법칙은 문제 크기가 프로세서 수에 따라 증가한다고 가정한다.

Speedup = S + P * N = S + (1 - S) * N

이는 고정 시간 모델이며 약확장성(Weak Scaling) 분석에 적합하고, 대규모 병렬 시스템에서는 낙관적 전망을 제공한다.

⤢✕

병렬 프로그램을 구성할 때 보는 선택지

데이터 분해(Data Decomposition)는 데이터를 나누어 각 프로세서에 할당하는 방식이다. 공간적 데이터를 나누는 도메인 분해와 작업별 데이터를 분할하는 기능적 분해가 여기에 속한다. 태스크 분해(Task Decomposition)는 작업 자체를 독립 태스크로 쪼개며, 단계별 분할인 파이프라인과 작업 분배 모델인 마스터-워커가 대표적이다.

프로그래밍 모델도 메모리 구조에 맞춰 달라진다.

공유 메모리 모델: OpenMP는 지시어 기반 병렬화에, Pthreads는 명시적 스레드 프로그래밍에, TBB는 태스크 기반 병렬화에 사용된다.
분산 메모리 모델: MPI는 메시지 패싱 인터페이스이며, PGAS는 분할 전역 주소 공간 모델이다.
하이브리드 모델: MPI + OpenMP와 GPU 오프로딩이 있다.

성능은 실행 시간만으로 판단하지 않는다.

지표	정의	이상적 값
Speedup	T1 / TN	N
Efficiency	Speedup / N	1 (100%)
Scalability	N 증가 시 Efficiency 유지	선형
Throughput	단위 시간당 작업 수	최대화

실제 병렬화에는 통신과 계산의 오버헤드가 따라온다. 통신 측면에서는 프로세서 간 데이터 전송 시간, 동기화 대기 시간, 네트워크 지연이 발생한다. 계산 측면에서는 작업 분배와 수집, 중복 계산, 로드 불균형을 고려해야 한다. Flynn 분류로 처리 구조를 파악하고 Amdahl의 법칙으로 순차 구간의 한계를 확인한 뒤, 이 비용을 함께 다루는 것이 병렬 시스템 설계의 출발점이다.