DEV Community

Gangguri
Gangguri

Posted on

Demystifying NCCL: An In-depth Analysis of GPU Communication Protocols and Algorithms

#ai #paper #machinelearning

Demystifying NCCL: An In-depth Analysis of GPU Communication Protocols and Algorithms

INTRODUCTION

  • AI, HPC 워크로드에서 GPU-to-GPU 통신 성능은 매우 중요하고, NCCL 라이브러리가 상당히 독보적인 위치에 존재한다

    • 듣기로는 RCCL, oneCCL이 이제 NCCL을 따라가는 중이라고 함

  • NCCL은 MPI와 달리 GPU간 통신에 최적화되어 있고, NVLink, PCIe, IB와 같은 토폴로지를 적극활용하여 latency, bandwidth를 높였다

    • MPI는 CPU, GPU를 포함한 통신에 최적화되어 있고, NCCL은 오직 cuda gpu간 통신에 매우 최적화되어 있음
    • MPI는 범용 라이브러리라 특정 디바이스가 가지는 성능을 극한까지 활용하지 못하는 듯

  • NCCL이 대규모 분산시스템에서 매우 중요하고 open source이지만, api 수준에서는 매우 잘 설명되어 있지만, 내부 기술적인 설명에 대해서는 부족하다

  • 이러한 자세한 기술적인 설명이 부족해서, 시스템 아키텍처 설계나 성능 최적화 단계에서 어려움이 생긴다

  • 본 논문에서는 NCCL의 내부 아키텍처, 주요 구현에 대해 알아보고 분석한다

  • 이 논문에서 제공하는 insight가 ATLAHS라는 application 네트워크 시뮬레이터 툴에 반영되어서, 아키텍처 설계, 시스템 최적화 같은 분야에 도움을 줄 수 있다

  • NCCL은 2.19.1. 버전을 기반으로 하며, 이후 버전이 더 많은 기능을 담고 있지만, 본 논문에서 설명하는 아키텍처나 통신전략 등이 계속 똑같이 지속될 것이며, 여기서 얻은 insight가 여전히 중요할 것이다

NCCL OVERVIEW

A. NCCL API

  • NCCL은 GPU 클러스터에서 collective 통신 operation에 대해서 latency, bandwidth를 높은 수준으로 최적화하는데 초점이 맞춰져 있다

  • NCCL은 다음과 같이 크게 4가지 기능을 제공한다

    • 1) Communicator Management

      • 모든 통신은 communicator를 통해 관리되며,
      • 싱글 프로세스에서 모든 디바이스를 관리하는 경우에는 ncclCommInitAll이 호출되고, 멀티 프로세스인 경우 각 프로세스가 ncclCommInitRank를 호출하여 유니크한 Rank를 부여받는다
      • ncclCommInitAll인 경우에는 싱글 프로세스이기 때문에 한 작업에 대해서 모든 디바이스가 호출되는 경우가 많기 때문에 랭크를 명시적으로 알고있을 수요가 적고
      • 멀티 프로세스에서는 각 프로세스에 작업을 분할하는 경우가 많기 때문에 랭크를 통해 디바이스를 분리하는 작업이 많기 때문
      • 모든 통신 작업이 종료된 후에는 자원을 free하는 작업을 하기 위해 2가지 함수가 있음
      • ncclCommDestroy는 모든 통신 작업이 종료되면 communicator를 destroy하는 것이고
      • ncclCommAbort는 작업 종료여부와 관계없이 즉시 모든 작업을 중단하고 해제함. 이는 데드락같은 예상치 못한 에러에 대응하기 위함

    • 2) Collective Communication

      • NCCL에서는 크게 5가지의 collective operation을 제공함
      • NCCL은 MPI의 in place 동작을 지원하기 위해 ncclBroadcast외에 ncclBcast가 존재하며, 일반적으로는 out-place인 스타일이 사용되기 때문에 ncclBcast는 사실상 deprecated인 상태

    • 3) P2P Communication

      • ncclSend, ncclRecv와 같은 P2P 통신도 지원함

    • 4) Group Calls

      • 예를 들어, All-to-All이나 one-to-All같은 통신에서는 P2P 통신 호출이 다수 발생하는데
      • NCCL에서는 ncclGroupStart, End operation 사이에 해야하는 통신을 모두 적고, end시점에 한꺼번에 launch한다
      • 이로써, 비싼 launch작업의 오버헤드를 하나로 줄이고, 후에 기술할 채널과 같은 병렬 통신을 수행해서 복수개의 통신채널을 가지는 환경에서 대역폭을 잘 활용할 수 있다

B. Lanuching Strategies

  • One CPU process per GPU

    • 단일 CPU 프로세스가 한 GPU만을 담당하기 때문에 CPU 경합이 존재하지 않는 최상의 상태이다
    • NUMA와 같이 cpu가 여러개이고, 각 cpu가 자신과 가까운 local memory 영역이 존재해 메모리 latency가 아주 짧은 시스템에서 아주높은 성능을 보인다

  • One CPU thread per GPU

    • 하나의 프로세스 안에 멀티 스레드가 존재하고 각 스레드가 gpu를 관리하는 환경
    • 경합이 발생할 수는 있으나, 같은 프로세스이기 때문에 메모리 공유가 copy없이 이루어질 수 있는 장점이 있음

  • One CPU thread for multiple GPUs

    • CPU자원을 최소로 먹지만, 모든 작업이 순차적으로 진행되기 때문에 성능면에서 아주 떨어지며
    • 주로 성능보다는 구현의 편의성이 중요한 프로토타입 단계에서 적합하다

