DuaLip-GPU Technical Report

이 논문은 대규모 선형 계획법 문제를 해결하기 위해 기존 CPU 기반 DuaLip 솔버의 한계를 극복하고, 커스텀 GPU 실행 기법과 재설계된 아키텍처를 통해 최소 10 배의 속도 향상을 달성한 새로운 솔버를 제안합니다.

핵심

듀얼립-GPU: 거대한 의사결정 문제를 해결하는 '초고속 레이서'

이 논문은 링크드인 (LinkedIn) 의 엔지니어들이 개발한 **'듀얼립-GPU (DuaLip-GPU)'**라는 새로운 소프트웨어에 대한 기술 보고서입니다. 이걸 쉽게 설명해 드릴게요.

1. 문제: 거대한 퍼즐을 CPU 로 맞추느라 지쳤습니다

링크드인 같은 거대 기업에서는 매일 수백만 명의 사용자와 수천 개의 광고나 콘텐츠를 어떻게 배분할지 결정해야 합니다. 예를 들어, "사용자 A 에게 광고 X 를 보여줄까, 광고 Y 를 보여줄까?"를 결정하는 건 단순한 선택이 아니라, 수백만 개의 조건을 동시에 만족시켜야 하는 거대한 **수학적 퍼즐 (선형 프로그래밍)**입니다.

과거에 사용하던 시스템 (이전 버전의 듀얼립) 은 이 퍼즐을 **CPU(일반 컴퓨터 두뇌)**로 풀었습니다. 하지만 문제는 두 가지였습니다:

1. 속도: 퍼즐 조각이 너무 많아서 CPU 가 땀을 흘리며 천천히 풀었습니다.
2. 유연성: 퍼즐 규칙이 조금만 바뀌어도 (예: 새로운 광고 조건 추가), 시스템을 통째로 고쳐야 해서 개발자들이 고생했습니다.

2. 해결책: GPU(그래픽 카드) 를 빌려와서 '레이싱'을 시키다

연구팀은 이 문제를 해결하기 위해 **GPU(게임이나 영상 처리에 쓰이는 강력한 병렬 처리 칩)**를 활용하기로 했습니다. GPU 는 동시에 수천 개의 계산을 할 수 있어, 이 거대한 퍼즐을 10 배 이상 빠르게 풀 수 있게 되었습니다.

하지만 단순히 GPU 를 끼우는 것만으로는 부족했습니다. GPU 가 퍼즐을 잘 풀 수 있도록 **새로운 방식 (아키텍처)**을 설계해야 했습니다.

3. 핵심 아이디어 3 가지 (비유로 설명)

① 레고 블록처럼 조립 가능한 설계 (프로그래밍 모델)

• 과거: 마치 맞춤형 맞춤 옷을 만드는 것처럼, 새로운 규칙이 생기면 옷을 다 뜯어고쳐야 했습니다.
• 현재: 레고 블록처럼 만들었습니다.
  • 목표 (Objective): 무엇을 달성할지 정하는 블록.
  • 제약 (Projection): "이건 안 돼"라는 규칙을 지키는 블록.
  • 최적화 (Optimizer): 블록을 어떻게 움직여야 최선인지 계산하는 블록.
  • 이제 새로운 규칙이 생기면, 기존 블록을 그대로 두고 새로운 레고 블록 하나만 끼우면 됩니다. 코드를 통째로 고칠 필요가 없습니다.

② 도로 정비를 통한 속도 향상 (알고리즘 개선)

수학적으로 퍼즐을 풀 때, 길이가 제각각인 도로 (데이터) 를 그대로 달리면 차가 흔들립니다. 연구팀은 두 가지 도로 정비를 했습니다.

• 길이를 맞추기 (Preconditioning): 모든 도로의 너비를 일정하게 맞춰서, 차가 한 번에 빠르게 달릴 수 있게 했습니다.
• 가속과 감속 조절 (Regularization): 처음엔 빠르게 달렸다가 (큰 규칙 적용), 목표에 가까워지면 천천히 정밀하게 조정하는 (규칙을 줄이는) 전략을 썼습니다. 이렇게 하면 처음엔 빠르게, 나중엔 정확하게 도착할 수 있습니다.

③ GPU 군단의 협력 (시스템 최적화)

수천 개의 GPU 가 함께 일할 때, 서로 대화하는 시간이 길면 속도가 느려집니다.

• 과거: 모든 GPU 가 서로의 모든 계산 결과를 주고받느라 시간이 걸렸습니다.
• 현재: 각 GPU 가 자신의 일 (사용자 그룹별 계산) 을 끝내고, 결과만 간단히 합쳐서 다시 나누어 줍니다. 마치 우편배달부들이 각자 구역을 돌다가, 최종 주소지 (중앙 서버) 에만 편지 한 통씩만 모아 보내는 것과 같습니다. 이렇게 해서 통신 시간을 극도로 줄였습니다.

