[Paper] Trivance: 지연 최적 AllReduce를 위한 멀티포트 네트워크 단축

Source: arXiv - 2602.17254v1

개요

AllReduce는 대규모 머신러닝 모델의 분산 학습을 뒷받침하는 핵심 집합 연산입니다. 새로운 논문 **“Trivance: Latency‑Optimal AllReduce by Shortcutting Multiport Networks”**는 이론적인 최소 통신 단계 수 ( log₃ n )를 유지하면서 네트워크를 통과하는 트래픽 양을 크게 줄이는 알고리즘을 소개합니다. 실제로 이는 오늘날 가장 큰 AI 워크로드를 구동하는 고성능 토러스형 인터커넥트(예: Google의 TPUv4)에서 더 빠른 그래디언트 집계를 의미합니다.

Key Contributions

• Latency‑optimal algorithm with reduced congestion: Trivance는 Bruck’s log₃ n 단계 한계를 만족하면서도 단계당 트래픽을 3배 감소시킵니다.
• Dual‑port exploitation: 이 방법은 양방향 링의 두 전송 포트를 동시에 활용하여 각 라운드에서 데이터가 이동하는 거리를 “단축”합니다.
• Joint reductions: 두 방향의 reduction 연산을 병합함으로써 Trivance는 추가 단계 없이 네트워크 부하를 더욱 감소시킵니다.
• Extension to multidimensional torus topologies: 이 설계는 2‑D 및 3‑D 토러스 네트워크로 자연스럽게 확장되어 대용량 메시지에서도 대역폭 최적성을 유지하면서 지연 시간 이점을 보존합니다.
• Empirical validation: 합성 및 실제 토러스 패브릭에 대한 실험 결과, 8 MiB까지의 메시지에 대해 기존 최상의 latency‑optimal 스킴 대비 5‑30 % 속도 향상을 보였으며, 32 MiB(2‑D) 및 128 MiB(3‑D)까지도 경쟁력 있는 성능을 나타냈습니다.

방법론

1. 네트워크 모델링: 저자들은 양방향 링(토러스의 기본 구성 요소)을 두 개의 독립적인 전송 포트—시계 방향 하나, 반시계 방향 하나—를 가진 것으로 간주한다.
2. 단계별 단축: 각 통신 라운드에서 모든 노드는 동시에 세 개의 “청크” 데이터를 전달한다: 각각의 이웃에게 하나씩, 그리고 이웃을 건너뛰는 하나를 전달하여, 단계당 이동 거리를 사실상 세 배로 만든다.
3. 통합 축소 연산: 방향당 단일 청크를 축소하는 대신, 노드들은 두 개의 들어오는 부분 결과를 하나의 축소로 결합하여 이후 수행해야 할 축소 연산 수를 절반으로 줄인다.
4. 토러스에 대한 재귀적 구성: 다차원 토러스는 각 차원마다 독립적인 링으로 분해된다. Trivance는 각 링에서 실행되며, 결과는 추가 홉을 피하도록 신중하게 순서를 정한 스케줄을 사용해 차원 간에 병합된다.
5. 평가 프레임워크: 저자들은 실제 TPUv4 대역폭/지연 수치를 기반으로 보정된 메시지 전달 시뮬레이터에 Trivance를 구현하고, 이를 Bruck 알고리즘, Swing 계열, 그리고 대역폭 최적의 링 기반 AllReduce와 비교한다.

결과 및 발견

• 지연 시간 이점: Trivance는 항상 ⌈log₃ n⌉ 라운드 내에 완료되며, 이는 모든 지연‑최적 AllReduce에 대한 이론적 최소값입니다.
• 혼잡 감소: 단계별 트래픽이 Bruck의 약 1/3 수준이어서 제한된 이분 절단 토러스 링크에서 대기열이 줄어듭니다.
• 대역폭 동등성: 큰 메시지에 대해 알고리즘의 처리량이 대역폭‑최적 링 AllReduce와 일치하여, 단축이 원시 데이터 이동 용량을 희생하지 않음을 확인합니다.

실용적인 시사점

• 더 빠른 분산 훈련 루프: 그래디언트 집계가 빨라져 각 훈련 단계에서 수 밀리초를 절감합니다—수천 개의 가속기로 확장할 때 중요합니다.
• 기존 하드웨어 활용도 향상: 새로운 실리콘이 필요 없으며, 알고리즘은 기존 포트 사용 방식을 재배열할 뿐이어서 현재 AllReduce 라이브러리(예: NCCL, XLA)의 즉시 교체가 가능합니다.
• 에너지 절감: 네트워크 혼잡이 감소하면 재전송이 줄고 링크 사용량이 낮아져 대규모 데이터센터 클러스터의 전력 소비를 감소시킵니다.
• AI를 넘어선 적용 가능성: 집합 연산에 의존하는 모든 워크로드(예: 분산 그래프 분석, 과학 시뮬레이션)는 동일한 지연 최적화 단축 기법의 혜택을 받을 수 있습니다.

제한 사항 및 향후 작업

• 대칭 양방향 포트를 가정: 이득은 양 방향 모두 동시에 전송할 수 있을 때에 기반한다; 비대칭이거나 반이중(half‑duplex) 링크는 이점을 감소시킨다.
• 메시지 크기 최적점: Trivance는 32 MiB 이하 메시지에서 뛰어나지만, 매우 큰 페이로드의 경우 더 단순한 스케줄링 덕분에 기존의 대역폭 최적 링이 여전히 선호될 수 있다.
• 하드웨어‑특정 튜닝: 현재 평가는 시뮬레이션된 TPUv4 토러스를 사용했으며, 다른 패브릭(예: InfiniBand, 이더넷 기반 클러스터)에서의 실제 성능은 실증적인 검증이 필요하다.
• 향후 방향: 이단계(shortcutting) 개념을 이종 토폴로지(예: 계층형 팻트리)로 확장하고, 워크로드별 최적 알고리즘을 자동 선택하는 적응형 집합 라이브러리와 통합하며, 신뢰할 수 없는 링크에 대한 내결함성 변형을 탐구한다.

저자

• Anton Juerss
• Vamsi Addanki
• Stefan Schmid

논문 정보

• arXiv ID: 2602.17254v1
• 분류: cs.DC, cs.NI
• 출판일: 2026년 2월 19일
• PDF: Download PDF