Week 9 — Scheduling Policies

Learning Objectives

Key Concepts

Setup & Configuration

# Install SGLang (if not already installed)
pip install sglang[all]

# Verify SGLang version supports --schedule-policy flag
python -m sglang.launch_server --help | grep schedule

# Download dataset for shared-prefix workload generation
# SGLang's built-in 'generated-shared-prefix' dataset does not need a file

# For ShareGPT comparison, download dataset
wget https://huggingface.co/datasets/anon8231489123/ShareGPT_Vicuna_unfiltered/resolve/main/ShareGPT_V3_unfiltered_cleaned_split.json

Experiments

# Sweep the three policies actually accepted by --schedule-policy.
# NOTE: dfs-weight is rejected by --schedule-policy in current SGLang (see warning below);
# 'random' is the third measured policy and is what the Results / Analysis Q2 report.
for policy in fcfs lpm random; do
  python -m sglang.launch_server \
    --model meta-llama/Llama-3.1-8B-Instruct \
    --schedule-policy $policy \
    --port 8001 &
  sleep 30
  python -m sglang.bench_serving \
    --backend sglang --port 8001 \
    --dataset-name generated-shared-prefix \
    --num-prompts 300 --request-rate 8 \
    2>&1 | tee results_sched_${policy}.txt
  kill %1; sleep 5
done

# Start vLLM server
vllm serve meta-llama/Llama-3.1-8B-Instruct \
  --port 8000 --disable-log-requests &
sleep 30

python benchmarks/benchmark_serving.py \
  --backend vllm \
  --model meta-llama/Llama-3.1-8B-Instruct \
  --dataset-name sharegpt \
  --dataset-path ShareGPT_V3_unfiltered_cleaned_split.json \
  --num-prompts 300 --request-rate 8 \
  2>&1 | tee results_vllm_baseline.txt
kill %1

for policy in fcfs lpm; do
  python -m sglang.launch_server \
    --model meta-llama/Llama-3.1-8B-Instruct \
    --schedule-policy $policy --port 8001 &
  sleep 30
  python -m sglang.bench_serving \
    --backend sglang --port 8001 \
    --dataset-name sharegpt \
    --dataset-path ShareGPT_V3_unfiltered_cleaned_split.json \
    --num-prompts 200 --request-rate 8 \
    2>&1 | tee results_sched_sharegpt_${policy}.txt
  kill %1; sleep 5
done

# Launch 2-worker DP server (requires 2 GPUs)
python -m sglang.launch_server \
  --model meta-llama/Llama-3.1-8B-Instruct \
  --dp 2 --port 8001

# Benchmark with cache-aware routing (default)
python -m sglang.bench_serving \
  --backend sglang --port 8001 \
  --dataset-name generated-shared-prefix \
  --num-prompts 500 --request-rate 10 \
  2>&1 | tee results_dp_router.txt

Experiment Results

Hardware

SGLang scheduling experiments run on NVIDIA L40S 48GB, A100 80GB HBM2e, and H100 80GB HBM3 (PACE Phoenix cluster), using Llama-3.1-8B-Instruct in BF16. H100 used a constructed shared-prefix workload to expose LPM's cache-locality benefit.

⭐ H100 measured — LPM vs FCFS on constructed shared-prefix workload

Workload: 150 requests, each built by prepending a fixed ~200-token system prompt to a ShareGPT sample. LPM's cache-locality ordering can keep those first ~200 tokens hot in the radix tree.

Random is the clear loser — 8.0% behind FCFS. LPM and FCFS are statistically tied (<2% difference). LPM's benefit requires cache pressure — with ample GPU memory, any non-random policy is equally good.

Scheduling Policy Comparison — SGLang (ShareGPT)

Figure 1: Throughput and TTFT per scheduling policy — LPM, FCFS, Random on L40S and A100 (ShareGPT workload)

Expected vs Actual

Metrics to Collect

Source Code Reading

What to Look For in the Source

Open the SGLang files listed above with your benchmark numbers in another tab — the connection between code path and measured metric becomes concrete. Three reading hooks are especially worth the effort:

sglang/srt/managers/schedule_policy.py — Where LPM / FCFS / Random Branch

Find the class that scores waiting requests against the radix tree. LPM sorts the waiting queue by matched_prefix_len per request (longer match → higher priority); FCFS sorts by arrival timestamp; Random shuffles. The branch is a small if self.policy == ... block — but the downstream consequence is the entire throughput delta you measured.

sglang/srt/mem_cache/radix_cache.py — Why LPM Lookup is Cheap

Look at match_prefix(). It walks the radix tree token-by-token until divergence — O(prefix_length), not O(num_cached_requests). This is why LPM scoring on a 10k-token waiting queue still costs <1ms and never shows up in the ITL numbers.

sglang/srt/router/ — Cross-Worker Cache Locality

The DP router computes a per-worker prefix match score by querying each worker's radix tree. The request is dispatched to the worker with the longest existing match. LPM works within a worker's queue; the router works across workers — they are orthogonal.

Written Analysis — Reference Answers

Below are reference answers based on the real measurements collected on PACE A100/L40S. Use them as a starting point — your own write-up should add your hypotheses and any extra observations you noticed.

Q1: Why are LPM and FCFS nearly identical on ShareGPT?

Q2: Why is Random scheduling worse on L40S than A100?

Q3: When does LPM win big in production?