GPU를 늘리면 최적화도 빨라질까: mPDLP

제작 중인 해설: SELECTED · 2026-10-10 KST Top 1 · 편집 점수 86/100 · INDUSTRY_TRIGGER. NVIDIA 자체 발표를 검토한 글이다. 독립 재현·원 도판 전수 대조·실제 검색 데이터 검토가 끝나지 않아 공개 준비 완료로 표시하지 않는다.

#1. GPU를 더 붙이면 답도 더 빨리 나올까?

계산 장치를 늘리는 것만으로는 최적화가 빨라지지 않는다. 누가 어떤 계산을 맡고, 다음 계산에 필요한 정보를 어디에서 받아야 하는지를 함께 설계해야 한다. NVIDIA의 mPDLP는 큰 선형계획 문제를 여러 GPU에 나누면서 통신을 줄이는 접근이다. 여기서 배울 핵심은 GPU의 개수보다 변수와 제약의 연결을 어떻게 나누는가다.

다만 출발점을 분명히 하자. 이 소식은 10월 7일 NVIDIA가 공개한 기술 설명이며, 회사가 측정한 결과다. 현재 확보한 근거는 기업 기술 본문이며, 독립 재현이나 동료평가 판본을 이 글에서 확인하지 않았다. 발표의 정확한 시각과 벤치마크 구현 버전도 확인되지 않았다. 제품 이름이 익숙하다는 이유로 이 빈칸을 채우지 않는다.

#2. 왜 큰 문제는 나누기만 해서는 풀리지 않을까?

한 창고의 배송량을 늘리면 다른 창고의 배송량이 줄어들 수 있다. 수요를 채워야 한다는 제약이 둘을 연결하기 때문이다. 큰 계획 문제에서도 각각의 결정은 따로 움직이지 않는다. 어떤 제약은 많은 변수를 함께 묶고, 한 변수는 여러 제약에 영향을 준다. 계산을 두 장치로 나누더라도 서로의 현재 값을 필요로 하는 이유다.

GPU가 맡은 산술을 빨리 마쳤는데 다음 입력이 다른 장치에서 아직 도착하지 않았다면 기다려야 한다. 한편 모든 정보를 매번 복사하면 기다리는 시간을 줄이기는커녕 전송량이 커질 수 있다. 장치의 메모리에 문제를 담는 일, 반복 계산을 수행하는 일, 결과를 실제 조건에 맞는 해로 확인하는 일도 구분해야 한다. 하나의 시간 숫자로 합치면 어디가 개선됐는지 보이지 않는다.

#3. 먼저 익힐 개념: 변수, 제약, 희소 행렬

선형계획(linear programming, LP)은 선형 비용을 작게 만들면서 선형 제약을 만족하는 연속 변수 값을 찾는다. 비용이 낮아도 수요를 못 채운 계획은 답이 아니다. 반대로 조건을 만족하는 계획이 여러 개라면 그중 비용을 비교해야 한다. 차량 대수처럼 정수만 허용해야 하는 결정은 추가 정수 제약이 필요한 별도 문제다. 일반 LP의 결과를 곧바로 정수 계획의 결과로 옮길 수 없다.

NVIDIA 본문은 다음 등식 제약 형태로 설명한다. 부등식과 목적함수의 다른 형태를 포함하는 모든 현실 문제를 이 표기 그대로라고 단정하지 않는다.

x는 결정할 n개 값, c는 그 값의 비용 계수다. b는 맞춰야 할 m개 제약 값이고, A는 변수와 제약을 잇는 m×n 행렬이다. l,u는 각 변수의 하한과 상한이다. 변수의 단위는 모델이 정한다. 배송량을 물량 단위로 잡고 c를 물량당 비용으로 잡으면 목적함수는 비용 단위가 된다. 서로 다른 행의 제약은 다른 단위를 가질 수도 있으므로 행렬 전체를 단일 물리량이라고 읽어서는 안 된다.

