Paper Review

[논문 리뷰] AlpaServe: Statistical Multiplexing with Model Parallelism for Deep Learning Serving

슈넌 2025. 3. 2. 20:04

AlpaServe: Statistical Multiplexing with Model Parallelism for Deep Learning Serving

Abstract

model parallelism can be additionally used for the statistical multiplexing of multiple devices.
We explore the new trade-off space and present a novel serving system.

 

Background

  • Cloud serving system should satisfy the SLO on latency
  • Intra-operator parallelism
    • single operator is partitioned across multiple devices
    • communication overhead
    • reduce end2end latency
    • expand available memory capacity
  • Inter-operator parallelism
    • a.k.a. pipeline parallelism
    • different operator execution
    • communication overhead between pipeline pages
    • increase end2end latency
    • throughput is better
    • allow to exceed memory limitation of a single GPU

Motivation & Tradeoff Analysis

3.1 Case Study: A two-model Example

두 모델이 있을 때 Colocation이 있을 때와 없을 때 성능을 비교한다.

 

(a) simple placement (b) model parallelism(inter-op parallelism)

 

(a)에서 1.3x speedup. → better burst tolerance

(b)에서 High CV란, arrival time의 coefficient of varience가 3이란 뜻인데, arrival time이 possion보다 매우 변동이 크다는 뜻이다. (더 burst)하다는 뜻. 이때 model pipelining은 더욱 효과를 발휘한다.

(d)를 보면 model parallelism은 request가 burst할 때 100% 사용하지만 simple placement는 50을 넘기기 힘들다.

(c) 실험은 model1의 비율은 20%, model2의 비율은 80% 일 때이다. model2가 burst가 더 크므로 simple placement의 성능이 안 좋다.

3.2 When is Model Parallelism Beneficial

Device Memory

해당 실험은 5GB parameter를 가진 모델을 8개 GPU에서 8개 모델을 사용하였다. 분배는 replication과 model parallelism 두 가지 방법을 사용하였다.

(a) replication은 다른 GPU에 같은 모델이 들어있는 것, (b)는 각 operator들을 나눠서 갖고 있는 것이다.

 

Device memory크기를 변화시켜 결과를 확인했을 때, memory가 충분하면 replication도 성능이 좋다. fig3. 4x row에 보면 결과가 비슷함을 알 수 있다.

 

Request Arrival

 

req/s가 올라가면서 model parallelism의 성능이 안 좋아지는데 model들이 equally saturated 되면 model parallelsim의 이점이 사라지고 communication overhead만 늘어난다. 반면에 replication은 어차피 모델들이 골고루 쓰이기 때문에 utilization이 높아진다.

 

하지만 CV가 커지면(bursty가 커지면) model parallelism의 성능이 더 좋다.

 

Service Level Objectives (SLO)

SLO가 performance에 어떤 영향을 끼치는지 실험을 하였다. SLO가 지난 것은 drop 시켰다.

 

(a) SLO가 tight할 때, Model Parallelism을 하는 것이 attainment가 더 좋다. SLO가 커진다는 것은 waiting queue에 들어가는 것이 많아진다는 것이고, 이는 request 양이 많다는 것과 같아서 비슷한 경향을 보인다. 하지만 real case에서 SLO Scale의 경우 5 미만인 경우가 대부분이기에 model parallelism이 좋다.

 

summary: Model parallelism은 device memory is limited, request rate is low, request CV is high, or SLO is tight일 때 좋다.

 

3.3 Overhead of Model Parallelism

fig 7에서 a를 overhead라고 두었을 때, model parallelism의 stage당 layency는 아래 식으로 표현된다.

  • single model latency = L이다. (n=no. of stages)
  • Fig7. (b)에서 overhead=1 (no overhead)일 때는 항상 성능이 좋다. 하지만 SLO가 커지고 overhead가 커지면 replication보다 성능이 안 좋아진다. → 즉 overhead가 performance에 큰 영향을 끼친다.

 

Inter-op parallelism

  • overhead=communication overhead이다.
  • slowest stage가 bottleneck이 될 수 있다. = uneven partition overhead
  • 대부분의 overhead는 uneven partition overhead이다.

Intra-op parallelism

  • overhead=collective communication overhead
  • cannot overlapped.
  • communication overhead is much higher than inter-op parallelism

 

single input latency에서는 inter-op parallelism은 성능 이득이 없음. communication overhead 때문에 오히려 조금 느려짐.

 

