Sarathi-Serve_LLM

Abstarct

| 사라티-Serve의 기여와 LLM 추론의 효율성을 높이는 방법을 간략하게 설명

https://arxiv.org/abs/2403.02310

Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve

 

 

이 논문의 초록은 LLM (대형 언어 모델) 서빙 요청이 두 가지 주요 단계를 거친다는 것을 설명합니다. 첫 번째 단계는 “프리필”, 사용자의 입력 프롬프트를 통해 첫 번째 출력 토큰을 생성합니다. 두 번째 단계는 “디코드”로, 나머지 출력 토큰을 하나씩 얻는 ge입니다.

• 프리필 단계: 이 단계는 높은 대기 시간을 가지지만, 입력 프롬프트의 실시간 처리를 통해 GPU 컴퓨팅을 최대한 활용합니다. 이는 많은 요청을 동시에 처리할 수 있게 되었습니다.
• 디코드 단계: 이 단계는 낮은 대기 시간을 가지지만, 요청당 단일 토큰만 처리하기 때문에 컴퓨팅 활용도가 낮습니다. 이로 인해 여러 요청을 배치하는 것이 매우 효과적입니다.
• 배치 처리의 도전: 여러 요청을 배치하고 디코딩 단계가 서로 얽히게 되어 높은 처리량과 낮은 대기 시간을 달성하기가 어렵습니다.
• 사라티-서브 소개: 이 논문에서는 이러한 처리량-대기 시간의 균형 문제를 해결하기 위해 사라티-Serve라는 효율적인 LLM 추론을 소개합니다. 사라티-Serve는 거의 동일한 크기의 청크로 요청을 “Chunked-Prefill”을 도입하고, 디코딩 중인 중간에 대한 요청을 하지 않고 새로운 요청을 배치할 수 있는 “무중단 스케줄링”을 구현합니다.
• 효율성 향상: 이러한 기술력 향상**: 이러한 기술 대기 시간 동안 다양한 조건과 조건을 갖춘 하드웨어에서 추론 성능을 발휘합니다. 미스트랄-7B de는 단일 A100 GPU에서 2.6배, Yi-34B 모델은 두 개의 A100 GPU에서 최대 3.7배 더 높은 서빙 시스템을 구현합니다.  또한, 팔콘-180B amle의 파이프라인 병렬성을 바꿨을 때 최대 5.6배의 시간을 들일 수 있습니다.

 

• 사라티-서브의 청크 프리필에 대한 이해

청크 프리필은 대규모 언어 모델 (LLM) 의 추론 프로세스를 최적화하기 위해 Sarathi-Serve에 도입된 주요 기술입니다.

- 정의 : 청크 프리필에는 프리필 요청을 더 작고 동일한 크기의 청크로 분할하는 작업이 포함됩니다. Sarathi-Serve는 전체 입력 프롬프트를 한 번에 처리하는 대신 여러 반복에 걸쳐 프리필 단계를 계산하며, 각 반복은 프롬프트 토큰의 하위 집합을 처리합니다 .

- 목적 : 청크 프리필의 주요 목표는 지연 시간을 최소화하면서 처리량을 향상시키는 것입니다. Sarathi-Serve는 대규모 프리필 요청을 세분화하여 GPU 리소스를 더 잘 활용할 수 있습니다. GPU 리소스는 한 번에 하나의 토큰만 처리되는 디코드 단계에서 활용도가 낮은 경우가 많습니다 .

- 메커니즘 : 청크 프리필을 계산하는 동안 각 청크는 모든 이전 청크의 키-값 (KV) 캐시에 액세스합니다. 즉, 계산 비용은 변하지 않지만 GPU에서 메모리 읽기가 증가하여 약간의 오버헤드가 발생할 수 있습니다. 하지만 이 기법은 지연 시간에 미치는 전반적인 영향을 최소화하도록 설계되었습니다.

- 이점 
 - 더 높은 처리량 : 청크 프리필은 진행 중인 디코딩을 일시 중지하지 않고도 여러 요청을 동시에 처리할 수 있으므로 높은 처리량 수준을 유지하는 데 도움이 됩니다 .
 - 지연 시간 영향 감소 : 이 방법을 사용하면 요청을 보다 균형 있게 처리할 수 있으므로 큰 입력 프롬프트를 처리할 때에도 지연 시간을 낮게 유지할 수 있습니다 .
 - 확장성 : 이 방법은 시스템에 부담을 주지 않으면서 효율적으로 처리할 수 있으므로 입력 프롬프트가 상당히 긴 시나리오에서 특히 유용합니다 .

요약하면 Sarathi-Serve의 청크 프리필은 LLM 추론의 복잡성을 관리하기 위한 전략적 접근 방식을 나타내며, 이를 통해 다양한 배포 시나리오에서 리소스 활용도를 높이고 성능을 개선할 수 있습니다.

• LLM 추론의 지속적인 스케줄링으로 인한 문제

대규모 언어 모델 (LLM) 추론에서의 지속적인 스케줄링은 성능 및 효율성에 영향을 미치는 몇 가지 중요한 문제로 이어질 수 있습니다.

- 파이프라인 지연: 지속적인 스케줄링은 특히 파이프라인 병렬 처리 (PP) 배포에서 파이프라인 지연이나 버블을 초래할 수 있습니다. 이러한 지연은 LLM 추론의 고유한 특성으로 인해 처리가 지연될 때 발생하며, 이로 인해 파이프라인의 여러 단계에서 데이터 및 처리의 흐름이 중단될 수 있습니다 .

- 비효율적인 리소스 활용 : 연속 스케줄링을 사용할 경우 시스템이 사용 가능한 GPU 리소스를 완전히 활용하지 못할 수 있습니다. 이러한 비효율성은 스케줄링이 다양한 길이의 프리필 및 디코드 반복을 효과적으로 관리하지 못해 GPU 사이클이 낭비되고 전체 처리량이 감소하기 때문에 발생합니다 .

