· KLDP.org · KLDP.net · KLDP Wiki · KLDP BBS ·
Linuxdoc Sgml/Parallel-Processing-HOWTO

Linux Parallel Processing HOWTO

Linux Parallel Processing HOWTO

Hank Dietz, pplinux@ecn.purdue.edu

v980105, 5 January 1998 1장-2장 이호, (i@flyduck.com), 3장 이후 선정필, (simje@maninet.com) 1999년 12월 3일, 최종 업데이트: 2000년 4월 18일
병렬처리(Parallel Processing)는 프로그램을 동시에 실행할 수 있는 여러 조각으로 나누어 각자 자신의 프로세서에서 실행함으로써 프로그램 수행 속도를 빠르게 한다는 개념이다. 프로그램을 N개의 프로세서에서 실행하면 하나의 프로세서 실행하는 것보다 N배까지 빨라질 수 있다. 이 문서는 리눅스 사용자들이 사용할 수 있는 네가지 병렬 처리에 대한 접근법을 다룬다. SMP 리눅스 시스템, 네트웍으로 연결된 리눅스 시스템의 클러스터, 멀티미디어 명령어(MMX같은)를 이용한 병렬 수행, 하나의 리눅스 시스템이 호스트하는 부속 (병렬) 프로세서(attached processor)가 이들이다.

1. 소개

병렬처리(Parallel Processing)는 프로그램을 동시에 실행할 수 있는 여러 조각으로 나누어 각자 자신의 프로세서에서 실행함으로써 프로그램 수행 속도를 빠르게 한다는 개념이다. 프로그램을 N개의 프로세서에서 실행하면 하나의 프로세서 실행하는 것보다 N배까지 빨라질 수 있다.

오랫동안 특별히 디자인한 "병렬 컴퓨터(parellel computer)"에서 여러개의 프로세서를 사용할 수 있었다. 이런 경향에 따라 리눅스는 현재 하나의 컴퓨터 내에서 여러개의 프로세서가 같은 메모리와 버스 인터페이스를 공유하는 SMP 시스템(종종 "서버"로 팔리는)을 지원한다. 이 외에도 여러대의 컴퓨터를 그룹을 지어 (예를 들어 각각 리눅스를 실행하고 있는 PC들의 그룹) 네트웍으로 서로 연결하여 병렬처리 클러스터(parellel-processing cluster)를 만들 수 있다. 리눅스를 이용한 병렬 컴퓨팅의 세번째 방법은 멀티미디어 확장 명령어(multimedia instruction extensions, MMX)를 사용하여 숫자 데이터 벡터를 병렬로 처리하는 것이다. 마지막으로 리눅스 시스템을 전용으로 부속 병렬처리 엔진(attached parellel processing compute engine)의 "호스트"로 사용하는 것도 가능하다. 이 문서에서는 이 모든 접근방법들을 자세히 다루도록 하겠다.

1.1 병렬처리가 내가 바라던 것인가?

여러개의 프로세서를 사용하는 것은 많은 연산의 처리하는 속도를 빠르게 할 수 있지만, 대부분의 응용프로그램들은 병렬처리라고 해서 아직 나아지는게 없다. 기본적으로 병렬처리는 다음 경우에 해당할 때 적당하다 :

  • 응용 프로그램이 여러개의 프로세서를 효과적으로 사용할 수 있도록 병행성을 가지고 있어야 한다. 어느정도 이는 프로그램 중에서 각기 다른 프로세서에서 독립적으로 동시에 실행할 수 있는 부분들을 파악하는 문제이다. 특정 시스템을 사용하여 병렬로 실행하는 경우, 어떤 것들은 병렬로 실행하는게 실제로 더 느린 경우가 있을 수 있다. 예를 들어 하나의 컴퓨터에서 4초가 걸리는 프로그램이 네 대의 컴퓨터에서 각각 1초만에 실행을 끝낸다 하더라도, 이들 컴퓨터가 서로의 동작을 통합하는데 3초나 그 이상의 시간이 걸린다면 아무런 속도개선이 이루어지지 않는다.
  • 관심을 가지고 있는 특정 응용프로그램이 이미 병렬화(병렬처리의 이점을 활용하여 다시 작성된) 되었거나, 병렬처리의 이점을 활용하는 최소한의 새로운 코딩을 하려고 해야 한다.
  • 연구분야에 관심있거나 어느정도 익숙한 사람이 병렬처리를 포함하도록 나서야 한다. 리눅스 시스템을 이용한 병렬처리가 반드시 어려운 것은 않지만, 대부분의 컴퓨터 사용자에겐 친숙하지 않고, "아무것도 모르는 사람들을 위한 병렬처리"같은 책도 아직 없는 상황이다. 이 HOWTO 문서가 알아야 할 모든것은 가지고 있진 않더라도 좋은 출발점이 될 것이다.

좋은 소식은 위의 내용이 모두 해당한다면, 복잡한 계산을 수행하거나 방대한 데이터를 처리하는 프로그램의 경우, 리눅스를 이용한 병렬처리가 슈퍼컴퓨터급의 성능을 발휘할 수 있다는 것이다. 더군다나 그것도 당신이 이미 가지고 있을 값싼 하드웨어를 사용하여 할 수 있다. 보너스로 병렬 리눅스 시스템이 바쁘게 병렬 작업을 수행하고 있지 않을 때는 다른 용도로 쉽게 사용할 수 있다.

병렬처리가 당신이 바라던 것이 아니더라도 어느정도 소소한 성능향상을 바란다면, 여전히 할 수 있는 일이 몇가지 있다. 예를 들어, 순차처리를 하는 프로그램들은 빠른 프로세서를 사용하고, 메모리를 추가하고, IDE 디스크를 빠른 와이드 SCSI 디스크로 바꾸는 등의 방법을 사용할 수 있다. 당신이 관심을 가지는 것이 이거라면 바로 <@@ref>sec_PerformanceIssues성능 문제장으로 넘어가고, 그렇지 않으면 계속 읽어주기 바란다.

병렬 처리가 여러분이 원하는 것이 아니더라도 여러분이 적어도 가장 온건한 성능 개선을 하고자 한다면 여러분이 할 수 있는 것들이 아직 남아 있다. 예를 들어서 여러분은 좀 더 빠른 프로세서, 메모리 추가, IDE 디스크를 빠른 와이드 SCSI로 바꾸는 등의 일을 함으로써 시퀀셜 프로그램들의 성능을 개선할 수 있다. 이것이 여러분이 관심이 있는 모든 것이라면 섹션 <@@ref>sec_PerformanceIssues성능 문제<@@ref>sec_PerformanceIssues성능에 대한 논란로 점프하라; 그렇지 않다면 계속 읽기 바란다.

1.2 용어

여러 해 동안 많은 시스템에서 병렬처리를 사용해왔지만, 대부분의 컴퓨터 사용자들은 여전히 좀 낯설 것이다. 따라서 병렬처리의 여러 방법들을 살펴보기 전에, 몇가지 일반적으로 사용하는 용어들에 익숙해지는 것이 필요하다.

SIMD (Single Instruction stream, Multiple Data stream, 단일 명령어, 다중 데이터 스트림) :

SIMD는 모든 프로세서가 똑같은 연산을 동시에 실행하지만, 각 프로세서가 자신만의 데이터에 대해 연산을 수행할 수 있는 병렬 실행 모델을 가리킨다. 이 모델은 배열의 모든 원소에 대해서 똑같은 연산을 수행하는 개념에 자연히 들어맞으며, 따라서 종종 벡터나 배열 처리와 관련된다. 모든 연산이 본래 동기화되어있으므로, SIMD 프로세서간의 상호작용은 대체로 쉽고 효과적으로 구현할 수 있다.

