SGI Origin 3000 수퍼컴퓨터를 이용한 병렬처리로 (아래의 내용을 읽은 후에 이동하여 읽을 것을 권장함)

병렬처리란? 

컴퓨터가 개발된 이래 컴퓨터의 두뇌에 해당되는 프로세서는 눈부신 발전을 거듭하였지만 처리해야 되는 작업이 지속적으로 대형화됨에 따라 단일 프로세서로 처리할 수 있는 능력의 한계에 도달하게 되었다. 이러한 난관을 극복하기 위하여 대두된 방법이 병렬 처리이다. 병렬 처리란 쉽게 말해서 하나의 작업을 처리하기 위해서 동시에 여러 개의 프로세서를 사용하여 작업의 처리 속도를 높이는 것을 말한다. 이렇게 다중프로세서를 동시에 사용하는 병렬처리를 통해 얻을 수 있는 성능 향상은 다음과 같이 기술될 수 있다.

하나의 프로세서를 사용하여 작업을 수행하였을 때 소요된 시간을 t라고 할때 p개의 프로세서를 사용하였을 때 이상적인 소요시간은 t/p일 것이다. 하지만 실제 병렬 처리에서 얻을 수 있는 성능은 알고리듬의 문제, 네트워크 문제 등으로 인하여 이보다 떨어지게 되는 것이 보통이다. 이러한 성능 향상으로 인하여 얻을 수 있는 가장 큰 장점은 각 분야의 연구자들이 컴퓨터의 자원부족으로 그동안 풀 수 없었던 문제들을 병렬처리를 통해 풀 수 있게 되었다는 것에 있다.

주어진 프로그램에서 데이터를 병렬 처리하느냐 또는 작업을 분할하여 병렬 처리하느냐에 따라 data parallelism 과 task parallelism으로 구분된다.

Data Parallelism

data parallelism에서는 동일한 code의 segment를 각각의 프로세서에서 동시에 실행하는 방법으로 각 프로세서는 처리해야 하는 데이터의 영역을 분할 할당 받는다. 이 방법은 Fortran에서 사용되는 Do 루프 같은 곳에 적용하여 사용할 수 있다. Data parallelism은 계산작업을 많은 수의 작은 subtask로 분산하는 방법이기 때문에 fine grain parallelism이라고도 불리운다.

다음과 같은 Fortran 프로그램은 Data parallelism의 예로 사용될 수 있다. 아래와 같은 행렬연산 문제는 data parallelism 에 가장 적합한 예제이다. 다음의 Fortran code는 행렬간의 곱셈문제이다.

Original code에 대한 병렬화는 프로세서간에 작업을 분할 배당하기 위해 필요한 OpenMP 디렉티브(directives)를 삽입하는 방법으로 이루어진다. 위의 code는 다음과 같이 간단한 디렉티브를 삽입하여 병렬화된 code로 변경할 수 있다.