4. 결과: 압도적인 속도 차이

실험 결과, 이 새로운 시스템은 기존 CPU 시스템보다 최소 10 배, 최대 10 배 이상 빠른 속도로 문제를 해결했습니다.

• 비유: 과거에는 말로 100km 를 가는 데 하루가 걸렸다면, 이제는 초고속 열차를 타고 1 시간도 안 걸려 도착한 것입니다.
• 또한, GPU 를 여러 대 추가할수록 속도가 비례해서 빨라져서, 문제가 커져도 걱정하지 않아도 됩니다.

5. 결론: 왜 이것이 중요한가요?

이 기술은 단순히 "계산이 빨라졌다"는 것을 넘어, 더 복잡하고 새로운 비즈니스 규칙을 실시간으로 적용할 수 있게 해줍니다.

• 링크드인에서는 이 시스템을 통해 사용자에게 더 적합한 콘텐츠를 보여주고, 광고주에게는 더 효율적인 예산 분배를 할 수 있게 되었습니다.
• 앞으로는 이 기술이 광고 배분뿐만 아니라, 물류, 교통, 에너지 관리 등 거대한 자원을 효율적으로 나누는 모든 분야에 적용될 수 있을 것입니다.

한 줄 요약:

"기존의 느리고 딱딱한 계산 방식을, GPU 의 강력한 힘을 빌려 레고처럼 유연하게 조립하고, 군대처럼 협력하게 만든 초고속 의사결정 시스템을 개발했습니다."

기술 요약

1. 문제 정의 (Problem Setting)

• 배경: 산업 현장 (LinkedIn 등) 에서 이메일/알림 할당, 콘텐츠 배정, 시장 형성 등 반복적인 주기로 대규모 LP 문제를 해결해야 합니다.
• 기존 시스템의 한계:
  • LinkedIn 의 오픈소스 프로젝트인 DuaLip (Scala/Spark 기반) 은 Ridge-regularized dual ascent 알고리즘을 사용했으나, CPU 중심의 런타임과 고정된 스키마 (Template) 에 강하게 결합되어 있었습니다.
  • 새로운 문제 형식 (Formulation) 을 표현하기 어렵고, 현대적인 가속기 (GPU) 를 효과적으로 활용하지 못했습니다.
  • 대규모 매칭 (Matching) 문제에서 병목 현상이 발생하여 확장성이 제한되었습니다.
• 목표: 재사용성이 높고 GPU 가속화에 최적화된 유연한 솔버 아키텍처를 구축하여, 극대규모 LP 문제를 빠르게 해결하고 새로운 제약 조건을 쉽게 추가할 수 있도록 하는 것입니다.

2. 방법론 (Methodology)

보고서는 세 가지 핵심 축을 통해 시스템을 재설계했습니다.

2.1. 연산자 중심 프로그래밍 모델 (Operator-Centric Programming Model)

기존의 "솔버 호출" 방식에서 벗어나, 문제 로직을 세 가지 기본 연산자 (Primitive) 로 분리하여 구성했습니다.

• ObjectiveFunction: 데이터와 쌍대 기울기 (Dual Gradient) 계산을 캡슐화합니다.
• ProjectionMap: 단순 제약 조건 (Simple Constraints, 예: 심플렉스, 박스 제약) 에 대한 블록별 투영 (Projection) 을 담당합니다.
• Maximizer: 이중 상승 (Dual Ascent) 을 수행하는 최적화 알고리즘입니다.
• 장점: 이 구조는 새로운 LP 형식이나 제약 조건 가족 (Constraint Families) 을 추가할 때 솔버 루프를 수정하지 않고 로컬하게만 코드를 구성하면 되므로 확장성이 매우 높습니다.

2.2. 알고리즘적 개선 (Algorithmic Enhancements)

Ridge-regularized dual ascent 알고리즘의 수렴 속도와 안정성을 높이기 위해 다음 세 가지 기법을 도입했습니다.

