高级算法大作业: 异构 GPU 集群调度

main 分支包含所有启发式算法, preemption 分支为抢占式调度算法, rl 分支为强化学习调度算法。

实现简介

目录结构:

./
├── data/                  # 数据和预处理脚本 (.csv 和 .header)
├── simulator/             # 模拟器源代码
│   ├── domain.py          # [定义] 基础数据结构 (Job, Node, Event)
│   ├── data_loader.py     # [输入] 数据解析与加载，变成 Job/Node 对象
│   ├── scheduler.py       # [大脑] 调度算法 (FIFO/First-Fit)，输入是“一堆待处理任务”和“一堆机器”，输出是“哪个任务去哪个机器”
│   ├── simulator.py       # [引擎] 离散事件模拟核心，维护时间轴 (now) 和事件堆 (events)
├── run_simulator.py       # [入口] 运行模拟器
├── benchmark.py           # [测试] 在小规模数据集 task1.csv 和 task2.csv 上测试

使用离散事件模拟（Discrete Event Simulation, DES）来模拟调度过程，本质上就是一个优先队列（Priority Queue）和一个 while 循环。

模拟器包含的核心对象:

• Cluster (集群状态): 维护所有 Node 的实时状态（剩余 GPU 显存数量等）。
• Scheduler (调度器): 核心算法实现在这里。输入是待调度队列，输出是 (Job, Node) 的配对。
• Event (事件): 只有两类核心事件
  1. JOB_ARRIVAL: 任务到达，加入等待队列。
  2. JOB_COMPLETION: 任务完成，释放资源。

模拟器输入:

• Node List: 机器列表（包含机器的显存大小、GPU type 等信息）。
• Job List: 任务流（包含一个任务/作业的提交时间、实际完成时间等信息）。
• Scheduler Algorithm: 实现的调度算法（例如，FIFO, SPT, EDF 等）

模拟器输出:

• 调度日志（Trace）：记录每个任务是何时开始运行的，在哪台机器上运行的。
• 核心指标（Metrics）：对应课程大作业要求
  1. 平均（加权）完成时间：如果作业有权重（优先级），则加权计算。
  2. 平均（加权）等待时间
  3. Makespan
  4. Deadline 违约率

针对异构性的设计

算力异构性

模拟器包含一个性能系数表，不同类型的 GPU 具有不同的 speedup。

• 同样的任务在 V100 上跑 10 分钟，在 T4 上可能需要 20 分钟。
• 在解析数据时，我们得到了 duration (这是原始 trace 里的时长，对应原始 gpu_type)。在模拟器中，当 Scheduler 决定把 Job A (原是 V100) 调度到 Node B (是 T4) 时，我们需要调整它的运行时长：

$$RealDuration = BaseDuration \times \frac{Perf(OriginalGPU)}{Perf(TargetGPU)}$$

在读取 trace 数据，构造 Job 对象时，我们会对 duration 的数值进行标准化获得一个任务量 workload，一个任务的实际任务量（与机器类型无关）为:

$$\text{Workload} = \text{Duration} \times \text{Speedup}_{\text{target}}$$

当允许调度器进行异构调度，即将一个任务分配到不是其目标 GPU 类型的机器上时，在放置（placement）策略上，默认采用 "Best-Fit" 策略：找到可分配的、性能最好的节点来分配。

显存异构性

在 PAI trace 中，任务是根据其原始目标 GPU（target_gpu_type）的显存容量来定义 gpu_req（占卡比）的。当它被迁移到另一种 GPU 上时，必须保持“绝对显存需求量”不变，因此“占卡比”需要根据两种显存容量的比例进行缩放。换算公式如下：

$$\text{AllocGPUReq} = \text{TargetGPUReq} \times \frac{\text{Memory}(\text{TargetGPU})}{\text{Memory}(\text{AllocGPU})}$$

例如，任务原始目标是 V100M32 (32GB)，申请 gpu_req=0.5 (即需要 16GB)。调度到 T4 (16GB) 上时，它依然需要 16GB，因此在 T4 上 gpu_req 变为 $0.5 \times \frac{32}{16} = 1.0$ (占满一张 T4)。

在读取 trace 数据，构造 Job 对象时，我们会对 gpu_req 的数值进行转换，获得一个显存需求量 gpu_mem_req，一个任务的实际显存需求（与机器类型无关）为:

$$\text{GPUMemReq} = \text{GPUNumReq} \times \text{MemPerGPU}_{\text{target}}$$

在 Philly trace 中，原始数据自带显存需求字段。

字段填补

我们所用的两个 Trace（Alibaba PAI/Philly）只包含“客观”的运行数据（提交时间、运行时长、资源用量），而缺少“主观”的业务约束信息（Deadline、优先级/权重）。我们在 preprocess 阶段合成这两种信息并注入。