C. Communication Cannels

  • NCCL을 구성하는 하드웨어 요소로는 GPU, CPU, NIC가 있고, 각각 통신에서 GPU는 reduction연산을 수행하거나, 데이터를 buffer에 옮기는 작업을 하고, CPU는 kernel을 launch하고 CPU단에서 할 수 있는 통합작업을 수행하고, NIC는 노드 간에 데이터 패킷을 전송한다

  • 만약 아주 큰 데이터를 처리하는데 하나의 SM만 사용한다면, 다른 SM을 활용하지 못해 느려지고, 처리속도가 느리다보니 link speed도 충족하지 못한다

  • 그래서 NCCL은 collective operation 작업을 여러 communication channel로 나눈다.

  • channel은 처리할 데이터를 균등하게 분할받으며, 각 channel은 할당받은 SM내에서 병렬적으로 처리된다

  • 그렇게, 많은 연산자원을 동시에 사용해 처리량을 증가시키고, 멀티 NIC환경에서 각 channel이 독립적으로 NIC를 통해 전송함으로써, 대역폭을 증가시키도록 한다

  • 하지만, 너무 많은 채널은 채널당 처리하는 chunk size가 감소하고, proxy thread가 작은 메세지를 일일히 패킹하고 전송하면서 대역폭 활용률이 감소한다

  • 그래서 gpu의 병렬성과 네트워크 효율성 사이에 최적의 채널 수를 찾는 것이 중요하다

  • NCCL은 communicator 초기화 단계에서 아키텍처나 네트워크 토폴리지를 고려해서 채널 구성을 한다

  • 이후 collective operation이 발생하면, NCCL은 선택된 통신, 알고리즘, 메세지 크기, 가용가능한 대역폭, 채널당 thread(처리량) 등을 고려해서 초기화한 채널들 중 얼마나 사용할 것인지 자동으로 정한다

  • NCCL_NTHREADS같이 채널을 정하는데 영향을 주는 변수가 있지만, 추천되지 않으며, 부정확한 결정이 될 수 있음으로 잘 사용되지는 않는다

    • NCCL_NTHREADS는 채널당 스레드 수를 지정하는 변수이고, 그럼으로, 가용가능한 warp의 수를 정함으로 채널의 처리량을 결정 짓는다.
    • 주로 warp은 고정된 수의 thread를 사용함. 튜닝되는 경우 거의 없음. 주로 32개 스레드

  • NCCL에는 어떻게 데이터를 이동시킬건지에 대한 논리적인 통신 토폴리지가 Ring혹은 Tree로 존재한다

  • Ring은 고리형태로 gpu를 연결하며, 단방향으로 흐른다

  • Tree는 위에서 아래로 아래에서 위 방향으로 데이터가 흐르며, NCCL에서는 통신 효율성을 위해 두개의 이진 트리를 생성한다

    • 디바이스 수가 짝수일 때는 뒤집고, 홀수일 때는 순서를 한칸 쉬프트한다
    • 그럼으로, 짝수일 때는 어떤 노드도 2번 이상 중간노드가 될 수 없고, 홀수일 때는 최대 한개의 노드만 2번의 중간노드 역할을 수행한다

  • 이러한 논리 통신 토폴리지는 communicator 초기화 시점에서 구성되며, 여러 통신에 걸쳐 재활용된다

  • 앞서 언급한 group call의 경우 각 p2p통신을 다른 채널에 할당해서 병렬처리한다

COMMUNICATION PROTOCOL

**

A. Simple Protocol

**

  • SP는 대역폭을 최대화하기 위해 설계되었고, 큰 메세지 전송에 유리하다

  • 데이터를 큰 청크로 나누어 채널에 할당하여 전송하고, 메모리 일관성을 위해 SP는 memory fence를 사용하여, 청크가 완전히 도착하기 전까지 메모리를 읽을 수 없게한다 (청크 단위로 barrier가 존재)

    • 메모리 일관성은 프로세스가 데이터를 읽었을 때, 예측한 값이 읽히도록 보장하는 것.
    • 즉, 메모리에 완전히 데이터가 쓰여진 시점에 읽히는 것을 보장하는 것

  • 이로 인해 예측가능한 메모리 접근이 가능하고, 순서가 보장되지만, 메모리를 접근할 수 없는 시간이 존재해 overhead가 발생

  • memory fence 자체 오버헤드가 아주 크기 때문에, 작은 메세지에서 memory fence 오버헤드가 차지하는 시간이 크며, 따라서 작은 메세지 전송에 불리하다

    • memory fence가 비싼이유는 도착지 메모리에 실제로 적힘을 보장해야하고, 순서를 보장하는 것 때문이라고 함(잘 모름)
    • 여기서 latency를 측정하는 기준은 데이터를 처음 사용할 수 있게되는 시점이라고 생각함
    • 주로 SP에서는 청크크기를 512K정도로 설정하는 것으로 알고 있음

B. LL Protocol

  • LL은 데이터의 무결성을 오버헤드가 큰 배리어를 사용하는 것이 아니라 flag를 데이터와 함께 보내서 flag가 도착한 시점에는 데이터의 무결성이 보장된 상태임을 말한다

  • flag는 4byte 데이터도 4byte 총 8byte가 한 스텝에 전송되며, 작은양의 페이로드를 가지기 때문에 빠르게 목적지에 도착하며 flag를 통해 빠르게 사용가능여부를 확인하고 바로 사용할 수 있다

  • 전송량의 반이 flag이기 때문에 대역폭 활용률은 매우 낮고, 다만 메세지 단위가 작아서 latency가 매루 빠르다

  • 그래서 latency가 중요한 작업에 최적화되어 있다