MIMD (Multiple Instruction stream, Multiple Data stream, 다중 명령어, 다중 데이터 스트림) :

MIMD는 각 프로세서가 근본적으로 독립적으로 동작하는 병렬 실행 모델을 가리킨다. 이 모델은 프로그램을 기능적인 토대에 바탕하여 병렬 실행할 수 있는 것으로 쪼개는 개념에 대부분 자연스럽게 들어맞는다. 예를 들어, 한 프로세서는 새로운 엔트리를 그래픽 화면으로 만들고 있을 때, 다른 프로세서는 데이터베이스 파일을 갱신하는 것이다. 이는 SIMD 보다는 더 유연한 모델이지만, 한 프로세서의 연산과 다른 프로세서의 연산의 상대순위가 바뀌는 시간 변화로 인하여 프로그램이 실패할 수 있는 경주 상황(race conditions)라는 악몽의 디버깅을 감수해야 한다.

SPMD (Single Program, Multiple Data, 단일 프로그램, 다중 데이터) :

SPMD는 MIMD의 제한된 버전으로 모든 프로세서가 같은 프로그램을 실행하는 것이다. SIMD와는 달리, SPMD 코드를 실행하는 각 프로세서는 프로그램을 실행 과정에서 다른 제어 흐름 과정을 따를 수 있다.

통신 대역폭 (Communication Bandwidth) :

통신 시스템의 대역폭은 데이터 전송을 시작한 때부터 어떤 단위의 시간동안 전송할 수 있는 데이터의 최대크기이다. 직렬 연결에서는 대역폭을 대개 baud 또는 비트/초 (b/s)로 표시하는데, 일반적으로 이것의 1/10에서 1/8이 바이트/초 (B/s)에 해당한다. 예를 들어, 1200 baud 모뎀은 약 120 B/s의 속도로 전송을 하고, 반면에 155 Mb/s ATM 네트웍 연결은 이보다 130000배 가량 빠른, 약 17 MB/s의 속도로 전송을 한다. 큰 대역폭은 프로세서 사이에 큰 데이터 블럭을 효율적으로 전송할 수 있게 한다.

통신 지체 (Communication Latency) :

통신 시스템의 지체(latency)는 보내고 받는 소프트웨어의 오버헤드를 포함하여, 한 객체를 전송하는데 걸리는 최소한의 시간을 말한다. 지체는 병렬처리에서 매우 중요한데, 병렬 실행으로 속도를 향상시킬 수 있는 코드 조각의 최소 실행 시간인, 최소 유용 알갱이 크기(minimum useful grain size)를 결정하기 때문이다. 기본적으로 코드 조각을 실행하는 시간이 결과값을 전송하는 시간(즉, 지체)보다 짧을 때, 그 코드 조각을 결과값을 필요로 하는 프로세서에서 직렬로 실행하는 것이 병렬로 실행하는 것보다 더 빠르다. 직렬로 실행하는 것은 통신 오버헤드가 없기 때문이다.

메시지 전달 (Message Passing) :

메시지 전달은 병렬 시스템 내부에서 프로세서간의 상호작용을 위한 모델이다. 일반적으로, 메시지는 한 프로세서에 있는 소프트웨어에서 만들어지고, 상호연결 네트웍을 통하여 다른 프로세서로 전달되어, 여기서 이를 받아 메시지 내용에 따라 동작하게 된다. 각 메시지를 처리하는 오버헤드(지체)가 클 수 있지만, 대개 각 메시지가 어느 정도 크기의 정보를 가질 수 있는지에는 거의 제한을 두지 않는다. 그래서 메시지 전달은 큰 대역폭을 초래하기도 하며, 한 프로세서에서 다른 프로세서로 큰 데이터 블럭을 전달하는 것을 매우 효율적인 방법으로 처리도록 되어 있다. 그렇지만, 값비싼 메시지 전달 연산의 필요를 최소화할 수 있도록, 병렬 프로그램에 있는 자료구조는 프로세서 간에 널리 퍼져 있어서 각 프로세서가 참조하는 대부분의 데이터는 자신의 지역 메모리 상에 있도록 해야 한다. 이러한 작업을 데이터 배치(data layout)라고 한다.

공유 메모리 (Shared Memory) :

공유 메모리는 병렬 시스템 내부에서 프로세서간의 상호작용을 위한 모델이다. 리눅스를 실행하고 있는 멀티프로세서 펜티엄 컴퓨터같은 시스템은 물리적으로 프로세서간에 하나의 단일 메모리를 공유한다. 따라서 한 프로세서가 공유 메모리에 값을 기록하면, 다른 어떤 프로세서든지 이 값을 직접 읽을 수 있다. 이와 달리 논리적인 공유 메모리는 각 프로세서가 자신만의 메모리를 가지며, 지역 메모리에 없는 메모리를 참조하면 이를 해당하는 프로세서간 통신으로 변환해줌으로써 구현한다. 이들 각각의 공유 메모리 구현은 일반적으로 메시지 전달보다 사용하기 쉽게 되어 있다. 물리적인 메모리 공유는 큰 대역폭을 가지며 지체가 적지만, 이는 단지 여러 프로세서가 동시에 버스에 접근하려하지 않을 때만이다. 따라서 데이터 배치(data layout)는 여전히 성능에 큰 영향을 미칠 수 있으며, 캐시 효과 등은 어떻게 배치하는 것이 가장 좋은 것인지 결정하기 힘들게 만든다.

집합 함수 (Aggregate Functions) :

메시지 전달과 공유 메모리 모델에서 통신은 모두 하나의 단일 프로세서에서 시작한다. 이와 반대로 집합 함수 통신은 본래 모든 프로세서 그룹이 서로 작용할 수 있는 병렬 통신 모델이다. 이런 작용의 가장 간단한 것은 장벽 동기화(barrier synchronization)로, 개별 프로세서들이 그룹에 있는 모든 프로세서가 장벽에 도달하길 기다리는 것이다. 개별 프로세서가 장벽에 도착하면서 부수효과(side effect)로 데이터를 출력하면, 통신 하드웨어는 모든 프로세서에서 수집한 값들에 임의의 함수를 적용한 결과값을 각 프로세서에게 전달할 수 있다. 예를 들어, 그 결과값은 "어떤 프로세서가 해를 찾았느냐"는 질문의 대답일 수도, 각 프로세서에서 온 값들의 합일 수도 있다. 지체(latency)는 매우 적겠지만, 하나의 프로세서가 차지하는 대역폭 역시 적은 경향이 있다. 전통적으로 이 모델은 데이터 값을 분산하기보다는 병렬 실행을 제어하는데 주로 사용된다.

총괄 통신 (Collective Communication) :

이는 집합 함수(aggregate function)의 다른 이름으르, 대부분 다중 메시지 전달 연산을 이용하여 구축된 집합 함수를 가리키는데 사용된다.

SMP (Symmetric Multi-Processor, 대칭형 멀티프로세서)

SMP는 일련의 프로세서들이 서로 대등하게 함께 동작하여, 어떤 작업 조각이든지 어떤 프로세서에서든 똑같이 실행될 수 있는 운영체제 개념을 말한다. 대체로 SMP는 MIMD와 공유메모리를 결합한 것이다. IA32 계열에서 SMP는 일반적으로 MPS(Intel Multi-Processor Specification, 인텔 멀티프로세서 규약)와 호환된다는 것을 의미한다. 앞으로는 이것은 "Slot 2"를 의미하게 될 것이다...

