기술 요약: 유전적 파편화 경사 하강법 (GFGD)

1. 문제 정의

머신러닝과 생성형 AI를 지원하는 현대적 GPU 클러스터는 **자원 활용도(resource utilization)**와 할당 가능성(allocatability) 사이의 심각한 긴장 상태에 직면해 있습니다. 미세한 단위의 GPU 공유(여러 작업이 GPU 슬라이스의 하위 부분을 점유하도록 허용)는 총체적인 활용도를 높이지만, 이는 **자원 파편화(resource fragmentation)**를 초래합니다. 이러한 파편화는 장치 전반에 걸쳐 이질적이고 결합할 수 없는 잔여 간극을 생성합니다. 결과적으로, 클러스터가 충분한 총 자유 용량을 보유하고 있더라도, 자유 용량이 장치 간에 파편화되거나 불균형하게 분산되어 있어 도착한 작업의 요구 사항에 맞는 적절한 할당을 형성할 수 없다는 이유만으로 해당 작업이 거부(불가능)될 수 있습니다.

FGD(Fragmentation Gradient Descent)와 같은 기존 솔루션은 온라인 "what-if" 시뮬레이션을 사용하여 배치 결정의 장기적 영향을 추정함으로써 이를 완화하려고 시도합니다. 그러나 FGD는 두 가지 주요 한계점을 가집니다:

1. 높은 온라인 오버헤드: 대규모 클러스터 규모와 급격한 작업 유입(bursty arrivals) 상황에서 병목 현상이 되는 비용이 많이 드는 온라인 시뮬레이션 및 클러스터 전체 지표의 재계산을 요구합니다.
2. 불충분한 신뢰성 모델링: FGD는 파편화를 신뢰성의 대리 지표로 취급합니다. 그러나 파편화를 줄이기 위해서는 부하를 통합(consolidation)해야 할 수도 있는데, 이는 활용도 핫스팟을 생성하고 **스트레스 기반 런타임 실패(stress-driven runtime failures)**를 증가시킬 수 있습니다. 반대로 부하를 분산하면 핫스팟은 줄어들지만 파편화는 증가합니다. 따라서 파편화 단독으로는 스트레스 상황에서의 신뢰성을 나타내는 충분한 통계량이 될 수 없습니다.

핵심 과제는 생산 환경에 적합한 엄격한 결정 시간 예산 내에서 런타임 실패를 명시적으로 제약하면서, 파편화를 관리하고 할당 가능성을 개선하는 스케줄러를 설계하는 것입니다.

2. 방법론: GFGD 프레임워크

저자들은 오프라인-온라인(offline-online) 스케줄링 프레임워크인 **유전적 파편화 경사 하강법(GFGD)**을 제안합니다. 핵심 설계 원칙은 비용이 많이 드는 정책 탐색과 신뢰성 보정을 오프라인 시뮬레이터로 전환하고, 온라인에서는 가벼운 상수 시간(constant-time) 연산만을 배포하는 것입니다.

A. 오프라인 단계: 실패 제약 정책 진화

오프라인 단계에서는 **유전 알고리즘(GA)**을 사용하여 압축되고 해석 가능한 배치 정책을 진화시킵니다.

• 정책 표현: 각 정책은 세 가지 목적을 균형 있게 조절하는 3차원 가중치 벡터 $w = [w_{frag}, w_{pwr}, w_{fail}]$로 표현됩니다:
  1. 파편화 변화량 ($\Delta Frag$): 장치 간 불균형(GPU당 메모리 활용도의 표준 편차)의 대리 지표.
  2. 전력 대리 지표 ($\Delta Pwr$): 활용도 기반 선형 전력 모델.
  3. 실패 위험 대리 지표 ($\Delta Fail$): 활용도가 높아짐에 따라 단조 증가하며, 고부하(high-stress) GPU를 강조하는 핫스팟 민감형 집계기.
• 최적화 목적 함수: GA는 완료율(completion rate), 꼬리 지연 시간(tail latency), 낭비되는 에너지, 다운타임, 그리고 고립된 용량(stranded capacity)의 가중 합산된 스칼라 비용 함수를 하드 런타임 실패(RF) 가드레일 조건 하에서 최소화합니다.
• 가드레일 메커니즘: 시뮬레이션 노이즈에 대한 견고성을 보장하기 위해, RF 제약은 여러 시뮬레이션 시행을 통해 추정된 실패율의 상한 신뢰 구간(Upper Confidence Bound, UCB)에 대해 적용됩니다. $RRF(w) \le RRF_{ref} + \epsilon$을 위반하는 정책은 폐기됩니다.
• 레짐별 학습: 다양한 클러스터 상태에 적응하기 위해 서로 다른 운영 레짐(저, 중, 고 활용도)에 대해 정책을 별도로 진화시킵니다.

B. 온라인 단계: 레짐 인식 경량 스케줄링

결정 시점에 온라인 스케줄러는 두 가지 가벼운 연산을 수행합니다:

1. 레짐 선택: 평균 메모리 활용도를 기준으로 현재 클러스터 상태를 분류하고, 해당 레짐에 대응하는 사전 진화된 정책 가중치 벡터를 선택합니다.
2. 유계 후보 점수 산정 (Bounded Candidate Scoring): 모든 GPU를 평가하거나 미래 상태를 시뮬레이션하는 대신, 스케줄러는 다음을 수행합니다:
   • 실행 가능한 GPU 집합을 식별합니다.
   • "앵커 + 랜덤(anchor + random)" 전략(최대 여유 메모리, 최소 위험 등의 극단값과 무작위 샘플 선택)을 사용하여 작은 고정 크기의 후보 집합(예: $k_{cand}=8$)을 샘플링합니다.
   • 선택된 가중치 $w$와 위에서 정의된 세 가지 대리 지표를 사용하여 이 후보들의 순위를 매깁니다.
   • 가장 높은 점수를 받은 GPU에 작업을 순차적으로 배치합니다.