희소(sparse) 행렬은 대부분의 원소가 0인 행렬이다. 0은 그 변수와 제약 사이에 해당 계수의 직접 연결이 없다는 뜻으로 읽을 수 있다. 저장할 값과 연산을 줄일 여지가 있지만, 0이 적다는 사실만으로 여러 GPU의 통신도 적어진다고 보장되지는 않는다. 남은 연결이 장치 경계를 어떻게 넘는지가 중요하다.

#4. 그림을 먼저 관찰하자: 무엇을 나누고 무엇을 주고받나?

입력 모델, 반복 계산, 해 확인이 서로 다른 역할을 맡는다는 그림이다. 반복 계산만 빨라져도 나머지 두 구간은 전체 시간에 남는다. 분할과 데이터 준비도 필요하다. 특히 발표가 제시한 전체 실행시간에는 전처리(presolve), CPU에서 행렬 A를 전치하는 작업, 그래프 분할, 후처리(postsolve)가 포함된다. GPU 반복 단계의 가속과 이 준비·정리 시간을 따로 읽는 이유다.

그림 크게 보기 · 새 탭

두 번째 그림의 원과 네모는 실제 GPU 개수가 아니라 변수와 제약의 두 종류를 나타낸다. 연결선 하나를 장치 경계가 가르면 상대편 값이 필요해질 수 있다. 이 장난감 그래프는 원문 Figure의 재현이 아니며 측정 데이터도 아니다. 경계를 가로지르는 연결과 각 장치가 맡은 일의 양을 동시에 관찰하기 위한 자체 예시다.

그림 크게 보기 · 새 탭

#5. 기존 방법과 달라진 방법을 세 단계로 보기

비교의 첫 기준은 한 GPU에서 계산하는 PDLP다. 장치 간 통신은 없지만 그 장치의 메모리와 계산 자원에 제약을 받는다. 두 번째 기준은 행렬을 2차원 블록으로 나누는 기존 D-PDLP다. 분산한 부분 결과를 합치는 통신이 필요하다. 세 번째로 Google OR-Tools PDLP는 공통 수학을 이해하는 참고 구현이다. OR-Tools를 이번 NVIDIA 다중 GPU 제품의 동일 버전 또는 동일 성능 기준이라고 취급하지 않는다.

mPDLP의 설명을 세 단계로 따라가자. 첫째, 변수와 제약을 서로 다른 종류의 노드로 보고 A의 비영 원소를 연결로 표현한다. 둘째, 장치 경계를 넘는 연결을 줄이는 최소 컷(min-cut) 방식으로 분할한다. 셋째, 각 장치가 맡은 계산을 수행하면서 필요한 상대 장치의 값을 교환한다. 원문이 설명하는 분할은 변수 쪽과 제약 쪽의 연결 관계를 함께 고려한다.

최소 컷은 연결을 적게 가르는 방향을 찾는다는 직관으로 출발할 수 있다. 하지만 연결의 개수나 전송량만 줄이는 목적과 각 GPU에 일을 고르게 배분하는 목적은 같지 않다. 일을 거의 맡지 않은 GPU와 대부분을 맡은 GPU를 나란히 놓으면, 통신량이 적더라도 기다림이 생길 수 있다. 현재 분할이 계산 부하를 충분히 반영하지 못한다는 한계는 발표에도 남아 있다.

#6. 식을 따라가면 통신의 위치가 보인다

PDHG(primal-dual hybrid gradient)는 PDLP의 기반 반복법이다. 원문의 부호 규약에 맞춘 두 갱신식은 다음과 같다. 여기서 k는 반복 번호이며 물리적 시간이 아니다. y는 등식 제약의 쌍대 변수, τ,σ는 스텝 크기다. 수치 스케일과 스텝 선택 조건 없이 이 식을 임의 값으로 반복하면 반드시 수렴한다고 주장할 수 없다. 비용 계수 c와 Aᵀy는 같은 변수당 비용 단위를 가져야 하고, b와 Ax는 각 제약 행의 단위가 맞아야 한다. τ와 σ는 이 스케일에 맞춰 갱신량을 조절하는 수치적 계수이지 초 단위의 물리적 시간이 아니다.

