7.1 의존 관계 분석하기
•
작업 의존 관계 그래프(task dependency graph)를 그려서 의존 관계를 찾는다.
만약 이 프로그램을 스레드를 사용해 구현했다면 육수를 끓이고, 채소를 써는 등 네 작업을 각각 네 개의 스레드에 맡길 수 있으며 이들을 동시에 실행할 수 있다.
•
작업 분해(task decomposition)와 데이터 분해(data decomposition)으로 나누어 볼 수 있다.
7.2 작업 분해
“문제를 한꺼번에 할 수 있는 여러 일로 나누려면 어떻게 해야 하는가?”
7.3 작업 분해: 파이프라인 패턴
•
가장 흔한 패턴은 파이프라인 처리(pipeline processing)이다.
•
데이터 → 단계1 → 단계2 → 단계3 → 결과
◦
각 단계는 서로 다른 처리 자원에서 실행된다.
◦
각 처리 자원은 자신이 맡은 단계의 다음 단계를 맡은 처리 자원과 통신한다.
•
예) 세탁, 건조, 정리(빨래개기)의 절차를 가지고 여러개의 빨래감을 처리한다고 가정해보자.
◦
세탁기가 첫 번째 빨래감을 처리하고, 두 번째 빨래감을 처리하는 동안, 건조기는 첫 번째 빨래감을 처리하고, 건조가 끝나면 정리를 할 수 있다.
◦
이러한 방식을 코드로 구현하려면
1.
독립적으로 실행되는 작업을 만든다.
2.
작업끼리 정보를 교환할 수 있도록 한다.
◦
쓰레드와 큐를 활용하면 두 가지 모두를 해결할 수 있다.
◦
각각 걸리는 시간이 20분, 10분, 5분이라고 가정했을 때 총 35분이 걸리지만 파이프라인 처리를 적용하면 총 75분만에 모든 빨래 절차를 끝낼 수 있다.
•
파이프라인 처리는 데이터 분해 같은 다른 분해 기법과 함꼐 결합해 쓰이기도 한다.
7.4 데이터 분해
해당 모델은 한 집합에 담긴 여러 요소를 같은 연산으로 한꺼번에 적용할 때 동시성을 발휘
“서로 독립적으로 작업을 수행하려면 데이터를 어떻게 나눠야 할까?”
⇒ 데이터 분해는 작업의 유형이 아닌 데이터를 대상으로 한다. 데이터를 청크(chunk)라는 몇 개의 덩어리로 나누는 과정이다.
SIMD 구조와 비슷하다. 그런 만큼 이런 부류의 작업에는 SIMD 구조가 가장 적합하다.
7.4.1 반복문 수준의 병렬성
for, while, for-each 등의 유형에 완벽하게 맞아 떨어짐
•
여러개의 파일을 읽어 각 파일에 특정 문자열을 찾는 경우, 스레드 N개가 각기 다른 1/N의 데이터 조각을 동시에 작업할 수 있다.
7.4.2 맵 패턴
맵 패턴은 함수형 프로그래밍 언어에서 쓰이던 개념을 기초로 하는데, 어떤 집합의 여러 요소에 동일한 연산을 적용할 때 쓰인다. 모든 개별 작업은 입력 데이터를 출력 데이터로 변환하는 역할만 하며 프로그램의 상태를 변경시키지 않는다. (처치 곤란 병렬 문제는 분해된 작업 간에 동기화나 정보 교환이 필요 없는 문제를 말한다.)
정말 많이 쓰이는 패턴이지만, 이보다 더 널리 쓰이는 패턴이 있는데..
7.4.3 포크/조인 패턴
대개의 애플리케이션에는 순차적인 부분과 동시적인 부분이 섞여 있다.
•
포크 단계(fork step)
◦
데이터를 여러 뭉치로 나눈 다음, 각 뭉치를 독립적인 작업에서 처리한다.
•
조인 단계(join step)
◦
모든 의존 작업의 결과가 나올 때까지 기다린 다음, 최종 결과를 계산한다. 동기화 지점.
7.4.4 맵/리듀스 패턴
•
맵 단계는 모든 입력이 동일한 함수에 입력해 결과를 얻는 단계로 맵 패턴과 같고, 그 뒤에 이어지는 리듀스 단계는 데이터를 종합하는 단계다.
•
데이터를 나누어 처리하며 결과를 하나의 값이 될 때까지 결합하는 점에서 포크/조인 패턴과 동일하지만, 조금 더 독립적이다.
•
단일 컴퓨터의 경계를 넘어 대규모 데이터를 여러 대의 컴퓨터를 동원해 처리하는 형태까지 확장할 수 있다.
•
맵 단계와 리듀스 단계 중 한쪽이 없을 수 있따는 점도 포크/조인 패턴과 다른 점이다.
7.5 분해된 작업의 크기 결정하기
문제를 잘게 분해했다면 작은 작업의 수가 늘어난다. 그리고 작업이 프로세서에 균등하게 분배되므로 병렬성이 증가하며 전체적인 시스템 성능이 향상된다. 그리고 단일 작업의 크기가 작고 빨리 수행된다.
하지만 작업의 수가 늘어나면서 정보 교환이 증가하고 이로 인한 오버헤드가 증가한다.
데이터를 분해할 때는 가능한 한 작게 작업을 만들어야 한다. 크기가 작은 작업을 만들면 싫든 좋든 병렬 실행을 늘릴 수밖에 없어서 유리하다. 필요하다면 작업 응집을 통해 일부 작업을 합쳐 통신 비용을 낮추거나 성능을 개선한다.
