병렬 성능과 확장성의 정량화

실제 성능향상도 S(n)은 Amdahl의 법칙을 따르지 않는다. 프로세서 개수가 작을 때는 S(n)=n의 이상적 성능향상도에 가깝다가, 이후 급격히 감소된다. 이것은 프로세스에서 계산을 위해 소비된 시간보다 더 많은 시간이 통신에 소비되기 때문이다.

경우에 따라서 측정된 성능향상도가 S(n)=n을 초과하는 경우도 있는데 이를 superlinear speedup 이라고 한다. 상황에 따라 그 원인을 확실하게 밝히는 것이 어렵지만, 대부분은 캐시 효과 때문이 다. 프로세스에서 사용되는 메모리 양이 프로세서의 outermost 캐시 크기의 정수배 정도로 줄면 캐시 사용률이 거의 100%가 되고 이때 메인 메모리의 속도는 성능에 영향을 주지 않게 된다.

성능향상도를 프로세서 개수로 나눈 병렬효율도 자주 사용된다. 병렬효율은 순차 프로세스와 비교 해 각 병렬 프로세스가 평균적으로 어느 정도의 성능을 발휘했는가를 나타내는 데, 이상적인 수치 는 1이다. 대부분 1보다 작은 값을 가지며 만약, superlinear의 경우라면, 1보다 큰 값을 보일 것 이다.

5.2. 병렬 프로그램의 병목 지점

성능을 저하시키는 병목 지점을 찾는 것이 복잡하고 어려운 일이지만, 병렬 프로그램 최적화 과정 에서 순차화와 불필요한 통신 등에 의해 야기된 문제들을 찾아내는 것은 반드시 필요하다.

5.2.1. 순차화

코드 확장성에 가장 나쁜 영향을 주는 것은 하나의 프로세스가 작업을 완료할 때까지 많은 프로 세스들이 기다리게 되는 순차화이다.

- MPI_Barrier 등과 같은 동기화 루틴을 포함한 집합 통신의 과도한 사용.

- 하나의 프로세스가 입력 파일을 읽어 들이고, 다른 프로세스들은 그것을 기다리는 상황 과 같은 단일 프로세스 I/O의 사용 Æ 병렬 I/O 사용을 권장

- blocking 점대점 통신의 사용 Æ non-blocking 점대점 통신의 사용 권잗

5.2.2. 불필요한 통신

통신은 계산보다 훨씬 많은 시간을 소비한다. 1GHz 클럭 속도를 가지는 프로세서의 경우 4사이클 이 소비되는 부동소수 연산은 4ns에 완료되지만, Quadrics(3.2Gbit/s link speed, 250~350 MB/s 대역폭, 2~5μs latency를 가지는 네트워크 장비)상에서 크기가 0인 데이터를 MPI_Send()를 이용 해 전송할 경우 최소 소프트웨어 latency는 약 4μs 정도가 소비된다.

- 작은 데이터를 여러 번 통신하는 경우 가능하다면 한 번의 큰 데이터 통신으로 대체하 는 것이 좋다.

- 집합 통신의 과도한 사용을 자제한다. 예로, Reduce로 충분한 곳을 Allreduce를 사용하 지 말 것.

5.3. 통신성능

메시지 패싱 프로그램에서 통신성능은 전체 프로그램의 성능에 영향을 준다. 통신성능을 분석하는 방법과 통신성능 향상을 위한 MPI 특성 이용 방법 등에 대해 알아본다.

5.3.1. 통신성능에 영향을 주는 요인들

통신성능에 영향을 주는 요인들은 다음과 같이 매우 다양하다.

- 플랫폼/아키텍처 관련 요인: 네트워크 어댑터의 type, latency와 대역폭. Multithreading 의 사용과 interrupt handling과 같은 OS 특성

- 네트워크 관련 요인: 네트워킹 하드웨어(Ethernet, FDDI, switch, router 등), 프로토콜, 네트워크에서 routing과 configuration, network contention과 saturation 등

- 어플리케이션 관련 요인: 알고리즘 효율성과 확장성, 통신 to 통신 ratios, 로드 밸런스, MPI 루틴의 type과 메시지 크기 등.