SWAR (SIMD Within A Register, 레지스터에서의 SIMD) :

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에 동의한 세 회사를 제외하고, 이들 확장 명령어들은 대충은 비슷하지만, 서로 호환되지는 않는다.

부속 프로세서 (Attached Processors) :

부속 프로세서는 본질적으로 특별한 유형의 계산 속도를 가속하기 위한 호스트 시스템에 연결된 특별한 목적을 가진 컴퓨터이다. 예를 들어, PC에 있는 많은 비디오와 오디오 카드는 제각기 일반 그래픽 연산과 오디오 DSP(Digital Signal Processing, 디지털 신호 처리) 속도를 높이도록 디자인된 부속 프로세서를 가지고 있다. 또한 배열에 대한 산술 연산 속도를 빠르게 하기 위한, 넓은 범위의 부속 배열 프로세서(attached array processor)들이 있다. 많은 상업용 슈퍼컴퓨터들은 실제로 워드스테이션 호스트와 부속 프로세서로 되어 있다.

RAID (Redundant Array of Inexpensive Disk, 여분의 값싼 디스크 배열) :

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 (Intel Architecture, 32-bit, 인텔 32비트 아키텍쳐) :

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 (Commercial Off-The-Shelf, 상업용 기성품)

많은 병렬 슈퍼컴퓨터 회사들이 사라지면서, COTS는 병렬 계산 시스템의 필요조건으로 일반적으로 다루어지게 되었다. 아주 이론적으로 하면, PC를 사용하는 유일한 COTS 병렬처리 기법은 SMP Windows NT 서버와 여러 MMX Windows 응용프로그램같은 걸로 만들어진 것이다. COTS 개념의 기반은 사실상 개발 시간과 비용의 최소화이다. 따라서 더 유용하고, 더 일반적인, COTS의 의미는 적어도 대부분의 서브시스템은 기성 제품 시장에서 이득을 얻어야 하지만, 다른 기술들은 효율적으로 사용될 수 있는 곳에 사용해야 한다는 것이다. 대부분의 경우, COTS 병렬처리는 노드는 기성 PC이지만 네트웍 인터페이스와 소프트웨어는 어느정도 맞춤으로 만든 클러스터를 가리킨다. 대개 실행할 리눅스와 응용프로그램 코드는 자유롭게 구할 수 있지만 (copyleft이거나 public domain인), 문자 그대로 COTS는 아니다.

1.3 예제 알고리즘

이 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에서는, 이 알고리즘의 여러가지 병렬 구현이 나오며, 각각은 다른 프로그래밍 방법을 사용한다.

1.4 이 문서의 구성

이 문서의 나머지는 다섯개 부분으로 나뉘어져 있다. 2, 3, 4, 5장은 리눅스를 이용한 병렬처리를 지원하는 세가지 다른 유형의 하드웨어 구성을 다루고 있다.

  • 2장은 SMP 리눅스 시스템을 다룬다. 이는 공유 메모리를 이용한 MIMD 실행을 직접적으로 지원하며, 메시지 전달 역시 쉽게 구현된다. 리눅스는 16개의 프로세서를 갖는 SMP 구성까지 지원하지만, 대부분의 SMP PC 시스템은 두개나 네개의 똑같은 프로세서를 가지고 만들어진다.
  • 3장은 각각 리눅스를 실행하고 있는 기계들을 네트웍으로 연결한 클러스터를 다룬다. 클러스터는 MIMD 실행과 메시지 전달, 그리고 대개 논리적 공유 메모리를 직접 지원하는 병렬처리 시스템으로 사용할 수 있다. 사용한 네트웍 방법에 따라 SMP 실행을 흉내내고, 집합 함수(aggregate function) 통신도 지원할 수 있다. 클러스터로 연결된 프로세서의 숫자는 두개에서 수천개까지 될 수 있는데, 이 숫자는 주로 네트웍을 구성하는 물리적인 배선에 의해 제한을 받는다. 어떤 경우, 클러스터에 서로 다른 유형의 기계들을 혼합할 수도 있다. 예를 들어, DEC Alpha와 펜티엄 리눅스 시스템을 결합할 수 있는데, 이런 것을 가리켜 이질 클러스터(heterogeneous cluster)라고 한다.
  • 4장에서는 SWAR, 즉 레지스터에서의 SIMD(SIMD Within A Register)를 다룬다. 이것은 매우 제한적인 유형의 병렬 실행 모델이지만, 반면에 일반적인 프로세서에 이미 구현되어 있는 기능이기도 하다. 최근에 근래의 마이크로프로세서에 MMX (그리고 다른 것들도) 확장 명령어들이 추가되면서 이런 접근방법이 더 효율적이 되었다.
  • 5장에서는 리눅스 PC를 간단한 병렬처리 시스템의 호스트로 사용하는 것을 다룬다. 꼽는 카드나 외부의 박스 형태로, 부속 프로세서는 리눅스 시스템에게 특정 종류의 응용프로그램에 대한 엄청난 처리 능력을 줄 수 있다. 예를 들어, 여러개의 DSP 프로세서를 제공하는 값싼 ISA카드를 이용하여, 경계계산 문제(compute-bound problem)를 위한 수백 MFLOPS의 처리 능력을 가질 수 있다. 그렇지만 이들 추가되는 보드들은 단지 프로세서일 뿐이다. 이들은 일반적으로 OS를 실행하거나 디스크나 콘솔 I/O 능력 등을 가지고 있지 않다. 이런 시스템을 유용하게 사용하기 위해 리눅스 "호스트"가 이들 기능들을 제공해야 한다.

이 문서의 마지막 장은 위에서 다룬 접근 방법들에 속하지 않는, 리눅스를 이용한 병렬처리에서 일반적으로 가지고 있는 관심들을 다룬다.

이 문서를 읽을 때 아직 우리가 모든 것들을 다 테스트해보진 못했다는 것과 여기서 다루는 내용의 많은 부분은 "아직 연구중인 특성"("생각했던 것처럼 잘 동작하지 않는다"는 것을 더 좋게 표현한 말이다 :-)이라는 것을 명심하기 바란다. 그렇지만 리눅스를 이용한 병렬처리는 현재 유용하며, 점점 더 많은 그룹들이 이를 더 잘 사용하기 위해 작업을 진행중이다.

이 HOWTO 문서를 작성한 사람은 Hank Dietz 박사로 현재는 West Lafayette 47907-1285에 있는 Purdue 대학의 전기 및 컴퓨터 공학(Electrical and Computer Engineering)의 부교수(Associate Professor)이다. Dietz는 리눅스 문서화 프로젝트(Linux Documentation Project, LDP)의 지침에 따라 이 문서에 대한 권한을 갖는다. 이 문안을 정확하고 공정하게 만들기 위해서 많은 노력을 했지만, Dietz나 Purdue 대학 모두 어떠한 문제나 에러에 대한 책임이 없으며, Purdue 대학은 여기서 다룬 어떠한 작업이나 결과물도 보증하지 않는다.

2. SMP 리눅스

이 문서는 병렬처리를 위해 SMP 리눅스 시스템을 어떻게 사용할 수 있는지에 관해 간단하게 개요를 제시한다. SMP 리눅스에 대한 가장 최근 정보는 아마도 SMP 리눅스 프로젝트의 메일링 리스트에서 얻을 수 있을 것이다. 이 리스트에 가입하려면 편지 본문에 subscribe linux-smp 라고 적어 majordomo@vger.rutgers.edu로 편지를 보내면 된다.