- 지연 시간 가변성 : 연속 스케줄링은 특히 입력 길이가 다른 요청을 처리할 때 지연 시간에 변동이 발생할 수 있습니다. 프리필 반복과 디코드 반복을 인터리빙하면 특정 요청의 대기 시간이 예측할 수 없으며, 이는 지연 시간이 짧은 응답을 일관되게 필요로 하는 애플리케이션에 해로울 수 있습니다 .

- 처리 불균형 : 스케줄링으로 인해 프리필 반복과 디코드 반복 간의 불균형이 발생할 수 있습니다. 이러한 불균형은 파이프라인 버블 및 스톨 문제를 악화시켜 추론 시스템의 성능을 더욱 떨어뜨릴 수 있습니다 .

- 복잡성 증가 : 지속적인 스케줄링을 관리하면 스케줄링 프레임워크가 복잡해져 앞서 언급한 문제를 완화할 수 있는 최적화를 구현하기가 더 어려워질 수 있습니다. 이러한 복잡성은 다양한 워크로드와 요청 패턴에 효과적으로 적응하는 데 방해가 될 수 있습니다 .

요약하면 LLM 추론의 지속적인 스케줄링은 파이프라인 지연, 비효율적인 리소스 활용, 지연 시간 변동성, 처리 불균형 및 복잡성 증가로 이어질 수 있으며, 이 모든 것이 추론 시스템의 전체 성능에 부정적인 영향을 미칩니다.

 

---

그림1 ❘ LLM 추론의 컴퓨팅 시간 분포에 관한 중요한 통찰력을 효과적으로 전달하며, 성능 개선을 위해 선형 연산자의 우선 순위를 지정하는 최적화 전략의 필요성을 강조

 

그림 1(a): vLLM 시스템에서 Generation Stall (생성 중단)

• 두 개의 A100 GPU를 사용하여 Yi-34B 모델로 128개의 요청을 처리하는 상황을 보여줍니다.
• Generation stall은 디코드 단계가 지연되어 생성이 몇 초간 중단되는 상황을 나타냅니다.

그림 1(b): 높은 Tail Latency (최상위 지연)

• 부하가 증가할수록 지연이 큰 폭으로 증가하는 양상을 보여줍니다.
• Sarathi-Serve는 처리량을 증가시키는 동시에 Generation Stall을 제거하여 tail latency를 줄이는 성능을 보여줍니다.

• 계산 시간 분석: 총 계산 시간을 선형 연산, 주의 메커니즘 및 기타 프로세스와 같은 여러 구성 요소로 나누는 방법을 보여줍니다. 선형 연산자가 프리필 단계와 디코드 단계 모두에서 런타임 비용의 대부분을 차지한다는 점을 강조하여 LLM 추론 성능을 최적화하는 데 선형 연산자가 갖는 중요성을 강조합니다.
• 선형 연산자의 기여도: 시퀀스 길이가 늘어나도 선형 연산자가 전체 런타임에서 계속해서 80% 이상을 차지하고 있음을 보여줍니다. 이 발견은 전반적인 추론 효율성을 높이기 위해 선형 연산에 최적화 노력을 집중하는 것이 중요하다는 것을 보여줍니다.
• 주의 비용 증가: 주의 메커니즘과 관련된 비용은 시퀀스 길이에 따라 4등분하여 증가하지만 계산 시간 측면에서는 선형 연산자가 여전히 지배적인 요소라는 점도 주목할 만합니다. 이러한 관찰은 주의력 비용의 영향을 줄이기 위한 전략만으로는 선형 작업자 비용을 해결하지 않고는 충분하지 않을 수 있음을 시사합니다.
• 디코딩 중 낮은 컴퓨팅 사용률: 이 수치는 디코드 단계에서 관찰된 낮은 컴퓨팅 사용률도 반영할 수 있는데, 이는 디코드 반복이 지연 시간이 짧지만 GPU의 처리 용량을 완전히 활용하지는 못한다는 것을 나타냅니다. 이러한 비효율성은 LLM 추론 시스템의 개선이 필요한 중요한 영역입니다.

 

---

Introduction

| LLM 추론의 최적화 필요성과 사라티-Serve의 기여를 위해, LLM 서비스 성능 극복 시스템의 접근 새로운 환경을 제시

 

 

대규모 언어 모델(LLMs)은 자연어 처리, 질의응답, 코드 생성 등 다양한 작업에서 뛰어난 성능을 보여주며, 챗봇, 검색, 코드 도우미 등 여러 응용 분야에서 사용이 급증하고 있습니다. 이러한 대규모 모델의 추론에는 GPU 계산이 많이 필요하며, 이들의 사용 증가로 인해 LLM 추론은 현재 GPU 작업의 중요한 부분을 차지하고 있습니다. 따라서 LLM 추론을 최적화하는 것은 최근 시스템 개발의 핵심 목표 중 하나로 떠올랐습니다.

 

LLM 추론에서 처리량(throughput)과 지연(latency)을 모두 최적화하는 것이 중요합니다. 처리량은 서비스 비용을 절감하고, 지연은 애플리케이션의 요구 사항을 충족하기 위해 필수적입니다. 하지만 본 논문에서는 현재의 LLM 서비스 시스템이 처리량과 지연 간의 트레이드오프 문제를 겪고 있음을 보여줍니다. 특히, 배치(batch) 처리를 통해 LLM 추론 처리량을 크게 증가시킬 수 있지만, 기존 시스템의 배치 처리 방식은 처리량이나 지연 중 하나를 포기해야 하는 결과를 초래합니다. 예를 들어, 그림 1(b)는 최신 LLM 서비스 시스템(vLLM)에서 부하 증가가 지연(latency)의 상위 1% 값을 얼마나 크게 증가시키는지 보여줍니다.

LLM 추론 요청은 두 단계로 진행됩니다.

