병렬성

병렬성은 하나의 일을 여러 조각으로 나눠 같은 순간에 나란히 진행하는 성질입니다. 조각을 맡을 장치가 그 수만큼 있어야 합니다. 그래야 전체가 끝나는 시간이 줄어듭니다. 나눌 수 없는 부분은 장치를 늘려도 줄지 않습니다.

쉽고 빠른 이해

병렬성은 큰 일 하나를 조각으로 잘라 여러 장치에 한꺼번에 얹는 것입니다. 사진 만 장의 크기를 줄이는 일이라면 여덟 조각으로 잘라 여덟 장치가 천이백오십 장씩 맡습니다.

장치 하나가 만 장을 차례로 처리하면 그 시간이 전부 걸립니다. 끝나는 시간을 줄이려면 같은 순간에 여럿이 진행하는 수밖에 없습니다.

도는 모양은 셋입니다.

1. 일을 서로 기다리지 않아도 되는 조각으로 나눕니다
2. 조각을 장치 여럿에 얹어 같은 순간에 돌립니다
3. 조각이 낸 결과를 모아 하나로 합칩니다

대가가 있습니다. 나누고 합치는 품이 새로 듭니다. 조각들이 같은 데이터를 함께 고치면 서로 밟지 않게 막아야 합니다. 막는 동안은 한 줄로 서서 나란히 돌지 못합니다.

그래서 일이 작거나 조각들이 서로를 기다리면 나누기 전보다 오래 걸립니다.

상세

설거지와 닮았습니다. 여덟이 달라붙으면 그릇을 닦는 일은 여덟 배로 빨라집니다. 헹구는 수도꼭지 하나 앞에서는 다 닦인 그릇도 한 줄로 서서 차례를 기다립니다.

병렬성은 한 일을 여러 조각으로 나눠 장치 여럿이 같은 순간에 각자 한 조각씩 진행하는 성질입니다. 명령을 실행하는 이 장치를 실행 장치라고 부릅니다.

숫자 백만 개를 더하는 일이 그런 일입니다. 백만 개를 네 토막으로 잘라 넷이 각각 더합니다. 마지막에 네 개의 값을 한 번 더 더하면 끝납니다.

성립하려면 둘이 필요합니다. 일이 서로 기다리지 않는 조각으로 나뉘어야 합니다. 그 조각을 맡을 실행 장치가 둘 이상 있어야 합니다. 둘 중 하나만 없어도 나란히 도는 구간이 생기지 않습니다.

동시성과 가르는 선

이 소절은 동시성과 병렬성을 가릅니다. 두 낱말은 섞여 쓰이지만 재는 것이 서로 다릅니다.

동시성은 여러 일을 겹친 시간 구간 안에서 함께 다루는 성질입니다. 어느 한 순간에 진행되는 계산이 하나뿐이어도 됩니다. 실행 장치 하나가 일 사이를 잘게 오가며 번갈아 돌려도 동시성입니다.

병렬성은 그 "어느 한 순간"을 봅니다. 같은 순간에 진행되는 계산이 둘 이상이어야 병렬입니다. 그래서 병렬성은 실행 장치 개수에 매입니다. 동시성은 매이지 않습니다.

일 ㄱ과 일 ㄴ 둘을 시간 위에 늘어놓으면 차이가 보입니다. 아래 그림에서 위아래가 시간입니다.

flowchart TD
    subgraph 하나["실행 장치 하나 — 번갈아 돈다"]
        A1["일 ㄱ"] --> A2["일 ㄴ"] --> A3["일 ㄱ"] --> A4["일 ㄴ"]
    end
    subgraph 둘["실행 장치 둘 — 같은 순간에 돈다"]
        subgraph D1["실행 장치 1"]
            B1["일 ㄱ"] --> B2["일 ㄱ"]
        end
        subgraph D2["실행 장치 2"]
            C1["일 ㄴ"] --> C2["일 ㄴ"]
        end
    end

위쪽은 장치 하나가 ㄱ과 ㄴ을 번갈아 돌립니다. 어느 한 순간을 잘라 보면 도는 것은 언제나 하나뿐입니다. 아래쪽은 장치 둘이 같은 순간에 ㄱ과 ㄴ을 각자 진행합니다.

표의 마지막 줄이 둘을 갈라 쓰는 이유입니다. 요청 만 건을 받아 내는 서버는 대부분의 시간을 입출력 응답을 기다리는 데 씁니다. 이런 일은 동시성으로 풀립니다. 계산 자체가 오래 걸리는 일은 번갈아 돌린다고 줄지 않습니다. 나눠서 같은 순간에 돌려야 줄어듭니다.