SMP 리눅스가 정말 제대로 동작하는가? 1996년 6월, 나는 새로운 상표의 (사실은 한물 간 품종이었지만 새 상표였다 ;-) 두개의 100MHz 펜티엄 프로세서를 가지는 시스템을 구입했다. 조립을 마친 시스템은 두개의 프로세서와 Asus 마더보더(motherboard), 256K 캐시, 32M RAM, 1.66G 하드디스크, 6배속 CDROM, Stealth 64 그래픽 카드와 15인치 모니터로, 이를 마련하는데 모두 1800$가 들었다. 이 가격은 이와 비슷한 사양의 프로세서 하나인 시스템보다 단지 몇백 달러정도 비싼 거였다. 제대로 동작하는 SMP 리눅스를 구할려면, 그저 보통의 단일 프로세서 리눅스를 설치하고, makefile에서 SMP=1을 막고 있는 주석을 해제하여 (비록 SMP1로 설정하는 것이 조금은 반어적이라는 것을 알지만) 커널을 다시 컴파일하고, lilo에게 새로운 커널을 알려주기만 하면 된다. 이 시스템은 매우 잘 동작하였고, 안정적이기도 하여, 지금까지 사용해온 나의 주 워크스테이션의 역할을 수행하기에 충분했다. 요약하면, SMP 리눅스는 정말로 제대로 동작한다.

다음 질문은 SMP 리눅스가 공유 메모리를 사용하는 병렬 프로그램을 작성하고 실행하는 데 있어 얼만큼이나 고수준으로 지원을 해주느냐이다. 1996년 초에는 이런 것은 별로 많지 않았다. 그러나 이제 많은 것이 변했다. 예를 들어, 이제는 매우 완벽한 POSIX 쓰레드(thread) 라이브러리가 있다.

공유 메모리 방식을 사용하는 것보다는 성능이 떨어질 수도 있지만, SMP 리눅스 시스템에서는 원래 소켓 통신을 사용하는 워크스테이션 클러스터(cluster)에서 동작하도록 개발된 대부분의 병렬 처리 소프트웨어도 사용할 수 있다. 소켓(3.3 장을 보라) 방식은 SMP 리눅스 시스템 뿐만 아니라, 여러개의 SMP 시스템을 네트웍으로 연결한 클러스터에서도 사용할 수 있다. 그렇지만 소켓은 SMP에서는 상당한 양의 불필요한 오버헤드(overhead)를 가지게 된다. 이런 오버헤드의 대부분은 커널 즉 인터럽트 핸들러에서 일어난다. SMP 리눅스에서는 보통 동시에 하나의 프로세서만이 커널 모드에 있을 수 있고, 부트 프로세서만이 인터럽트를 처리할 수 있도록 인터럽트 컨트롤러가 설정되어 있기 때문에 문제는 더 심각해진다. 그럼에도 불구하고, 전형적인 SMP 통신 하드웨어가 클러스터 네트웍보다는 훨씬 좋기 때문에, 원래 클러스터에서 사용하려고 만든 클러스터용 소프트웨어도 SMP에서 더 좋은 성능을 보인다.

이 장의 나머지에서는 SMP 하드웨어에 대해서 이야기하고, 병렬 프로그램 프로세스 사이에서 메모리를 공유하는 기본적인 리눅스 메커니즘을 살펴보고, 원자성(atomicity), 휘발성(volatility), 락(lock), 캐시 라인(cache line)에 대해서 아주 간단하게 알아보고, 마지막으로 여러가지 공유 메모리 병렬 처리 라이브러리들에 대해 약간의 조언을 하도록 한다.

2.1 SMP 하드웨어(Hardware)

SMP 시스템들은 여러해 전부터 사용되어 왔지만, 얼마전까지만해도 기계마다 기본적인 기능들을 서로 다르게 구현하는 경향이 있어서, 운영체제에서 SMP를 지원하는 것이 호환성이 없었다. 이런 문제를 종식시킨 것은 인텔에서 발표한 다중프로세서 규약(Multiprocessor Specification, 간단히 줄여서 MPS라고 한다)이다. MPS 1.4 규약은 http://www.intel.com/design/pro/datashts/242016.htm에서 PDF 파일 형식으로 된 문서로 구할 수 있으며, http://support.intel.com/oem_developer/ial/support/9300.HTM에서 MPS 1.1 규약에 대한 개요를 볼 수 있지만, 인텔이 자신의 WWW 사이트를 종종 개편을 하기 때문에 이 주소는 바뀌었을 수도 있다. 많은 제작들은 4개의 프로세서까지 지원하는 MPS 호환 시스템들을 만들고 있지만, 이론적으로 MPS는 더 많은 프로세서들을 지원할 수 있다.

MPS가 아니면서 IA32(인텔 32비트 CPU)가 아닌 시스템 중에서 SMP 리눅스가 지원하는 시스템으로는 Sun4m 다중프로세서 SPARC 시스템이 유일하다. SMP 리눅스는 인텔 MPS 1.1과 1.4 호환 시스템을 대부분 지원하며, 16개까지의 486DX, Pentium, Pentium MMX, Pentium Pro, Pentium II 프로세서를 지원한다. 지원하지 않는 IA32 프로세서로는 인텔 386, 486SX/SLC 프로세서와 (부동 소숫점 연산 하드웨어가 없으면 SMP 기계에 맞지 않는다), AMD와 Cyrix의 프로세서들이다 (이들 프로세서는 다른 SMP 지원 칩들을 필요로 하는데, 이 글을 쓰고 있을 때 아직 이들 칩들은 나와있지 않았다).

MPS 호환 시스템들의 성능은 천차만별로 달라질 수 있다는 점은 꼭 이해하고 넘어가야 한다. 일반적인 예상대로 성능의 차이를 나타내는 요인 중의 하나는 프로세서 속도이다. 대체로 좀 더 빠른 클럭의 프로세서을 사용하면 더 빠른 시스템이 되며, Pentium Pro 프로세서를 사용한 시스템이 Pentium 프로세서를 이용하는 시스템보다 빠른 경향이 있다. 그렇지만 MPS에서는 공유 메모리(shared memory)를 하드웨어적으로 어떻게 구현해야 하는지는 명시하지 않고 있다. 단지 소프트웨어적인 관점에서 공유 메모리가 어떻게 동작해야 하는지만 명시하고 있을 뿐이다. 그래서 구현하고 있는 공유 메모리 방식이 SMP 리눅스의 특징과 특정 프로그램의 특징에 어떻게 맞아들어가느냐에 따라서 성능이 달라질 수 있다.

MPS 호환 시스템들의 차이는 우선 물리적으로 공유 메모리에 접근하는 것을 어떻게 구현하느냐에서 나타난다.

각 프로세서가 독자적인 L2 캐시를 가지는가?(Does each processor have its own L2 cache?)

일부 MPS Pentium 시스템과, 모든 MPS Pentium Pro와 Pentium II 시스템은 독자적인 L2 캐시를 가지고 있다. (L2 캐시는 Pentium Pro나 Pentium II 모듈에 들어있다) 일반적으로 독자적인 L2 캐시를 사용하면 처리 속도를 최대화할 수 있다고 알려져 있지만, 리눅스에서는 명백하게 그런 것은 아니다. 이를 혼란하게 하는 주된 이유는, 현재의 리눅스 스케줄러가 각 프로세스를 똑같은 프로세서에서 실행되게 하는 프로세서 친화력(processor infinity)의 개념을 따르지는 않기 때문이다. 프로세스가 실행되는 프로세서는 금방 바뀔수 있다. 이 문제는 최근에 "프로세서 결합(processor binding)"이라는 제목으로 SMP 리눅스 개발 공동체에서 토론된 적이 있다. 프로세서 친화력 없이 별도의 L2 캐시를 갖게되면, 어떤 프로세스가 이전에 실행되던 프로세서가 아닌 다른 프로세서에서 시간을 할당받아 실행되는 경우 상당한 오버헤드를 초래할 수 있다.