이 접근 방식은 온라인 "what-if" 시뮬레이션을 제거하여, 스케줄링 오버헤드를 휴리스틱 수준에 가깝게 낮추면서도 파편화를 고려하는 동작을 유지합니다.

3. 주요 기여

본 논문은 다음과 같은 기여를 주장합니다:

1. 실패 제약 오프라인 정책 학습: 파편화를 유일한 신뢰성 대리 지표로 사용하는 대신, 가드레일을 통해 런타임 실패를 명시적으로 제어하는 최적화 문제로서 GPU 스케줄링을 정식화했습니다.
2. 해석 가능한 정책의 GA 진화: 파편화 및 에너지 대리 지표를 최적화하면서 런타임 실패 제약을 준수하는 압축된 레짐별 3항 가중치 벡터를 진화시켰습니다.
3. 경량 온라인 스케줄링: 레짐 매칭 정책 선택과 상수 예산 후보 랭킹을 통해 FGD 수준의 시뮬레이션 없이도 휴리스틱에 가까운 오버헤드를 달성하면서 경쟁력 있는 할당 가능성과 신뢰성을 유지합니다.
4. 선택적 리스크 예측기: 다중 정책 선택을 위한 옵션 기능으로, 상태 수준의 진입 불가 예측기(Gradient Boosting Decision Trees 사용)를 제공합니다 (단, 핵심 온라인 경로에는 필수적이지 않음).

4. 실험 결과

저자들은 Alibaba GPU 클러스터의 프로덕션 트레이스와 합성 워크로드를 기반으로 캘리브레이션된 이산 이벤트 시뮬레이터를 사용하여 GFGD를 평가했습니다. 비교 대상은 FGD(bounded-candidate), Min-Power(PWR), 그리고 고정 가중치 Failure-Aware(FA) 휴리스틱입니다.

• 스케줄링 오버헤드: 클러스터 크기가 32에서 1024개의 GPU로 확장됨에 따라, GFGD는 FGD 대비 스케줄링 결정 시간을 5.1배에서 136.9배까지 단축했습니다. 후보군 평가 덕분에 오버헤드는 낮고 안정적으로 유지되었으며, 1024개 GPU 규모에서 평균 1.14 ms, P95 1.82 ms를 기록했습니다.
• 신뢰성 및 효율성:
  • 런타임 실패: GFGD는 다양한 스트레스 레벨($K_U$ sweep)에서 FGD 및 고정 가중치 FA 베이스라인에 비해 런타임 실패(NRF)를 크게 감소시켰습니다.
  • 완료율: GFGD는 FGD 대비 낭비되는 에너지를 약 74%에서 82%까지 줄이면서도 거의 완벽한 완료율(종종 1.000)을 유지했습니다.
  • SLO 안정성: SLO 압박 하에서 불안정성을 보인 Min-Power 베이스라인에 비해, GFGD는 시작 데드라인 미스(SD)를 실질적으로 줄였습니다.
• 강건성:
  • 스트레스 민감도: 명목 스트레스 레벨에서 훈련된 GFGD 정책은 다양한 실패 민감도 계수($K_U \in \{0, 1, 2, 3\}$) 테스트 하에서도 강건함을 유지했습니다.
  • 워크로드 변화: 작업 수, 지속 시간, 도착 돌발성(burstiness)의 분포 변화에 대한 탄력성을 입증했습니다.
  • 유형 불일치: GPU 타입과 실패율 간의 매핑이 무작위화되었을 때도 GFGD는 안정성을 유지하며, 고정된 타입-신뢰성 매핑에 의존하는 에너지 우선 전략보다 우수한 성능을 보였습니다.

5. 의의 및 주장

본 논문은 GFGD를 공유 GPU 클러스터의 "1차 병목(first-order bottleneck)"인 파편화에 대한 실질적인 솔루션으로 포지셔닝합니다. 그 의의는 다음과 같습니다:

• 복잡성과 성능의 분리: 정교한 파편화 인지형 배치(기존의 비용이 많이 드는 시뮬레이션이 필요했던 방식)의 이점을 오프라인 학습과 경량 온라인 스코어링을 통해 달성할 수 있음을 보여줍니다.
• 명시적 신뢰성 제어: 파편화 지표가 신뢰성에 충분하다는 가설에 도전하며, 할당 가능성을 위해 과도한 런타임 실패를 감수하는 트레이드오프를 방지하기 위해 명시적인 실패 위험 항과 하드 가드레일을 도입했습니다.
• 프로덕션 적합성: 결정 시간을 일정하고 낮게 유지함으로써, GFGD는 급격한 작업 유입이 발생하는 대규모 프로덕션 클러스터에 필요한 엄격한 결정 시간 예산을 충족하며, 시뮬레이션 중심의 스케줄러를 대체할 수 있는 실행 가능한 대안을 제시합니다.

저자들은 GFGD가 온라인 "what-if" 시뮬레이션의 계산 부담 없이 할당 가능성, 에너지 효율성, 신뢰성의 균형을 성공적으로 맞춘다고 결론짓습니다.