throughput에서는 inter-op parallelism이 좋고, inter-op나 intra-op는 model과 input을 split해서 GPU 수가 변해도 memory는 그대로 사용하지만, replication은 복제하기 때문에 linear하게 늘어남.

 

3.4 Queueing Theory Analysis

앞에서 말한 내용을 수학적으로 증명하는 부분이다. 여기서 input은 Possion arrival process를 따른다.

Latency: D, sever=1 일 때 queue는 M/D/1을 따른다.

람다0는 request rate이고, Lq는 평균 request 수이다. W는 평균 latency이다.

 

이 부분을 가정하고 3.1의 A two-model Example 부터 보자. p는 두 모델의 비율이라고 하면 각 모델의 request rate와 average layency는 다음과 같이 표현된다.

두 independent한 모델의 queue에 대한 average latency는 다음과 같이 표현된다.

p^2이 나오는 이유: (chat-gpt가 알려줌)

그니까 결국, 저 대기 시간은 발생했을 때 latency고, 발생하냐 안 하냐도 들어가야 하기 때문에 pW1+(1-p)W2로 표현이 되는 것이다.

 

직관적으로 p=1/2일 때 제일 좋다. 다른 곳에 치중이 안 되고 골고루 분배받기 때문이다.

 

model parallelism에서는 latency=Ds이고, maximum stage latency=Dm일 때 다음과 같이 표현된다.

model-parallelism overhead가 없다고 생각하면, Ds=2Dm=D이고(2 stage니까) p=1/2일 때라고 생각하면

 

다음과 같이 표현된다. 이렇게 되면 model parallelism의 waiting time이 simple의 절반이 된다. 또한, p=1/2이 아닐 때, Wsimple은 증가하지만, Wpipeline은 그대로이다. 그렇기 때문에 Fig2. (c)에서 보였듯이, gap이 시간이 지날 수록 커지게 된다.

 

이제 overhead가 있는 case에 대해서 확인해보자.

  • Communication overhead factor: alpha
  • Uneven Partition overhead factor: beta

single device delay와 stage delay는 다음과 같이 표현될 수 있다.

 


여기서 아래 공식을 만족시키는 alpha와 beta의 최대 값을 구해보면,

total utilization: lamda * D의 함수로 표현이 가능하다.

utilization이 높아지면 model parallelism의 효과가 줄어든다. 따라서 overhead가 낮아져야 하고, utilization이 낮을 때(queueing이 잘 안 될 때)는, alpha 값을 줄여서 communication overhead를 줄여야 한다.

 

이것은 uniform Poisson distribution이기 때문에 non-uniform이나, burtsty한 상황에서는 model parallelism의 효과가 더 크게 나타날 수 있다.

Method

  • To reduce the overhead of model parallelism, minimizes the stage imbalance
  • Determine model-parallel placements according to the arrival pattern to maximize SLO attainments

 

AlpaServe는 centralized controller를 두고 각 group에 request를 dispatch한다. 각 그룹에는 다양한 모델의 복제된 파라미터가 있고, model parallelism을 적절히 사용하게 한다.

 

4.1 Automatic Parallelization for Inference

Alpa를 통해서 여러 Configuration에 대한 성능을 알아낸다.

  • Inter-op parallelism → DP를 사용하여 optimal
  • Intra-op parallelism → Integer Linear Programming (ILP)

Inter-op pass

  • optimize the overall pipeline latency(forward, backward, weight synchrnoization) → forward propagation만 refomulate해서 minimizing the maximal stage latency
  • layer k개를 s stage로 나눴을 때 maximum latency를 다음과 같이 표현할 수 있다.

latency(i, k)는 layer i부터 k까지의 stage latency이다.

모든 K에 대해서 latency를 profile하면 되므로 탐색 space가 좁다.

 

4.2 Placement Algorithm

각 Group이 어떻게 모델의 subset을 갖고 있을지 정해야 한다. “Placement”는 다음 세 가지를 의미한다. SLO 달성도를 높이기 위한 Placement를 찾는 것이 이번 절의 목표이다.

  • cluster group partition
  • model selection
  • parallel configuration

하지만 device와 model의 개수가 많아질수록 configuration space가 늘어나기 때문에 탐색은 어려운 문제이다. 또한, SLO 달성도는 간단한 analytical formula로 표현되기 어렵다.

 