상대적으로 값이 싼 상당수의 시스템들은 두개의 Pentium 프로세서가 하나의 L2 캐시를 공유하도록 만들어져 있다. 이 방식의 안좋은 점은 두개의 프로세서가 서로 캐시를 사이에 두고 경쟁을 해야한다는 것으로, 특히 여러개의 서로 독립적인 프로그램을 실행하는 경우 성능이 현저하게 떨어진다는 것이다. 좋은 점은 많은 병렬 프로그램들에게 있어서 두 개의 프로세서가 공유 메모리의 똑같은 라인에 접근하는 경우 하나만이 이를 캐시에 가져오면 되어, 버스를 둘러싼 경쟁을 피할 수 있어서 캐시를 공유하는게 실질적으로 도움이 된다는 것이다. 또한 프로세서 친화력을 적용하지 않는 경우 L2 캐시를 공유하는 것이 피해가 더 적다. 따라서 병렬 프로그램의 경우 L2 캐시를 공유하는 것이 일반적으로 생각하는 것만큼 나쁘지는 않다.

두개의 Pentium 프로세서가 256K 캐시를 공유하는 시스템을 사용해본 경험에 따르면, 필요한 커널 작업의 정도에 따라서 시스템의 성능이 상당히 크게 달라졌다. 최악의 경우 속도가 1.2배 정도밖에 빨라지지 않았지만, "데이터를 가져오는 것은 공유하는(shared fetch)" 효과를 제대로 이용하는 계산 중심적인 SPMD 스타일의 코드를 사용하였을 때 2.1 배까지 빨라지는 것을 보기도 하였다.

버스 설정(Bus configuration)?

먼저 이야기할 것은 요즘에 나오는 대부분의 시스템들은, 프로세서에 하나 이상의 PCI 버스가 연결되어 있고, 이는 또다시 브릿지(bridge)를 통하여 하나 이상의 ISA/EISA 버스에 연결되어 있다는 것이다. 브릿지를 통하는 경우 대기시간(latency)이 늘어나게 되고, EISA나 ISA는 일반적으로 PCI에 비해서 낮은 대역폭을 제공하기 때문에 (ISA가 제일 낮다), 디스크 드라이브나, 비디오 카드, 다른 고성능 장치들은 PCI 버스 인터페이스를 통하여 연결되어야 한다.

PCI 버스가 하나밖에 없더라도 계산 중심적인 병렬 프로그램의 경우 MPS 시스템은 괜찮은 성능개선 효과를 보여준다. 하지만 I/O 처리속도는 하나의 프로세서를 사용할 때보다 더 나아지지 않으며, 프로세서들이 버스를 사이에 두고 경쟁을 하기 때문에 아마도 성능이 조금 떨어지게 될 것이다. 따라서 I/O 속도를 높이고 싶다면 여러개의 독자적인 PCI 버스와 I/O 콘트롤러(예를 들어 여러개의 SCSI 체인들)를 가지는 MPS 시스템을 구입하는 것이 좋다. 이 때 SMP 리눅스에서 이들 시스템을 지원하는지 조심스럽게 살펴보아야 한다. 또한 현재의 SMP 리눅스에서는 어느 순간이든 하나의 프로세서만이 커널모드에 있을 수 있기 때문에, I/O 처리를 할 때 커널에서 소요하는 시간이 적은 I/O 콘트롤러를 사용해야 한다는 점을 명심해야 한다. 정말 고성능을 원한다면 시스템 콜(system call)을 통하지 않고, 사용자 프로세스가 직접 장치로 I/O를 하는 것도 고려해 볼 필요가 있다. 이는 생각만큼 어렵지도 않고, 안정성을 해치지도 않는다 (3.3 장에서 기본 기술에 대해서 설명하고 있다).

버스 속도와 프로세서 클럭 속도의 관계를 살펴보는 것도 매우 중요하다. 지난 몇해동안 이들 사이의 관계는 불명확하게 이해되어 왔다. 대부분의 시스템이 지금은 똑같은 PCI 클럭 속도를 사용하고 있지만, 더 빠른 클럭 속도의 프로세서가 더 느린 버스 클럭과 쌍을 이루는 것은 드문 일이 아니다. 이의 고전적인 예로, 일반적으로 Pentium 133은 Pentium 150보다 더 빠른 버스를 사용하였고, 다양한 벤치마크에서 특이한 결과를 나타냈다. 이런 효과는 SMP 시스템에서 더욱 증폭된다. 이는 버스 클럭 속도를 빠르게 하는 것보다도 더 중요한 문제이다.

메모리 중첩과 DRAM 기술(Memory interleaving and DRAM technologies)?

메모리 중첩은 실제로 MPS와는 아무런 일도 같이 하지 않는다. 그러나 MPS 시스템에서 이것이 종종 언급되는 것을 볼 수 있는데, 이는 이들 시스템이 대체로 메모리 대역폭을 더 많이 필요로 하기 때문이다. 기본적으로 2-way나 4-way 중첩은 RAM에 블럭 접근을 할 때, 이것이 하나가 아니라 여러개의 RAM 뱅크(bank)를 사용하여 이루어지도록 RAM을 조직화한다. 이는 더 높은 메모리 접근 대역폭을 제공하게 되는데, 특히 캐시 라인(cache line) 읽기나 쓰기에 있어서 더욱 그러하다.

이것의 효과에 대해서는 그다지 명쾌하지 않은데, EDO DRAM이나 여러가지 다른 메모리 기술들은 이와 비슷한 종류의 연산 속도를 향상시키기 때문이다. http://www.pcguide.com/ref/ram/tech.htm에서 DRAM 기술에 대해 무척 잘 정리되어있는 개요를 볼 수 있다.

그렇다면, 예를 들어 2-way의 중첩되는 EDO DRAM을 쓰는 것이 중첩을 사용하지 않는 SDRAM을 쓰는 것보다 더 좋은가? 이것은 매우 훌륭한 질문이며, 그 대답은 간단하지 않다. 왜냐하면 중첩기술이나 다른 흥미있는 기술들은 대체로 비싸기 때문이다. 여기에 들어가는 똑같은 돈을 보통 메모리에 투자한다면 훨씬 많은 양의 메인 메모리를 사용할 수 있을 것이다. 가장 느린 DRAM을 사용한다 하더라도 디스크를 이용한 가상 메모리보다는 훨씬 빠르다.

2.2 공유 메모리 프로그래밍에 대한 소개

SMP에서 병렬처리를 사용하는 것이 충분히 할만한 것이라고 결정을 내렸다면, 이제 어디서부터 시작하는게 좋을까? 그럼, 공유 메모리 통신이 실제로 동작하는 방식에 대해서 조금 더 배우는 것으로 그 첫발을 내딛어보도록 하자.

