집합 통신은 어떻게 전달될까: Ring과 Tree

집합 통신의 조합과 확장에서는 All-Reduce가 각 GPU의 배열을 같은 위치끼리 합산하고, 그 결과를 모두에게 돌려주는 동작임을 살펴봤습니다. 그러나 결과의 정의만으로는 누가 누구에게 먼저 보낼지 정해지지 않습니다.

집합 통신의 이름은 필요한 결과를, 통신 알고리즘은 그 결과를 만드는 전달 순서를 설명합니다. 이번에는 같은 입력을 이웃에게 돌려 보내는 Ring과, 가지를 따라 모으고 펼치는 Tree로 계산해 보겠습니다. 이후 단계 수와 전달량을 비교하고, 그림 속 연결이 실제 하드웨어와 어떻게 다른지 살펴보겠습니다.

Ring에서 조각을 전달하며 합산하기

Ring은 참여자마다 다음 전달 상대를 정해 하나의 순환을 만드는 방식입니다. GPU 네 개의 순서를 0 → 1 → 2 → 3 → 0으로 두겠습니다. 각 GPU는 다음 GPU로 보내면서 이전 GPU에서 받을 수 있습니다. 한 GPU만 일하고 나머지가 차례를 기다리는 방식이 아닙니다.

목표는 네 GPU의 입력을 같은 위치끼리 더한 배열을 만들고, 모든 GPU가 그 배열을 갖게 하는 것입니다. 이를 두 구간으로 나누겠습니다. 먼저 조각마다 합을 완성하고, 그다음 완성된 조각들을 모두에게 전달합니다. 처음부터 모든 GPU에 전체 합을 만들 필요는 없습니다.

각 GPU에 네 원소 배열이 있다고 하겠습니다. 첫째 위치를 조각 A, 둘째를 B, 셋째를 C, 넷째를 D로 부릅니다. 예를 들어 A의 입력값은 GPU 0부터 차례로 1, 10, 100, 1000이며, 모두 더한 결과는 1111입니다. 여기서는 원소 하나가 조각 하나지만, 실제 큰 배열은 여러 원소를 묶어 조각으로 나눌 수 있습니다.

각 조각을 이웃에게 보내고, 받은 GPU가 같은 위치의 자기 입력을 더하도록 해 보겠습니다. 조각이 다른 세 GPU를 거치면 네 GPU의 값이 모두 반영됩니다. 서로 다른 조각을 동시에 돌리면 각 GPU에 합산을 마친 조각 하나씩 남길 수 있습니다. 이것이 Ring으로 Reduce-Scatter를 수행하는 과정입니다.

아래 그림은 네 GPU의 입력에서 시작합니다. 다음 버튼을 눌러 세 번의 전달을 차례로 살펴보세요. GPU의 위치와 색은 고정되어 있습니다. 각 GPU의 벡터에서 A·B·C·D 위치를 계속 보여주며, 이번에 더한 위치에 테두리를 표시했습니다. 화살표는 보내는 조각입니다.

GPU 상자는 합산 중인 벡터 전체를 보여줍니다. 조각을 받으면 해당 위치의 자기 값에 더하고, 다른 위치의 값은 그대로 둡니다. 첫 전송에서 GPU 1은 A의 값 10을 GPU 2로 보냅니다. GPU 2는 자신의 A 값 100을 더해 110을 만들고, 다음에는 GPU 3이 1000을 더해 1110을 만듭니다. 마지막으로 GPU 0이 1을 더하면 A의 합 1111이 완성됩니다.

다른 조각도 같은 시각에 다른 위치에서 이동합니다. 세 번 전달한 뒤 GPU 0, 1, 2, 3에는 각각 A=1111, B=2222, C=3333, D=4444가 준비됩니다. 마지막 장면의 진한 칸은 각 GPU가 맡은 완성된 결과 조각입니다. 옅은 칸은 계산 중 남은 값이며 Reduce-Scatter의 결과에 포함되지 않습니다. 따라서 전체 결과를 어느 한 GPU에 먼저 모을 필요가 없습니다. 여기서는 결과 조각과 rank의 대응이 맞도록 첫 전달 조각을 골랐으며, 실제 라이브러리의 내부 조각 배치는 달라질 수 있습니다.

완성된 조각을 모두에게 전달하기

이제 합산은 끝났지만 각 GPU에는 결과의 일부만 있습니다. 각자가 가진 완성된 조각을 같은 Ring 순서로 전달하면 됩니다. 받은 조각을 보관하면서 다음 이웃에게도 전달하면, 점차 모든 조각이 모입니다. 이 단계가 All-Gather입니다. 아래 그림은 각 GPU가 맡은 완성 결과만 남긴 상태에서 시작합니다. 아직 없는 결과 위치는 —로 표시하고, 다음 단계마다 받은 값으로 그 위치를 채웁니다. 그림의 빈칸은 메모리가 실제로 비워졌다는 뜻이 아니라, 아직 해당 위치의 완성 결과를 갖고 있지 않다는 뜻입니다.

첫 단계에서 GPU 0은 A를 GPU 1로 보내고 D를 GPU 3에서 받습니다. 다음에는 받은 D를 전달하면서 C를 받습니다. 세 단계 뒤 모든 GPU가 A부터 D까지 갖습니다. 이때는 완성된 값을 복사하므로 다시 더하지 않습니다.