일단 여기서는 history를 trace로 하여 arrival distribution을 예측하여 시뮬레이션하는 방법으로 실험하였다.

해당 논문은 two-level placement algorithm을 소개한다.

  • Simulator-Guided Greedy Model Selection
    • 어떤 모델을 group에 넣을지 정하는 알고리즘
  • Enumeration-Based Group Partition and Model Parallel Configuration Selection
    • 어떻게 모델을 나눌지 결정하고, 알고리즘 1에서 선택한 것에 대해 SLO를 평가하는 알고리즘

Algorithm 1 Simulator-Guided Greedy Model Selection

model parallel configuration은 고정하고 어디에 무슨 모델을 둘지만 결정한다.

여기서는 Beam search algorithm을 사용하여 best selection을 찾는다. model, group, parallelizes의 모든 가능한 수를 탐색한다. 탐색하여 SLO 달성도가 높은 k개를 beam selection에 넣고, selection에는 가장 높은 것을 넣는다. 그렇게 new selection이 선택되지 않을 때까지 계속 탐색을 진행한다.

  • M: number of models
  • G: number of groups
  • R: number of replicas
  • S: number of requests
  • B: beam size

Time complexity: O(MGRSB)

 

Algorithm 2 Enumeration-Based Group Partition and Model Parallel Configuration Selection

다양한 group partition과 model-parallel configuration 중에서 best one을 하나 뽑는 것이다. 이 알고리즘을 design하던 중 현상 하나가 있었는데, 작은 모델과 큰 모델을 같은 group에 두면 작은 모델이 큰 모델을 기다리느라 SLO를 만족하지 못할 때가 많았음. 따라서 model buckets을 만들고 비슷한 크기의 모델끼리 모아두었다.

  • 먼저 모델 사이즈(latency)에 따른 Bucket을 분리한다.
  • Bucket마다 루프를 돌면서 각 bucket을 어느 device에 할당할지 결정한다.
  • bucket 각각에 대해 할당된 device를 그룹화한다.
  • 각 그룹에서 가능한 parallel configuration을 찾음
  • 얻은 bucket, group, parallel config, workload를 입력으로 하여 algorithm 1을 beam search가 아닌 greedy_selection으로 진행
  • bucket에 대하여 모든 placement를 concat하고, best SLO 달성도를 얻은 것을 뽑음.

모든 choice를 다 탐색하는 것은 느리기 때문에 heuristic 방법을 사용하여 search space를 prune한다.

 

각 bucket마다 requests per second 요청량이 비슷해야 load balancing이 되므로 bucket configuration에서 request 수가 너무 많이 차이 나는 것들은 제외했다. 또한, 마지막 그룹을 제외한 모든 group이 같은 크기와 parallel configuration을 가진다고 가정하였다. 마지막 그룹은 device 수가 group size로 나눠 떨어지지 않을 수 있기 때문에 제외하였다.

 

4.3 Runtime Scheduling

  • 모든 요청은 centralized controller에게 가고, 각 그룹에 dispatch한다.
  • Controller는 가장 짧은 queue length를 가진 group에게 request를 dispatch한다.
  • 각 그룹은 FCFS로 queue를 처리하고, request가 SLO를 만족시키는지 확인하고 못한다면 reject한다.
  • others: 구현하지는 않았지만 고려하면 좋은 점
    • Batching: 이득이 있을 수 있으나 gain은 limited. 특히 큰 모델에 대해서는 이미 GPU를 fully saturate하니 성능 이득이 제한적임
    • Preemption: convey effects를 해결할 수 있는 좋은 방법임
    • Swapping: tight SLO를 만족시키기 위해서는 해당 방법은 좋은 approach는 아님
    • Fault tolerance: 한 모델이 single GPU로 할당되었는데, 막상 못하게 되면 group 전체가 마비됨. 고려가 필요함.

Implementation

Real system과 simulator를 통해 AlpaServe를 실험하였다.

실제 시스템은 기존에 존재하는 Alpa를 확장하여 설계하였고, Simulator는 continuous-time, discrete-event simulator를 사용하였다.

 

Evaluation

6.1 Experiments Setup

Cluster Testbed는 8개 노드에서 총 64개의 V100 GPU를 사용하였다. (각 노드당 8개 GPU)

Model은 Transformer 기반의 BERT와 GShard MoE를 사용하였다.

 

Metric

  • SLO attainment (major evaluation metric)
  • minimal number of devices the system needs
  • maximum average request rate
  • the maximum traffic burstiness the system can support
  • minimal SLO the system can handle