얼핏 생각하면 공유 메모리 통신이란 하나의 프로세서가 메모리에 값을 저장하면, 다른 프로세서가 이를 읽어들이는 것이라고 생각할 수도 있다. 하지만 불행히도 그렇게 간단하지만은 않다. 예를 들어, 프로세스와 프로세서 사이의 관계가 무척 복잡하게 얽혀 되어있다고 하자. 프로세서의 갯수보다 현재 동작하는 프로세스의 수가 적다고 하더라도 그렇고, 그 반대의 경우도 마찬가지다. 이 장의 남은 부분에서는 특별히 신경쓰지 않으면 심각한 문제를 야기할 수 있는 중요한 논점들 - 무엇을 공유할 것인지 판단하는데 사용하는 두가지 서로 다른 모델과, 원자성(atomicity) 논점, 휘발성(volatility) 개념과 하드웨어 락(lock) 명령, 캐시 라인(cache line) 효과, 그리고 리눅스 스케줄러 논점 - 을 간단히 요약하도록 하겠다.

모두 공유하기 대 일부를 공유하기(Shared Everything Vs. Shared Something)

공유 메모리 프로그래밍에서는 일반적으로 모두 공유하기일부를 공유하기라는 두가지의 근본적으로 서로 다른 모델을 사용한다 . 이 두가지 모델은 모두 프로세서들이 공유메모리로 데이터를 쓰고, 공유메모리에서 데이터를 읽어들임으로써 통신을 할 수 있게 한다. 두 모델의 다른점은, 모두 공유하는 모델에서는 모든 자료구조를 공유메모리에 두는 반면에, 일부를 공유하는 모델에서는 사용자가 공유할 자료구조와 하나의 프로세서에 국한되는 자료구조를 명시적으로 지정한다는 것이다.

어떤 공유메모리 모델을 사용할 것인가? 이는 종교에 대한 질문과 비슷하다. 많은 사람들은 자료구조를 선언할 때 이것을 공유할 것인지 따로 구별할 필요가 없기 때문에, 모두 공유하는 모델을 좋아한다. 이 때는 동시에 하나의 프로세스(프로세서)만이 자료에 접근할 수 있도록, 충돌을 일으킬 수 있는 공유하는 자료에 접근하는 코드 주위에 락(lock)을 걸기만 하면 된다. 그렇지만 이것 역시 말처럼 간단하진 않다. 그래서 많은 사람들은 일부만을 공유하는 모델이 가져다주는 상대적인 안전성을 더 선호하기도 한다.

모두 공유하기(Shared Everything)

모두 공유하는 방식의 장점은 이미 만들어져 있는 순차적인 프로그램을 선택하여 쉽게 모두 공유하는 병렬 프로그램으로 변환할 수 있다는 것이다. 여기서는 어떤 자료가 다른 프로세서에서 접근할 수 있는 것인지 먼저 판단해야 할 필요가 없다.

간단하게 살펴보면, 모든걸 공유하는 방식의 가장 큰 문제점은 하나의 프로세서가 취한 행동이 다른 프로세서들에게 영향을 미칠 수 있다는 것이다. 이 문제는 두가지 방향으로 나타난다 :

  • 많은 라이브러리들은 공유할 수 없는 자료구조들을 사용한다. 예를 들어, UNIX에서 대부분의 함수들은 errno라는 변수에다가 에러코드를 담아 돌려준다. 만약 모두 공유하는 두 개의 프로세스가 여러가지 함수를 부른다면, 이들은 똑같은 errno 변수를 공유하기 때문에 서로 간섭을 일으키게 될 것이다. 비록 지금은 errno 문제를 해결한 라이브러리가 있긴 하지만, 이와 비슷한 문제는 대부분의 라이브러리에 여전히 남아 있다. 예를 들어, 미리 특별한 주의를 기울이지 않고, 모두 공유하는 여러개의 프로세스들이 X 라이브러리의 함수들을 호출한다면, X 라이브러리는 제대로 동작하지 않을 것이다.
  • 일반적으로 포인터를 잘못 사용하거나, 배열에서 인덱스를 잘못 지정한 경우, 최악의 결과로 이 코드를 수행하던 프로세스가 죽기도 한다. 이때 core 파일을 만들어 무슨 일이 일어났는지 단서를 제공해주기도 한다. 모두 공유하는 병렬처리에서는 이런 잘못된 접근이 발생하면 다른 프로세스까지도 죽게 할 가능성이 커서, 지역화(localize)를 하거나 에러를 고치는 것을 거의 불가능하게 만든다.

이런 종류의 문제는 일부를 공유하는 방식에서는 흔히 일어나진 않는다. 왜냐하면 명백하게 지정한 자료구조만이 공유되기 때문이다. 그리고, 모두 공유하는 방식은 모든 프로세서가 완전히 똑같은 메모리 이미지를 실행하는 경우에만 동작한다는 것은 당연한 일이다. 즉, 여러개의 서로 다른 코드 이미지들 사이에서는 모두 공유하는 방식을 사용할 수 없다 (다르게 말하면, SPMD만을 사용할 수 있지, 일반적인 MIMD는 사용할 수 없다).

모두 공유하는 방식을 지원하는 가장 일반적인 유형은 쓰레드 라이브러리(threads library)이다. 쓰레드는 본래, 대체로 일반적인 UNIX 프로세스와는 다르게 스케줄이 이루어지고, 가장 중요한 점으로 동일한 메모리 맵에 접근할 수 있는 "가벼운" 프로세스이다. POSIX Pthreads패키지는 여러 포팅 프로젝트에서 촛점을 받아 왔었다. 여기서 중요한 질문은, 이들 포팅중의 어떤 것들이 실제로 프로그램에 있는 쓰레드들을 SMP 리눅스에서 병렬로 실행할 수 있느냐이다 (이상적으로, 각 쓰레드마다 하나의 프로세서를). POSIX API는 이를 요구하지 않으며, http://www.aa.net/~mtp/PCthreads.html같은 버전에서는 분명하게 병렬 쓰레스 실행을 구현하지 않고 있다 - 프로그램의 모든 쓰레드들은 하나의 리눅스 프로세스 안에 들어있다.

SMP 리눅스에서의 병렬처리를 지원한 첫번째 쓰레드 라이브러리는 지금은 한물간 bb_threads 라이브러리로, ftp://caliban.physics.utoronto.ca/pub/linux/에서 구할 수 있다. 이는 리눅스의 clone()함수를 사용하여, 독자적으로 스케줄되며, 하나의 주소공간을 공유하는, 새로운 리눅스 프로세스를 생성(fork)하는 매우 작은 라이브러이다. SMP 리눅스 기계는 각 "쓰레드들"이 완전한 리눅스 프로세스이기 때문에 여러개의 이들 "쓰레드들"을 병렬로 실행할 수 있다. 대신 이의 댓가로 다른 운영체제의 일부 쓰레드 라이브러리들이 제공하는 것과 같은 "가벼운" 스케줄링 제어를 할 수 없다. 이 라이브러리는 새로운 메모리 조각을 각 쓰레드의 스택으로 할당하고, 락(lock)의 배열(mutex 개체들)들을 원자적으로 접근할 수 있는 함수를, C로 포장된 어셈블리 코드를 조금 사용하여 제공하고 있다. 문서는 README와 간단한 예제 프로그램으로 구성되어 있다.