C. LL128 Protocol

  • LL에서 레이턴시는 높게 유지하고 대역폭만 늘린 프로토콜

  • 128바이트를 보내고 8바이트 플래그여서 대역폭 활용률이 95에 근전합

  • 다만, inter node같은 대역폭이 크게 줄고 레이턴시가 크게 증가하는 상황에서는 LL128이 대역폭증가량이 미미해지고, 레이턴시가 크게증가해져서 장점이 상쇄된다. 그래서 NVLink를 사용하는 환경에서 유리하다

    • LL이 RDMA를 사용못하기 때문에 NVLink사용가능한 환경에서 더 차이가 두드러지는듯.
    • 근데 왜 사용못하는지 설명못함
      • cpu를 써야해서인건 아는데 왜 써야되는지 납득불가

  • 다만 PCIe나 innterconnect 인프라에서 데이터를 쪼개지 않아야하고, 재정렬을 하면 안됨. 이것이 보장되지 않는 경우에는 무결성을 위해 LL128을 사용할 수 없다

    • LL에서는 데이터 단위가 작기 때문에 쪼개거나 재정렬이 일어나는 경우가 없지만, LL128은 데이터가 비교적 커서 데이터가 쪼개지거나 랜덤한 순서로 발송되면서 flag도착시점이 완료시점을 보장하지 못함
    • 보장되는 경우에는 flag가 곧 완료시점임
    • SP는 배리어를 써서 상관없는 얘기

D. Protocol Selection and Comparison

  • 프로토콜은 NCCL_PROTO 변수를 통해 명시적으로 정해도 되지만, NCCL에서 자동으로 tuning model을 통해 정해질 수 있다

  • 이 모델은 네트워크 토폴리지, gpu 아키텍처, 메세지 크기, 자원 가용성, 사전에 이루어진 성능측정 결과 등을 통해 결정한다

  • 주로 LL/LL128은 작은메세지, SP를 큰 메세지에 고르곤 한다

DATA-TRANSFER METHODS AND TRANSPORT LAYER

  • NCCL은 통신 성능을 위해 mult-GPU, single-node이냐 multi-node이냐와 같은 설정이나 네트워크 토폴리지에 따라 다른 통신 전략을 설계한다

A. Intra-node Data Transfer

  • GPU가 동일 노드 내에 있는 경우 GPUDirect P2P를 주로 사용한다

    • cpu 개입없이 gpu간 메모리를 직접 접근하는 것

  • 그래서 NVLink가 활성화된 경우에는 GPUDirect P2P를 위해 NVLink를 가장 우선적으로 활성화한다

  • NVLink가 비활성화된 상태에서는 PCIe를 통한 GPUDirect P2P를 사용한다.

    • 여전히 cpu개입이 없으며, 있는 것보다 훨 빠르다

  • P2P_DIRECT라는 모드가 있는데 이 모드는 멀티 프로세스인 경우에는 IPC를 통한 통신을 건너뛰고 gpu memory pointer를 공유함으로써 직접적으로 접근할 수 있게 해준다

  • 또한, directSend, directRecv primitives를 통해 intermediate FIFO buffer를 건너뛸 수 있게 해준다

    • intermediate FIFO buffer는 GPU의 파이프라이닝 모델때문에 stage상태에 따라 소비될 수 있는 상태까지 보류하고 있는 단계인듯

  • GPUDirect가 사용불가능한 경우 Host memory를 사용하는 SHM 모드가 활성화되고 추가적인 시간과 copy가 발생한다

  • 만약 multi-socket(한 노드에 cpu 여러개)인 환경이라면, 각 socket에 NIC가 할당되고 다수의 NIC를 활용할 수 있는 환경이라면

  • NCCL에서는 CPU를 거치지 않고 intra 통신에서 GPU-&gtNIC-;&gtNIC-;&gtGPU;연결을 할 것이다. GPUDirect RDMA를 사용해서

  • 이 설정은 명시적으로 NCCL_CROSS_NIC통해서 설정될 수도 있고, NCCL에서 토폴리지를 분석해서 자동으로 설정할 수도 있다

잡지식

  • RDMA는 노드간 통신에서 CPU를 거치지 않고 host memory에 접근할 수 있는 기술

  • GPUDirect RDMA는 노드간 통신에서 host memory를 건너뛰고, gpu memory에 직접 접근할 수 있는 기술