나란히 도는 장치

같은 순간에 둘 이상을 진행하려면 실행 장치가 둘 이상 있어야 합니다. 그 장치는 한 층에만 있지 않습니다.

CPU(Central Processing Unit, 중앙 처리 장치) 안에서 명령을 실제로 실행하는 단위 하나를 코어라고 부릅니다. 요즘 칩은 코어를 여러 개 답니다. 코어가 여덟이면 같은 순간에 여덟 갈래가 진행됩니다.

표의 첫 줄에 이름이 붙어 있습니다. SIMD(Single Instruction Multiple Data, 한 명령 여러 데이터)입니다. 이 방식을 극단까지 민 장치가 GPU(Graphics Processing Unit, 그래픽 처리 장치)입니다. 작은 코어를 수천 개 달아 같은 연산을 많은 데이터에 한꺼번에 겁니다.

운영체제 쪽에서 갈래 하나를 맡는 단위는 스레드입니다. 스레드는 한 프로세스 안에서 따로 도는 실행 흐름입니다. 스레드를 여덟 개 만들어도 코어가 하나면 번갈아 돌 뿐입니다.

스케줄러가 스레드를 서로 다른 코어에 얹어야 그때부터 나란히 돕니다.

flowchart TD
    subgraph P["프로세스"]
        S1["스레드 1"]
        S2["스레드 2"]
        S3["스레드 3"]
        S4["스레드 4"]
    end
    S1 -- 스케줄러가 얹는다 --> K1
    S2 --> K2
    S3 --> K3
    S4 --> K3
    subgraph M["기계"]
        subgraph CH["칩"]
            K1["코어 1"]
            K2["코어 2"]
            K3["코어 3"]
        end
    end

스레드 1과 2는 각자 코어를 하나씩 받아 나란히 돕니다. 코어 3에 얹힌 스레드 3과 4는 그 코어 안에서 번갈아 돕니다. 같은 프로세스 안의 스레드여도 어느 코어에 얹히느냐로 갈립니다.

무엇을 나누나

무엇을 조각내느냐로 병렬성이 셋으로 갈립니다.

앞의 둘은 프로그램을 짜는 쪽이 나눕니다. 마지막 하나는 CPU 가 스스로 해서 프로그램이 손댈 것이 없습니다. 실무에서 "병렬로 돌린다"고 말할 때는 대개 앞의 둘입니다.

나눌 수 없는 부분이 만드는 천장

어느 일이든 나눌 수 없는 부분이 남습니다. 조각으로 나누는 준비, 조각의 결과를 합치는 마무리, 한 번에 하나만 들어가야 하는 구간이 그렇습니다. 이렇게 한 갈래로만 진행되는 구간을 직렬 구간이라고 부릅니다.

아래 그림은 그 구간이 어디에 놓이는지를 보입니다.

flowchart TD
    A["준비 · 조각으로 나눈다"] --> P1["조각 1"]
    A --> P2["조각 2"]
    A --> P3["조각 3"]
    P1 --> B["마무리 · 결과를 합친다"]
    P2 --> B
    P3 --> B

가운데 줄만 실행 장치 수만큼 나란히 돕니다. 위아래의 준비와 마무리는 장치를 늘려도 그대로 남는 직렬 구간입니다. 그래서 전체가 줄어드는 폭에 천장이 생깁니다.

전체 일의 열에 아홉을 나눌 수 있어도 남은 한 몫이 직렬이면, 장치를 아무리 늘려도 열 배 아래에서 멈춥니다. 남은 한 몫은 장치를 늘려도 그대로 걸리기 때문입니다. 전체 시간은 아무리 줄여도 원래의 한 몫 아래로는 못 내려갑니다. 그래서 열 배가 천장입니다.

이 천장을 암달의 법칙이라고 부릅니다. 다음 그림은 천장의 모양입니다.

xychart-beta
    title "직렬이 열에 하나일 때 빨라지는 배수"
    x-axis "실행 장치 수" ["1", "2", "4", "8", "16", "32"]
    y-axis "배수" 0 --> 10
    line [1, 1.8, 3.1, 4.7, 6.4, 7.8]

장치를 하나에서 둘로 늘릴 때는 거의 두 배로 빨라집니다. 열여섯에서 서른둘로 늘릴 때는 1.4 배밖에 안 빨라집니다. 곡선이 10 에 닿지 못하고 눕습니다.