첫 식은 비용과 제약의 영향을 반영해 x를 움직이고, 투영(projection)으로 변수별 허용 구간 [l,u]에 돌려놓는다. 상한을 넘어간 값을 상한으로 되돌리는 단순한 예를 떠올릴 수 있다. 이것만으로 등식 제약까지 모두 만족했다고 말할 수는 없다. 그 부분은 Ax와 b의 차이를 함께 검사해야 한다.

뒤에서 풀 배송 예제의 숫자를 미리 사용해 보자. 두 창고의 상한이 각각 6과 8이고, 임시로 계산한 배송량이 7과 3이라면 변수 범위로의 투영은 이를 6과 3으로 바꾼다. 각각의 용량 제한은 지켰지만 합은 9라서 수요 10을 채우지 못한다. 이는 투영의 역할만 보이는 가상 계산이며 실제 mPDLP 반복에서 얻은 중간값이나 수렴 실험이 아니다. ‘범위 안에 있음’과 ‘모든 제약을 만족함’은 별개다.

둘째 식의 2x^{k+1}−x^k는 새 값과 이전 값의 차이를 더 반영한 외삽(extrapolation) 값이다. 새 값 자체와 구분해서 읽자. Aᵀy와 Ax에는 변수–제약 연결의 계산이 들어 있다. 행렬을 여러 장치에 나누면 이 계산에 필요한 값이 다른 장치에 있을 수 있고, 바로 그 지점이 통신 설계와 연결된다.

그림 크게 보기 · 새 탭

원문에는 통신 의존성만 보이려고 Aᵀy를 계산한 다음 Ax를 계산하는 두 행렬–벡터 곱으로 줄인 표기도 있다. 비용 항 c, 변수 범위로의 투영, 스텝 크기 τ·σ, 외삽을 생략한 설명용 축약이다. 따라서 이 두 곱만 반복하는 것을 위의 완전한 PDHG 솔버나 실행 가능성 판정으로 읽으면 안 된다. 축약 표기는 어떤 값이 장치 경계를 넘어 필요해지는지 보여주고, 전체 갱신식은 그 값이 최적화 문제에 어떻게 쓰이는지 설명한다.

#7. 함께 풀어보자: 배송 계획은 어떻게 바뀌나?

이제 원문 결과와 분리한 설명용 계산을 해 보자. 두 창고에서 보낼 양을 a,b로 두고, 수요는 10단위라고 정한다. 첫 창고의 용량은 6, 둘째 창고는 8이며 단위 비용은 각각 2와 3이다. 조건은 a+b=10, 0≤a≤6, 0≤b≤8이다. 이 용량 제한은 일반식에서 변수 상한 u에 해당한다. 연구가 사용한 실제 배송 데이터는 아니다.

수요 조건에서 b=10−a를 얻는다. 비용 2a+3b에 대입하면 30−a가 된다. 조건을 만족하면서 a를 크게 할수록 비용이 작아진다. 첫 창고의 상한 6을 택하면 a=6,b=4, 비용은 24다. 배송량의 합은 10이고 두 용량을 넘지 않는다. a를 1 줄이고 b를 1 늘리면 비용이 1 늘어나므로 이 해가 최적임을 직접 확인할 수 있다.

이제 조건을 바꿔 보자. 첫 창고 용량이 4로 줄어들면 같은 계산의 해는 a=4,b=6, 비용 26이다. 목표는 그대로지만 가능한 해의 범위가 달라졌다. 첫 창고 용량이 1이면 둘째 창고가 최대 8을 보내도 합이 9이므로 수요 10을 채울 수 없다. 이 경우는 비싼 답을 찾는 문제가 아니라 설정한 제약이 함께 만족 가능한지부터 확인하는 문제다.

이 작은 예제를 두 GPU로 나누면 성능이 좋아질까? 산술이 몇 번뿐이므로 실제 통신·설정 비용까지 고려하면 유리하다고 단정할 수 없다. 계산한 24와 26은 최적 목적값의 비교이며 GPU 속도 측정이 아니다. 답·허용오차·실행시간은 서로 다른 질문이다.