B. Inter-node Data Transfer

  • 노드간 통신에서는 cpu에서 proxy thread로 관리된다

  • 주로 TCP Socket통신과 IB를 통해서 하냐로 나눠진다

  • 1) Socket-Based Communication

    • RDMA를 지원하지 않는 경우에 사용된다
    • host memory의 pinned memory를 사용하며, 이 buffer를 경유하게 되며, 그 과정에서 추가 copy overhead를 발생시킨다
    • sender와 reciever는 buffer의 상태가 받고 보낼 수 있는지 확인하고 통신하는 랑데부 프로토콜을 사용한다

  • 2) IB Verbs Transport

    • RoCE와 마찬가지로 cpu간섭없이 통신할 수 있는 토폴리지가 여기에 해당한다
    • 하드웨어 설정에 따라 구현이 달라지며,
    • 기본적으로 NIC는 gpu메모리를 직접 접근할 수 없기 때문에 host memory에 버퍼를 두고 이 버퍼에 RDMA write/read한다
    • proxy thread는 gpu - host - nic - host - gpu 사이에 일어나는 통신을 관장하고, 랑데부 프로토콜이 사용된다
    • 아래는 위의 노드간 기본 RDMA설정에서 IB가 최적화 한 것들이다
    • a) The GPUDirect RDMA Optimization
      • IB에서는 GPUDirect RDMA를 활용해서 NIC가 GPU 메모리에 직접 접근할 수 있어 host memory 개입이 없다
      • GDRDMA는 두 디바이스가 모두 같은 PCIe switch에 있어야 가능하고, 각 gpu에 중간 버퍼를 할당한다
      • 그리고, 이 버퍼를 RDMA에서 사용가능한 공간(nv_peer_mem)으로 지정하고 여기에 NIC가 직접 읽고 쓰게 된다(host memory 접근없이)

    • b) Per-peer Multi-channel Connections

      • 대역폭을 증가시키고 혼잡을 완화하기 위해 IB에서는 gpu-nic경로에 논리 채널2개를 할당한다
      • 각 채널은 ncclIbSendComm이라는 구조체에 QP들을 포함하고 있다
      • isend통신이 시작되면 두개의 채널을 번갈아가며 사용하면서 트래픽을 분산시킨다
      • 여기서 중요한 점은 단일 채널이라면, 통신단계에서 전송->전송완료대기에서 완료대기 단계에 대역폭이 놂.
      • 그래서 이때동안 다른 채널에서 전송하게 하면 NIC를 더 바쁘게 사용하게해서 대역폭 활용을 늘리고 혼잡을 완화할 수 있음

    • c) QP Layout

      • 랭크쌍마다 RDMA plugin에서 두개의 RC를 QP에 할당하고, 각 RC혹은QP가 하나의 방향이다(송수신)
      • forward QP(송신측->수신측)는 RDMA 전송작업을 통해 버퍼에 데이터를 작성하고, 마지막에는 완료 알림을 전송한다
      • 작은 메세지의 경우, 데이터와 크기에 대한 정보를 한번에 보내 오버헤드를 줄이고
      • 큰 메세지의 경우, adpative routing을 사용하며, 마지막 메세지에는 데이터를 보내지않고 크기정보만 보내서, 마지막 데이터임을 전달함
      • adaptive routing은 링크 및 네트워크 상황에 맞춰서 현재 상황에서 가장 빠른 경로로 데이터를 전송하는거 -> 데이터 순서가 보장안됨(다만, 패킷이 도착한 순서가 다를 수 있다는 거지, 작업 완료는 순서대로임)
      • 그래서 모든 데이터가 도착한 이후에 마지막 데이터를 보내서 완료를 보장함
      • reserve QP(수신측->송신측)에서는 CTS메세지를 통해 보내야할 버퍼주소, 키, 태그정보들을 포함하는 정보를 보냄
      • CTS와 데이터를 수신하는 채널은 분리되어 있음
      • CTS &lt-; 데이터 &lt-; CTS &lt-; 데이터 &lt-; CTS 순에서 CTS가 데이터 전송을 block하는 것을 방지하기 위함

    • d) Local Flush with Loop-back RDMA_READ

      • 수신측에서 IMM을 수신받고 완료라고 판단할 수 있지만, IMM은 송신측에서 모든 데이터전송 request가 송신측 NIC를 떠났을 때, 발행된다.
      • 즉, IMM이 실제 메모리에 데이터가 쓰여진 시점을 보장하지 않음
      • NCCL에서 실제 데이터 사용시점에 데이터가 메모리에 있음을 보장하는 작업을 한다
      • flush QP는 자기 자신에 연결된 것으로, 자기 자신에게 Read작업을 요청한다.
      • 이 read작업은 PCIe작업 큐 맨 뒤에 위치하게 되며, 모든 PCIe작업이 끝나느 시점 즉, 메모리에 모든 데이터가 도착한 시점에 실행되어, 모든 데이터가 메모리에 적혔음을 보장한다.

NCCL COLLECTIVIE ALGORITHMS

  • collective operation은 NCCL의 핵심이며, 효율적이고 동기화된 GPU간의 통신을 가능하게 한다

  • 데이터 이동, 의존성을 관리하고 통신 경로를 최적화하며, 확장성을 보장한다

  • NCCL collective operation은 low-level의 primitive들로 구성되어 있으며, 멀티 채널로 분배된다

  • Ring이냐 Tree이냐하는 결정은 어떤 collective operation, message size, topology로 정해진다

  • 이 섹션에서는 collective algorithm의 디자인과 주요 특징에 대해서 살펴본다

A. Overview of Algorithm and Protocol Support

  • NCCL에는 6개의 protocol이 있지만 모든 알고리즘에 사용되지는 않고, 하드웨어나 런타임 제약에 따라 정해진다.

  • 주로 ring이냐 tree냐로 프로토콜을 정하지만, CollNet과 NVLS는 allreduce에 특화된 프로토콜이고, NVLS는 reducescatter,, allgather도 지원한다

  • CollNet같은 경우는 switch 같은 네트워크 인프라가 collective operation에 참여할 수 있는 경우에 사용된다

    • 예를들어, reduction이나 일부 연산이 switch에 할당될 수 있고, 그럼으로, 데이터 이동과 레이턴시를 줄일 수 있게된다.
    • 즉, NVIDIA SHARP는 스위치 단에서 만나는 데이터를 reduction해주는 것
    • reduction: 여러 프로세스가 가진 데이터를 하나로 합치는 것(Sum, Avg …)

  • CollNet Direct는 노드 내에서 switch를 사용한 reduction을 수행하며, all-to-all을 하는 것이고

  • CollNet Chain은 GPU를 선으로 연결해서, 체인 위로가면서 switch를 사용한 reduction을 수행하고, 내려오면서 결과를 전파하는 broadcast를 수행한다

  • NVLS는 NVLink Switch가 있는 시스템에서 동작한다

  • 기본 NVLS는 노드 내부에서 reduction을 NVLink SHARP를 사용하고, 노드 간에서는 CollNet과 똑같이 스위치에서 연산한다

  • NVLS Tree는 노드 내부 연산은 같고, 외부에서는 트리 토폴로지에서 switch없이 reduction 및 전파된다.

  • 본 논문에서 분석단계에서 CollNet, NVLS는 다루지 않는다

  • NVSwitch, SHARP가능한 조건 등 하드웨어 조건이 너무 타이트해서이며

  • 새로운 알고리즘도 계속 나오지만 CollNet, NVLS를 포함하여 아직 널리 사용되지는 않고 있기 때문에

  • Ring, Tree 알고리즘만 다루더라도 충분할 것이다

