병렬처리(Parallel Processing)는 프로그램을 동시에 실행할 수 있는 여러 조각으로 나누어 각자 자신의 프로세서에서 실행함으로써 프로그램 수행 속도를 빠르게 한다는 개념이다. 프로그램을 N개의 프로세서에서 실행하면 하나의 프로세서 실행하는 것보다 N배까지 빨라질 수 있다.
오랫동안 특별히 디자인한 "병렬 컴퓨터(parellel computer)"에서 여러개의 프로세서를 사용할 수 있었다. 이런 경향에 따라 리눅스는 현재 하나의 컴퓨터 내에서 여러개의 프로세서가 같은 메모리와 버스 인터페이스를 공유하는 SMP 시스템(종종 "서버"로 팔리는)을 지원한다. 이 외에도 여러대의 컴퓨터를 그룹을 지어 (예를 들어 각각 리눅스를 실행하고 있는 PC들의 그룹) 네트웍으로 서로 연결하여 병렬처리 클러스터(parellel-processing cluster)를 만들 수 있다. 리눅스를 이용한 병렬 컴퓨팅의 세번째 방법은 멀티미디어 확장 명령어(multimedia instruction extensions, MMX)를 사용하여 숫자 데이터 벡터를 병렬로 처리하는 것이다. 마지막으로 리눅스 시스템을 전용으로 부속 병렬처리 엔진(attached parellel processing compute engine)의 "호스트"로 사용하는 것도 가능하다. 이 문서에서는 이 모든 접근방법들을 자세히 다루도록 하겠다.
여러개의 프로세서를 사용하는 것은 많은 연산의 처리하는 속도를 빠르게 할 수 있지만, 대부분의 응용프로그램들은 병렬처리라고 해서 아직 나아지는게 없다. 기본적으로 병렬처리는 다음 경우에 해당할 때 적당하다 :
좋은 소식은 위의 내용이 모두 해당한다면, 복잡한 계산을 수행하거나 방대한 데이터를 처리하는 프로그램의 경우, 리눅스를 이용한 병렬처리가 슈퍼컴퓨터급의 성능을 발휘할 수 있다는 것이다. 더군다나 그것도 당신이 이미 가지고 있을 값싼 하드웨어를 사용하여 할 수 있다. 보너스로 병렬 리눅스 시스템이 바쁘게 병렬 작업을 수행하고 있지 않을 때는 다른 용도로 쉽게 사용할 수 있다.
병렬처리가 당신이 바라던 것이 아니더라도 어느정도 소소한 성능향상을 바란다면, 여전히 할 수 있는 일이 몇가지 있다. 예를 들어, 순차처리를 하는 프로그램들은 빠른 프로세서를 사용하고, 메모리를 추가하고, IDE 디스크를 빠른 와이드 SCSI 디스크로 바꾸는 등의 방법을 사용할 수 있다. 당신이 관심을 가지는 것이 이거라면 바로 성능 문제장으로 넘어가고, 그렇지 않으면 계속 읽어주기 바란다.
병렬 처리가 여러분이 원하는 것이 아니더라도 여러분이 적어도 가장 온건한 성능 개선을 하고자 한다면 여러분이 할 수 있는 것들이 아직 남아 있다. 예를 들어서 여러분은 좀 더 빠른 프로세서, 메모리 추가, IDE 디스크를 빠른 와이드 SCSI로 바꾸는 등의 일을 함으로써 시퀀셜 프로그램들의 성능을 개선할 수 있다. 이것이 여러분이 관심이 있는 모든 것이라면 섹션 성능에 대한 논란로 점프하라; 그렇지 않다면 계속 읽기 바란다.
여러 해 동안 많은 시스템에서 병렬처리를 사용해왔지만, 대부분의 컴퓨터 사용자들은 여전히 좀 낯설 것이다. 따라서 병렬처리의 여러 방법들을 살펴보기 전에, 몇가지 일반적으로 사용하는 용어들에 익숙해지는 것이 필요하다.
SIMD는 모든 프로세서가 똑같은 연산을 동시에 실행하지만, 각 프로세서가 자신만의 데이터에 대해 연산을 수행할 수 있는 병렬 실행 모델을 가리킨다. 이 모델은 배열의 모든 원소에 대해서 똑같은 연산을 수행하는 개념에 자연히 들어맞으며, 따라서 종종 벡터나 배열 처리와 관련된다. 모든 연산이 본래 동기화되어있으므로, SIMD 프로세서간의 상호작용은 대체로 쉽고 효과적으로 구현할 수 있다.
MIMD는 각 프로세서가 근본적으로 독립적으로 동작하는 병렬 실행 모델을 가리킨다. 이 모델은 프로그램을 기능적인 토대에 바탕하여 병렬 실행할 수 있는 것으로 쪼개는 개념에 대부분 자연스럽게 들어맞는다. 예를 들어, 한 프로세서는 새로운 엔트리를 그래픽 화면으로 만들고 있을 때, 다른 프로세서는 데이터베이스 파일을 갱신하는 것이다. 이는 SIMD 보다는 더 유연한 모델이지만, 한 프로세서의 연산과 다른 프로세서의 연산의 상대순위가 바뀌는 시간 변화로 인하여 프로그램이 실패할 수 있는 경주 상황(race conditions)라는 악몽의 디버깅을 감수해야 한다.
SPMD는 MIMD의 제한된 버전으로 모든 프로세서가 같은 프로그램을 실행하는 것이다. SIMD와는 달리, SPMD 코드를 실행하는 각 프로세서는 프로그램을 실행 과정에서 다른 제어 흐름 과정을 따를 수 있다.
통신 시스템의 대역폭은 데이터 전송을 시작한 때부터 어떤 단위의 시간동안 전송할 수 있는 데이터의 최대크기이다. 직렬 연결에서는 대역폭을 대개 baud 또는 비트/초 (b/s)로 표시하는데, 일반적으로 이것의 1/10에서 1/8이 바이트/초 (B/s)에 해당한다. 예를 들어, 1200 baud 모뎀은 약 120 B/s의 속도로 전송을 하고, 반면에 155 Mb/s ATM 네트웍 연결은 이보다 130000배 가량 빠른, 약 17 MB/s의 속도로 전송을 한다. 큰 대역폭은 프로세서 사이에 큰 데이터 블럭을 효율적으로 전송할 수 있게 한다.
통신 시스템의 지체(latency)는 보내고 받는 소프트웨어의 오버헤드를 포함하여, 한 객체를 전송하는데 걸리는 최소한의 시간을 말한다. 지체는 병렬처리에서 매우 중요한데, 병렬 실행으로 속도를 향상시킬 수 있는 코드 조각의 최소 실행 시간인, 최소 유용 알갱이 크기(minimum useful grain size)를 결정하기 때문이다. 기본적으로 코드 조각을 실행하는 시간이 결과값을 전송하는 시간(즉, 지체)보다 짧을 때, 그 코드 조각을 결과값을 필요로 하는 프로세서에서 직렬로 실행하는 것이 병렬로 실행하는 것보다 더 빠르다. 직렬로 실행하는 것은 통신 오버헤드가 없기 때문이다.
메시지 전달은 병렬 시스템 내부에서 프로세서간의 상호작용을 위한 모델이다. 일반적으로, 메시지는 한 프로세서에 있는 소프트웨어에서 만들어지고, 상호연결 네트웍을 통하여 다른 프로세서로 전달되어, 여기서 이를 받아 메시지 내용에 따라 동작하게 된다. 각 메시지를 처리하는 오버헤드(지체)가 클 수 있지만, 대개 각 메시지가 어느 정도 크기의 정보를 가질 수 있는지에는 거의 제한을 두지 않는다. 그래서 메시지 전달은 큰 대역폭을 초래하기도 하며, 한 프로세서에서 다른 프로세서로 큰 데이터 블럭을 전달하는 것을 매우 효율적인 방법으로 처리도록 되어 있다. 그렇지만, 값비싼 메시지 전달 연산의 필요를 최소화할 수 있도록, 병렬 프로그램에 있는 자료구조는 프로세서 간에 널리 퍼져 있어서 각 프로세서가 참조하는 대부분의 데이터는 자신의 지역 메모리 상에 있도록 해야 한다. 이러한 작업을 데이터 배치(data layout)라고 한다.
공유 메모리는 병렬 시스템 내부에서 프로세서간의 상호작용을 위한 모델이다. 리눅스를 실행하고 있는 멀티프로세서 펜티엄 컴퓨터같은 시스템은 물리적으로 프로세서간에 하나의 단일 메모리를 공유한다. 따라서 한 프로세서가 공유 메모리에 값을 기록하면, 다른 어떤 프로세서든지 이 값을 직접 읽을 수 있다. 이와 달리 논리적인 공유 메모리는 각 프로세서가 자신만의 메모리를 가지며, 지역 메모리에 없는 메모리를 참조하면 이를 해당하는 프로세서간 통신으로 변환해줌으로써 구현한다. 이들 각각의 공유 메모리 구현은 일반적으로 메시지 전달보다 사용하기 쉽게 되어 있다. 물리적인 메모리 공유는 큰 대역폭을 가지며 지체가 적지만, 이는 단지 여러 프로세서가 동시에 버스에 접근하려하지 않을 때만이다. 따라서 데이터 배치(data layout)는 여전히 성능에 큰 영향을 미칠 수 있으며, 캐시 효과 등은 어떻게 배치하는 것이 가장 좋은 것인지 결정하기 힘들게 만든다.
메시지 전달과 공유 메모리 모델에서 통신은 모두 하나의 단일 프로세서에서 시작한다. 이와 반대로 집합 함수 통신은 본래 모든 프로세서 그룹이 서로 작용할 수 있는 병렬 통신 모델이다. 이런 작용의 가장 간단한 것은 장벽 동기화(barrier synchronization)로, 개별 프로세서들이 그룹에 있는 모든 프로세서가 장벽에 도달하길 기다리는 것이다. 개별 프로세서가 장벽에 도착하면서 부수효과(side effect)로 데이터를 출력하면, 통신 하드웨어는 모든 프로세서에서 수집한 값들에 임의의 함수를 적용한 결과값을 각 프로세서에게 전달할 수 있다. 예를 들어, 그 결과값은 "어떤 프로세서가 해를 찾았느냐"는 질문의 대답일 수도, 각 프로세서에서 온 값들의 합일 수도 있다. 지체(latency)는 매우 적겠지만, 하나의 프로세서가 차지하는 대역폭 역시 적은 경향이 있다. 전통적으로 이 모델은 데이터 값을 분산하기보다는 병렬 실행을 제어하는데 주로 사용된다.
이는 집합 함수(aggregate function)의 다른 이름으르, 대부분 다중 메시지 전달 연산을 이용하여 구축된 집합 함수를 가리키는데 사용된다.
SMP는 일련의 프로세서들이 서로 대등하게 함께 동작하여, 어떤 작업 조각이든지 어떤 프로세서에서든 똑같이 실행될 수 있는 운영체제 개념을 말한다. 대체로 SMP는 MIMD와 공유메모리를 결합한 것이다. IA32 계열에서 SMP는 일반적으로 MPS(Intel Multi-Processor Specification, 인텔 멀티프로세서 규약)와 호환된다는 것을 의미한다. 앞으로는 이것은 "Slot 2"를 의미하게 될 것이다...
SWAR는 하나의 레지스터를 여러개의 정수 항목으로 쪼개고 레지스터 너비의 연산을 사용하여 이들 항목들에 SIMD 병렬 계산을 수행한다는 개념을 가리키는 일반적인 용어이다. k-bit 레지스터와 데이터 통로, 함수 단위를 갖는 기계가 있을 때, 오래전부터 보통의 레지스터 연산을 사용하여 n개의 k/n 비트 항목 값에 SIMD 병렬 연산을 할 수 있다고 알려져왔다. 이런 방식의 병렬성은 보통의 정수 레지스터를 사용하여 구현할 수 있지만, 많은 고성능 마이크로프로세서들은 멀티미디어 위주 작업에 이 기법의 성능을 높이기 위해 최근 특별 명령어들을 추가했다. 인텔/AMD/Cyrix의 MMX(MultiMedia eXtension)를 비롯하여, 디지털(Digital) Alpha의 MAX(MultimediA eXtensions), 휴렛- 팩커드(Hewlett-Packard) PA-RISC의 MAX(Multimedia Acceleration eXtensions), MIPS의 MDMX(Digital Media eXtension, "Mad Max"라고 발음한다), 선(Sun) SPARC의 V9 VIS(Visual Instruction Set) 등이 있다. MMX에 동의한 세 회사를 제외하고, 이들 확장 명령어들은 대충은 비슷하지만, 서로 호환되지는 않는다.
부속 프로세서는 본질적으로 특별한 유형의 계산 속도를 가속하기 위한 호스트 시스템에 연결된 특별한 목적을 가진 컴퓨터이다. 예를 들어, PC에 있는 많은 비디오와 오디오 카드는 제각기 일반 그래픽 연산과 오디오 DSP(Digital Signal Processing, 디지털 신호 처리) 속도를 높이도록 디자인된 부속 프로세서를 가지고 있다. 또한 배열에 대한 산술 연산 속도를 빠르게 하기 위한, 넓은 범위의 부속 배열 프로세서(attached array processor)들이 있다. 많은 상업용 슈퍼컴퓨터들은 실제로 워드스테이션 호스트와 부속 프로세서로 되어 있다.
RAID는 디스크 I/O의 신뢰성과 대역폭을 늘리는 간단한 기술이다. 여기에는 여러가지 서로 다른 변형이 있지만, 모두 두가지 핵심 개념을 공유하고 있다. 먼저, 각 데이터 블럭은 n+k 디스크 드라이브 그룹으로 줄을 지어, 각 드라이브는 단지 데이터의 1/n 만큼 읽고 쓰기만 하지만, 각 드라이브 대역폭의 n배의 대역폭을 가지게 된다. 두번째로, 여분으로 데이터를 기록하여, 한 디스크 드라이브가 실패하더라도 데이터를 복구할 수 있도록 한다. 이것은 매우 중요한데, 그렇지 하지 않으면 n+k 드라이브 중 하나가 실패한 경우 전체 파일 시스템이 날라갈 수 있기 때문이다. http://www.dpt.com/uraiddoc.html에 가면 RAID 전반에 관한 좋은 개요가 있다. 리눅스 시스템에서의 RAID 옵션에 대한 정보는 http://linas.org/linux/raid.html에서 찾을 수 있다. 전문 RAID 하드웨어 지원과는 별도로, 리눅스는 하나의 리눅스 시스템이 여러개의 디스크를 호스트하는 소프트웨어 RAID 0, 1, 4, 5도 지원한다. 자세한 것은 소프트웨어 RAID mini-HOWTO와 다중 디스크 튜닝(Multi-Disk Tuning) mini-HOWTO를 참조하기 바란다. 클러스터에 있는 여러 기계에 있는 디스크 드라이브들의 RAID는 직접적으로 지원되지 않는다.
IA32는 실제로 병렬처리하고는 관련이 없고, 단지 일반적으로 인텔 386 프로세서와 호환된는 명령어 집합을 가지는 프로세서들의 부류를 가리킨다. 기본적으로, 286 다음에 나온 모든 인텔 x86 프로세서는 IA32의 특징인 32비트 플랫 메모리 모델(flat memory model)과 호환된다. AMD와 Cyrix 역시 수많은 IA32 호환 프로세서를 만든다. 리눅스가 주로 IA32 프로세서에서 발전해왔으며, IA32가 상품시장의 중심에 있기 때문에, PowerPC나 Alpha, PA-RISC, MIPS, SPARC 등의 다른 프로세서와 구별하여 IA32라는 용어를 사용하는 것이 편리하다. 곧 출시될 IA64(EPIC, Explicitly Parallel Instruction Computing, 명시된 병렬 명령 계산을 지원하는 64비트 프로세서)는 아마도 복잡한 문제가 되겠지만, 처음 나오게 될 IA64 프로세서인 머세드(Merced)는 1999년까지는 제품이 나오진 않을 예정이다.
많은 병렬 슈퍼컴퓨터 회사들이 사라지면서, COTS는 병렬 계산 시스템의 필요조건으로 일반적으로 다루어지게 되었다. 아주 이론적으로 하면, PC를 사용하는 유일한 COTS 병렬처리 기법은 SMP Windows NT 서버와 여러 MMX Windows 응용프로그램같은 걸로 만들어진 것이다. COTS 개념의 기반은 사실상 개발 시간과 비용의 최소화이다. 따라서 더 유용하고, 더 일반적인, COTS의 의미는 적어도 대부분의 서브시스템은 기성 제품 시장에서 이득을 얻어야 하지만, 다른 기술들은 효율적으로 사용될 수 있는 곳에 사용해야 한다는 것이다. 대부분의 경우, COTS 병렬처리는 노드는 기성 PC이지만 네트웍 인터페이스와 소프트웨어는 어느정도 맞춤으로 만든 클러스터를 가리킨다. 대개 실행할 리눅스와 응용프로그램 코드는 자유롭게 구할 수 있지만 (copyleft이거나 public domain인), 문자 그대로 COTS는 아니다.
이 HOWTO에서 언급하고 있는 여러가지 병렬 프로그래밍 접근 방법들의 사용법을 좀 더 잘 이해할 수 있도록, 예제 문제를 하나 다루어보도록 하자. 비록 간단한 병렬 알고리즘이지만, 여러 다른 병렬 프로그래밍 시스템을 시연하는데 사용해왔던 알고리즘을 선택함으로써, 각 접근방법을 비교하고 대조하는 것이 조금 더 쉬울 것이다. M.J.Quinn의 책 (Parallel Computing Theory And Prictice (병렬 계산 이론과 실습)); 2판, McGraw Hill, New York, 1994에서는, 다양한 서로 다른 병렬 슈퍼컴퓨터 프로그래밍 환경(예를 들어, nCUBE 메시지 전달, 순차 공유 메모리(sequent shared memory))을 시연하기 위해, Pi 값을 계산하는 병렬 알고리즘을 사용하고 있다. 이 HOWTO에서, 우리도 똑같은 기본 알고리즘을 사용하도록 하자.
이 알고리즘은 x의 정사각형 아래에 있는 영역을 합하여 Pi의 근사값을 계산한다. 순수한 순차 C 프로그램으로 만든다면 알고리즘은 다음과 비슷할 것이다.
#include <stdlib.h>;
#include <stdio.h>;
main(int argc, char **argv)
{
register double width, sum;
register int intervals, i;
/* get the number of intervals */
intervals = atoi(argv[1]);
width = 1.0 / intervals;
/* do the computation */
sum = 0;
for (i=0; i<intervals; ++i) {
register double x = (i + 0.5) * width;
sum += 4.0 / (1.0 + x * x);
}
sum *= width;
printf("Estimation of pi is %f\n", sum);
return(0);
}
그렇지만 이 순차 알고리즘은 쉽게 "곤란한 병렬(embarrassingly parallel)" 구현이 된다. 이 영역들은 간격(intarval)별로 쪼개고, 프로세서가 몇개라도 프로세서간에 상호작용할 필요 없이, 자기에게 할당된 간격을 독립적으로 합할 수 있다. 일단 지역별로 합이 계산되었다면, 전체합을 만들기 위해 서로 더해야 한다. 이 과정은 프로세서간에 어느정도 레벨의 조정과 통신을 필요로 한다. 마지막으로 전체 합은 Pi값의 근사치가 되어 한 프로세서에서 이를 출력하게 된다.
이 HOWTO에서는, 이 알고리즘의 여러가지 병렬 구현이 나오며, 각각은 다른 프로그래밍 방법을 사용한다.
이 문서의 나머지는 다섯개 부분으로 나뉘어져 있다. 2, 3, 4, 5장은 리눅스를 이용한 병렬처리를 지원하는 세가지 다른 유형의 하드웨어 구성을 다루고 있다.
이 문서의 마지막 장은 위에서 다룬 접근 방법들에 속하지 않는, 리눅스를 이용한 병렬처리에서 일반적으로 가지고 있는 관심들을 다룬다.
이 문서를 읽을 때 아직 우리가 모든 것들을 다 테스트해보진 못했다는 것과 여기서 다루는 내용의 많은 부분은 "아직 연구중인 특성"("생각했던 것처럼 잘 동작하지 않는다"는 것을 더 좋게 표현한 말이다 :-)이라는 것을 명심하기 바란다. 그렇지만 리눅스를 이용한 병렬처리는 현재 유용하며, 점점 더 많은 그룹들이 이를 더 잘 사용하기 위해 작업을 진행중이다.
이 HOWTO 문서를 작성한 사람은 Hank Dietz 박사로 현재는 West Lafayette 47907-1285에 있는 Purdue 대학의 전기 및 컴퓨터 공학(Electrical and Computer Engineering)의 부교수(Associate Professor)이다. Dietz는 리눅스 문서화 프로젝트(Linux Documentation Project, LDP)의 지침에 따라 이 문서에 대한 권한을 갖는다. 이 문안을 정확하고 공정하게 만들기 위해서 많은 노력을 했지만, Dietz나 Purdue 대학 모두 어떠한 문제나 에러에 대한 책임이 없으며, Purdue 대학은 여기서 다룬 어떠한 작업이나 결과물도 보증하지 않는다.