- MPI 구현 관련 요인: 메시지 버퍼링 방법, 메시지 패싱을 구현하는데 사용되는 프로토 콜, sender-receiver 동기화 type 등 Æ 여러 MPI 루틴을 구현하는데 사용하는 알고리즘 의 효율성은 MPI 구현마다 다를 수 있으며 프로그램 성능에도 영향을 끼친다.

- SMP 클러스터 specific 요인들: SMP 클러스터 환경에서는 하나의 SMP 노드에서 실행 되는 MPI 작업의 수가 통신 성능에 영향을 준다. 일반적으로 한 노드에서 실행되는 MPI 작업이 하나보다 많아지게 되면 작업당 통신 대역폭이 감소한다. aggregate 대역폭은 saturation에 도달할 때까지 MPI 작업의 수에 따라 증가한다. saturation된 후 steady 상 태이거나 혹은 감소하게 된다. intra-node 통신에 대해 shared memory를 사용하면 한 노드에서 실행되는 작업의 수가 증가함에 따라 작업당 통신 대역폭이 감소하는 것을 최소 화 할 수 있다.

5.3.2. 메시지 버퍼링

메시지 버퍼링은 송신의 시작과 그에 대응되는 수신의 완료 사이에서 데이터를 저장해 두는 것을 말한다. 버퍼링은 시스템에 의해서 또는 유저에 의해 수행될 수 있다. 시스템 버퍼링은 유저에게 노출되지 않으며 그 구동 방식은 implementation 의존적이다. MPI 표준은 시스템 버퍼링이 어떤 방식으로 구현되는가에 대해 의도적으로 정의하지 않고 있다. 유저가 제공하는 버퍼 공간은 명시 적으로 선언되고 사용자 프로그램에 의해 운영된다. 송신에 대한 버퍼링 구현은 다음과 같은 방식 이 있으며, 성능에 다르게 영향을 준다.

- 송신측 버퍼링 - 수신측 버퍼링 - 버퍼링 없음

- 일정 조건이 만족될 때 버퍼링 (eager, rendezvous 프로토콜)

시스템 버퍼링의 장점은 비동기 통신을 통하여 성능을 개선시킬 수 있다는 것이다. 시스템 buffered 송신의 경우 대응되는 수신 연산이 포스트(post) 되지 않은 경우에도 기다리지 않고 송 신 작업을 수행할 수 있다.

버퍼링의 단점은 안정성(robustness)에 있다. 버퍼가 고갈(depletion)되면 프로그램이 다운(fail)되 거나 지연될 수 있다. 버퍼링이 되는지 된다면 어떻게 구현되는지 MPI 구현(implementation)마다 다르기 때문에 이쪽 시스템에서 문제없는 코드라도 다른 시스템에서는 그렇지 않을 수 있다. 이와 같은 의존성을 가지는 코드는 대부분의 시간을 제대로 실행해서 바른 결과를 내놓더라도 불안정 하다.

5.3.3. MPI 메시지 패싱 프로토콜

MPI 메시지 패싱 프로토콜은 MPI implementation이 메시지 전달을 위해 사용하는 정책과 내부 방식을 기술한다. 프로토콜은 MPI 표준에서 정의되지 않는다. MPI implementation은 한 MPI 루 틴에 대해서 몇 가지 프로토콜의 조합을 사용할 수 있다. 예로 표준 송신은 작은 메시지의 경우 eager 프로토콜을 큰 메시지에 대해서는 rendezvous 프로토콜을 사용할 수 있다. MPI 메시지 패

싱 프로토콜은 종종 메시지 버퍼링과 함께 동작한다.

5.3.3.1. Eager Protocol

비동기 프로토콜. eager 프로토콜은 송신 프로세스가 메시지를 보내면 수신 프로세스가 메시지를 저장할 수 있다는 가정하에 작동한다. 수신 프로세스가 포스트 되지 않은 상태라면 메시지는 버퍼 에 저장된다. 이 가정에 의해 MPI 구현은 수신 프로세스를 위한 일정량의 가용 버퍼 공간을 확보 해 두어야 한다. eager 프로토콜은 일반적으로 메시지 크기가 작을 때 사용(이때 메시지 크기는 MPI 작업 수에 의해 제한됨)한다.

