Ring vs Tree Collectives

collective operation의 의미와 구현은 다르다.

AllReduce의 의미:
  값을 합산하고 모든 rank가 결과를 갖는다

AllReduce의 구현:
  ring, tree, 또는 hybrid 알고리즘으로 통신을 스케줄한다

그래서 all-reduce를 이해한 뒤에는 “이 통신을 어떤 모양으로 흘릴 것인가”를 봐야 한다.

Ring

Ring은 rank들을 원형으로 이어서 이웃끼리 chunk를 주고받는다.

rank 0 -> rank 1 -> rank 2 -> rank 3 -> rank 0

큰 tensor를 rank 수만큼 chunk로 나누고, 각 rank가 동시에 send와 receive를 반복한다. 링크들이 동시에 바쁘게 움직이므로 bandwidth를 잘 쓴다.

좋은 상황:
  큰 gradient bucket
  큰 parameter shard
  bandwidth가 병목인 통신

대신 여러 step을 돌아야 하므로 작은 메시지에서는 latency가 부담이 될 수 있다.

AllReduce on N ranks:
  ReduceScatter 단계: N - 1 step
  AllGather 단계:    N - 1 step

Tree

Tree는 rank들을 트리처럼 묶는다.

leaf ranks -> parent ranks -> root
root -> parent ranks -> leaf ranks

reduce할 때는 값이 root 방향으로 올라가고, broadcast할 때는 root에서 다시 내려온다.

좋은 상황:
  작은 control tensor
  작은 metadata
  latency가 병목인 통신

Tree는 step 수가 대략 log(N)에 가까워서 작은 메시지에 유리하다. 하지만 모든 링크가 동시에 같은 양의 데이터를 계속 보내는 구조는 아니기 때문에, 아주 큰 tensor에서는 ring보다 bandwidth 활용이 낮을 수 있다.

NCCL은 골라서 쓴다

실전에서는 보통 직접 ring이나 tree를 구현하지 않는다. NCCL 같은 collective library가 tensor 크기, GPU topology, link 종류를 보고 알고리즘을 고른다.

작은 메시지:
  latency가 중요 -> tree 계열이 유리할 수 있음

큰 메시지:
  bandwidth가 중요 -> ring 계열이 유리할 수 있음

중간 크기:
  hybrid가 선택될 수 있음

학습자가 가져가야 할 결론은 단순하다.

collective의 의미를 이해한다
통신량과 message size를 본다
topology를 본다
실제 구현은 NCCL의 선택과 profile 결과로 확인한다

확인

• Ring은 왜 큰 tensor에서 bandwidth를 잘 쓸 수 있는가?
• Tree는 왜 작은 메시지에서 유리할 수 있는가?
• AllReduce의 의미를 안다고 해서 실제 통신 시간이 바로 결정되지 않는 이유는 무엇인가?