1. Prefill 단계: 사용자의 입력 프롬프트를 처리하여 첫 번째 출력 토큰을 생성합니다.
2. Decode 단계: 이전 단계에서 생성된 토큰을 기반으로 새로운 토큰을 한 번에 하나씩 생성합니다. 이 단계는 특별한 종료 토큰이 생성될 때까지 반복됩니다.

Prefill 단계는 계산 집약적(compute-bound)이며, 입력 프롬프트의 모든 토큰을 병렬로 처리합니다. 반면, Decode 단계는 한 번에 하나의 토큰만 처리하므로 메모리 집약적(memory-bound)입니다. 따라서 Decode 단계는 배치 크기가 클수록 GPU를 더 효율적으로 사용할 수 있지만, Prefill 단계는 배치 크기 증가로 인한 성능 향상이 제한적입니다.

현재의 LLM 추론 스케줄러는 크게 두 가지로 분류할 수 있습니다:

• Prefill 우선형 스케줄링: Prefill 단계를 먼저 처리하여 이후 Decode 배치 크기를 키우는 방식.
• Decode 우선형 스케줄링: Decode 단계를 먼저 처리하여 지연을 최소화하는 방식.

본 논문에서는 이러한 두 전략이 각각의 근본적인 단점을 가지고 있어 온라인 추론 서비스에 적합하지 않음을 주장합니다(그림 2 참고).

 

• 청크 프리필이 프리필 효율성을 향상시키는 방법

• 프리필 요청 분할 :  청크 프리필은 프리필 요청을 더 작고 동일한 크기의 청크로 나눕니다. 이를 통해 모델은 입력 프롬프트를 한 번에 모두 처리하지 않고 여러 번 반복하여 처리할 수 있습니다. 이렇게 하면 프리필 단계에서 GPU 리소스를 더 잘 활용할 수 있습니다. 프리필 단계는 일반적으로 메모리 사용량이 많고 작은 세그먼트에서 처리할 경우 GPU 컴퓨팅을 포화시킬 수 있습니다.
• 지연 시간 영향 감소 : 프리필 토큰을 더 작은 청크로 처리하여 진행 중인 디코드 작업의 지연 시간에 미치는 영향을 최소화합니다. 이는 진행 중인 디코딩을 일시 중지하지 않고도 새 요청을 동시에 처리할 수 있어 출력 토큰의 흐름을 일정하게 유지할 수 있기 때문에 특히 유용합니다.
• 처리량 향상 : 청킹 메커니즘을 사용하면 시스템에서 더 큰 배치 크기를 처리할 수 있어 처리량을 높일 수 있습니다 .이는 새 요청을 실행 중인 일괄 처리로 지연 없이 스케줄링하면 로드 밸런싱을 돕고 처리 파이프라인의 유휴 시간을 줄일 수 있기 때문입니다.
• 메모리 효율성 : 청크 프리필은 또한 각 청크에 대한 주의 작업이 KV (키-값) 캐시에 효율적으로 액세스하도록 하여 메모리 사용을 최적화합니다. KV 캐시를 여러 번 로드하면 약간의 오버헤드가 발생하지만 전체 계산 비용은 변하지 않아 프로세스의 효율성이 향상됩니다.
• 입력 크기에 대한 적응성 : 실제 입력 프롬프트에는 수천 개의 토큰이 포함될 수 있는 경우가 많기 때문에 청크 프리필을 사용하면 긴 프롬프트를 관리 가능한 크기로 나누어 효과적으로 처리할 수 있습니다. 이를 통해 시스템에 부담을 주지 않으면서 GPU 컴퓨팅을 효과적으로 활용할 수 있으므로 입력이 많아도 성능이 유지됩니다.

 

청크 프리필은 요청을 더 작은 청크로 분할하여 지연 시간에 미치는 영향을 줄이고, 처리량을 개선하고, 메모리 사용을 최적화하고, 다양한 입력 크기에 맞게 조정함으로써 프리필 효율성을 향상시킵니다.이러한 개선 사항은 종합적으로 LLM 추론 프로세스의 효율성을 높이는 데 기여합니다.

 

---

그림2

 

그림 2: 현재 LLM 서비스 시스템의 Throughput-Latency Tradeoff

• 각 스케줄링 정책이 처리량(throughput)과 지연(latency)에 미치는 영향을 도식화했습니다.
• Prefill 우선 시스템 (vLLM, Orca): 처리량은 높지만, TBT(time-between-tokens, 토큰 간 시간)가 길어져 지연이 증가합니다.
• Decode 우선 시스템 (FasterTransformer): 지연은 적지만 처리량이 낮습니다.
• Sarathi-Serve: Stall-free batching을 통해 높은 처리량과 낮은 지연을 동시에 달성.

---

 

2. Background

이 섹션에서는 일반적인 LLM 모델 아키텍처와 이들의 자가회귀 추론 프로세스(autoregressive inference process)를 설명합니다. 또한 스케줄링 정책과 주요 성능 지표에 대한 개요를 제공합니다.

 

 

2.1 Transformer 아키텍처 번역

 

대규모 언어 모델(LLM), 예: GPT-3, LLaMA, Yi 등은 토큰 예측(next token prediction) 작업으로 학습된 디코더 전용 Transformer 모델입니다. 이러한 모델은 동일한 구조의 계층(layer)들로 이루어진 스택(stack)으로 구성되며, 각 계층은 두 가지 주요 모듈로 이루어져 있습니다: 셀프 어텐션(self-attention)과 피드포워드 네트워크(FFN).

 

 

1. Self-attention 모듈

셀프 어텐션은 Transformer 아키텍처의 핵심 구성 요소로, 시퀀스의 각 부분이 모든 이전 부분을 참조해 문맥적인 표현을 생성할 수 있도록 합니다.

• Query(Q), Key(K), Value(V) 벡터: 입력 토큰을 선형 변환하여 생성됩니다.
• Attention 연산:
  • 각 Query 벡터와 시퀀스의 모든 Key 벡터 간의 내적(dot-product)을 계산해 의미론적 관계를 평가합니다.
  • Softmax 연산을 통해 가중치 벡터를 생성한 후, 이를 Value 벡터에 적용해 최종 결과를 얻습니다.
