Collective communication

Collective communication

Collective operations, inter-process communication이라고도 하는데, multiple processes가 모두가 참여하는 통신(데이터를 전달) 패턴[1]을 의미한다. 즉 n개의 process가 있을 때, 1:1로 데이터를 전송하는 것이 아닌 하나의 데이터를 n개의 processes에게 나눠주거나 n개의 processes의 데이터를 하나로 모으는, 집단이 참여하는 기본 통신 패턴을 의미한다.

 

SPMD 프로그램(data parallelism을 활용하는 프로그램)에서는 한 문제를 여러 개의 process가 나눠서 해결한다. 예를 들어, 한 덩어리의 데이터를 n개의 process에게 나눠주거나, 문제를 푸는 과정에서 서로 간에 데이터 전달, 마지막으로 각 process의 결과(partial result)를 다시 모아서 하나의 결과로 만드는 경우 등이 있을 수 있다.

 

최근에 multiple GPUs를 이용한 딥러닝이 대세가 되고 있는데, multiple GPUs를 이용한 네트워크 학습에서 multiple GPUs간의 데이터 전송은 꼭 필요한 operation이다. 예를 들어 N-size batch를 동일한 크기로 나눠서 각 GPU에 전송하면, 각 GPU는 독립적으로 forward를 진행하고 최종 결과물만을 다시 한 GPU에 모아 loss를 계산할 수 있다.

 

Multiple GPUs 환경과 같은 데이터 전송 overhead가 큰 distributed memory system에서 이러한 데이터 통신 패턴을 최적화하는 것은 매우 중요하다. 오늘은 자료 [1], [2], [3]을 바탕으로 multiple process가 모두 참여하는(=collective) 통신 패턴(communication)의 기본 4가지 패턴, broadcast, scatter, gather, reduce를 정리해보고자 한다. Fig 1.은 4가지 패턴을 잘 정리한 그림이다. 

 

Fig 1. Basic ollective communication pattern [3]

 

 

 

데이터 나누기 : Broadcast

Fig 2. Broadcast [1]

 

Broadcast pattern은 한 process가 가진 데이터의 동일한 복사본을 통신에 참여하는 모든 processes(nodes)에게 전송하는 pattern이다. 실행 결과 모든 processes는 동일한 데이터 복사본을 가지게 된다. SPMD 프로그램에서 global value를 여러 processes에 나눠줄 때 사용된다. Multi GPUs 환경에서의 딥러닝 학습 시, 계산된 loss를 모든 GPUs에게 전송하는 경우에 사용된다. 

 

 

 

데이터 나누기 : Scatter

Fig 23 Scatter [1]

 

Scatter pattern은 한 process가 가진 데이터를 나누어 모든 processes에게 하나의 part씩을 전송하는 pattern이다. 실행 결과 모든 processes는 각기 다른 partial data를 가지게 된다. SPMD 프로그램에서 processes가 각자만의 data에 대한 계산을 실행하도록 하는 데(data parallelism) 사용된다. Multi GPUs 환경에서의 딥러닝 학습 시, N-size mini-batch를 등분하여 모든 GPUs에게 한 part씩 전송하는 경우 사용된다. 각각의 GPU는 전송받은 각자의 데이터를 이용하여 독립적으로 계산(forward 과정)할 수 있다.

 

 

 

데이터 모으기 : Gather

Fig 4. Gather [1]

 

Gather pattern은 모든 processes가 가진 각자의 데이터를 한 process에 전송하여 모으는 통신 pattern이다. 실행 결과 한 process는 모든 processes가 가진 데이터를 모두 가지게 된다. SPMD 프로그램에서 개별 processes가 가진 데이터를 모으거나, 개별 processes가 처리한 결과(partial-result)를 모아 하나의 결과를 만드는 데 사용된다. 후술할 reduce operation과 다른 점은 단순히 데이터를 모으는 패턴이기에, 모든 결과를 보존해야 하는 경우나 partial-result들을 이용해 하나의 결과를 계산하는 과정이 병렬적으로 구현하기 어려운 경우 사용된다. Multi GPUs 환경에서의 딥러닝 학습 시, 각 GPU가 처리한 결과를 하나의 GPU에 모은 후, loss를 계산하는 데 사용된다. 

 

 

 

데이터 모으기 : Reduce

Fig 5. Reduce [1]

 

Reduce pattern은 모든 processes가 가진 각자의 데이터를 한 process에 전송하여 하나의 결과를 생성하는 통신 pattern이다. 실행 결과 한 process는 모든 processes가 가진 데이터를 이용해 계산한 결과 데이터를 가지게 된다. SPMD 프로그램에서 개별 processes가 처리한 결과(partial-result)를 모아 하나의 결과를 만드는 데 사용된다. Fig 5에서 3개의 processes는 a, b, c를 가지고 있는데, 함수 f를 이용하여 Node 1은 f(a, b, c) 결과를 가지게 된다. 이때 f는 parallel 계산이 가능해야 하기에 associative property(결합법칙)를 만족해야 한다. 가능한 f의 예로는 sum, max, min, multiply, and 등이 있으며, 결합법칙이 성립하지 않는 subtract 연산은 f로 사용할 수 없다.

 

 

 

Reference

[1] https://en.wikipedia.org/wiki/Collective_operation

[2] Tao Yang, Collective Communication in MPI and Advanced Features, CS240A

[3] https://hpc-tutorials.llnl.gov/mpi/collective_communication_routines/