OpenMP는 병렬 디렉티브의 표준으로 많은 하드웨어 업체들이 채택하고 있다. OpenMP 디렉티브는data parallelism과 task parallelism에 모두 적용될 수 있다. SGI사는 OpenMP의 지원 및 개발을 주도하고 있는 회사이다. OpenMP에 대한 정보를 자세히 알고 싶으면 OpenMP website(http://www.openmp.org)를 방문하면 된다.

OpenMP에서 병렬로 처리되는 루프는 디렉티브 바로 다음에 오는 루프이다. 위의 예제에서 병렬로 실행되는 루프는 K 루프 (DO K=1,N) 이다.

각 프로세서는 서로 다른 데이터 어레이 영역을 할당 받어서 실행을 하게 된다. K 루프에서 N이 20이고 사용된 프로세서가 4라고 할 때 각 프로세서는 다음과 같이 데이터 영역을 할당 받어 처리하게 된다.

Processor	Iterations of K	Data Elements
proc0	K=1:5	A(I, 1:5) B(1:5 ,J)
proc1	K=6:10	A(I, 6:10) B(6:10 ,J)
proc2	K=11:15	A(I, 11:15) B(11:15 ,J)
proc3	K=16:20	A(I, 16:20) B(16:20 ,J)

Data parallelism에서는 각 프로세서가 동일한 code segment를 실행하게 되는데 위의 예제에서는 다음과 같은 segment가 각 프로세서에서 동일하게 실행된다.

Data parallelism은 병렬화를 점진적으로(incrementally) 할 수 있다는 편리성이 있다.

점진적 병렬화의 의미는 프로그램 전체를 한꺼번에 병렬화 시키는 것이 아니라 계산량이 많은 루프부터 병렬화 시키고 원하는 병렬효율이 커질 때까지 다른 루프를 점진적으로 병렬화하여 실행할 수 있다는 것이다.

Task parallelism은 다중의 독립된 code segments를 각 프로세서에 분산하여 동시에 실행하는 방법을 쓰는 병렬 기법이다. 이 기법은 주어진 code를 여러 개의 부분들로 분할하여 각 프로세서에서 독립적으로 동시에 실행하는 것이 가능할 때 사용하는 방법이다. Task parallelism 은 계산 작업을 작은 수의 subtasks로 분할하여 실행하기 때문에 coarse grain parallelism으로 불리운다. 이 방법은 data parallelism 보다 높은 수준에서 병렬기법이 적용되기 때문에 일반적으로 병렬효율이 더 높은 방법이다. 이 방법은 parallel overhead가 작고 data parallelism에 비해 적용이 쉽다는 장점이 있지만 code의 특성상 각 부분들이 밀접하게 연결되어 데이터를 주고 받아야 되는 경우에는 적용하기 곤란한 방법이다.

다음과 같은 abstract code를 병렬화하는 것을 예를 들면,

이 경우에도 다음과 같이 OpenMP 디렉티브를 삽입하여 task parallelism을 구현할 수 있다.

OpenMP SECTION 디렉티브를 사용하게 되면 각 SECTION은 다른 프로세서에 할당되게 된다. 위의 code를 4개의 프로세서를 사용하여 처리한다고 할 때 각 프로세서는 다음과 같은 code segments를 할당받아 처리하게 된다.

위와 같은 병렬처리 기법을 사용하여 병렬처리를 할 경우 얻을 수 있는 성능향상은 이상적인 경우에 프로세서의 수가 늘어나는 것에 비례하여 선형적으로 늘어나야 하지만 여러 가지 성능 제한 요소들로 인하여 그렇지 못한 경우가 대부분이다. 이러한 병렬 성능향상의 한계를 기술한 법칙이 Amdahl's law이다. 이 법칙에 의하면 주어진 code에서 병렬로 실행되지 않는 부분이 성능을 제한하며 성능향상의 상한선이 정해진다고 한다. 이 법칙은 다음과 같이 수식화 될 수 있다. 주어진 code에서 F % 만큼 병렬화 된다고 할 때 프로세서의 숫자가 무한개로 늘어나도code는 100/(100-F) 보다 빠르게 실행될 수 없다. 그리고 주어진 프로세서의 수 P개에서 얻을 수 있는 최대 병렬효율은 다음과 같이 표시된다.

여기서 성능 향상비인 Speed Up Ratio는 P개의 프로세서를 사용했을 경우 얻은 계산 소요시간과 1개의 프로세서를 사용했을 경우 얻은 소요시간을 나누어서 얻을 수 있는 값이다.

위의 두 식을 이용하면 주어진 code에서의 병렬화 정도를 나타내는 F를 계산할 수 있고 이를 이용하면 병렬계산을 통해 얻을 수 있는 최대의 성능 향상비를 알 수 있게 된다.

C나 Fortran같은 언어를 이용하여 병렬 프로그래밍을 구현하기 위해서는 프로세서간의 통신 등을 지원하는 병렬 프로그래밍 지원 라이브러리의 도움이 필요하다. 병렬 컴퓨터 개발 초기에서 하드웨어 업체들마다 서로 다른 병렬 라이브러리를 개발하여 지원을 하였지만 병렬 컴퓨터가 확산되면서 성능 문제나 포팅(Porting) 문제 등으로 인해 많은 병렬 지원 라이브러리가 사라지고 현재에는 공유 메모리형 병렬 지원 라이브러리인 OpenMP와 분산 메모리형 병렬 지원 라이브러리인 MPI(Message Passing Interface)만이 광범위하게 사용되고 있다. OpenMP와 MPI는 각각 http://www.openmp.org 와 http://www.mpi-forum.org 라는 비영리기관에서 표준을 정하고 있고 대부분의 하드웨어 업체들이 지원을 하고 있어 이들 라이브러리를 사용하여 개발을 할 경우 여러 하드웨어에서 수정 없이 사용할 수 있다는 장점을 가질 수 있다.

OpenMP의 표준은 1996년에 SGI사가 공유 메모리형 병렬 컴퓨터에서 소스 코드의 호환성을 갖는 병렬 프로그래밍 인터페이스를 만들기 위해 시작되었다. 이 프로젝트는 SGI사가 슈퍼 컴퓨터의 대명사였던 Cray사를 인수하면서 벡터 컴퓨터와 스칼라 컴퓨터에서 공히 사용할 수 있는 API(Application Programming Interface)의 필요성으로 인해 개발 속도가 가속화되어 1997년에 Fortran에 대한 OpenMP의 표준이 발표되고 1998년에 C/C++에 대한 표준이 뒤이어서 발표되었다. 2000년에는 Fortran 95에 대한 표준이 OpenMP V2.0에 포함되어 발표되었다. OpenMP는 OpenMP를 지원하는 컴파일러에서 인식할 수 있는 디렉티브(Directives)기반의 API이다. 프로그램 개발자는 기존 원시 code의 수정 없이 OpenMP에서 지정된 적절한 디렉티브를 삽입함으로써 손쉽게 병렬 프로그램화 할 수 있다. OpenMP는 아래의 예와 같이 Fortran에서의 Do 루프같은 곳에 주로 사용되어 병렬화 하기 때문에 종종 Loop Level Parallelism으로 불리기도 한다.

OpenMP는 병렬 디렉티브를 프로그램의 일부분에만 삽입하는 단계적인 병렬화(Incremental Parallelism)의 적용이 가능하기 때문에 상대적으로 접근이 용이하다. 또 기존 직렬 프로그램의 수정을 최소화할 수 있고 디버깅이 쉽다는 장점을 가지고 있다.

OpenMP는 공유 메모리를 갖는 병렬 컴퓨터에서 공히 사용할 수 있는 업계의 표준이기 때문에 이식성이 뛰어난 API이다.

MPI는 각 프로세스간에 데이터 교환을 지원해주는 Functions(C 언어의 경우)과 Subroutines(Fortran 언어의 경우)을 모은 라이브러리를 지칭한다. MPI의 표준이 제정되기 전까지는 초병렬 컴퓨터(Massively Parallel Processor)와 같은 분산 메모리형 컴퓨터마다 서로 다른 Message Passing Library를 가지고 있어 프로그램 개발자에게 부담이 되었다. 이러한 문제점을 해결하기 위해 40여개의 기관을 대표하는 MPI Forum(http://www.mpi-forum.org)가 결성되어 2년여의 노력 끝에 개발된 것이 MPI이다. 최초의 MPI 표준은 1994년에 제정된 MPI-1 표준이고 현재에는 일방향 통신(One-Sided Communication)이 가능해진 MPI-2 표준이 개발되어 발표되었다. 이 표준은 각 함수 또는 서브루틴의 이름과 해당되는 Output, calling sequences등을 기술하고 있어 MPI 표준을 지원하는 모든 하드웨어에 개발된 프로그램을 공히 사용할 수 있는 뛰어난 이식성을 보장한다. 각 하드웨어 제조업체는 MPI 표준을 지원하면서 제품의 특성에 맞는 최적화된 MPI 버전을 탑재하고 있다.

MPI 프로그램은 일반적으로 다음과 같은 형태를 가지고 있다.

MPI header file로 C에서는 #include <mpi.h>, Fortran에서는 INCLUDE 'mpif.h'를 사용한다.

이 파일에는 모든 MPI Function과 Subroutine에 대한 정의가 되어 있다. 이를 정의한 후에 MPI를 사용하기 위해서는 반드시 MPI 환경을 초기화 시켜줘야 하고 프로그램 마지막에는 MPI를 종료 시켜줘야 한다. MPI의 초기화에는 MPI_Init을 사용하고 MPI_Comm_rank, MPI_Comm_size를 사용하여 MPI의 실행을 위한 초기 환경을 구축한다. 이후에 MPI_RECV나 MPI_SEND같은 메시지 통신함수를 이용하여 병렬계산을 수행하고 MPI_FINALIZE를 불러 MPI 프로그램을 종료시킨다.

MPI는 단순히 디렉티브만을 삽입하는 OpenMP와는 달리 개발자가 많은 것을 지정해줘야 한다. MPI는 단계적 병렬화를 구현할 수 없고 기존 직렬 프로그램의 수정이 많이 필요해 개발시간이 오래 걸리는 단점이 있지만 일단 개발이 완료되면 여러 하드웨어에서 사용할 수 있고 병렬 성능도 뛰어나다.

병렬 프로그램에서 좋은 병렬 효율을 보이기 위해서는 각 프로세스에 동일한 크기의 일을 수행할 수 있도록 일을 분배해야 한다. 그렇지 못하면 가장 많은 일을 할당 받은 프로세스가 종료 될 때까지 다른 프로세스는 대기 상태에 있기 때문에 병렬 효율이 크게 떨어지게 된다. 이러한 문제를 load balancing 문제라고 한다. 많은 계산문제에서 작업량을 균등하게 분배하는 것은 쉬운 일은 아니며 각 응용분야에서 적절한 분배를 위한 여러 가지 load balancing technique이 개발되어 사용되고 있다

병렬 슈퍼 컴퓨터의 성능을 제대로 활용하기 위해서는 풀고자 하는 문제의 크기가 적절해야 한다. 단일 프로세서로도 충분한 문제를 병렬로 처리할 경우 계산시간 대비에서 프로세스간의 통신에 소요되는 시간이 더 커지게 되기 때문에 기대하는 만큼의 성능이 나오지 않을 것이다.

병렬 슈퍼 컴퓨터 사용자들에 중요한 부분 중의 하나는 좋은 software tools이라고 할 수 있다. 이러한 도구들 중에 주로 사용되는 것에는 다음과 같은 것들이 있다.

- 병렬 컴파일러(parallel compilers)
- 병렬 디버거(parallel debuggers) [ PDF ]
- 성능해석도구(performance analysis tools) [ PDF ]  
- 병렬 계산 소프트웨어 라이브러리(parallel math software library)

참고 1: For performance analysis: http://techpubs.sgi.com > search speedshop (enter) 하여 찾아서 가져온 Book :  32% SpeedShop User's Guide (즉, 위의 성능해석도구란의 PDF 파일)를 클릭하여 SpeedShop 관련 명령어들의 사용법을 읽은 후, 
예를 들어,  본 서버의 /usr/demos/SpeedShop/generic 디렉토리에 있는 generic.c 파일을 본인의 HOME directory 로 copy 해 온 후,  
% cc generic.c (enter)     하여 컴파일한 후에, 
% ssrun -pcsampx a.out (enter)       하여 ssrun(SpeedShopRun)을 실행한 후,
% ls -la a.out.* (enter)      하여 새로 생성된 파일이나 사람이 읽을 수 없는 매우 긴 이름의
                                    "a.out.?숫자" 파일을 확인한 후,
% prof a.out.?숫자 (enter)   하면, a.out 실행파일의 성능을 ASCII 파일 형태로 볼 수 있다. 
참고 2: For parallel debuggers: http://trinitas.mju.ac.kr/infosearch > search workshop (enter), and refer to % /usr/demos/WorkShop directory.
참고 3: For parallel math software library: SCSL(Scientific Computing Software library) 소개 및 http://trinitas.mju.ac.kr/infosearch > search scsl (enter).
참고 4: For parallel compilers: SGI Origin 3000 수퍼컴퓨터를 이용한 병렬처리로