• 여러 개의 어텐션 헤드(head)를 사용하여 병렬적으로 연산하며, 각 결과를 결합해 최종 출력을 만듭니다.

 

2. Feed-forward 네트워크 (FFN)

• 구성: 두 개의 선형 변환과 하나의 비선형 활성화 함수로 구성됩니다.
  1. 첫 번째 선형 계층: 입력 토큰 임베딩을 높은 차원으로 변환.
  2. 비선형 활성화 함수: 주로 ReLU 또는 GELU 사용.
  3. 두 번째 선형 계층: 임베딩을 원래 차원으로 되돌림.

FFN

 

 

피드 포워드 신경망은 가장 기본적인 인공신경망 구조로, 정보가 한 방향으로만 흐르는 특징을 가집니다. 입력층에서 출발하여 은닉층을 거쳐 최종적으로 출력층에 도달하는 구조입니다.

구조적 특징

1. 층(Layers)
   • 입력층: 원시 데이터를 받는 첫 번째 층
   • 은닉층(Hidden Layer): 1개 이상으로 구성 가능
   • 출력층: 최종 결과를 생성하는 층
2. 뉴런(Neurons)
   • 각 뉴런은 입력 데이터와 가중치(weights)를 통해 연결됨
   • 활성화 함수를 통해 비선형성 추가
   • 대표적인 활성화 함수: ReLU, Sigmoid, Tanh

작동 원리

1. 순전파(Forward Propagation)
   • 입력 데이터가 층을 통과하며 변환
   • 각 뉴런에서 가중합(weighted sum) 계산
   • 활성화 함수를 통해 출력값 결정
2. 역전파(Backpropagation)
   • 손실 함수를 최소화하기 위해 가중치 조정
   • 경사하강법(Gradient Descent) 사용
   • 오차를 뒤로 전파하며 각 층의 가중치 업데이트

수학적 표현

각 뉴런의 출력은 다음과 같이 계산됩니다:

• y = f(Σ(w * x) + b)
  • y: 뉴런의 출력
  • f: 활성화 함수
  • w: 가중치
  • x: 입력
  • b: 편향(bias)

장단점

장점	한계
간단하고 이해하기 쉬운 구조	깊은 네트워크에서 기울기 소실 문제 발생
다양한 문제에 적용 가능	복잡한 순환 패턴 학습에 부적합
병렬 처리에 용이	시퀀스 데이터 처리에 제한적

응용 분야

1. 분류 문제
2. 회귀 분석
3. 패턴 인식
4. 데이터 예측
5. 이미지 및 신호 처리

발전 모델

현대에는 더 복잡한 신경망 구조가 개발되었습니다:

• CNN (합성곱 신경망)
• RNN (순환 신경망)
• Transformer 모델

구현 고려사항

1. 적절한 층의 개수 선택
2. 뉴런 수 결정
3. 활성화 함수 선택
4. 과적합 방지 기법 적용 (드롭아웃, 정규화 등)

 

 

 

 

2.2 LLM Inference Process 번역

자가회귀 디코딩 (Autoregressive Decoding)

LLM 추론은 두 가지 주요 단계로 이루어집니다:

1. Prefill 단계:
   • 사용자의 입력 프롬프트를 처리하여 첫 번째 출력 토큰을 생성합니다.
2. Decode 단계:
   • 이전 단계에서 생성된 토큰을 기반으로 한 번에 하나의 출력 토큰을 생성하며, 종료 토큰(end-of-sequence)이 생성될 때까지 반복됩니다.
   • 이 단계에서는 키(Key)와 값(Value) 데이터를 캐시(KV-cache)에 저장하여 어텐션 연산의 중복 계산을 방지합니다.

Prefill과 Decode 단계의 특성

• Prefill 단계:
  • 수백~수천 개의 입력 토큰을 한 번에 병렬 처리합니다.
  • 병렬 처리 덕분에 GPU를 효율적으로 활용할 수 있습니다.
• Decode 단계:
  • 이전 토큰의 출력을 사용해 새로운 토큰을 생성합니다.
  • 한 번에 하나의 토큰만 처리하므로 계산 효율이 낮고, 메모리 사용량(memory-bound)이 높습니다.

멀티 테넌트 환경에서 배치 기반 LLM 추론

• 배치 처리: 여러 사용자의 요청을 하나의 배치로 묶어 동시에 처리함으로써 GPU 활용도를 높이는 방식입니다.
• 효과: 특히 디코드 단계에서 배치 크기가 클수록 GPU의 메모리 접근 비용이 여러 요청에 분산되어 효율성이 증가합니다.

GPU 활용 최적화를 위한 최근 기술

• PagedAttention: 다수의 요청을 동시에 실행하여 캐시 분산 문제를 해결.
• Multi Query Attention (MQA) 및 Group Query Attention (GQA): KV-cache 크기를 줄여 GPU 메모리 병목 현상을 완화.

---

 

이 알고리즘은 배치를 요청 단위로 처리합니다. 새 요청은 현재 배치가 모두 완료된 경우에만 추가됩니다. 이는 토큰 간 시간(time-between-tokens, TBT) 지연을 최적화하지만, 많은 디코드 전용 반복(iteration)에서 작은 배치 크기로 인해 GPU 자원을 낭비할 가능성이 높습니다.

 

주요 단계

1. 현재 배치 초기화: 빈 배치 BBB로 시작.
2. 새로운 요청 추가:
   • 배치가 비어 있을 경우 새로운 요청 RnewR_{new}Rnew​을 추가.
   • GPU 자원을 할당할 수 있는 한 요청을 배치에 추가.
3. Prefill 처리: 추가된 요청의 프리필(prefill) 단계 실행.
4. Decode 처리:
   • 배치에 있는 요청이 완료될 때까지 디코드 실행.
   • 요청 완료 여부를 확인해 배치에서 제거.