eager 프로토콜의 장점은 동기화 지체의 감소에 있다. 즉, 송신 프로세스는 메시지 송신을 위해 수신 프로세스로부터의 OK 신호를 기다릴 필요가 없다. eager 프로토콜은 프로그래머가 MPI_Send만 이용해 비동기 통신의 효과를 누릴 수(사실은 구현에 의존적이지만) 있으므로 프로 그래밍이 단순하다.

eager 프로토콜의 단점은 scalable 하지 않다는 것이다. 임의의 수의 송신프로세스로부터 메시지 를 받기 위해 많은 버퍼링 공간이 필요하며, 버퍼공간이 초과되면 메모리 exhaustion과 프로그램 termination이 발생할 수 있다. 그리고, 소수의 메시지가 보내진다면 버퍼 공간이 낭비될 수도 있 다. 메시지를 네트워크에서 끌어와서 버퍼 공간에 데이터를 복사하므로 수신 프로세스 측면에서 보면 eager 프로토콜이 CPU에 부하를 줄 수도 있다.

5.3.3.2. Rendezvous Protocol

동기 프로토콜. 수신 프로세스의 버퍼 공간이 만들어 질 수 없을 때, eager 프로토콜의 버퍼 한계 가 초과된 경우 사용한다. 송신, 수신 프로세스 사이에 동기화(handshaking)이 필요하며 아래와 같은 과정을 거쳐 통신이 이루어지게 된다.

- 송신 프로세스는 수신 프로세스로 메시지 봉투 정보를 보낸다.

- 수신 프로세스에 봉투 정보가 수신되고 저장된다.

- 버퍼 공간 사용 가능하면, 수신 프로세스는 송신 프로세스에게 응답한다.

- 송신 프로세스는 수신 프로세스로부터 응답을 받고 데이터를 보낸다.

- 수신 프로세스는 데이터를 받는다.

Rendezvous 프로토콜은 eager 프로토콜보다 scalable하고 안정적이다. 수신 측에서는 작은 메시 지 봉투 정보를 저장할 버퍼만 필요하게 된다. 송신 프로세스 user space에서 수신 프로세스 user space로 직접 복사를 통해 데이터 전송이 이뤄지므로 데이터를 복사하는 부하가 eager 보 다 줄어든다.

송신과 수신 사이에 동기화(handshaking)가 필요하므로 동기화 지체가 발생하는 것이 단점이다.

수신 프로세스로부터의 신호를 기다리는 동안 블로킹 되는 것을 피하기 위해 논-블로킹을 사용하 면 프로그래밍 복잡성이 증가하게 된다.

5.3.4. Sender-Receiver 동기화

rendezvous 프로토콜을 사용하는 경우와 같이, 동기 MPI 통신은 송신 수신 작업 사이에 동기화 가 필요하다. MPI 표준은 이와 같은 동기화가 어떻게 구현돼야 하는가를 정의하지 않는다. MPI implementor에게는 다음과 같은 의문이 남겨진다.

- 수신 프로세스는 다른 프로세스에서 송신을 하려 한다는 것을 어떻게 알 수 있을까?

- 수신 프로세스는 얼마나 자주 수신 메시지를 체크해야 할까?

- 논-블로킹 송신이 시작된 후, 프로세스는 송신 작업을 위해 얼마나 많은 CPU 사이클 시간을 할당해야 할까?

MPI 구현은 대부분 송-수신 동기화를 위해 polling과 interrupt, 두 가지 다른 모드를 사용한다.

polling 모드에서 사용자의 MPI 작업은 일정한 간격(implementation defined)을 두고 통신 이벤 트 서비스와 check를 위해 시스템에 의해 주기적으로 interrupted 된다. user task가 다른 작업을 하느라 바쁜 경우 통신 이벤트가 발생하면, 기다려야 한다. interrupt 모드에서 사용자의 MPI 작 업은 통신 이벤트가 발생했을 때 시스템에 의해 interrupted 된다. 다음과 같은 특성을 가지는 프

polling 모드에서 사용자의 MPI 작업은 일정한 간격(implementation defined)을 두고 통신 이벤 트 서비스와 check를 위해 시스템에 의해 주기적으로 interrupted 된다. user task가 다른 작업을 하느라 바쁜 경우 통신 이벤트가 발생하면, 기다려야 한다. interrupt 모드에서 사용자의 MPI 작 업은 통신 이벤트가 발생했을 때 시스템에 의해 interrupted 된다. 다음과 같은 특성을 가지는 프