# GPU-Cluster-Scheduling **Repository Path**: sunineo/GPU-Cluster-Scheduling ## Basic Information - **Project Name**: GPU-Cluster-Scheduling - **Description**: No description available - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: main - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2026-08-07 - **Last Updated**: 2026-08-07 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 高级算法大作业: 异构 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](/data/README.md). ```shell # 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 .. ``` 执行模拟器： ```bash 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 ``` 示例结果： ```shell 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 ``` ```shell 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 |