NVIDIA cuOpt, 대규모 선형계획을 여러 GPU에 분산하는 mPDLP 공개

NVIDIA가 10월 7일 cuOpt에 NVLink 연결 GPU로 선형계획 문제를 분산하는 mPDLP를 소개했다. 회사의 B200 평가에서 tsp-gaia-10m 처리시간은 단일 GPU 대비 전체 과정 4.2배, PDLP 계산 단계만 11.4배 빨라졌다. 작은 문제나 GPU 간 통신이 많은 구조에서는 오히려 느려질 수 있다.

내용·출처 업데이트 · 2026. 10. 10. 오후 7:01

단일 GPU PDLP 대비 GPU당 최대 메모리 사용량을 최대 6분의 1로 줄였다는 회사 설명이며, 문제의 비영 원소 수 상한은 21억개다.

100개 이상의 LP 문제를 허용 오차 10⁻⁶·1시간 제한으로 평가했다. 다중 GPU는 DGX B200의 전면 NVLink 연결 환경, 단일 GPU는 B200 한 개를 사용했다.

비영 원소가 1000만개를 넘는 대부분의 큰 문제에서 기존 다중 GPU D-PDLP보다 1.2~2.5배 빨랐지만, 초대형 벤치마크 3개에서는 더 느렸다.

연속된 희소 행렬·벡터 곱의 의존성을 함께 고려해 그래프를 분할하고 GPU 간 데이터 교환을 줄인다.

Kinaxis는 변수 1억3500만개 이상인 공급망 모델을 H100 8개로 처리해 3.3배 개선을, PSR은 변수 1억8500만개인 에너지 모델을 B200 8개로 처리해 5배 이상 개선을 보고했다.

현재 분할은 GPU별 계산 부하를 반영하지 않는다. 부하 인식 분할과 통신·계산 병렬화는 향후 개선 과제다.

GPU 수를 늘리기 전에 실제 제약 행렬의 분할 결과와 전체 처리시간을 측정해야 증설 효과를 판단할 수 있다.