B. Communication Primitives

  • NCCL collective operation은 low-level의 communication primitives로 구성되어 있다

    • direct 버전으로는 위에서 언급한 directSend, directRecv가 있고, 이것은 gpu 메모리를 IPC나 추가적인 copy없이 서로 참조하는 p2p 통신이다. 또한, 중간 FIFO buffer를 거치지 않음

  • primitives의 네이밍은 동작의 순서와 같다. 가령 recvReduceSend()의 경우 peer에게 데이터를 받고, local에서 reduction을 수행하고, 다음 peer에게 send한다

  • NCCL runtime에서는 primitives를 GPU마다 다르게 유연하게 배치하며, 이 배치는 loop문을 통해 반복된다. 그럼으로, 다양한 알고리즘, 토폴로지, 전송 계층 등에서 유연하게 통합될 수 있다

    • 다양한 환경에서 유연하게 primitives를 배치할 수 있다는 말

  • primitives는 어떤 protocol을 사용하느냐에 따라 다르게 구성되고, 동기화(방식?), buffer 관리, 전송 크기 등이 달라진다

  • 주로 Tree, Ring와 같은 source와 destination이 각각 1개이거나 총3개 이하인 직접 통신하는 peer가 적은 상황에 최적화되어 있으며, 이는 대부분의 collective operation에 해당한다.

  • 하지만, all-to-all같은 source와 destination이 N인 경우에는 덜 효율적이다.

C. Iterative Execution of NCCL Collectives

  • NCCL에서는 collective operation에 들어오는 입력을 가용가능한 채널 수로 나누고, 각 채널은 이 데이터를 나눠받아, 병렬처리할 수 있게된다

  • 각 채널은 데이터를 순서대로받아, 채널안에서 데이터 처리가 순차적으로 진행된다

  • 데이터의 원소수가 Count이고, 채널마다 입력의 시작하는 위치는 workOffset 간격으로 정해지고

  • 효율적인 데이터 전송 및 연산을 위해 각 채널은 고정된 버퍼 사이즈를 할당받으며, 이는 protocol에 의해 정해진다

  • 각 channel은 outer, inner loop를 돌며 데이터를 처리하고, 처리해야하는 데이터 총량이 buffer size를 넘어가면, outer loop를 추가해 처리하고,

  • inner loop에서는 buffer size만큼의 데이터를 처리하며, 각 반복에서는 loopCount 수만큼의 원소를 청크크기로 데이터를 처리한다

  • NCCL은 처리량을 높이기 위해 outer loop 단위 내에서 데이터를 나누고, 이를 파이프라이닝한다. 이때, 나눠진 데이터 세그먼트를 slot이라고하고, 주로 8개로 나눈다

    • NCCL_STEPS 파라미터로 slot수를 조절할 수 있다

  • 매 elementary step마다 각 slot에 chunkCount로 나눠진 청크 하나가 들어가서 처리되며, 연산작업과 통신작업이 수행될 수 있다.

    • 하나의 슬롯에 하나의 청크가 들어가며, 각 슬롯은 warp를 통해 병렬로 처리된다
    • 즉, 각 elementary step이 warp을 통해 병렬로 처리된다. 즉, inner loop자체가 병렬처리되는 것

  • NCCL에서 unit은 데이터를 다루는 아주 기본적인 단위이며, 그 크기는 어떤 collective를 사용하느냐에 따라 달라진다

  • 예를 들어, allgather, broadcast의 경우에는 유닛크기가 1byte이고, reducescatter, allreduce, reduce의 경우에는 float, int와 같은 user-defined이다.

    • 그 이유는 allgather, broadcast의 경우에는 단순히 데이터를 전송하는데에 초점이 있어서, single byte가 패킹하고 전송하는데에 유연한 장점이 있기 때문이고,
    • reduce 통신들은 type을 보존하면서 전송해야 reduction연산이 잘 수행될 수 있기 때문이다

  • 여기서 loopCount는 outer loop에서 처리되는 원소의 수이고, chunkCount는 청크 크기이면서 inner loop하나당 처리하는 크기, inner loop의 각 loop가 elementary loop이다

  • 표4에서 effective data per slot의 뜻은 slot안에 들어가는 “실제” 데이터 크기를 뜻하는 거다. LL은 반이 flag이니 반인 16K인것이고, LL128은 120data에 8flag가 있어서 그런것으고, Simple에서는 순수 데이터만 있으니 slot크기와 동일한 것

    • 정확히 8/128과 (600-562.5)/600이 같은 값임