#8. 반복 단계 11.4배와 전체 실행 4.2배는 왜 다른가?

NVIDIA는 all-to-all NVLink로 연결한 DGX B200에서 100개가 넘는 LP, 목표 허용오차 10⁻⁶, 1시간 제한으로 비교했다고 보고한다. tsp-gaia-10m에서는 반복 단계 속도 향상이 최대 11.4배였지만 전체 실행의 향상은 4.2배였다. 8개 B200의 mPDLP와 단일 B200의 cuOpt PDLP를 비교한 수치이며, 아래의 D-PDLP 비교와는 기준이 다르다. 발표 HTML에서 이 목표 오차의 구체적 잔차 정의·정규화·정지 판정 구현까지는 확인하지 못했다. 튜토리얼 설정과 같은 의미라고 확정하지 않는다. 반복 단계가 끝났다고 분할·준비·후처리까지 모두 사라지는 것은 아니다.

그림 크게 보기 · 새 탭

막대가 길수록 기준 대비 보고된 속도 향상이 크다는 뜻이다. 11.4배를 다른 문제의 기대 성능으로 사용하거나 두 막대를 서로 다른 장비의 절대 실행시간처럼 비교하지 않는다. 보고된 전체 시간의 4.2배와 반복 시간의 11.4배만으로 준비 과정이 정확히 몇 초 걸렸는지도 계산할 수 없다. 각 구간의 원래 시간이 별도로 필요하다.

#원본 산점도의 축과 기준선 읽기

발표의 그림 5는 가로축에 행렬의 비영 원소 수(nnz)를 놓는다. 변수 개수와는 다른 양이다. 세로축은 단일 GPU 실행시간을 다중 GPU 실행시간으로 나눈 비다. 1보다 크면 그 문제에서는 다중 GPU가 빨랐고, 1보다 작으면 단일 GPU가 빨랐다는 뜻이다. 가로축은 로그 눈금이므로 같은 간격이 같은 개수 증가를 뜻하지 않는다.

그림 6은 두 방식 모두 8개 B200을 쓴 비교다. 분자는 D-PDLP 시간, 분모는 mPDLP 시간이다. 따라서 그림 5와 6의 같은 높이가 같은 기준 장치 대비 성능을 뜻하지 않는다. 각 점은 문제 하나의 관찰이며, 큰 nnz에서도 기준선 아래 점이 보인다. nnz만 알면 속도 향상을 보장할 수 있다는 그래프가 아니다.

확인 질문: 두 그래프에서 모두 2배인 점을 보면 같은 실행시간이라고 말할 수 있을까? 아니다. 각각 다른 기준 실행시간으로 나눈 비이며, 절대 시간은 이 비만으로 알 수 없다.

#9. 반대 사례와 허용오차를 어떻게 읽을까?

통신을 줄이는 분할이 모든 병목을 없애는 것은 아니다. 발표의 향후 개선 절은 현재 분할이 GPU별 계산 부하를 고려하지 않고, 핵심 행렬–벡터 계산의 통신과 연산도 순차적으로 수행한다고 밝힌다. 부하를 반영한 분할과 통신·계산의 겹쳐 실행은 앞으로 개선할 항목이다. 따라서 이미 두 기능까지 적용해 모든 GPU를 균등하게 활용했다고 설명하면 안 된다. 연결을 적게 자르는 일과 각 GPU의 일을 고르게 나누는 일은 서로 관련되지만 같은 목표는 아니다. [공식 발표, Continuing to improve cuOpt mPDLP]

초대형 문제에서도 기존 D-PDLP보다 느린 사례가 세 개 있었다. 이것은 큰 문제라면 자동으로 유리하다는 해석을 막는다. 장치 경계를 넘는 연결, GPU별 계산량, 분할과 전처리 부담이 서로 달라질 수 있다. GPU 개수와 가장 좋은 사례만 표시하면 이 차이를 숨기게 된다. 다음 검토에서는 좋아진 문제와 느려진 문제의 조건을 함께 비교해야 한다.