좀더 최근에 clone()을 사용하는 POSIX 쓰레드 버전이 개발되었다. 이 라이브러리는 LinuxThreads로, SMP 리눅스에서 사람들이 가장 선호하는 모두 공유하는 라이브러리이다. POSIX 쓰레드들도 문서화가 잘되어있고, LinuxThreads READMELinuxThreads FAQ 역시 매우 잘되어 있다. 지금의 주요한 문제는 POSIX 쓰레드를 제대로 하려면 이를 자세하게 알아야한다는 것이고, LinuxThreads는 아직은 계속해서 작업중이라는 것이다. 또한 POSIX 쓰레드 표준이 표준화 과정에서 계속 발전되고 있어, 이미 바뀐 예전 버전의 표준에 맞춰 프로그램을 작성하지 않도록 주의를 기울여야 한다는 것 역시 문제이다.

일부를 공유하기(Shared Something)

일부를 공유하는 것은 정말로 "공유할 필요가 있는 것만을 공유하는" 것이다. 이 접근법은 각 프로세서의 메모리 맵의 똑같은 위치에 공유데이터가 할당되게 하는 것에 유의한다면 일반적인 MIMD(SPMD가 아니라) 용으로 동작하게 된다. 더 중요한 특징은, 일부를 공유하는 방식은 성능을 예측하고 조율하며, 코드를 디버깅하는 것 등을 쉽게 만들어준다는 것이다. 유일한 문제로는 :

  • 사전에 무엇이 정말로 공유할 필요가 있는지 아는게 힘들다.
  • 공유 메모리에 객체를 실제로 할당하는 것은 골치아픈 작업이다. 특히 스택에 할당되던 객체인 경우 더욱 그렇다. 예를 들어, 공유 데이터를 별도의 메모리 영역에 할당을 해야할 필요가 있는 경우가 있는데, 이 때는 별도의 메모리 할당 함수를 사용하고, 각 프로세스가 이를 참조할 때 또다른 포인터를 사용해야 한다.

현재 리눅스 프로세스 그룹들이 독자적인 메모리 공간을 가지면서, 상대적으로 작은 메모리 영역만을 함께 공유하게 하는데에는 두개의 유사한 방식을 사용한다. 리눅스 시스템을 설정할 때 바보같이 "System V IPC"를 빼버리지 않았다면, 리눅스는 "System V 공유 메모리"라는 다른 시스템 사이에서도 호환성이 있는 방식을 제공한다. 다른 방식은 mmap() 시스템 콜을 통하여 메모리 매핑(memory mapping) 기능을 사용하는 것이다. 이는 구현방식이 UNIX 시스템마다 크게 차이가 난다. 이들 호출에 대해서는 매뉴얼 페이지들에서 배울 수 있다. 그리고 2.5장과 2.6장에 나오는 개괄은 이를 처음 시작할 때 도움이 될 것이다.

원자성과 순서(Atomicity And Ordering)

위의 두가지 모델 중 어떤 것을 사용하더라도 결과는 매우 비슷하다. 여러분은 자신이 만든 병렬 프로그램에 들어 있는 모든 프로세스들이 접근하여 읽고 쓸수 있는 메모리 조각에 대한 포인터를 얻게 된다. 이 말은 내가 만든 병렬 프로그램이 공유 메모리 객체들을 마치 보통의 지역 메모리에 있는 것처럼 접근할 수 있다는 것을 의미하지는 않는다.

원자성이란 한 객체에 대한 작업이 쪼개지지 않고, 중단될 수 없는 일련의 과정으로 이루어지는 것을 가리키는 개념이다. 불행히도, 공유 메모리에 대한 접근은 공유 메모리에 있는 자료에 대한 모든 작업이 원자적으로 이루어진다는 것을 내포하진 않는다. 미리 특별한 주의를 기울지지 않는다면, 버스(bus)에서 단 한번만에 처리가 이루어지는 간단한 읽기/쓰기 연산만이 (즉, 정렬이 된 8, 16, 32 비트 연산이지, 정렬이 안되어 있거나 64 비트 연산은 아니다) 원자성을 가진다. 더욱 나쁜 것은, GCC같이 "똑똑한" 컴파일러는 최적화를 통해 메모리 작업을 제거하여, 한 프로세서가 한 일을 다른 프로세서에서 볼 수 없게 만들어버리기도 한다. 다행히도, 이들 문제들은 모두 고칠 수 있다... 접근 효율성(access efficiency)과 캐시라인 크기(cache line size) 사이의 관계만 걱정거리로 남겨두고서 말이다.

그렇지만 이들 논점에 대해서 토론하기 전에, 이들은 모두 각 프로세서에서의 메모리 참조가 코딩한 순서대로 이루어지고 있다고 가정하고 있다는 것을 지적할 필요가 있다. Pentium은 그렇게 하고 있지만, 앞으로 나올 인텔의 프로세서들은 그렇지 않을 수도 있다는 것도 기억하기 바란다. 따라서, 앞으로 나올 프로세서에 대비하여, 공유 메모리에 접근하는 코드 주위를, 모든 미결된 메모리 접근을 완료하여 메모리 접근이 차례대로 이루어지도록 하는 명령어로 둘러싸야 할 필요가 있다는 것을 깊이 새기길 바란다. CPUID 명령어는 이런 부수효과(side-effect)를 위해 예약되어 있는 것이다.

휘발성(Volatility)

GCC 옵티마이저(optimizer)가 공유 메모리 객체의 값을 레지스터에 버퍼링하는 것을 막으려면, 공유 메모리에 있는 모든 객체들을 volatile 속성을 가지도록 선언해야 한다. 이렇게 하면, 한번의 접근만으로 이루어지는 모든 공유 객체의 읽기/쓰기는 원자적으로 일어나게 된다. 예를 들어, p가 정수에 대한 포인터이고, 이것이 가리키고 있는 정수가 공유 메모리에 있다고 하자. ANSI C에서는 이를 다음과 같이 정의할 수 있다.


volatile int * volatile p;

이 코드에서, 첫번째 volatilep가 가리키는 int 값을 말하며, 두번째 volatile는 포인터 그 자체를 말한다. 물론 이는 귀찮은 작업이지만, GCC가 매우 강력한 최적화를 수행할 수 있도록 하기 위해서 치러야 하는 것이다. 적어도 이론적으로는, GCC에 -traditional 옵션을 주는 것으로도, 몇가지 최적화를 희생하는 대신 올바른 코드를 만들어내는데에는 충분하다. 왜냐하면 ANSI K&R C 이전에는 모든 변수는 따로 register라고 지정하지 않은 이상 모두 volatile이었기 때문이다. 여전히 GCC로 cc -O6와 같이 컴파일을 하고, 필요한 것에만 volatile이라고 지정할 수도 있다.

모든 프로세서의 레지스터를 수정하는 것으로 표시되어 있는 어셈블리어 락(lock)을 사용하면, GCC가 모든 변수들을 다 내보내서(flush), volatile이라고 선언함으로써 발생하는 "비효율적인" 코드들을 피할 수 있게 하는 효과가 있다는 소문이 있어왔다. 이런 방법은 GCC 2.7.0을 사용하는 경우, 정적으로 할당되는 전역변수에 대해서는 제대로 동작하는 것처럼 보인다... 그렇지만, 이런 행동은 ANSI C 표준에서는 필요하지 않다. 더 나쁜 것은 읽기 접근만을 하는 다른 프로세스들은 변수 값을 영원히 레지스터에 버퍼링을 할 수 있어서, 공유 메모리의 값이 실제로 변하는 것을 절대로 알아차리지 못할 수도 있다. 요약하면, 하고 싶은대로 해도 좋지만, volatile라고 지정한 변수만이 제대로 동작한다는 것을 보장할 수 있다.