각 GPU의 벡터에서 이번에 새로 채운 위치에는 테두리가 표시됩니다. 화살표는 이번에 보내는 조각 하나만 표시합니다. 상자에 있는 모든 조각을 매번 보내는 것은 아닙니다. 네 GPU가 각각 조각 하나씩 전달하므로 Reduce-Scatter 세 단계와 All-Gather 세 단계로 같은 All-Reduce 결과가 완성됩니다. 이 단계 구분은 데이터 의존성을 설명하며 단계마다 CPU가 별도 함수를 호출하거나 전체 GPU를 동기화해야 한다는 뜻은 아닙니다.

Tree에서 모으고 다시 펼치기

Tree는 참여자 사이에 부모와 자식 관계를 두고 전달하는 방식입니다. 간단한 예로 GPU 1은 0에게, GPU 3은 2에게 먼저 보냅니다. 두 곳에서 합산을 동시에 진행한 뒤 GPU 2의 부분합을 GPU 0에 더합니다. 마지막으로 전체 합을 반대 방향으로 배포합니다. 아래 그림에서 다음 버튼을 눌러 합산 두 단계와 배포 두 단계를 진행해 보세요. GPU의 위치는 바뀌지 않습니다. 진한 화살표는 그 단계에 실제로 전달하는 방향이고, GPU 상자는 전달이 끝난 뒤의 값입니다.

두 번의 합산 단계로 GPU 0에 전체 합이 모이고, 두 번의 배포 단계로 모두에게 전달됩니다. Ring 예시보다 단계는 적지만 한 번에 보내는 데이터가 배열 전체입니다. 따라서 네 단계라는 숫자만 보고 여섯 단계인 Ring보다 빠르다고 판단할 수 없습니다.

이것은 원리를 설명하기 위한 단순한 Tree입니다. NCCL의 double binary tree 설명은 데이터를 두 트리에 나눠 보내 중간 노드의 부담을 분산하는 방식도 다룹니다. 여기의 단순 예시가 현재 NCCL Tree 구현 전체를 재현하는 것은 아닙니다.

단계 수와 전달량을 함께 보기

GPU 수를 p, GPU 하나의 입력 배열 크기를 M바이트라고 하겠습니다. 균등하게 조각을 나누는 Ring All-Reduce는 두 구간에서 각각 p−1단계를 거칩니다. 각 단계에서 GPU 하나가 보내는 양은 M/p바이트이므로 다음과 같습니다.

단계 수 = 2(p − 1)
GPU당 총 송신량 = 2(p − 1)M/p

수신량도 같은 크기이며, 위 송신량에 다시 포함한 값은 아닙니다. 네 GPU 예시에서는 각 GPU가 배열 크기의 1.5배를 보내고 1.5배를 받습니다. 반면 위 Tree의 GPU 0은 합산에서 배열 두 개를 받고 배포에서 두 개를 보내지만, 잎인 GPU 1은 하나를 보내고 하나를 받습니다. 참여자별 부담도 다릅니다.

단계를 시작하고 다음 데이터가 준비되기를 기다리는 비용이 크면 단계가 많은 방식이 불리할 수 있습니다. 큰 데이터를 오래 보내는 상황에서는 연결의 대역폭을 얼마나 고르게 사용하는지가 중요해집니다. 단계가 적다는 장점과, 전송량·자원 사용이 고르게 나뉜다는 장점을 함께 봐야 합니다. 실제 구현은 데이터를 더 작은 단위로 나눠 파이프라인으로 전송하기도 하므로 이 계산을 그대로 실행 시간 공식으로 사용하지는 않습니다.

논리적 이웃과 실제 연결 구별하기

Ring이라는 이름 때문에 GPU가 원형 케이블로 연결되어야 하는 것은 아닙니다. 알고리즘이 정한 이웃 사이의 전달도 실제로는 스위치나 여러 링크를 거칠 수 있습니다.

서로 다른 전송이 같은 물리 링크를 공유하면 대역폭을 나눠 사용합니다. 따라서 같은 Ring이라도 GPU의 순서를 바꾸면 공유 링크를 지나는 트래픽이 달라질 수 있습니다. NVIDIA의 토폴로지를 고려한 집합 통신 설명도 이러한 연결 구조와 전달 순서의 관계를 보여줍니다.

개발자는 보통 필요한 집합 통신을 요청하고 라이브러리가 사용할 수 있는 알고리즘과 경로를 선택하도록 합니다. 현재 NCCL 알고리즘 설정에는 Ring과 Tree 외의 방식도 있습니다. 특정 알고리즘이 모든 메시지 크기와 하드웨어에서 가장 빠르다고 고정하지 않는 것이 좋습니다. 부동소수점 합산은 덧셈 순서에 따라 마지막 자릿수가 달라질 수 있다는 점도 정수 예시와 구별해야 합니다.

이제 결과의 종류와 전달 방법을 구별할 수 있습니다. 다음에는 모델과 계산을 배치하는 방식에서 출발해 어떤 통신이 필요한지 살펴보겠습니다.