장단점

• 장점: 디코드 단계에서 토큰 간 간섭(interference)이 없어 최소 지연을 달성.
• 단점: 처리량(throughput)이 낮음. 배치 내 일부 요청이 일찍 끝나더라도 마지막 요청이 완료될 때까지 자원을 활용하지 못함.

 

반복 단위 배치 처리 (Iteration-level batching, vLLM)

 

핵심 설명

이 알고리즘은 요청을 더 세분화하여 반복 단위(iteration-level)로 배치를 구성합니다. 새 요청은 GPU 메모리가 가용할 때마다 배치에 추가됩니다. 이는 처리량을 개선하지만, 프리필 단계에서 디코드 요청 간의 간섭으로 인해 생성 중단(generation stall)이 발생할 수 있습니다.

 

주요 단계

1. 현재 배치 초기화: 배치를 빈 상태로 초기화.
2. 새 요청 처리:
   • GPU 자원이 가용한 경우 새로운 요청 RnewR_{new}Rnew​을 배치에 추가.
3. Prefill 우선 처리:
   • 새로 추가된 요청의 프리필 단계를 즉시 처리.
4. Decode 처리:
   • 모든 프리필 요청을 처리한 후에 디코드 실행.

 

장단점

• 장점: 디코드와 프리필 요청을 혼합하여 처리량을 높임.
• 단점: 프리필 단계가 길어질 경우 디코드 요청이 대기 상태에 빠지는 생성 중단 발생.

 

비교 요약

특징알고리즘 1 (Request-level)알고리즘 2 (Iteration-level)

추가 요청 시점	배치가 비었을 때만 추가 가능	GPU 자원이 가용할 때마다 추가
지연 최적화	TBT 지연 최적화	생성 중단으로 인해 지연 증가
처리량	낮음	높음
GPU 활용도	비효율적	상대적으로 효율적

 

Sarathi-Serve와의 차이점

Sarathi-Serve는 위 두 알고리즘의 단점을 극복하기 위해 청크 기반 프리필(chunked-prefill)과 스톨 없는 스케줄링(stall-free scheduling)을 도입하여 디코드 요청의 지연을 줄이고, 처리량을 최대화합니다.

---

 

 

2.3 Multi-GPU LLM Inference

멀티 GPU 환경에서 LLM 추론

모델 크기의 지속적인 증가로 인해 LLM은 멀티 GPU 또는 멀티 노드 배포를 필요로 합니다. 또한, 디코드 단계의 처리량은 GPU에 적재 가능한 최대 배치 크기에 의해 제한됩니다. 이러한 제약을 극복하기 위해 모델 병렬화(model parallelism)가 사용되며, 이는 모델 가중치를 여러 GPU에 분산하여 더 큰 배치 크기를 지원할 수 있도록 합니다.

 

병렬화 방식

1. Tensor Parallelism (TP):
   • 모델의 각 계층(layer)을 GPU들에 걸쳐 분할합니다.
   • 가중치와 키-값(KV) 캐시를 GPU 워커(worker) 간에 균등하게 분할하여 처리량을 선형적으로 확장합니다.
   • 제약 사항:
     • 각 계층의 연산에는 두 번의 All-Reduce 통신(주의산 및 FFN 계산 시)이 필요합니다.
     • 이러한 통신은 계산 경로의 병목 구간에 위치하므로, GPU 간 고속 연결(예: NVLink)에서만 선호됩니다.
2. Pipeline Parallelism (PP):
   • 모델을 계층 단위로 분할하여 각 GPU가 특정 계층을 담당하도록 합니다.
   • 모든 GPU가 효율적으로 작동할 수 있도록 **마이크로 배치(micro-batch)**를 사용합니다.
   • PP는 한 번의 통신으로 여러 계층의 계산 결과를 전송할 수 있어 TP보다 효율적인 계산-통신 비율을 제공합니다.
   • 제약 사항:
     • 노드 간 통신이 필요한 경우, 효율성이 떨어질 수 있음.

비교

• TP는 단일 노드에서 높은 대역폭 연결이 가능한 경우 선호되며, PP는 여러 노드가 연결된 환경에서 더 적합합니다.
• TP는 각 계층에 대해 많은 통신이 필요하지만, PP는 계층 사이의 활성화 데이터만 전달하면 되므로 더 적은 통신을 요구합니다.

 

 

2.4 Performance Metrics

지연(latency) 메트릭

1. TTFT (Time-To-First-Token):
   • 요청이 시스템에 도착한 시점부터 첫 번째 출력 토큰이 생성되기까지의 지연 시간.
   • 시스템의 초기 응답성을 평가합니다.
2. TBT (Time-Between-Tokens):
   • 한 요청의 연속된 출력 토큰 사이의 간격.
   • 모델 응답의 유창함(fluidity)에 영향을 미칩니다.
   • 부하가 증가하면 스케줄링 지연이 증가해 TTFT와 TBT 모두에 영향을 미칩니다.

처리량(throughput) 메트릭

Capacity:

• 특정 지연 한계(SLO) 내에서 시스템이 처리할 수 있는 최대 요청 부하(초당 요청 수)로 정의됩니다.
• 처리량이 높을수록 운영 비용이 감소하고 효율성이 증가합니다.

 

 

2.5 Scheduling Policies for LLM Inference

스케줄러의 역할

스케줄러는 요청 승인(admission control)과 배치 정책(batching policy)을 관리합니다. 이 섹션에서는 기존 LLM 추론 스케줄러를 크게 두 가지로 나누어 설명합니다:

1. Prefill 우선 스케줄러
2. Decode 우선 스케줄러

1. 요청 단위 배치 처리(Request-level batching)

• 적용 사례: FasterTransformer, Triton Inference Server.
• 작동 방식:
  • 요청 배치를 선택하고, 해당 배치가 완료될 때까지 처리합니다.
  • 배치 내 요청의 입력/출력 토큰 수가 서로 다르면, 짧은 요청을 0으로 채우는 패딩(padding)을 사용합니다.