일반 변수에도 volatile 속성을 암시하는 형변환(type cast)을 사용하여 volatile 접근을 할 수 있다. 예를 들어, 보통의 int i;*((volatile int *) &i);같이 선언하여 volatile로 접근할 수 있다. 이렇게 하면 휘발성(volatility)이 필요한 경우에만, 이런 오버헤드를 사용하도록 할 수 있다.

락(Locks)

++i;는 항상 공유 메모리에 있는 변수 i에 1을 더한다고 생각해왔다면, 다음 이야기는 조금은 놀랍고 당황스러울지도 모르겠다. 하나의 명령으로 코딩을 했다고 하더라도, 값을 읽고 결과를 쓰는 것은 별도의 메모리 처리(transaction)을 통해서 이루어지며, 이 두 처리 사이에 다른 프로세서가 i에 접근할 수도 있다. 예를 들어, 두개의 프로세서가 모두 ++i; 명령을 수행하였는데, 2가 증가하는게 아니라 1이 증가할 수도 있다는 것이다. 인텔 Pentium의 "구조(Architecture)와 프로그래밍 매뉴얼"에 따르면, LOCK 접두어는 다음에 나오는 명령어가 그것이 접근하는 메모리 위치에 대해 원자적으로 이루어지는 것을 보장하기 위해 사용된다.


BTS, BTR, BTC                     mem, reg/imm
XCHG                              reg, mem
XCHG                              mem, reg
ADD, OR, ADC, SBB, AND, SUB, XOR  mem, reg/imm
NOT, NEG, INC, DEC                mem
CMPXCHG, XADD

그렇지만, 이들 연산을 모두 사용하는 것은 그다지 좋은 생각은 아닌 것 같다. 예를 들어, XADD는 386에서는 존재하지도 않고, 따라서 이를 사용하는 것은 호환성의 문제를 발생시킬 수 있다.

XCHG 명령어는 LOCK 접두어가 없더라도 항상 락을 사용한다. 따라서 이 명령어는 세마포어(semaphore)나 공유 큐(shared queue)같은 고수준의 원자적인 구성체를 만드는 경우에 좋은 원자적인 연산이다. 당연히 C 코드로 GCC가 이 명령어를 만들어내도록 할 수는 없다. 대신 인라인(in-line) 어셈블리 코드를 조금 사용해야 한다. 워드(word) 크기의 volatile 객체인 obj와 워드 크기의 레지스터 값인 reg가 있다면, GCC 인라인 어셈블리 코드는 다음과 같다 :


__asm__ __volatile__ ("xchgl %1,%0"
                      :"=r" (reg), "=m" (obj)
                      :"r" (reg), "m" (obj));

락(lock)을 하는데 비트(bit) 연산을 사용하는 GCC 인라인 어셈블리 코드의 예제가 bb_threads library라이브러리의 소스 코드에 있다.

메모리 처리(transaction)를 원자적으로 만드는 것에도 이에 따르는 비용이 있다는 것을 기억할 필요가 있다. 보통의 참조는 지역 캐시를 사용할 수 있다는 사실에 비추어보면, 락(lock)을 하는 연산은 약간의 오버헤드를 수반하고, 다른 프로세서의 메모리 활동을 지연시킬 수 있다. 락(lock) 연산을 사용하는 경우 가장 좋은 성능을 내고 싶다면 가능한 이를 적게 사용하는 것이 좋다. 더 나아가 이들 IA32 원자적인 명령어들은 다른 시스템과의 호환성이 없다.

어떤 순간이든 많아도 하나의 프로세서만이 주어진 공유 객체를 갱신하는 것을 보장하는 여러가지 동기화(synchronization) - 상호 배제(mutual exclusion)를 포함하여 - 를 구현하는데 보통의 명령어를 사용할 수 있도록 하는 여러가지 다른 접근방법이 있다. 대부분의 OS 교재에서는 이들 기법을 적어도 하나 이상씩은 다루고 있다. Abraham Silberschatz와 Peter B Galvin이 지은 운영체제 개념(Operating System Concepts) 4판(ISBN 0-201-50480-4)에서 이를 아주 잘 다루고 있다.

캐시라인 크기(Cache Line Size)

원자성에 관련된 기본적인 것으로서 SMP 성능에 큰 영향을 미칠 수 있는 것으로 캐시라인 크기가 있다. MPS 표준에는 어떤 캐시가 사용되든지 간에 참조는 일관적이어야 한다고 하고 있지만, 사실은 하나의 프로세서가 메모리의 특정 라인에 기록을 할 때, 이전 라인의 캐시된 복사본이 모두 무효화(invalidate)되거나 갱신(update)되어야 한다. 이 말은 두 개나 그 이상의 프로세서가 동시에 같은 라인의 다른 부분에 데이터를 기록하려고 하면, 상당량의 캐시와 버스 통행(traffic)이 발생할 수 있으며, 실질적으로 캐시에서 캐시로 라인을 전달하게 된다. 이 문제는 잘못된 공유(false sharing)라고 한다. 그 해결책은 병렬로 접근되는 데이터가 되도록이면 각 프로세서마다 다른 캐시 라인에서 올 수 있도록 데이터를 조직화하도록 하는 것이다.

잘못된 공유는 L2 캐시를 사용하는 시스템에서는 문제가 안될거라고 생각할 수도 있겠지만, 여전히 별도의 L1 캐시가 있다는 것을 기억하자. 캐시의 조직과 구별된 별도의 레벨의 갯수는 모두 변할 수 있지만, Pentium L1 캐시라인 크기는 32 바이트이고, 전형적인 외장형 캐시라인 크기는 256 바이트 가량이다. 두 항목의 주소가 (물리적 주소이든, 가상 주소이든) ab이고, 가장 큰 프로세서당 캐시라인 크기가 c이고, 이들은 모두 2의 몇 제곱승이라고 하자. 매우 엄밀하게 하면, ((int) a) & ~(c - 1)((int) b) & ~(c - 1)이 같을 때, 두개의 참조가 똑같은 캐시라인에 존재하게 된다. 더 규칙을 간단화하면 병렬로 참조되는 공유 객체가 적어도 c 바이트가 떨어져 있다면, 이들은 다른 캐시 라인으로 매핑이 된다는 것이다.

리눅스 스케줄러 논점(Linux Scheduler Issues)

병렬처리에서 공유 메모리를 사용하는 전적인 이유는 OS의 오버헤드를 피하자는 것이지만, OS 오버헤드는 통신 그 자체 외의 것에서 발생하기도 한다. 우리는 이미 만들어야 할 프로세스의 갯수가 기계에 있는 프로세서의 갯수보다 같거나 작아야한다고 말했었다. 그러나 정확히 얼마나 많은 프로세스를 만들어야 할 지 어떻게 결정할 수 있을까?

최고의 성능을 내려면, 여러분이 작성한 병렬 프로그램에 있는 프로세스의 갯수는, 다른 프로세서에서 계속해서 실행될 수 있는 프로세스의 갯수하고 같아야 한다. 예를 들어, 네개의 프로세서가 있는 SMP 시스템에서 하나의 프로세스가 다른 목적으로 (예를 들어 WWW 서버) 동작하고 있다면, 여러분이 만든 병렬 프로그램은 세개의 프로세스만을 사용해야 한다. 시스템에 몇 개의 다른 프로세스들이 있는지는 uptime 명령에서 돌려주는 "평균 부하(load average)"를 참조하여 대강은 알 수 있다.

다른 방법으로 renice 명령이나 nice()




sponsored by andamiro
sponsored by cdnetworks
sponsored by HP

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2005-04-23 19:57:06
Processing time 0.0044 sec