Simulator Fidelity를 보장하기 위해 Table 2를 통해서 fidelity를 확인하였다.

 

실제 환경과 비교하였을 때 상당히 비슷한 성능을 보이는 것을 확인할 수 있다. 시뮬레이터를 통해 모델 사이즈가 크고 오래 걸리는 모델들을 빠르게 실험할 수 있다.

 

6.2 End-to-end Results with Real Workloads

Workloads

ML inference trace가 공개되어 있는 것이 없기 대문에 2개의 production trace를 proxy로 사용하였다. MAF1(2019)와 MAF2(2021)는 Azure에서 2주 동안 발생한 trace를 모아서 재가공한 것이다.

 

MAF1은 steady & dense incoming request, MAF2는 Bursty

 

Setup

  • default SLO: 5 x inference latency (SLO Scale=5)
  • Scaling rate & CV to control the rate and burstiness

Baselines.

  • Selective Replication (SR)
    • AlpaServe without model parallelism (mimics existing serving systems)
  • Clockwork++
    • SOTA model serving system Clockwork improved version
    • original: Continuously swaps models with small models
    • ++ version은 공정한 평가를 위해 (큰 모델에서는 swap overhead가 크기 때문에) swapping overhead를 0으로 하고, SR algorithm을 사용하여 2개의 window boundary마다 replacement가 발생하도록 하였다. (자세한 것은 Clockwork를 이해할 필요가 있어서 일단 패스)

 

SLO attainment vs. cluster size.

  • Fig. 12의 첫 번째 row를 보면 device 수에 따른 SLO 달성도가 나온다.
  • Baseline들보다 AlpaServe가 SLO 달성도가 높았고, Model parallelism을 통해 99% SLO 달성을 위한 device 수가 현저히 줄었다. 심지어 swap overhead가 없는 Clockwork++에 대해서도 성능이 좋았는데, 이는 bursty traffic에 대해 model parallelism이 robust하기 때문이다.
  • 또한, replication만 하는 방법은 memory fraction을 발생시킬 수 있지만, model parallelism을 사용하면 flexible하게 모델을 배치할 수 있다.

SLO attainment vs. rate.

  • Fig. 12의 두 번째 row로 가면, request rate에 따른 SLO 달성도를 볼 수 있다.
  • 비교적 stable한 trace인 MAF1에 대해서는 높은 SLO 달성도를 보이지만 MAF2에서는 rate scale이 커지면 SLO 달성률이 떨어지는 것을 볼 수 있다.
  • replication based placement는 bursty traffic에 대비하기 위해 “hot” 모델에 대해 GPU에 배치를 해두는데, bursty traffic이 발생하지 않는 중간중간의 시간에서 idle한 부분이 생겨버린다. 하지만 AlpaServe는 더 적은 replica를 사용하기 때문에 이 부분에서 손해가 적다.

SLO attainment vs. CV.

  • Fig. 12의 세 번째 row는 CV에 따른 SLO 달성도 변화를 보여준다.
  • CV가 높을수록 bursty하다고 볼 수 있다.
  • AlpaServe의 Model Parallelism이 bursty case를 해결할 수 있다.

SLO attainment vs. SLO.

  • Fig. 12의 4번째 row는 SLO에 따른 SLO 달성도를 보여준다.
  • SLO가 낮을 때(tight 할 때)는 intra-op parallelism을 사용하여 latency가 긴 모델을 빠르게 처리할 수 있도록 하고, SLO가 클 때는 inter-op parallelism을 사용하게 하여 throughput을 높였다.

 

6.3 Serving Very Large Models

common practice에서는 Large Model을 돌리기 위해 parallelism strategy를 설정하고 dedicated GPU에 할당을 했어야 했다. AlpaServe는 optimal GPU allocation & model placement를 찾고, statistical multiplexing을 통해 다양한 workload에 대한 robustness를 얻는다. 비교군으로 inter-op and intra-op parallelism의 모든 조합에 대해서 실험을 진행하였다.

 

Traffic은 Gamma Process로 average rate 8 request/s and CV of 4로 실험하였다. CV와 SLO 값을 변경하면서 실험을 진행하였다.

 

dedicated GPU를 사용하는 것보다 group으로 나누고 적절히 model을 배치하고 inter-op & intra-op parallelism을 설정하여 balance를 맞추는 것이 성능이 좋다는 것을 알 수 있다.