D. Mapping Communication Pipelines to CUDA Hierachy

  • 성능을 측정을 잘 하기 위해 어떻게 통신 channel과 데이터 파이프라이닝이 gpu의 병렬모델에 적용되는지를 이해해야한다

  • NCCL은 수십만개의 스레드를 SM을 CUDA’s thread organization이라는 계층구조를 통해서 관리한다

  • 1) Grid and Block Structure

    • NCCL kernel은 실제 동작하는 channel과 같은수의 차원인 (nChannel, 1, 1)으로 구성된 grid 하나를 런치한다
    • 그리고 이 grid는 다수의 block으로 구성되며, 각 block이 하나의 채널로 맵핑되어 있따
    • block은 가변적인 수의 thread로 이루어져있고, 파라미터로 최소 최대 스레드수를 정할 수 있으며, 정확한 thread수는 kernel launch 준비 단계에서 NCCL’s autotuning 시스템을 통해 정의된다

  • 2) Channel-to-Block ID Mapping

    • 각 블럭에 하나의 채널을 맵핑하기 위해서 channelMask와 비트마스크를 수행하여, 각 블럭에 활성화된 channel이 몇번째인지 channel ID에 기록한다
      • blockidx.x에서 1,2,3,… 이것들이 각각 하나의 블럭을 의미하기에 각 x에 channel ID가 맵핑됨
      • 다시 복기하자면, block은 thread의 집합이다

  • 3) Warp-Level Organization

    • 각 block은 특정한 역할을 가지고 warp으로 분류된다. (block하나당 warp 여러개)
    • 최초의 두개의 warp중 0번째 communicator의 메타데이터를 shared memory에 옮기고, 1번째는 channel에 대한 데이터를 옮긴다. 나머지 warp은 통신 및 연산 작업을 담당한다
      • warp은 SM내에서 할당 재할당될 수 있기 때문에 0,1warp은 빠르게 작업을 마치고 다시 통신 혹은 연산 작업으로 배치됨
      • 통신도 copy, reduction 등의 작업을 함
    • collective에 따라 작업하는 warp의 수가 정해지며 descriptor의 nWarps에 명명되어 있따
    • NVLS AllRedcue의 경우 intra 단계와 inter단계를 분리한다.
      • intra와 inner는 순차적인 작업이지만, NCCL은 청크단위로 작업을 처리하기 때문에 순차적인 작업이 파이프라이닝되어 overlap될 수 있어, 역할에 따라 warp을 그룹핑하는게 의미가 있다
    • P2P통신에서는 send, recv작업으로 분할할 수 있으며, 각 작업에 할당되는 warp은 해당 작업에 현재 수행중인 통신작업량에 비례한다

  • 4) Slot-Based Pipeline Execution

    • 각 채널의 버퍼는 slot으로 나뉘고 slot들은 파이프라이닝되고 이것은 thread 레벨에서 이루어진다
      • 여기서 말하는 버퍼는 C에서 말한 채널당 할당한 버퍼 맞음
      • 각 채널당 하나의 블럭이고 각 블럭에 여러개 warp임. 채널작업은 여러 warp으로 구성되어 있음
    • 각 slot은 데이터 위치에 관한정보 외에 pipeline state를 포함한 정보를 가지는 ncclConnFifo 구조체를 가진다
      • 이 pipeline state가 현재 이 slot내 데이터가 연산중인지, 전송대기중인지, 전송중인지, 연산대기중인지와 같은 상태를 나타낸다

  • 5) Thread-Level Data Movement

    • 가장 세분화 되었을 때는, thread단위로 작업(데이터)을 분배하는 것이고, 구체적으로 각 스레드는 데이터를 한 loop안에 늘어뜨려서 실행한다.
    • 작업량은 protocol에 의해 정해진다
      • 각 protocol마다 buffer 크기와 slot크기가 다르기 때문에 각 warp 및 thread가 할당받는 데이터양이 다름
    • warp내에 thread는 동시에 같은 작업(send, reduce, copy)를 수행하지만, 각자 다른 데이터를 처리하게 되면서 GPU의 SIMT 아키텍처를 최대로 활용하게 된다
      • SIMD는 하나의 명령에 다수의 데이터를 처리하는방식이고, SIMT는 하나의 명령에 다수의 thread를 사용하는 개념
      • 두개의 가장 큰 차이점은 유연성이다. SIMD는 하나의 명령을 할당된 모든 thread가 처리해야하기 때문에 획일적이나
      • SIMT는 할당된 thread들 중 일부를 명령에 할당하고 나머지를 다른 명령에 사용할 수 있게 해. thread사용에 분기를 발생하는 것임으로
      • 더 유연하고 자원을 의도에 따라 쉽게 분배할 수 있어 프로그래밍에 용이하다

  • 6) Concurrent Pipeline Execution

    • NCCL의 통신작업은 하나의 흐름이 아니라 동시에 일어나는 데이터 연산 및 이동이 병렬화된 형태이다
    • 한 통신을 위해 다수의 채널이 여러 SM을 거쳐 수행되고, 각 채널의 slot들은 다른 pipeline stage를 가지며, 각 채널 내에 다수의 warp은 서로 다른 통신 단계 혹은 작업을 처리한다
    • 이러한 멀티 레벨 병렬구조로 최상의 대역폭 활용률을 달성한다
      • 정리하자면, 하나의 통신 작업을 여러개의 채널이 나눠서 처리하고, 이 채널은 여러 SM에 걸쳐있다. 각 SM에는 일부 채널들이 있고, 채널들은 병렬처리된다
      • 각 채널에서는 slot단위로 데이터를 쪼개고, 연산->통신대기->통신->연산대기와 같은 흐름으로 처리되며, slot들이 파이프라인 형태로 겹쳐지며 동시에 수행된다
      • 각 slot의 현재 pipeline stage 작업은 작업량에 따라 1~N개의 warp이 처리한다

E. Qualitative Algorithm Analysis

  • 위와 같은 반복적인 모델구조에서 현재 loop가 pipeline되느냐 안되느냐에 갈린다

  • 다음으로 본 논문의 저자는 pipeline 여부로 알고리즘을 나누고, 각 알고리즘의 분석에 대해서 loop단위에서 elementary step의 흐름에 대해서 설명한다

  • 앞서 계속 언급한 것처럼 알고리즘 런타임이 마치 데이터 크기와 같은 파라미터로 결정되는 것처럼 말했지만, 실제로는 더 많은 요인이 영향을 미치기 때문에 런타임을 파라미터들로 예측하는게 비현실적이다

  • 성능 측정에 가장 중요한 것은 “어떻게 GPU가 분배되어있는가” 이다.

    • 예를 들어 4개의 gpu가 같은 노드에 있는 것과 각각 다른 노드에 있는 것은 완전히 다른 대역폭과 latency를 가진다

  • 이러한 이유로 알고리즘의 복잡도를 단순화하고 실용적이게 하는게 매우 어렵다

  • 그럼으로, 양적인 분석보다는 질적인 분석을 하고, 구체적으로 이론적인 런타임을 제공하기보다는 필수 동작들에 대해서 집중할거다

  • 1) Non-pipelined Pattern

    • 이 패턴에서는 현재 iteration이 다음 iteration 시작전에 반드시 완료되어야하는 경우로
    • 주로 Ring AllReduce, Ring AllGather, Ring ReduceScatter가 있다
    • a) Ring AllReduce
      • Ring AllReduce는 데이터를 reduction하는 phase와 전파하는 phase 총 2개가 있다
      • 동작 순서 
    1. 0번째에는 보내기만함  

2. 1~k-2까지는 받고, reduce, 보내기  