그래서 병렬로 돌릴 때 먼저 재는 것은 실행 장치 개수가 아니라 직렬 구간의 몫입니다.

나란히 돌리며 치르는 값

병렬로 바꾸면 없던 비용이 셋 생깁니다.

첫째는 나누고 합치는 품입니다. 조각을 만들고 장치에 얹고 결과를 모으는 일에 시간이 듭니다. 일이 작으면 이 품이 얻는 것보다 커져서 나누기 전보다 오래 걸립니다.

둘째는 같은 데이터를 함께 고치는 데서 옵니다. 조각 둘이 한 값을 같이 고치면 결과가 실행 순서에 따라 달라집니다. 이것이 경쟁 상태입니다.

막으려면 한 번에 하나만 들어가게 하는 락 같은 장치를 씁니다. 스레드 ㄱ이 락을 쥐면 스레드 ㄴ은 ㄱ이 놓을 때까지 기다립니다. 락으로 감싼 구간은 그대로 직렬 구간이 됩니다.

sequenceDiagram
    participant A as 스레드 ㄱ
    participant B as 스레드 ㄴ
    participant L as 락
    A->>L: 쥔다
    A->>A: 값을 고친다
    B->>L: 쥐려고 한다
    Note over B,L: ㄱ이 놓을 때까지 ㄴ은 기다린다
    A->>L: 놓는다
    B->>L: 쥔다
    B->>B: 값을 고친다

나란히 돌리려고 나눈 일이 여기서 다시 한 줄로 섭니다. 락으로 감싼 구간이 길수록 직렬 구간의 몫이 커집니다.

셋째는 하드웨어를 나눠 쓰는 데서 옵니다. 코어들은 메모리로 가는 길을 함께 씁니다. 모든 코어가 데이터를 계속 읽어 대면 이 길이 먼저 막힙니다.

데이터를 담는 단위도 걸림돌이 됩니다. 코어는 값을 하나씩 읽지 않습니다. 정해진 크기의 덩어리로 묶어 읽어 옵니다. 그 덩어리가 캐시 라인입니다.

값은 서로 달라도 그 둘이 같은 캐시 라인에 담겨 있으면, 두 코어가 서로 최신본을 넘기느라 시간을 버립니다. 이것을 거짓 공유라고 부릅니다.

flowchart TD
    C1["코어 1"]
    C2["코어 2"]
    C1 -- 값 ㄱ을 고친다 --> V1
    C2 -- 값 ㄴ을 고친다 --> V2
    subgraph L["캐시 라인 하나"]
        V1["값 ㄱ"]
        V2["값 ㄴ"]
    end

두 코어가 고치는 값은 서로 다릅니다. 담긴 덩어리가 하나라서 그 덩어리를 통째로 주고받게 됩니다. 값을 두 덩어리로 떼어 놓으면 사라지는 손해입니다.

그래서 병렬로 나눌 만한 일이 따로 있습니다. 조각들이 서로 기다리지 않아야 합니다. 조각 하나가 나누는 품보다 충분히 커야 합니다. 직렬 구간의 몫이 작아야 합니다.

하나만 어긋나도 실행 장치를 늘린 만큼 줄지 않습니다. 늘린 만큼 실제로 줄어드는 정도를 확장성이라고 부릅니다.

관련 항목

병렬성을 실제로 내주는 하드웨어

CPU · 코어 · GPU · SIMD · 멀티코어 · 클러스터 · 캐시 라인 · 하이퍼스레딩

나란히 도는 실행 단위

스레드 · 프로세스 · 태스크 · 워커 스레드 · 스레드 풀 · 고루틴 · 스케줄러

일을 나누고 결과를 합치는 방식

데이터 병렬성 · 태스크 병렬성 · 명령어 수준 병렬성 · 병렬 처리 · fork-join · MapReduce · 파이프라이닝 · 분할 정복

나란히 돌 때 서로 밟지 않게 막는 수단

락 · 뮤텍스 · 원자적 연산 · 임계 구역 · 상호 배제 · 메모리 모델 · 불변 데이터 · 스레드 안전

나란히 돌릴 때 자주 나는 오류·장애

경쟁 상태 · 데드락 · 라이브락 · 기아 · 락 경합 · 거짓 공유

병렬로 얻는 이득의 천장을 다루는 개념

암달의 법칙 · 구스타프손의 법칙 · 확장성 · 병목 · 처리량 · 지연 · 수평 확장

병렬성과 헷갈리는 이웃

동시성 · 비동기 · 멀티태스킹 · 다중화 · 분산 처리