[Paper] 단일 GPU를 넘어: PDLP를 분산 멀티-GPU 시스템으로 확장

Source: arXiv - 2601.07628v1

개요

이 논문은 프라임‑듀얼 하이브리드 그래디언트(PDHG) 알고리즘의 분산 메모리 구현을 소개한다. 이 구현은 다수의 GPU에 걸쳐 실행될 수 있어 기존 단일‑GPU LP 솔버의 메모리 및 속도 한계를 뛰어넘는다. 제약 행렬을 2‑D 그리드의 GPU에 분할하고 고성능 NCCL 통신을 활용함으로써, 저자들은 이전에는 단일 가속기에서는 너무 커서 처리할 수 없었던 대규모 선형 프로그램을 완전한 배정밀도 정확도와 인상적인 속도 향상으로 해결할 수 있음을 보여준다.

Source: …

주요 기여

• 멀티‑GPU PDHG 프레임워크: 단일 GPU용으로 검증된 PDHG 솔버(cuPDLPx)를 2‑D 격자 방식으로 LP 제약 행렬을 분할하여 임의 개수의 GPU에서 사용할 수 있도록 확장했습니다.
• 로드‑밸런싱 데이터 분배: nonzero‑aware 파티셔닝 방식과 블록‑단위 랜덤 셔플링 전략을 도입해 각 GPU가 지속적으로 작업을 수행하도록 하여 지연 GPU를 방지합니다.
• 통신 효율 설계: NVIDIA의 NCCL 라이브러리와 융합 CUDA 커널을 활용해 원시‑쌍대 업데이트를 최소 오버헤드로 동기화합니다.
• 완전 FP64 수치 정확도: 분산 실행 환경에서도 이중 정밀도 결과를 보장하여 많은 산업용 최적화 파이프라인의 요구 사항을 충족합니다.
• 광범위한 실증 검증: MIPLIB, Hans 인스턴스, 실제 데이터셋 등에서 강력한 확장성을 입증했으며, 최고 단일‑GPU 기준 대비 수배에 달하는 속도 향상을 달성했습니다.

방법론

1. Problem formulation – LP는 표준 형태로 표현되며, PDHG 알고리즘은 그래디언트 단계와 근접 연산자를 사용하여 원시(변수)와 이중(제약) 벡터를 반복적으로 업데이트한다.
2. 2‑D grid partitioning – 큰 희소 제약 행렬 (A)를 행과 열 모두에서 슬라이스하여 각 서브 행렬을 논리적 격자상의 별도 GPU에 할당한다. 이를 통해 메모리 사용량과 연산 작업이 분산된다.
3. Nonzero‑aware distribution – 행/열을 단순히 균등하게 나누는 대신, 알고리즘은 먼저 블록당 비영(非零) 항목 수를 계산하고 블록을 재분배하여 각 GPU가 대략 동일한 비영 개수를 받도록 한다. 이는 실제 연산 부하와 상관관계가 있다.
4. Block‑wise random shuffling – 각 GPU 내부에서 블록은 매 반복마다 무작위 순서로 처리되어, 상관관계에 의한 부하 불균형을 감소시키고 수렴 안정성을 향상시킨다.
5. Communication layer – 각 PDHG 단계 후에 GPU들은 경계 원시/이중 값을 교환해야 한다. 이는 NCCL의 all‑reduce와 point‑to‑point 기본 연산을 사용하고, 여러 작은 메시지를 하나의 GPU 실행으로 결합하는 융합 커널에 래핑하여 지연 시간을 줄인다.
6. Implementation – 기존 cuPDLPx 코드베이스 위에 구축하여, 저자들은 핵심 알고리즘을 변경하지 않은 채 분산 데이터 구조, 통신 루틴, 그리고 커널 융합을 추가하였다.

결과 및 발견

• 메모리 혁신: 32 GB GPU에서 메모리 부족 오류가 발생하던 문제들이 각 GPU당 ≤ 12 GB만 사용되는 4‑GPU 클러스터에서 원활히 실행되었습니다.
• 통신 오버헤드: NCCL 통신은 16 GPU에서도 전체 실행 시간의 < 12 %를 차지했으며, 이는 융합 커널 및 2‑D 파티셔닝의 효과를 입증합니다.
• 수치 정확도: 모든 실험에서 FP64 솔루션 품질을 유지했으며, 잔차는 단일‑GPU 솔버와 상대 허용오차 1e‑12 이내에서 일치했습니다.

실용적 함의

• 확장 가능한 최적화 서비스: 클라우드 제공자는 이제 메모리 제한을 걱정하지 않고 LP 해결을 다중 GPU 서비스로 제공할 수 있어, 대규모 물류, 금융, 에너지 계획 모델을 온디맨드로 해결할 수 있습니다.
• 기존 파이프라인과의 통합: 구현이 cuPDLPx를 기반으로 하고 표준 CUDA/NCCL API를 사용하기 때문에, 개발자는 현재 GPU 가속 데이터 사이언스 스택(예: RAPIDS, PyTorch)에 최소한의 코드 변경만으로 쉽게 적용할 수 있습니다.
• 비용 효율적인 하드웨어 활용: 단일 대형 GPU를 프로비저닝하는 대신(이는 희소하거나 비용이 많이 들 수 있음), 여러 일반 GPU를 집합하여 유사한 성능을 달성함으로써 하드웨어 ROI를 향상시킬 수 있습니다.
• 다른 솔버를 위한 기반: 2‑D 파티셔닝 및 로드 밸런싱 아이디어는 메모리 병목 현상을 겪는 다른 1차 방법(예: ADMM, 확률적 경사)에도 적용 가능합니다.

제한 사항 및 향후 작업

• 희소 행렬 구조 의존성: 현재 파티셔너는 비교적 균일한 희소성 패턴을 가정합니다; 매우 불규칙한 행렬은 여전히 부하 불균형을 초래할 수 있습니다.
• 네트워크 토폴로지 민감도: 실험은 고속 NVLink‑연결 클러스터에서 수행되었습니다; 이더넷 기반 다중‑노드 설정에서는 높은 지연으로 인해 성능이 저하될 수 있습니다.
• 알고리즘 확장: 저자들은 적응형 스텝‑사이즈 스킴과 혼합‑정밀도 변형을 탐구하여 정확성을 유지하면서 실행 시간을 더욱 줄이는 방안을 계획하고 있습니다.
• 보다 넓은 벤치마크 스위트: 향후 작업에는 머신러닝에서 등장하는 LP 벤치마크(예: 대규모 서포트‑벡터 머신) 테스트와 고수준 모델링 언어와의 통합이 포함됩니다.

저자

• Hongpei Li
• Yicheng Huang
• Huikang Liu
• Dongdong Ge
• Yinyu Ye

논문 정보

• arXiv ID: 2601.07628v1
• 분류: math.OC, cs.DC
• 발행일: 2026년 1월 12일
• PDF: PDF 다운로드