엔비디아 cuOpt, 1억 변수 LP 지원
최근 30일 조회수 — 좋아요 —핵심 요약
다중 GPU 솔버 mPDLP이 NVLink로 연산을 분산해 초대형 선형계획 문제의 속도와 메모리 효율을 높였다.
엔비디아(NVIDIA)가 GPU 기반 의사결정 최적화 도구 cuOpt에 다중 GPU용 선형계획법 솔버 mPDLP(Multi-GPU Primal-Dual hybrid gradient for Linear Programming)를 도입했다. NVLink로 연결된 여러 GPU에 계산을 분산해 변수 1억 개를 넘는 최적화 문제까지 처리하고, 단일 GPU로는 수렴에 수 시간이 걸리거나 메모리 한도를 넘던 병목을 줄이는 것이 핵심이다.1
선형계획법(LP)은 비용을 최소화하면서 공급량이나 생산능력 같은 제약을 만족하는 변수 조합을 찾는다. 공급망에서는 품목과 운송 경로가 늘고, 전력망에서는 분산형 발전원을 실시간으로 반영하면서 문제 규모가 커지고 있다. 엔비디아에 따르면 기존 cuOpt도 대규모 LP에서 단일 GPU로 CPU 솔버보다 10배 넘는 속도 향상을 낼 수 있지만, 가장 큰 계획 문제에는 충분하지 않았다.1
mPDLP의 토대인 PDLP(Primal-Dual hybrid gradient for Linear Programming)는 원시해 (x)와 쌍대해 (y)를 반복 갱신하는 1차 방법이다. 계산의 중심에는 희소 행렬-벡터 곱셈(SpMV)이 있다. 제약조건 행렬을 (A)라고 하면 반복 과정에서 (A^\top y)로 (x)를, (Ax)로 (y)를 갱신한다. 나머지는 변수 범위 투영과 기본 산술처럼 GPU에 나누기 쉬운 원소별 연산이다.
관건은 메모리 대역폭의 영향을 크게 받는 SpMV를 여러 GPU에 어떻게 배치하고, 직전 반복에서 나온 벡터를 다음 계산에 전달하느냐다. mPDLP은 이를 NVLink 연결 GPU에 분산한다. 엔비디아 발표 기준으로 비제로 원소가 최대 21억 개인 LP에서 단일 GPU PDLP보다 GPU당 최대 메모리 사용량을 6분의 1로 낮출 수 있다. 2008년 공개된 비제로 원소 1억400만 개 이상의 벤치마크 zib03에서는 1년 전보다 풀이 속도가 약 10배 빨라졌다고 회사는 밝혔다.1
엔비디아는 공급·생산 계획 업체 키낵시스(Kinaxis)와 에너지 시스템 용량 확장 모델을 다루는 PSR을 적용 사례로 제시했다. 다만 공개 자료의 성능 수치는 엔비디아가 제시한 결과이며, GPU 수와 문제 구조에 따른 통신 비용이나 외부 솔버와의 동일 조건 비교 결과는 제공된 자료만으로 확인하기 어렵다.
Footnotes
읽기 목록은 이 브라우저에 저장됩니다.
출처
- Scaling Decision Optimization to 100 Million Variables and Beyond with mPDLP in NVIDIA cuOpt | NVIDIA Technical Blog — NVIDIA Technical Blog
이 글은 위 출처를 근거로 자동 생성된 뒤 발행됐습니다. 원문을 함께 확인해 주세요. 교차 보도 없이 단독 출처로 작성됐습니다.