• 한계:
  • 배치의 요청이 모두 완료되기 전에는 새로운 요청을 추가할 수 없어 GPU 자원 활용이 비효율적.
  • 긴 요청이 포함된 경우 대기 시간이 늘어납니다.

2. 반복 단위 배치 처리(Iteration-level batching)

• 적용 사례: Orca, vLLM, TensorRT-LLM, LightLLM.
• 작동 방식:
  • 요청이 실행되는 동안에도 새로운 요청이 배치에 동적으로 추가될 수 있음.
  • Prefill 요청을 우선적으로 처리하여 이후 Decode 단계에서 더 큰 배치를 가능하게 함.
• 한계:
  • 긴 프리필 요청이 실행될 경우 디코드 요청이 대기 상태에 놓이는 **생성 중단(generation stall)**이 발생.

배치 처리 효과

• Prefill: 입력 토큰을 병렬로 처리하므로 효율성이 높음.
• Decode: 낮은 계산 강도와 메모리 의존성으로 인해 효율성이 낮음.
• 배치를 통해 Decode 단계의 GPU 활용률을 높일 수 있음.

PagedAttention 기술

• 효과:
  • 캐시 단편화(fragmentation)를 제거해 더 많은 요청을 병렬로 처리 가능.
  • 최신 LLM 모델(LLaMA2, Falcon, Yi)에서 메모리 병목 현상을 완화.
• 예: LLaMA2-70B는 KV 캐시 크기가 이전 모델(LLaMA-65B)보다 8배 작아졌음.

---

그림3

설명

• Y축: 초당 처리 가능한 토큰 수.
• X축: 배치 크기.
• Prefill 단계: 처리량은 배치 크기 1에서 이미 거의 포화 상태에 도달하여, 배치 크기가 증가해도 큰 효과가 없습니다.
• Decode 단계: 배치 크기가 증가함에 따라 처리량이 선형적으로 증가합니다.

결론

• Prefill 단계는 병렬 처리로 GPU를 효율적으로 활용하지만, 배치 크기 증가로 얻는 성능 향상이 제한적입니다.
• Decode 단계는 메모리 의존적(memory-bound)이지만, 큰 배치 크기를 통해 처리량을 대폭 개선할 수 있습니다.
• Prefill: 배치 크기가 성능에 거의 영향을 주지 않음.
• Decode: 배치 크기가 성능 향상에 큰 영향을 미침.

---

 

3. Motivation

 

이 섹션에서는 Prefill과 Decode 단계의 성능 특성을 분석하고, 현재 시스템이 처리량(throughput)과 지연(latency) 간의 트레이드오프를 겪는 이유를 설명합니다. 또한 파이프라인 병렬 처리(pipeline parallelism)에서 발생하는 파이프라인 공백(pipeline bubbles) 문제를 강조합니다.

 

3.1 Prefill과 Decode 단계의 비용 분석

Prefill과 Decode의 처리량

• Prefill 단계:
  • 모든 입력 토큰을 병렬로 처리해 GPU 계산을 포화 상태로 만듭니다.
  • 배치 크기 증가로 얻는 처리량 향상은 제한적입니다.
• Decode 단계:
  • 한 번에 하나의 토큰만 처리하므로 GPU 계산 활용이 비효율적입니다.
  • 배치 크기 증가에 따라 처리량이 선형적으로 증가합니다.

 

Prefill과 Decode의 계산 시간 분해

• Prefill 단계:
  • 대부분의 실행 시간은 선형 계층(linear layers)에 의해 소모됩니다.
  • 어텐션 연산 비용은 시퀀스 길이에 따라 증가하지만, 선형 계층의 비용이 여전히 주요 성분입니다.
• Decode 단계:
  • 낮은 산술 강도(arithmetic intensity)로 인해 GPU의 계산 능력을 충분히 활용하지 못함.

3.1의 주요 결론

1. Prefill 단계는 계산 집약적(compute-bound)이고, Decode 단계는 메모리 집약적(memory-bound)입니다.
2. Decode 단계는 처리량 향상을 위해 더 많은 토큰을 배치에 포함시킬 수 있는 여지가 크다.

 

---

그림4 : Prefill과 Decode 단계의 계산 시간 분석

설명

• Y축: Prefill 및 Decode 단계의 실행 시간(ms).
• X축: 입력 시퀀스 길이(Sequence Length) 및 배치 크기.
• Prefill 단계에서는 선형 계층(linear layers)이 전체 실행 시간의 대부분(80% 이상)을 차지하며, 어텐션 연산의 영향은 비교적 작습니다.
• Decode 단계의 계산 시간은 토큰 1개를 처리하는 데 필요한 비용이 Prefill 단계의 토큰 128개를 처리하는 비용과 거의 동일합니다.

결론

• Prefill 단계는 계산 집약적(compute-bound)으로 GPU 성능을 최대한 활용합니다.
• Decode 단계는 메모리 병목(memory-bound)으로 인해 GPU의 계산 능력을 충분히 활용하지 못합니다.
• 선형 계층 최적화가 LLM 추론 성능을 높이는 데 중요합니다.
• Decode 단계의 낮은 계산 강도는 GPU 자원의 낭비로 이어지며, 배치 크기를 키워 이를 보완할 수 있습니다.

 

그림5 : Prefill과 Decode의 산술 강도

 

설명

• Y축: 산술 강도(FLOPs/bytes, 메모리 대 계산 비율).
• X축: 배치 내 토큰 수.
• Prefill:
  • 배치 크기가 클수록 메모리-계산 비율이 높아져 GPU 활용도가 증가.
• Decode:
  • 산술 강도가 매우 낮아, 메모리 병목(memory-bound)에 의해 GPU 계산 자원이 낭비됨.
• Sarathi-Serve:
  • 프리필 청크와 디코드 요청을 결합해 산술 강도 균형을 맞춤.

결론