• 截止时间（Deadline） 使用 "Slack Factor" (松弛因子) 模型来生成截止时间。

  • 逻辑: 任务越长，给它的缓冲时间通常越多。
  • 计算公式: $\text{Deadline} = \text{SubmitTime} + \text{Duration} \times \text{Slack}$
  • 实现: 对于每个任务，随机生成一个松弛因子 $k$（例如在 1.5 到 4.0 之间均匀分布）。
    • $k=1.0$ 意味着任务必须紧接着提交立刻完成（不可能）。
    • $k=2.0$ 意味着任务有两倍于其运行时长的时间窗口。

• 权重（Weight/Priority） 既然没有真实的业务优先级，我们可以模拟不同重要性的任务，具体来说，我们随机选择一个1-5的整数权重。

快速开始

下载数据集，详情参见data.

# enter data directory
cd data

# Alibaba Pai 数据集
cd pai && bash download_data.sh && cd ..

# Philly 数据集
cd philly && bash download_data.sh && cd ..

# go back to root
cd ..

执行模拟器：

python -u run_simulator.py \
    --dataset pai \
    --schedule hrrn --placement best_fit --heterogeneous \
    --jobs_limit 10000 --gpus_limit 5

# dataset: pai | philly
# schedule: fifo | spt | edf | hrrn | sufferage
# placement: first_fit | best_fit
# heterogeneous: enable heterogeneous scheduling (True/False)
# jobs_limit: limit the number of jobs to load, if not specified, load all jobs
# gpus_limit: limit the number of GPUs in the cluster, if not specified, load all nodes


# Run benchmark tests on task1.csv and task2.csv
python -u benchmark.py

示例结果：

python -u run_simulator.py --dataset pai --schedule hrrn --placement best_fit --heterogeneous --jobs_limit 10000 --gpus_limit 10

>>> Phase 1: Data Loading
Loaded 50 machines. Machine type distribution: {'V100': 10, 'P100': 10, 'MISC': 10, 'T4': 10, 'V100M32': 10}
Loaded 10000 jobs.
>>> Phase 2: Initialization
    Selected Scheduler: HRRNScheduler | Heterogeneous: True
>>> Phase 3: Job Submission
>>> Phase 4: Running Simulation...
[Simulation Started]
    Progress: 10000/10000 (100.0%) - Waiting: 0
[Simulation Completed]
>>> Phase 5: Statistics
    Total Completed Jobs: 10000
    Average JCT: 5539.27 s
    Average Weighted JCT: 5391.39 s
    Average Wait: 417.18 s
    Deadline Violation Rate: 2.29 %
    Makespan: 1352760.91 s
    Unscheduled Jobs: 0

python -u run_simulator.py --dataset philly --schedule hrrn --placement best_fit --heterogeneous --jobs_limit 10000 --gpus_limit 10

>>> Phase 1: Data Loading
Loaded 20 machines. Machine type distribution: {'2x12': 10, '8x24': 10}
Loaded 10000 jobs.
>>> Phase 2: Initialization
    Selected Scheduler: HRRNScheduler | Heterogeneous: True
>>> Phase 3: Job Submission
>>> Phase 4: Running Simulation...
[Simulation Started]
    Progress: 9999/10000 (100.0%) - Waiting: 1
[Simulation Completed]
>>> Phase 5: Statistics
    Total Completed Jobs: 9999
    Average JCT: 13458.36 s
    Average Weighted JCT: 14004.19 s
    Average Wait: 4736.33 s
    Deadline Violation Rate: 20.36 %
    Makespan: 3636499.00 s
    Unscheduled Jobs: 1

调度算法对比

仅测试前 10,000 条 job 记录, 启用异构性 + best_fit; 仅对每种 GPU 类型保留 5 个 nodes，制造排队现象。

• Alibaba Pai 数据集

指标 (Metrics)	FIFO	SPT	EDF	HRRN	SUFFERAGE
平均完成时间 (Avg JCT)	19496.10 s	7847.78 s	7792.34 s	7880.31 s	9780.18 s
加权完成时间 (Avg W-JCT)	19309.64 s	7628.19 s	7596.28 s	7702.36 s	9568.63 s
平均等待時間 (Avg Wait)	14359.74 s	2591.50 s	2589.16 s	2611.96 s	5008.42 s
截止违约率 (Deadline Miss)	66.82 %	7.36 %	8.96 %	13.34 %	5.10 %
集群最大完工时间 (Makespan)	1526124.27 s	1458987.27 s	1441217.91 s	1448715.68 s	1631385.14 s

• Microsoft Philly 数据集

指标 (Metrics)	FIFO	SPT	EDF	HRRN	SUFFERAGE
平均完成时间 (Avg JCT)	157978.96 s	30690.23 s	36577.54 s	36408.62 s	36590.78 s
加权完成时间 (Avg W-JCT)	159089.26 s	31437.28 s	37462.80 s	37143.95 s	37626.40 s
平均等待時間 (Avg Wait)	149029.49 s	21848.61 s	27625.11 s	27648.92 s	28079.43 s
截止违约率 (Deadline Miss)	96.24 %	60.24 %	85.39 %	78.42 %	65.54 %
集群最大完工时间 (Makespan)	3732928.00 s	4543413.00 s	4958705.00 s	4298369.00 s	4497811.50 s