6.4 Robustness to Changing Traffic Patterns

지금까지 실험은 사전에 미리 trace를 모두 알고 있는 상태로 실험을 했었다. 하지만 실제 환경에서는 과거를 통해 미래를 예측한다 할지라도 어떠한 변화가 있을지 모르기 때문에 부정확한 예측이 발생한다. 그렇기에 traffic pattern이 바뀌었을 때 AlpaServe의 성능을 측정하였다.

 

두 가지 trace로 나눴는데, 한 개는 MAF1에서 1시간짜리 trace와 실제 arrival process를 사용한 방법에 대해서 AlpaServe와 SR에 대해서 실험하였고, Clockwork++은 실제 arrival process를 online에서 실행하였다.

 

 

실험 결과에서 알 수 있듯이, 4개의 변인에 대해서 모두 SLO 달성률이 Clockwork++와 SR 보다 높았다. 특히 CV Scale이 커질수록 SR의 Robustness가 떨어지는 것을 확인할 수 있었다.

 

이를 통해, highly-dynamic traffic pattern에서는 model parallelism을 활용한 statistical multiplexing이 다른 replication이나 replacement algorithm보다 성능이 좋다는 것을 알 수 있다.

 

6.5 Benefits of Dynamic Batching

Batching을 하는 것은 GPU utilization을 높이고 throughput을 향상 시키지만, 큰 모델에 대해서는 성능 이득이 없다. 이유는 크게 두 가지로 (1) 이미 큰 모델은 GPU를 saturate하고, (2) batching을 할 경우 latency가 길어지므로 SLO가 tight할 때는 사용이 어렵다. 본 논문에서는 그렇기 때문에 batching을 하지 않도록 설정을 하였고, 대신에 batching이 AlpaServe와 orthogonal한 것을 증명하였다.

 

Device group이 idle한 상태라면 request가 왔을 때 바로 처리하고, 그렇지 않으면 model 마다 request queue를 두고, device가 idle한 상태가 되었을 때 queue에 있는 것을 batching하였다. batching 성능 확인을 위해 작은 모델(S1)을 사용하였고, 4 requests/s의 average rate와 4 CV를 사용하였다.

 

 

  • Fig. 15의 왼쪽은 maximum batch size를 바꿔가며 실험을 진행한 것이다.
    • SLO가 tight한 경우에는 어차피 batching을 못하기 때문에 차이가 발생하지 않는다.
    • SLO가 큰 경우에도 결국 input sequence length가 커지면 GPU가 saturate되기 때문에 batching이 2 이상인 경우에 대해서 성능이 동일하다.
  • Fig. 15의 오른쪽은 Clockwork++에 batching을 적용했을 때와 비교한 것이다.
    • batching을 적용하지 않았을 때도 AlpaServe가 충분히 좋은 성능을 보여준다.
    • batching을 적용했을 때 Clockwork++보다는 absolute improvement가 줄어드는데, 그 이유는 model parallelism에서 다양한 batch size로 인해서 stage imbalance가 발생하기 때문이다. 그럼에도 Clockwork++보다 준수한 성능을 보인다.

6.6 Ablation Study

4.1과 4.2에서 소개한 auto-parallelization과 placement algorithm의 효과를 입증하기 위해 ablation study를 진행하였다. 기존 inter-op parallelism에서는 각 pipeline stage마다 동일한 수의 layer를 할당하였는데, 이는 workload imbalance를 야기할 수 있다. 하지만 auto-parallelization은 computational graph level에서 최대한 balance가 맞도록 모델을 나눈다.

 

연한 색이 layer수를 균등하게 나눈 것이고 진한 색이 automatic algorithm으로 나눈 것이다. 실험 결과를 통해 inter-op parallelism overhead이 줄어든 것을 확인할 수 있다.

 

placement algorithm에 대해서 round robin과 greedy placement만 했을 때, group partitioning까지 적용했을 때 나눠서 실험을 진행하였다.

 

Round robin의 경우 어느 경우에서도 99%에 도달하지 못하였고, group partition이 없으면 greedy placement의 성능이 크게 떨어지는 것을 확인할 수 있었다.

Conclusion

해당 논문은 AlpaServe라는 multi-model serving system을 제안하였고, model parallelism을 접목하여 시스템을 구성하였다. AlpaServe는 model parallelism이 다양한 scenario에 대해서 유용하다는 것을 입증하였다.