10⁻⁶이라는 수치도 단독으로는 충분하지 않다. 공식 튜토리얼은 상대 primal·dual·gap 허용오차를 각각 설정한다. primal 측면은 원래 변수와 제약의 만족 정도를, dual 측면은 쌍대 조건의 만족 정도를, gap은 목적값의 차이를 통해 최적성에 얼마나 접근했는지를 평가하는 데 쓰인다. 하지만 실제 계산식과 정규화 방식은 구현 문서와 버전을 확인해야 한다. 이 튜토리얼의 세 설정이 발표의 모든 벤치마크에서 정확히 같은 기준이었다고 확정하지 않는다.

앞의 배송 예에서 비용이 좋아 보여도 배송량 합이 10에 못 미치면 실행 가능한 계획이 아니다. 수치적 허용오차를 둔다면 어떤 제약에 얼마나 미달해도 되는지까지 시스템 요구와 연결해야 한다. 최적화 프로그램이 종료 상태를 내보냈다는 사실과 사업·안전·운영 조건을 만족했다는 사실은 따로 확인해야 한다.

#10. 핵심 한계: 통신량, 계산량, 구현 버전

최소 컷으로 통신을 줄이는 목표만으로 계산 부하까지 균등해지지는 않는다. 데이터의 연결 구조가 달라지면 같은 장치 개수에서도 결과가 달라질 수 있다. NVIDIA는 계산 부하를 고려하는 분할과 다른 개선을 향후 과제로 설명한다. 향후 계획을 이미 구현된 기능으로 소개하지 않는다.

계산과 통신을 겹쳐 실행하는 것도 아직 향후 개선 항목이다. 발표는 현재 핵심 SpMV 반복이 통신과 계산을 순차 수행한다고 설명한다. 데이터를 기다리는 동안 장치 내부 계산을 먼저 하는 개선안을 현재 구현의 성과로 섞으면 안 된다. 마찬가지로 실행 가능한 해를 더 빨리 얻기 위해 최적성을 일부 양보하는 feasibility polishing도 향후 항목이다. ‘조건을 만족하는 해’와 ‘최적값에 충분히 가까운 해’는 같은 판정이 아니다.

기술 본문, cuOpt README·LICENSE·VERSION·튜토리얼 셀과 OR-Tools PDLP 정의 파일을 읽었다. GPU에서 솔버를 실행하거나 원시 벤치마크 데이터를 재분석하지 않았다. 원본 그림 5·6의 픽셀은 추가로 확인해 축·비교 기준을 대조했다. 원 도판의 재사용 권리와 원시 시간 자료 검토는 미완료이며, 눈금에서 읽은 근삿값을 정밀 측정값처럼 추가하지 않는다. 다음 검증에서는 문제별 입력, 정확한 구현 버전, 원시 시간과 실패 결과를 함께 확보해야 한다.

#11. 실제 변화와 다음 확인 질문

이 접근의 설명 가치는 큰 문제를 여러 장치에 배치하는 기준에 있다. 단순히 GPU를 늘렸다는 소식보다, 어떤 값이 다른 계산에 필요한지를 구조로 표현한다는 점을 배울 수 있다. 다만 이것이 독자의 배송·전력·자원 배분 문제에서도 이득을 준다는 뜻은 아니다. 먼저 대표 입력과 기존 방식의 전체 시간, 실행 가능한 해의 품질을 확보해야 한다.

다음 검토는 문제별 전체 실행시간, 분할 시간, GPU별 계산량, 정확한 솔버 버전과 중단 기준을 확인하는 일이다. 튜토리얼이 고정한 패키지 26.8.0과 읽은 README의 26.10.00은 서로 다르다. 코드가 공개돼 있다는 이유로 발표에 사용한 버전이 무엇인지 추정하지 않는다. 다른 연구팀의 독립 재현이나 같은 문제의 실패 결과도 새로운 검토 트리거다.

#12. 출처와 열람 범위