1. Jacobi 스타일 행 정규화 (Row Normalization): 이중 문제 (Dual Problem) 의 조건수 (Conditioning) 를 개선하기 위해 제약 행렬 $A$의 행을 정규화합니다. 이는 Hessian 행렬의 고유값을 균일하게 만들어 기울기 하강법의 수렴을 가속화합니다.
2. 정규화 파라미터 $\gamma$의 연속적 감쇠 (Continuation Scheme): 초기에는 큰 $\gamma$값으로 빠른 수렴을 유도하고, 최적화 진행에 따라 $\gamma$를 서서히 감소시켜 원래 LP 해에 가까운 정밀한 해를 찾도록 합니다.
3. 원시 변수 스케일링 (Primal Scaling): 원시 변수 $x$의 크기 차이가 크면 Ridge 정규화 항이 특정 좌표에 과도하게 영향을 미칠 수 있으므로, 좌표별 스케일링 인자를 도입하여 정규화 항의 균형을 맞춥니다.

2.3. GPU 실행 및 희소 레이아웃 (GPU Execution & Sparse Layout)

GPU 에서의 병렬성을 극대화하기 위한 시스템 수준의 최적화를 수행했습니다.

• 희소 행렬 레이아웃: 매칭 문제의 구조 (블록 대각 구조) 를 고려하여 CSC (Compressed Sparse Column) 형식을 사용했습니다. 이는 메모리 국소성을 높이고 불필요한 포인터 오버헤드를 제거합니다.
• 배치 투영 (Batched Projections): GPU 커널 실행 오버헤드를 줄이기 위해, 다양한 크기의 투영 연산을 로그 간격으로 버킷화하여 배치 (Batch) 로 처리합니다.
• 분산 통신 패턴: 각 GPU 가 로컬 열 (Column) 단위로 계산을 수행하고, 이중 변수 ($\lambda$) 만을 동기화합니다. 통신 부하가 희소성이나 데이터 크기가 아닌 이중 변수의 차원에만 의존하도록 설계되어 확장성이 뛰어납니다.

3. 주요 기여 (Key Contributions)

1. 유연한 라이브러리 인터페이스: 스키마에 종속되던 기존 방식을 대체하여, 다양한 LP 형식과 제약 조건을 쉽게 추가할 수 있는 연산자 중심의 모델을 제시했습니다.
2. 강화된 알고리즘: Ridge-regularized dual ascent에 행 정규화, 연속적 감쇠, 원시 스케일링을 결합하여 대규모 문제에서의 수렴성과 안정성을 크게 향상시켰습니다.
3. GPU 네이티브 실행: PyTorch 기반의 희소 연산과 분산 통신 패턴을 활용하여, 기존 CPU 기반 시스템 대비 10 배 이상의 속도 향상을 달성하고 다중 GPU 환경에서 선형에 가까운 확장성을 입증했습니다.

4. 실험 결과 (Results)

• 수치적 정확도: PyTorch 구현체가 기존 Scala/Spark 솔버와 거의 완벽하게 일치하는 수치적 결과를 보였습니다 (상대 오차 1% 미만).
• 성능 향상:
  • 중간 규모 문제 (25M 소스) 에서 단일 GPU 만으로도 Scala 대비 약 9 배의 속도 향상을 보였습니다.
  • 대규모 문제 (100M 소스) 에서 4 개 GPU 를 사용할 경우, Scala 대비 약 10 배 이상의 속도 향상을 달성했습니다.
• 확장성 (Scaling): GPU 수를 늘릴수록 해결 시간이 선형적으로 감소하며, 4 개 GPU 환경에서 이상적인 선형 확장 (4 배) 에 근접하는 3.86 배의 속도 향상을 기록했습니다.
• 알고리즘 개선 효과: 행 정규화와 $\gamma$ 감쇠 전략을 적용했을 때, 특히 초기 단계의 수렴 속도가 크게 개선됨을 확인했습니다.

5. 의의 및 결론 (Significance)

이 연구는 산업 현장의 극대규모 선형 계획법 문제를 해결하는 패러다임을 전환했습니다.

• 하드웨어 효율성: CPU 중심의 레거시 시스템을 현대적인 GPU 클러스터로 전환하여, 막대한 계산 자원을 효율적으로 활용할 수 있게 했습니다.
• 유연성과 재사용성: "Call a solver" 방식이 아닌 구성 가능한 연산자 모델을 통해, 새로운 비즈니스 로직이나 제약 조건이 추가되더라도 솔버 코드를 대규모로 수정할 필요 없이 빠르게 대응할 수 있습니다.
• 실용성: LinkedIn 과 같은 대규모 플랫폼에서 매일/매주 발생하는 반복적인 최적화 작업의 처리 시간을 획기적으로 단축하여, 실시간 의사결정 및 자원 할당의 효율성을 극대화했습니다.

결론적으로, DuaLip-GPU는 Ridge-regularized dual ascent 알고리즘을 현대적인 GPU 아키텍처에 맞게 재해석하고 최적화하여, 극대규모 매칭 및 할당 문제를 위한 강력하고 유연한 솔루션을 제공합니다.