• Decode 단계의 낮은 산술 강도를 보완하기 위해 프리필 청크를 결합하여 GPU 활용도를 높일 수 있음.

---

3.2 Throughput-Latency Tradeoff (처리량-지연 트레이드오프)

 

반복 단위 배치 처리(Iteration-level batching)는 시스템 처리량을 향상시키지만, 지연(latency) 증가를 초래할 수 있습니다. 이는 프리필(prefill) 요청과 디코드(decode) 요청이 교차 실행되면서 발생하는 생성 중단(generation stall) 현상 때문입니다.

---

그림6 : 배치 크기에 따른 선형 계층 실행 시간

 

설명

• Y축: 선형 계층의 실행 시간(ms).
• X축: 배치 내 토큰 수.
• 배치 크기가 작은 경우 실행 시간은 메모리 접근 시간에 의해 결정.
• 배치 크기가 임계값(약 500~600개)을 넘어서면 연산이 계산 집약적(compute-bound)으로 전환되어 실행 시간이 선형적으로 증가.

>>> 배치 크기를 적절히 조정하면 메모리 병목을 극복하고 GPU 계산 자원을 효과적으로 활용할 수 있음.

그림7 :

• 이 그림은 요청 A, B, C, D가 순차적으로 들어오는 상황에서 다양한 스케줄링 정책의 동작을 보여줍니다.
• vLLM과 Orca:
  • 프리필 요청(C, D)이 배치에 추가될 때 기존 디코드 요청(A, B)이 중단(stalled)됩니다.
  • 특히 vLLM은 배치 내 모든 프리필 요청을 처리한 후에야 디코드가 재개되므로 생성 중단이 발생합니다.
• FasterTransformer:
  • 디코드 요청(A, B)이 완료될 때까지 새로운 프리필 요청(C, D)을 배치하지 않습니다.
  • 지연은 최소화되지만, 처리량은 낮습니다.
• Sarathi-Serve:
  • 프리필 요청을 청크(chunk) 단위로 나누어 기존 디코드 요청(A, B)과 함께 실행합니다.
  • **스톨 없는 스케줄링(stall-free scheduling)**을 통해 생성 중단을 방지하고 처리량과 지연을 모두 최적화합니다.

---

결론

현재의 LLM 스케줄러는 처리량과 지연 간의 트레이드오프에 직면합니다.

• Prefill 우선 시스템 (vLLM, Orca): 처리량은 높지만 지연(TBT)이 증가.
• Decode 우선 시스템 (FasterTransformer): 지연은 낮지만 처리량이 낮음.
• Sarathi-Serve는 **청크 기반 프리필(chunked-prefill)**과 스톨 없는 스케줄링을 통해 이러한 트레이드오프를 극복합니다.

 

3.3 Pipeline Bubbles waste GPU Cycles (파이프라인 공백 문제)

 

파이프라인 병렬 처리(pipeline parallelism, PP)는 LLM 추론의 확장성을 높이는 데 유용하지만, **파이프라인 공백(pipeline bubbles)**으로 인해 GPU 자원이 낭비될 수 있습니다.

• 공백은 마이크로 배치(micro-batch) 간의 실행 시간이 불균형할 때 발생합니다.

Pipeline Bubbles의 유형

1. PB1 (Prefill 길이 차이에 따른 공백):
   • 연속된 마이크로 배치의 프리필 토큰 수가 달라 발생.
2. PB2 (Prefill과 Decode 간 계산 시간 차이에 따른 공백):
   • 프리필 단계와 디코드 단계의 계산 시간이 다를 때 발생.
3. PB3 (디코드 간 컨텍스트 길이에 따른 공백):
   • 디코드 단계에서 어텐션 연산의 비용이 축적된 컨텍스트 길이에 따라 다르기 때문에 발생.

---

그림8 :

• Orca:
  • A, B, C, D 요청을 처리하는 과정에서 프리필 길이 차이와 디코드 계산 시간 차이로 인해 GPU 공백이 발생.
• Sarathi-Serve:
  • **균일한 계산(batch uniformity)**을 유지해 공백을 최소화.
  • GPU의 활용도를 높이고 처리량을 증가시킴.

---

 

결론

Sarathi-Serve는 프리필과 디코드 요청을 균형 있게 결합해 GPU 공백을 최소화하고, 멀티 노드 환경에서 효율적인 병렬 처리를 가능하게 합니다.

 

 

4. Sarathi-Serve: Design and Implementation (Sarathi-Serve: 설계 및 구현)

Sarathi-Serve는 높은 처리량과 예측 가능한 지연 시간(Tail Latency)을 동시에 제공하기 위해 설계되었습니다. 이 시스템은 다음 두 가지 핵심 기술로 이루어져 있습니다:

1. Chunked-prefills: 프리필 요청을 작은 단위(청크)로 나누어 계산을 분산.
2. Stall-free batching: 실행 중인 디코드 요청을 중단하지 않고 새로운 프리필 요청을 추가 처리.

이 두 기술은 처리량을 극대화하면서 지연 시간을 최소화하고, 기존 시스템의 주요 한계를 극복합니다.

 

4.1 Chunked-prefills

문제 정의

디코드 배치에는 계산 강도의 여유(arithmetic intensity slack)가 존재합니다. 이를 활용해 디코드 배치에 추가 계산 작업(프리필 요청)을 병합할 수 있습니다. 그러나, 실제 사용 시 프리필 요청은 수천 개의 토큰으로 이루어져 있으며, 이러한 긴 프리필 요청을 디코드와 함께 처리하면 지연 시간이 크게 증가합니다.

 

해결책: Chunked-prefills

Chunked-prefills는 큰 프리필 요청을 적당한 크기의 작은 **청크(chunk)**로 나누어 여러 반복(iteration)에 걸쳐 처리하는 기술입니다.

핵심 원리:

1. 프리필 요청의 토큰 길이가 짧아질수록 GPU 계산이 더 효율적으로 이루어질 수 있음.
   • 예: 프리필 요청의 시퀀스 길이가 512 토큰일 때 GPU 계산 성능이 포화에 가까워짐(Figure 4 참조).
