정용화 박진원 성능평가연구팀선임연구원 성능평가연구팀책임연구원 팀장 본고는최근들어활발하게연구가진행중인병렬처리분야중에서여러가지병렬프로그래밍방법에대한정의및특징을살펴보고 대표적인사례에대해요약해본다 먼저데이터병렬성을이용한프로그래밍방법과대표적인프로그래밍언어 에대해살펴본후 어드레스공간이공유되는공유메모리 분산공유메모리시스템에서의프로그래밍방법과최근표준화작업이진행중인 에대해서알아본다 끝으로어드레스공간이공유되지않는분산메모리시스템에서의프로그래밍방법과표준메시지패싱인터페이스인 에대해서술한다 서론 컴퓨터기술은매우빠른속도로발전해가고있으며 그중에서도가장활발하게연구가진행중인분야는병렬처리 분야이다 병렬처리란다수의프로세서들이여러개의프로그램또는한프로그램의분할된부분들을분담하여동시에처리하는기술을말하며 이렇게함으로써처리시간이매우오래걸리는비효율성문제를극복할수있다 그러나병렬처리시스템의하드웨어분야가급격한발전을한것에비해 이러한시스템에서수행되는병렬소프트웨어에대한연구는빈약한실정이다 본고에서는병렬처리의구현을위한병렬프로그래밍모델에대한정의및특징을살펴보고 대표적인사례에대해요약해본다 병렬처리의구현을위한병렬프로그래 밍 에대한연구는크게두가지관점으로구분할수있다 먼저기존의순차형언어로작성된프로그램을병렬컴파일러를이용하여병렬프로그램으로변환하는관점이다 이방법은사용자로하여금병렬프로그램작성에관한부담을덜어줄수있기때문에이상적인방법처럼보일수있다 그러나병렬컴파일러에의해수행되는병렬화부분은극히제한적이고데이터종속성등의복잡한문제를해결해야하기때문에 병렬처리를수행하는관점에서는효율적이라할수없다 다른관점은병렬처리에적합한병렬프로그래밍언어를사용하여사용자가직접병렬프로그램을작성하는관점이다 이러한병렬프로그래밍방법은다시두가지로분류될수있는데 첫번째부류는기존의순차형언어에병렬성을추가하여언어를확장시킨것이고 두번째부류는전
1 int n; 2 float **A, diff=0; 3 main() 4 { read(n); 5 A malloc(a 2D array of size n+2 by n+2 doubles); 6 initialize(a); 7 Solve(A); 8 } 9 procedure Solve(A) 10 float **A; 11 { int i, j, done=0; 12 float diff=0, temp; 13 while (!done) do 14 diff=0; 15 for i 1 to n do 16 for j 1 to n do 17 temp = A[i,j]; 18 A[i,j] 0.2*(A[i,j]+A[i,j-1]+A[i-1,j]+A[i,j+1]+A[i+1,j]); 19 diff += abs(a[i,j] - temp); 20 if (diff/(n*n) < TOL) then done=1; 21 } 그림 미분방정식의해를구하는커널 혀새로운병렬프로그래밍언어를개발하는것이다 두번째부류의경우효과적인병렬프로그램을작성할수있다는장점이있으나 사용자입장에서기존의순차형언어와전혀다른새로운언어를익혀야한다는부담때문에대규모응용분야에활용되지못하고있는실정이다 따라서본고에서는전자의부류에속하는언어를기반으로하여 데이터병렬 공유메모리 메시지패싱등대표적인 가지프로그래밍모델로병렬프로그램을작성하는방법에대해살펴본다 데이터병렬모델 설명을위하여간단한미분방정식의해를구하는순차프로그램을 그림 에기술하였다그 림 에서 번줄의데이터종속성은대각선방향을갖지만 해가수렴할때까지 번줄의 을반복한다는의미에서앞으로논의할병렬프로그램들은 내에서의데이터종속성을무시한다 즉 하나의 내에서 그리드점의계산은독립적으로수행될수있다고가정한다 데이터병렬모델 은수행되는계산을대규모어레이데이터에서전역적변환을수행하는하나의제어쓰레드로간주할수있기때문에 이러한미분방정식의해를구하는커널에특히적합하다 즉 계산과데이터는유사하게취급되고 데이터의간단한분해와할당이부하분산을보장하며 규칙적인할당은간단한프리미티브에의하여서술될수있다
전자통신동향분석 제 권제 호 년 월 1 int n, nprocs; 2 float **A, diff=0; 3 main() 4 { read(n); read(nprocs); 5 A G_MALLOC(a 2D array of size n+2 by n+2 doubles); 6 initialize(a); 7 Solve(A); 8 } 9 procedure Solve(A) 10 float **A; 11 { int i, j, done=0; 12 float mydiff=0, temp; 13 DECOMP A[BLOCK, *]; 14 while (!done) do 15 mydiff=0; 16 for_all i 1 to n do 17 for_all j 1 to n do 18 temp = A[i,j]; 19 A[i,j] 0.2*(A[i,j]+A[i,j-1]+A[i-1,j]+A[i,j+1]+A[i+1,j]); 20 mydiff += abs(a[i,j] - temp); 21 REDUCE(mydiff,diff,ADD); 22 if (diff/(n*n) < TOL) then done=1; 23 } 그림 데이터병렬커널 그림 는데이터병렬프로그래밍모델에의한프로그램의예를보여주고있다 특징적인부분은먼저 번줄에서동적으로할당된공유데이터 가일반적인 이아닌광역인 으로할당된다 이외에순차프로그램과다른부분은 번줄의문 번줄에서 루프대신에 루프 프로세스당개별적인 변수사용 번줄의문등이있다 여기서 루프는 이병렬로수행될수있다는것을의미하고 문은 을프로세스에할당하는목적외에도분산메모리머신상에서데이터가어떻게배분되느냐를지정하는데에도사용된다 특히 그림 의경우는첫번째좌표 행 가 개의프로세스에 집단적으로배분되고두번째좌표 열 는전혀배분되지않는 할당을나타낸다 또한 변수는각각의프로세스가할당된그리드점에대한계산을독립적으로수행할수있게해주며 문은시스템으로하여금부분적인 값들의합을공유변수 로나타낼수있게해준다 이러한데이터병렬프로그래밍을위한표준언어로는 년대초 이최초로발표되었으며 추가적인병렬 및데이터위치지정지시어 가보완된 이 년에 포럼에의해발표되었다 데이터병렬표준언어인 의주요기능을요약하면 표 과같고 자세한내용
은 에서볼수있다 표 주요기능 관련 관련 기타 데이터병렬프로그래밍모델은 그림 에나타낸미분방정식의해를구하는커널과같이대규모어레이데이터에서규칙적인계산에대한배분및할당을지정하는데적합하지만 계산의배분이나통신패턴이시간에따라예측불가능하게변하는불규칙응용에는적합하지않다장과 장에서는프로세스들이각자의제어쓰레드를갖고개별적으로통신할수있는보다유연하고 그러나좀더낮은수준의프로그래밍모델들에대해서살펴볼것이다 공유메모리모델 공유어드레스공간에서는데이터병렬모델에서와같이행렬 를간단히공유어레이로선언할수있으며 프로세스들이순차프로그램에서와똑같은색인으로 함으로써공유어레이를액세스할수있다 통신은필요에따라서암시적으로생성된다 그러나명시적인병렬프로세스에의하여 프로세스를생성하고동기에의해조정하고계산을프로세스에할당할수있는메커니즘이필요하다 본고에서살펴보는프리미티브는 와같이일반적으로낮은수준의프 로그래밍환경을의미하고 대표적인프리미티브를요약하면 표 와같다 표 기본적인공유어드레스공간프리미티브 형식 의미 로 를수행하는 프로세스를생성 바이트의공유데이터를할당상호배타적인액세스를획득상호배타적인액세스를해제 프로세스간전역동기 프로세스의종료를대기 공유어드레스공간에서의병렬커널에대한프로그램을 그림 에나타냈다 병렬성을위한특별한프리미티브는진하게표시하였고 일반적으로라이브러리호출이나매크로로구현된다 먼저하나의메인프로세스가운영체제에의하여프로그램수행을시작한다 번줄에서 을이용하여그리드 를공유어드레스공간에 차원어레이로할당한후초기화한다 또한본고에서는 이나 처럼전역데이터는공유되고 등과같이프로시저의스택에있는데이터는그프로시저를수행하는프로세스에한정된다고가정하자 그리고 번줄에서프로시저 를수행할 개의프로세스를생성하고메인프로세스자신도 를호출함으로써 총 개의프로세스가그프로시저의병렬수행을가능케한다 여기서계산을프로세스에할당하는것과어떤데이터를액세스하느냐는 와같이다른프로세스에서상이한값을갖는몇개의지역변수들과루프제어변수들에의하여결정된
전자통신동향분석 제 권제 호 년 월 1 int n, nprocs; 2 float **A, diff; 3 LOCKDEC(diff_lock); BARDEC(bar1); 4 main() 5 { read(n); read(nprocs); 6 A G_MALLOC(a 2D array of size n+2 by n+2 doubles); 7 initialize(a); 8 CREATE(nprocs-1,Solve,A); 9 Solve(A); 10 WAIT_FOR_END; 11 } 12 procedure Solve(A) 13 float **A; 14 { int i, j, done=0, pid; 15 float mydiff=0, temp; 16 int mymin 1+(pid*n/nprocs); mymax mymin+n/nprocs-1; 17 while (!done) do 18 mydiff=diff=0; 19 for i mymin to mymax do 20 for j 1 to n do 21 temp = A[i,j]; 22 A[i,j] 0.2*(A[i,j]+A[i,j-1]+A[i-1,j]+A[i,j+1]+A[i+1,j]); 23 mydiff += abs(a[i,j] - temp); 24 LOCK(diff_lock); 25 diff += mydiff; 26 UNLOCK(diff_lock); 27 BARRIER(bar1,nprocs); 28 if (diff/(n*n) < TOL) then done=1; 29 BARRIER(bar1,nprocs); 30 } 그림 공유어드레스공간에서의병렬커널 다 예를들어 를이용하여어떤행을어떤프로세스에할당할것인가가 번줄에명시되어있다 다음은 루프인데 각각의 은여러프로세스에의해병렬로수행될수있다 여기서다음 수행여부를결정하는 번줄의계산은각각의프로세스에의해별도로이루어진다 비록이계산은중복되어수행되지만 완료프래그를송수신하는것보다는훨씬경제적이다 실질적으로갱신을수행하는 번줄은순차프 로그램과기본적으로동일하다 할당을위한루프제어문의경계를제외할때유일한차이는각프로세스가자체의지역변수 를관리한다는점이다 이러한지역변수는각각의 마지막에공유변수 에적립된다 번줄이후의남은부분중흥미로운부분은상호배타적동기 와사건동기 이다 먼저여러프로세스에의한공유변수로의적립은상호배타적으로이루어져야한다 즉 번줄의위험지역
의상호배타적수행을위하여 번줄의 쌍이사용된다과같은록은배타적권한을제공하는공유토큰으로간주될수있다 프리미티브에의한이러한록의획득은프로세스에게그위험지역의수행을허용한다 그프로세스는위험지역의수행을완료할때 프리미티브를이용하여그록을해제한다 이때 프리미티브는상호배타적동기를보장하도록구현되어야한다 일단프로세스가자신의 를전역 에적립하면 모든프로세스가동일한동작을수행하여 에적립된데이터가모든그리드점에대해유효한값을갖도록기다려야한다 이는 로구현된전역사건동기를필요로한다 즉 이 동작은참여하는다른모든프로세스가이동작을수행할때까지각각의프로세스는기다려야한다 일단 를통과하면 번줄에서각프로세스는 값을읽고모든그리드점의평균차이 가오류한계 에미치지못하는지를확인한다 확인결과오류한계에미치지못하면그 루프를빠져나오기위해 프래그를세트하고 오류한계를초과한다면또다른 을수행한다 마지막으로메인프로세스에서수행되는번줄의 는특별한형태의동기로 메인프로세스는자신이생성한 개의프로세스가종료되기를기다린다 이때다른프로세스들은 를호출하지않지만 프로시저를종료함으로써암시적으로동기에참여한다 요약하면 이간단한커널의예에서보여준병렬프로그램은구조적으로순차프로그램과크게다르지않다 가장큰차이는루프의경계를변화시킨제어흐름과간단하고포괄적인동기화프리미티브에있다 계산루프의주요부분이나주요자료구조및이에대한참조는순차프로그램과차이가없다 일반적으로간단한프로그램은이러한분할과할당만으로도병렬화되지만 복잡한프로그램에서보다높은성능을얻기위해서는많은변화가필요할수도있다 지금까지공유어드레스공간에서의병렬커널프로그래밍에대해서살펴보았다 이러한공유어드레스공간을이용하는프로그래밍방법은지난 년간발표된많은버스기반의공유메모리시스템과최근에급부상하고있는분산공유메모리시스템에서꾸준히발전해왔다 그러나각각의시스템이상이한프로그래밍환경을제공한결과 특정한시스템에서개발된병렬프로그램이다른시스템에서동작하지않는이식성의문제점이있었다 이러한이식성의문제를해결하기위하여공유메모리프로그래밍모델의표준으로 가 년에제안되었으나 루프수준의병렬성만을제공하는등여러가지제약에의하여널리사용되지않고있었다 그러나비슷한시기에발표된메시지패싱표준의급격한보급에자극받아 와 등의몇몇업체를중심으로 에기반한새로운공유메모리표준에대한논의가시작되었고 년말라는표준을발표하게되었다 컴파일러지시어 에기반한 의프로그래밍방법은기존에존
전자통신동향분석 제 권제 호 년 월 표 주요부분 관련 관련 관련 관련 관련 관련 재하는순차프로그램을신속히병렬화할수있을뿐만아니라 개발된프로그램은 워크스테이션에서부터 개의프로세서를장착한 수퍼컴퓨터까지광범위하게사용될수있다 특히 개념에의해서 병렬알고리즘을간단히구현할수있으므로 기본적인루프수준의병렬성만을지원하는 의문제점을크게보완하였다 현재 에대한바인딩만을제공하지만 년말까지 에대한지원도계획하고있으며 광범위한응용분야에서활용될것으로기대된다 의주요부분을요약하면 표 과같고 자세한내용은 에서볼수있다 메시지패싱모델 마지막으로지역적인어드레스공간에서명시적인메시지패싱 에의한병렬커널에대해서살펴보자 우선공유어드레스공간이존재하지않으므로 행렬 를공유한다고선언하여각프로세스로부터의액세스를가능케할수가없다 따라서자료구조 는프로세스들의지역적인어 드레스공간에걸쳐서할당되는몇개의작은자료구조들에의해서표현되어야한다 그림 에메시지패싱프로그램의예를나타낸다 이렇게간단한프로그램에서는 그림 에서보여준공유어드레스공간에서의프로그램과구조적으로큰차이가없다 가장큰차이는논리적으로공유되는행렬 를표현하기위한자료구조와어떻게프로세스간통신이구현되느냐에달려있다 먼저그행렬을 크기를갖는하나의어레이 로표현하는대신에 각프로세스는 크기의어레이 를자신의지역어드레스공간에할당한다 이어레이는 행렬의 개의행과인접한경계의데이터를유지하기위한 개의추가적인행으로구성된다 여기서인접한경계행은명시적으로통신되어야하고추가적인행에저장된다 특히 메시지패싱프로그램에서는통신과동기가모두 개의프리미티브 에의해서수행된다 일반적으로공유어드레스공간에서는데이터전송이수신측에서 명령에의
1 int n, nprocs, pid; 2 float **mya; 3 main() 4 { read(n); read(nprocs); 5 CREATE(nprocs-1); 6 Solve(); 7 WAIT_FOR_END; 8 } 9 procedure Solve() 10 { int i, j, done=0, pid, n'=n/nprocs; 11 float mydiff=0, temp; 12 mya malloc(a 2D array of size [n/nprocs+2] by n+2); 13 initialize(mya); 14 while (!done) do 15 mydiff=0; 16 if (pid!= 0) then SEND(&myA[1,0],n*sizeof(float),pid-1,ROW); 17 if (pid!= nprocs-1) then SEND(&myA[n',0],n*sizeof(float),pid+1,ROW); 18 if (pid!= 0) then RECEIVE(&myA[0,0],n*sizeof(float),pid-1,ROW); 19 if (pid!= nprocs-1) then RECEIVE(&myA[n'+1,0],n*sizeof(float),pid+1,ROW); 20 for i 1 to n' do 21 for j 1 to n do 22 temp = mya[i,j]; 23 mya[i,j] 0.2*(myA[i,j]+myA[i,j-1]+myA[i-1,j]+myA[i,j+1]+myA[i+1,j]); 24 mydiff += abs(mya[i,j] - temp); 25 REDUCE(0,mydiff,sizeof(float),ADD); 26 if (pid == 0) then 27 if (mydiff/(n*n) < TOL) then done=1; 28 BROADCAST(0,done,sizeof(int),DONE); 29 } 그림 메시지패싱을이용한병렬커널 하여시작되지만 메시지패싱프로그램에서데이터전송을시작하는것은 동작이다 메시지가수신프로세서에도착하면 그프로세서에서 를수행할때까지그메시지는네트워크큐나시스템버퍼에일시적으로저장된다에의해서그프로세스는수신된메시지를네트워크큐나시스템버퍼로부터지역적인 응용프로그램의 어드레스공간의지정된위치에옮겨놓는다 즉 자체는데이터가네트워크를통하여전송되는동작과무관하 다 또한일반적으로 나 는특정아키텍처의라이브러리형태로구현된다 지금까지여러가지버전의 프리미티브가개발되었으나 의미론적으로동기적 비동기적 블로킹 논블로킹등으로구분할수있다 이중가장간단한형태인동기적 는대응하는 가수행된것이확실한경우에만제어가호출프로세스로넘겨진다 그리고동기적 는지정된수신버퍼에데이터가저장된때제어를호출프로세스로넘긴다
전자통신동향분석 제 권제 호 년 월 표 기본적인메시지패싱프리미티브 형식 를시작하는프로세스생성 프로세스간전역동기 프로세스의종료를대기 의미 부터 바이트를 식별자와함께 프로세스로전송 프로세스로부터 식별자를갖는 바이트의메시지를수신하고이를 에서시작하는버퍼에저장 식별자를갖는메시지가 프로세스로전송되었는지를확인 식별자를갖는메시지가 프로세스로부터수신되었는지를확인 표 프리미티브 프로세스관리관련 통신자관리관련프로세스그룹 관리관련 그룹관리관련 일대일통신 블로킹 관련 논블로킹 집합통신관련 기타 사실이러한동기적 쌍을사용하면 번줄의통신은교착상태를발생시킨다 교착상태를피하는첫번째방법은절반의프로세서는 후 를호출하고나머지절반의프로세서는 후 를호출하도록하는것이다 또다른방법으로는다른의미를갖는 를사용하는것이다 예를들어블로킹비동기적 는 전송하는응용의자료구조로부터그메시지가복사되어시스템의책임하에전송될수있는상태가될때 제어가호출프로세스로넘겨진다 이는동기적 와비교할때전송프로세스의신속한제어복귀를허용하지만제어복귀자체가수신프 로세스로의메시지전송을의미하지는않는다 또한논블로킹비동기적 는가장신속히제어를복귀시킴으로써계산과메시지패싱간중복을최대한허용한다 이는제어복귀가즉시수행되지만제어복귀자체가메시지의상태나응용자료구조에대해아무런의미를보장하지못하기때문에 필요에따라그상태를확인 하는것이사용자의책임으로남게된다 이러한비동기적통신은교착상태를피하고성능을최적화할수있지만프로그래밍이복잡해진다는단점도있으므로 목적에맞게적절히사용되어야한다 다시 그림 의메시지패싱프로그램에대해살펴보자 번줄의프로세스간통신이공유
어드레스공간에서의개별적인데이터에대해서가아니라집단적으로이루어진다 물론개별적인데이터에대한메시지패싱이가능하지만 송수신오버헤드가상당히크기때문에적합치않은방법이다 일단프로세스가인접한경계행을수신하면 할당된그리드점에대한계산을순차프로그램이나공유어드레스공간에서의프로그램과거의동일하게수행할수있다 차이점은루프경계가 순차프로그램의 에서 이나공유어드레스공간에서의 에서 가아닌에서 이라는점이다 사실개별적인어드레스공간을갖는메시지패싱프로그램의 번줄에서다른프로세스에의해서참조되는동일한이름의 는논리적으로공유되는 의상이한행을지칭한다 마지막으로개별적인 변수를논리적으로공유되는 변수로적립하거나 조건을평가하는등의동기화동작은공유어드레스공간에서의동작과완전히다르게수행된다 예를들어 동기적 쌍은동기사건을내포하여 상호배타적접근및사건동기를위하여 등의특별한동작및추가적인변수가필요치않다 또한자주사용되는통신패턴의효과적인사용을위하여여러프로세스가참여하는집합 통신에대한프리미티브들이제공되기도하는데 예를들어 번줄의 여러프로세스의개별적인변수들로부터한프로세스의단일변수로적립 와 번줄의 하나의프로세스에서모든프로세스로전송 등이있다 지금까지언급한기본적인메시지패싱프리미티브들을요약하면 표 와같고 년에 포럼에의해발표된표준 에서제공되는프리미티브들은 표 와같다 초기의메시지패싱라이브러리로 이산업표준으로채택되어사용되기도하였으나 성능상의문제로인하여현재는 에비하여많이사용되고있지않다 특히 포럼에서는표준에포함되지않은새로운개념들에대한지속적인논의끝에 라는새로운표준의초안을 년말에발표하였는데 대표적인내용으로는프로세스생성및관리 일방적인 통신 집합통신의확장 외부인터페이스 병렬 등이있다 또한 에서는 외에도 언어로의바인딩을제공한다에대한자세한내용은 에서볼수있다 참고로지금까지설명한데이터병렬의표준인 공유메모리표준인 그리고메시지패싱의표준인 의상대적인특징을비교하면 표 과같다 표 병렬프로그래밍표준의비교 맺음말 지금까지대표적인병렬프로그래밍모델에대한정의및장단점등에대해알아보았고 이를이용하여병렬화하는구체적인사례를살펴보았다 또한각각의프로그래밍모델에서급격히보급되
전자통신동향분석 제 권제 호 년 월 고있는표준언어들의특징에대해서도알아보았다 병렬프로그래밍모델은그모델이고려하는병렬성지원수준및난이도등각기다른특징을지니고있기때문에 어떤응용문제에적합한방법이다른응용문제에서는적합치않을수가있다 따라서 현재까지는여러가지응용문제에모두적합한이상적인방법은존재하지않으며 수행되는병렬시스템과해결하고자하는응용문제에따라서적합한프로그래밍방법을결정해야할것이다 참고문헌 병렬처리특집 정보과학회지