3. k-1에는 각 GPU에서 각 segment가 모든 GPU로부터 reduction된 상태여서 전파하는 일만 남았음. 받아서 reduce하고 send하기 전에 copy하는 과정을 거침. 그 이유는 현재 reduce하고 있는 데이터는 메모리에 존재하지만, 통신에서 사용되는 중간 결과이기 때문에 소프트웨어 관점에서 보관하려면 copy해서 output buffer에 보관해놔야함  

4. k~2k-3에서는 완전히 reduce된 segment를 이전 gpu에서 받아서, 복사해서 output buffer에 담고, 다음 gpu에 넘겨줌  

5. 2k-2에서는 받기만 함. 모든 gpu가 전달 받은 상태

    • b) Ring AllGather

      • allgather는 완전한 데이터를 모든 rank가 가지기 위해 각 gpu가 생성한 segment를 전파하면서 완전한 데이터로 구성하는 작업이다
      • 동작 순서
      • 1. 0번째, in-place 설정인 경우, 이미 output buffer에 해당 세그먼트가 있음으로 바로 Send. 아닌경우, input buffer에서 output buffer로 옮기는 과정이 필요해, copySend
        • in-place는 input buffer하고 output buffer가 같아, 메모리 소비를 아낄 수 있는 설정
        • in-place설정은 데이터 나중에 써야하는 경우에는 손상되지 않는 경우에만 사용할 수 있고 혹은 input data를 덮어써서 변형이 생겨도 문제없는 경우에만 사용할 수 있음
      • 2. 1~k-2에서는 받은 세그먼트를 저장하고 넘긴다
      • k-1에서는 받고, 완료된다

    • c) Ring ReduceScatter

      • 각 GPU에 존재하는 데이터를 세그먼트 단위로 reduction해서, 최종적으로 각 gpu에는 하나의 완전히 reduction된 세그먼트만 남는다
      • 최소에는 각 GPU가 자신의 데이터를 k개의 세그먼트로 구분해서 buffer에 담는다 sendBuff를 통해서
      • 동작순서
      • ring allreduce의 초중반와 완전히 동일하다.
      • 마지막에는 초기에 데이터를 담아둔 buff에 한 세그먼트가 완전히 reduction된 상태로 존재한다

  • 2) Pipelined Pattern

    • Tree AllReduce, Ring BroadCast, Ring Reduce가 pipeline 패턴을 가진다

    • a) Tree AllReduce

      • Reduce후에 BroadCast로 총 2가지 단계로 이루어져 있음
      • Tree 토폴로지에서 노드는 GPU단위가 아니라 “노드”단위로 구성된다.
      • 노드 내에 gpu는 단순한 chain형식으로 구성된다
      • 이 통신에서는 이 두 phase가 동시에 수행된다.
      • Reduce는 루트방향으로 진행되고 동시에 Broadcast가 루트에서 아래로 진행된다
      • 두 단계에서 할당받은 SM을 불균등하게 나눠받고, 주로 대역폭 집약적인 reduction 단계에 더 많은 스레드를 할당한다
      • Reduce Phase
      • Leaf노드는 Send를 수행하고, Middle 노드는 하나 혹은 다수의 자식노드로 부터 데이터를 받아서 reduce하고 Send함
      • Root노드는 recvReduceCopySend를 하고, 받은 데이터를 최종 reduction하고 output buffer(user-defined)에 담음
        • 마지막 send는 broadcast를 위한 것
      • Broadcast Phase
      • Root가 보낸 reduced data를 children이 recvCopySend하고 마지막 leaf노드에서 recv하고 output buffer로 copy하고 종료
        • 여기서 leaf가 recv하고 copy하지만 왜 recvCopy가 아닌지는 몰겠
        • 유추하자면, primitive에 공존하는 copy는 통신 중간에 소실되는것을 방지하는 것 같고, 최종 primitive에서는 반환되는지 받기만하고 나중에 따로 copy해도되는 거 같기도함

    • b) Ring BroadCast

      • Ring Broadcast는 root에서 다른 노드에게 데이터를 전파하는 것이다.
      • Ring 구조이긴 하지만, directed chain이라하는 이유는 한방향으로 전파해서 결국 긴 사슬처럼 보이기 때문임
      • 동작 순서
      • root에서 시작하고 in-place냐 아니냐에 따라 send 혹은 copySend로 나뉨
      • Middle에서는 recvCopySend하고
      • Last에서는 recv하고 추가로 receive buffer에 copy함
      • 의문) ring의 양방향으로 보내면 root에서는 병목이 있어도 그 이후부터는 대역폭을 동시에 활용해서 좋지 않남
        • NCCL ring은 단방향임
      • 의문) 파이프라인 구조에 대한 설명이 없음

    • c) Ring Reduce

      • 각 GPU에 있는 데이터를 root에 하나로 reduction하는 통신
      • 동작순서
      • 초기노드에서 통신을 시작하며 send
      • 중간 노드들은 recvReduceSend
      • Root에서 recvReduceCopy
        • 여기서는 copy하네? + 초기노드는 root바로 전인듯?

**

**

