Orca: The beginning of Morden LLM serving.

总的来说，ORCA最重要的历史贡献，是在Transformer自回归推理中系统化提出Iteration levelscheduling，迭代级调度和Selective Batching(选择性批处理), 前者是后来通常所说的Continuos batching的重要基础。

Orca改变的是推理引擎最基本的执行单位，这项设计今天仍然适用于单卡和双卡推理。

Abstract

论文的摘要很直接。首先，传统的Request level batching不适合自回归生成。例如现在我们有三个请求

A 需要生成100 tokens
B 需要 20 tokens
C 在A \ B 执行10轮后到达。
2022年那会，传统的Request Batching会把A \ B 作为固定Batch交给Execution Engine,等B返回之后，还得等待A运行，而C则要等待一整个Batch才能加入。

所以Orca自然不会放过这个现象，Orca让Scheduler在每次model iteration结束之后，重新决定batch的组成。

Iterations	1	2	3	4	5
Traditional	A+B	A+B	A+B	A+B	C
ORCA	A+B	A+B	A+C	A+C	A+C

这样batch就不再是固定的了

而随之而来的一个问题就是，不同请求的Sequence Length 不一样，怎么Batch呢
所以这就是第二个创新点的来源， Selective Batching，只对Transformer中适合批处理的算子执行batching，而不要求所有算子都采用相同的batch结构

例如现在有三个亲求，两个是Decode,一个是batching
那么对于Decode的来说，一般的Tensor shape是 1x d 的Q, 和 context lenght x d 的 k
而对于prefill，就是token x d
这些attention操作无法直接组成一个具有统一序列长度的普通Dense batch，如果为了统一形状，要padding的话就会产生大量的无效计算

所以作者认为，不必要强制所有算子一起batch，这就是selective batching，一个Transformer block中，有些算子不关心输入来自哪条请求，例如Linear，只要hidden size相同就可以

Introduction

这一部分，我们重点看看作者对Attention的解释。

在计算注意力的时候，我们一般是

Q = XW_q K = XW_k V = XW_v

这些Linear PROJECTION 是有模型参数的，而GPU Decode的时候，反复从HBM中加载模型权重是重要成本。增大Batch size就可以提高权重的复用效率

作者宁愿让ATTENTION 分别执行，也要让Linear / MLP 能够以更大的batch执行，因为后者通常能够获得更明显的权重方寸摊销收益。

Chanllenges and Proposed Solutions

作者提出了serving里面的两个困难

Early-finished / Late- joining Requests
Batching an Arbitrary Set of Requests

就是request的到达不同、request的并行需求不同

Orca的基本结构非常简单：

他们通过维护一个基础的 Request pool ,通过scheduler选入到 Scheduler中进行协调。然后交给Execution Engine.

与传统的Serving 区别是，engine只负责执行一次Iteration,完成之后就把控制权交还给Scheduelr。

假设Request pool中有

A: 已经生成20 tokens, going on
B: 5tokens , going on
C just arrived

然后scheduler可以根据输入来构造

这个东西其实就是线代的推理引擎中 scheduler state Management 的雏形。

Selective batching: 此处，假设有 (1,1,2,3) 四种token数目的亲求，作者不是构造 $R^{4 x 3 x H}$ ,而是直接生成 7XH 维度的向量。等到Attention的的时候再单独的分割切开。分别读取需要的KV，再一起merge,这样就避免了为了完成，组成一个规则的Batch，而放进去大量Padding，浪费计算。

Distributed Architecture

作者把控制信息 (Request IDs, Token Indices) 和实际的GPU Tensor Data分开传输

Control Plane 通过独立通信通道传输调度元数据，避免务必要的GPU同步
Data Plane: 通过NCCL 传输真正的Tensor data

目的就是让GPU持续运行。不用等待CPU通过GPU通信机制同步控制信息。

Scheduling Algorithm

1.调度原则: Iteration - level First Come First Serve

假设请求A比B更早，那么A的Iteration数目不应该少于B

2. KV Cache Reservation

作者定义

max_bs: 最大 Batch size
n_slots: 可用的KV Cache Token slots 总数
n_rsrv 目前预留的 Token slots
max_tokens 某条请求允许达到的最大的总token数目，包含输入和生成部分

下面是核心代码:

def select_batch(requests, reserved, capacity, max_bs):
  batch  = []

  for req in requests_by_arrival_time(requests):
    if req.is_running:
      continue
    if len(batch) == max_bs:
      break
    if req.is_new:
      needed = req.max_tokens
        if reserved + needed > capacity:
          break

          reserved += needed
    batch.append(req)
  return batch, reserved