2. 입력 프롬프트가 수천 개의 토큰으로 이루어진 경우(예: 7000+ 토큰) 이를 여러 청크로 나누어 처리하면 GPU 계산과 메모리 병목을 효과적으로 관리 가능.

결과:

청크 단위로 나뉜 프리필 요청은 배치에서 적절한 수의 토큰으로 구성되어 디코드 배치에 결합될 수 있습니다. 이는 **디코드 간 지연(TBT)**에 미치는 영향을 최소화하면서 GPU 활용도를 높입니다.

 

그림 9 :

 

4.2 Stall-free Batching

문제 정의

기존 시스템(vLLM, Orca)은 프리필 요청을 처리하기 위해 디코드 요청을 일시 중단(stall)시킵니다.

이는 디코드 간 지연(TBT)을 증가시키고 사용자 경험을 저하시킵니다.

 

 

해결책: Stall-free Batching

Stall-free Batching은 디코드 요청을 중단하지 않고 프리필 요청을 함께 처리하는 스케줄링 기법입니다.

동작 원리:

1. 토큰 예산(token budget) 설정:
   • 사용자가 지정한 TBT SLO(Service Level Objective, 서비스 수준 목표)를 기반으로, 배치 내 최대 토큰 수를 결정.
   • 배치에서 새 요청을 추가할 때 토큰 예산을 초과하지 않도록 보장.
2. 디코드 요청 우선 처리:
   • 실행 중인 디코드 요청을 먼저 배치에 포함.
3. 프리필 청크 추가:
   • 기존 프리필 요청의 일부(청크)를 배치에 추가.
4. 새 요청 추가:
   • 배치 내 남은 토큰 예산에 따라 새 요청의 프리필 청크를 배치에 포함.
    

 

• 각 반복에서 디코드 요청을 먼저 배치에 포함하고, 이후 프리필 요청의 청크를 추가.
• 모든 요청을 포함한 뒤, 최종 배치를 처리.

 

 

4.3 Determining Token Budget (토큰 예산 결정)

토큰 예산 설정의 중요성

• 작은 토큰 예산: 디코드 지연(TBT)이 감소하지만 GPU 활용도가 낮아질 수 있음.
• 큰 토큰 예산: 처리량은 증가하지만 디코드 지연이 발생할 가능성이 높아짐.

토큰 예산 결정 요소

1. 디코드 지연 감소:
   • 작은 청크를 생성하면 디코드 배치의 지연 영향을 최소화할 수 있음.
2. 프리필 청크 오버헤드:
   • 청크가 많아질수록 이전 청크의 키-값(KV) 캐시를 반복적으로 읽어야 하므로 메모리 읽기 비용이 증가.
   • 하지만, 적절히 큰 청크(예: 2048 토큰)는 오버헤드를 최소화하면서 효율성을 유지.
3. 타일 양자화(Tiling Quantization):
   • GPU 계산은 행렬 곱셈 연산에서 타일 크기에 따라 효율성이 달라짐.
   • 타일 크기에 맞지 않는 청크 크기(예: 257)는 효율을 저하시킬 수 있음.
4. 파이프라인 병렬 처리:
   • 더 큰 청크는 파이프라인 단계 간 실행 시간 차이를 증가시켜 파이프라인 공백을 유발할 수 있음.

결론:

사용자가 지정한 SLO, 하드웨어 속성, 병렬 처리 구성에 따라 적절한 토큰 예산을 선택해야 함.

 

 

 

4.4 Implementation (구현)

Sarathi-Serve 구현 방식

1. vLLM 기반 확장:
   • 기존 vLLM 코드베이스를 기반으로 청크 프리필(chunked-prefill)과 스톨 없는 배치(stall-free batching) 기능을 추가.
2. Paged Chunk Prefill:
   • FlashAttention v2와 FlashInfer 커널을 사용해 효율적으로 구현.
3. 파이프라인 및 텐서 병렬 처리 지원:
   • NCCL 라이브러리를 사용해 파이프라인 및 텐서 병렬 처리 통신을 최적화.
4. 오픈소스 제공:
   • 프로젝트 소스 코드는 GitHub에서 공개됨.

 

 

5. Evaluation

 

평가 목표

Sarathi-Serve를 다양한 모델과 GPU 환경에서 평가하여 다음 질문들에 답합니다:

1. 최대 처리량: 특정 서비스 수준 목표(SLO) 하에서 모델이 처리할 수 있는 최대 부하(초당 요청 수)는?
2. SLO 변화에 따른 성능: SLO 조건이 달라질 때 Sarathi-Serve의 성능은 어떻게 변화하는가?
3. 병렬 처리 성능: 텐서 병렬(Tensor Parallelism)과 파이프라인 병렬(Pipeline Parallelism) 환경에서 Sarathi-Serve는 얼마나 효과적인가?
4. 청크 프리필 오버헤드: Chunked-prefills로 인해 발생하는 추가 비용은?
5. 핵심 기술 분석: Sarathi-Serve의 두 가지 주요 기술(청크 프리필, 스톨 없는 배치)의 각각의 효과는?

 

Table.3 :

 

 

5.1 Capacity Evaluation (처리 용량 평가)

실험 환경

• Sarathi-Serve를 네 가지 모델과 두 가지 데이터셋에서 평가:
  • 모델: Mistral-7B, Yi-34B, LLaMA2-70B, Falcon-180B.
  • 데이터셋:
    1. OpenChat_ShareGPT4: 사용자와 챗봇 간의 대화 데이터.
    2. Arxiv_Summarization: 긴 과학 논문의 요약 작업.

평가 기준

• SLO 조건:
  • Strict SLO: 짧은 지연 시간이 필요한 실시간 대화형 애플리케이션.
  • Relaxed SLO: 완벽한 실시간 반응은 필요하지 않으나 일정 시간 내 응답해야 하는 애플리케이션.