F. Benchmarking

  • 이번 섹션에서는 NCCL collective를 벤치마킹했다

  • 그림6은 Tree, Ring AllReduce를 3가지 protocol에 따라 intra, inter-node 세팅에서 실험했다

  • 사양

    • CSCS의 Alps 슈퍼컴퓨터
    • 16노드, GH200
    • intra-node bandwidth = 150GB/s
    • 방향마다 inter-node bandwidth = 25GB/s

  • 그림6

    • 그림6, inter-node

      • 작은 메세지에서는 LL, LL128이 Ring, Tree에서 모두 우세 (64KB이하) 메세지가 GB단위가 되면, SP와 비교해 크게 하락(GB근처에서 매우 느려짐)
      • 작은 메세지의 오버헤드와 flag 오버헤드 때문임
      • 추가로, LL128가 LL와 큰 메세지 크기(2^22이하)에서 NVLink안에서는 우세하지만, RoCE를하는 대규모 inter-node 통신에서는 그 이점이 상쇄된다
      • LL128로 얻는 이점보다 RoCE에서 느려지는 정도가 훨씬커서 LL128의 이점이 크게 두드러지지 않는다는 의미인듯
      • LL128은 LL보다는 동기화 빈도가 낮지만, 여전히 많아서 대규모 스케일에서 지연이 발생하는 경우 동기화 딜레이가 누적되어 LL보다 느려질 수 있다
      • 반면 SP는 메세지 크기가 매우크고 동기화 빈도가 아주적어서, 네트워크 latency에 대해 영향이 매우 적다. 동시에 대역폭은 크게 유지하면서

    • 그림6, intra-node

      • intra에서는 LL128의 이점을 살려, 성능이 일관되게 높게 나온다.
      • 무슨이점?) 위에서 정리먼저해야함
      • 작은 메세지에서는 여전히 좋은 성능을 보이거나 LL보다 아주 약간 떨어지는 정도이다
      • 큰 메세지에서는 표1에서 분석한 것처럼(100% vs 95%) SP와 5%정도 성능차이가 있다
      • LL은 작은 메세지에서 최고의 성능을 SP는 큰메세지에서 최고의 성능을 보인다

    • inter, intra를 종합했을 때, 큰 메세지에서는 Ring이 작은 메세지에서는 Tree가 우세하다

      • 솔직히 작은메세지에서는 또이또이해 보이고, 큰메세지에서는 확실히 Ring이 좋은듯
      • 이유는?)

    • 3가지 교훈

      • 1. LL, LL128이 작은 메세지에서 최적이며, 특히 inter-node에서
      • 물론 SP가 큰 메세지에서는 우세하다
      • 2. 통신환경이 intra냐 inter냐에 따라 알고리즘 선택이 중요해진다
      • 특히, LL128의 경우에 그러하다
      • 3. NCCL의 autotuning을 활용하자
      • 사전정의된 시스템에서 수동적으로 알고리즘을 선택하는 것도 좋지만
      • 이미 잘 정의된 NCCL의 autotuning을 사용하는 것도 역시 안정적으로 성능을 보장한다. 대부분의 사례에서

    • 다른 collective에 대한 실험도 했지만 모두 AllReduce와 같은 결과가 나와 부록, 그림7에 수록한다

INTEGRATION INTO ATLAHS

  • 정리하자면, 본 논문에서의 분석들이 ATLAHS를 설계하는데 큰 도움을 줬고

  • 실제로 기존의 런타임을 측정을 추상화하던 것들이나 SOTA tool인 AstraSim에 비해 상당히 실제 런타임과 비슷하게 측정했다. 오차 약 5%이하

RELATED WORK AND OUTLOOK

최근 연구들은 분산 딥러닝과 HPC 환경에서 NCCL, MPI, Gloo와 같은 collective communication 라이브러리에 대해 상세한 분석과 성능 평가를 제시해 왔다. 예를 들어, Lee와 Lee [25]는 다양한 학습 아키텍처와 배포 설정에서 이들 라이브러리를 비교하는 실증적 연구를 수행했으며, 특히 대규모 All-Reduce 연산에서 노드 내 GPU 간 통신에 있어 NCCL이 뚜렷한 우위를 보인다는 점을 강조했다. 동시에 가상화나 컨테이너화로 인한 오버헤드 환경에서는 성능 저하가 발생할 수 있다는 점도 지적했다. Weingram 등 [26]의 종합 설문 연구와 같은 다른 연구들은 NCCL, RCCL, oneCCL, Gloo 등 산업계 솔루션을 포괄적으로 검토하며 collective 라이브러리 생태계 전반에 대한 넓은 시각을 제공한다. 이들은 NCCL이 GPU 중심 collective에서 여전히 사실상의 표준(gold standard)으로 자리 잡고 있지만, 대안 라이브러리들도 그 최적화 기법과 하드웨어 지원을 따라잡기 위해 빠르게 발전하고 있음을 언급한다. 이러한 연구들은 성능과 아키텍처 선택에 대한 중요한 통찰을 제공하지만, 대부분 실증적 벤치마크, 고수준 비교, 혹은 특정 알고리즘 혁신에 초점을 맞추고 있다. 반면 본 연구는 collective 구현 내부의 반복적 실행 알고리즘, 통신 프로토콜, 데이터 의존성을 체계적이고 심층적으로 분석한다는 점에서 차별화된다.

광범위한 채택에도 불구하고, NCCL은 적응성, 토폴로지 인지, 장애 허용성을 강조하는 최근의 발전들로부터 도전을 받고 있다. Blink와 같은 신흥 라이브러리는 다수의 트리를 동적으로 구성하고 고급 네트워크 토폴로지를 활용함으로써 상당한 성능 향상을 달성하며, 대규모 및 이기종 클러스터에서 NCCL의 ring 및 tree 알고리즘을 능가하는 성능을 보이고 있다 [26], [27]. SCCL [28]과 같은 자동화 프레임워크는 특정 하드웨어에 맞춰 collective를 합성하고 튜닝함으로써, 수작업으로 최적화된 루틴을 넘어서는 성능을 달성하며 연구의 최전선을 확장하고 있다. 분산 AI 워크로드가 점점 더 자원 집약적이고 장시간 실행되는 방향으로 발전함에 따라, 장애 허용성과 복원력 또한 핵심 요구사항으로 부각되고 있다 [26]. 이러한 흐름에 발맞추기 위해, 우리는 향후 NCCL이 자동화된 알고리즘 선택, 견고한 장애 처리, 그리고 in-network computation이나 smart NIC과 같은 기능을 제공하는 차세대 패브릭과의 더욱 긴밀한 통합을 지원해야 할 것으로 본다. 이러한 개선은 점점 더 요구 수준이 높아지는 분산 학습 환경에서 높은 성능, 확장성, 그리고 신뢰성을 유지하는 데 필수적이다.

Top comments (0)