# Distributed-Inference-Scheduler-Edge

**Repository Path**: Lss__sjk/distributed-inference-scheduler-edge

## Basic Information

- **Project Name**: Distributed-Inference-Scheduler-Edge
- **Description**: 边缘集群AI推理的分布式任务调度
2025年华为嵌入式软件大赛-算法组

- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2025-08-07
- **Last Updated**: 2025-08-07

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README


# 边缘集群AI推理的分布式任务调度 - 解决方案

本项目是针对“边缘集群AI推理的分布式任务调度”赛题的解决方案。该方案在 [2025年华为嵌入式软件大赛-算法组] 的杭夏赛区复赛中取得了 **第八名** 的成绩。
 
## 1. 项目简介

在多用户共享算力资源的边缘计算场景中，本方案旨在设计一个高效的任务调度算法。算法需要处理来自多个用户的、具有不同启动时间和性能需求的AI推理任务，并将它们合理地分配到异构的服务器集群上。最终目标是在满足各类复杂约束（如服务器性能、显存、通信延迟、任务时限）的前提下，**最大化所有用户的总吞吐量**。

## 2. 核心挑战

该问题是一个复杂的NP-hard调度优化问题，主要挑战包括：

- **异构性 (Heterogeneity)**: 服务器的NPU数量、处理速度（`k`值）、显存大小（`m`值）各不相同。
- **时效性 (Timeliness)**: 每个用户的任务请求都有一个严格的时间窗口 `[s, e)`，超时完成或未完成都会导致严重的扣分。
- **多目标优化 (Multi-objective Optimization)**: 需要在多个冲突的目标之间取得平衡：
    1.  **高吞吐量**: 尽快完成所有用户的推理样本。
    2.  **低延迟**: 用户的请求完成时间不应远超其截止时间`e`。
    3.  **低迁移成本**: 用户任务在不同NPU之间频繁切换（迁移）会受到惩罚。
- **动态性与复杂性 (Dynamism & Complexity)**: 系统的状态（如NPU的空闲时间）是动态变化的，而推理耗时、显存占用与`batchsize`的非线性关系也增加了决策的复杂度。

## 3. 算法设计

为了应对上述挑战，本方案采用了一种**基于离散事件模拟的、带有前瞻性分析的贪心策略**。算法的核心思想是在每个决策点，为当前“最需要”服务的用户，选择一个“未来综合成本最低”的NPU进行任务分配。

### 3.1 总体框架：离散事件模拟

传统的按毫秒递增（`time++`）的模拟方式效率低下。本算法采用**离散事件驱动**的模式，时间轴只在关键事件发生时才向前推进。关键事件包括：
1.  有新的用户任务到达其允许的最早发送时间 `s`。
2.  某个NPU完成了当前任务，变为空闲状态。

通过直接跳转到下一个最近的事件时间点，算法大大减少了不必要的计算，保证了在30秒的时限内完成复杂的调度决策。

### 3.2 调度核心：动态优先级队列

在任何一个时间点，都可能有多个用户等待被调度。算法通过一个动态优先级函数来决定下一个为谁服务。用户的优先级 `priority` 由以下几个因素加权构成：

1.  **就绪状态**: 只有当 `current_time >= user.ready_to_send_time` 时，用户才会被考虑。
2.  **紧急度 (Urgency)**: `urgency = 剩余样本数 / 剩余时间`。这个指标衡量了任务的紧迫程度，剩余时间越少、剩余任务越多的用户优先级越高。
3.  **濒危状态 (At-Risk)**: 当一个简单的预估显示用户可能无法在截止时间 `e` 前完成任务时，会被标记为`at_risk`，并获得一个巨大的优先级加成，以被优先抢救。
4.  **静态宽松度**: 任务时间窗口 `e - s` 越短的用户，其容错空间越小，因此被赋予一个较高的基础优先级。

在每个决策时刻，算法会选择当前优先级最高的用户进行处理。

### 3.3 NPU选择策略

为选定的用户选择最佳NPU是算法的另一个关键。

#### 3.3.1 迁移惩罚与“鸟巢”模型 (Nest Model)

为了减少评分规则中的`move`惩罚，算法引入了“鸟巢”模型。每个用户维护两个NPU列表：
- **主巢 (Primary Nest)**: 存储用户最近最常用的NPU。
- **备用巢 (Reserve Nest)**: 存储用户曾经使用过但非近期的NPU。

在选择NPU时，会优先考虑“主巢”中的NPU。这种策略建立了任务的**局部性（Locality）**，有效减少了不必要的迁移。

#### 3.3.2 成本计算 (Cost Calculation)

选择NPU的依据是**预估成本 `cost`**。对于一个候选NPU，其成本主要由**任务预估启动推理时间**构成。
`cost = max(NPU当前空闲时间, 用户请求到达时间) + 迁移惩罚`
其中，`迁移惩罚`是一个巨大的常数（`MIGRATION_PENALTY`），仅当选择的NPU不是用户上一次使用的NPU时才会被计入。这使得算法会极力避免迁移，除非留守原地的等待时间成本过高。

#### 3.3.3 前瞻性决策 (Lookahead Decision-Making)

当为最高优先级的用户（记为A）找到的多个NPU选择的预估成本相近时（在一个容忍度 `LOOKAHEAD_TIE_TOLERANCE` 内），简单的贪心选择可能不是全局最优的。例如，选择A的最低成本NPU可能会严重阻塞下一个重要用户（记为B）的执行。

此时，算法会启动一个**前瞻性分析**：
1.  遍历所有A的低成本候选NPU。
2.  对于每个候选，**模拟**将A的任务分配给它后，系统状态的变化。
3.  在此模拟状态下，计算下一个优先级最高的用户B的**最小执行成本**。
4.  最终选择那个能使 `cost(A) + w * cost(B)` 总成本最小的NPU分配给A。`w` 是一个权重系数。

这个前瞻机制以少量的额外计算为代价，提高了决策的全局视野。

### 3.4 动态批处理大小 (Dynamic Batch Sizing)

`batchsize`的大小直接影响推理耗时和显存占用。算法的策略是：
- **最大化利用**: 在不超过服务器显存和用户剩余样本数的前提下，尽可能使用大的`batchsize`以提高单次处理效率。
- **风险规避**: 对于被标记为 `at_risk` 的用户，算法会**主动减小`batchsize`**（例如减半）。虽然这会降低单次效率，但可以缩短单次推理的绝对时间，更快地释放NPU，进行下一次调度，增加其在时限内完成所有任务的可能性。

## 4. 代码结构说明

代码组织清晰，主要分为数据结构定义和核心逻辑实现。

### 4.1 主要数据结构 (`struct`)

- `ServerType`: 存储服务器种类的静态信息（`g, k, m`等）。
- `User`: 存储用户的动态和静态信息，包括任务需求（`s, e, cnt`）、调度状态（`samples_to_schedule`, `ready_to_send_time`）以及用于启发式策略的数据（`priority`, `last_npu_id`, `primary_nest`等）。
- `Decision`: 存储为用户做出的一个调度决策，用于最终输出。
- `CandidateNpu`: 在NPU选择过程中，用于存储候选NPU及其评估成本，方便排序。

### 4.2 核心函数

- `main()`: 程序入口，调用`read_input()`和`solve()`。
- `read_input()`: 读取所有输入数据，并进行初始化。
- `solve()`: **主调度循环**。实现了上文所述的离散事件模拟框架。循环直到所有用户的样本都被调度完毕。
- `update_user_priority_and_risk()`: 根据当前时间和用户状态，计算每个用户的动态优先级。
- `calculate_assignment_cost()`: 计算将一个用户分配给一个特定NPU的成本。
- `update_nest()`: 在一次调度完成后，更新用户的“鸟巢”列表。

### 4.3 关键全局变量与超参数

- `npu_free_time`: 一个二维向量，记录了每个NPU的预计空闲时间，是整个模拟系统的核心状态。
- `current_global_time`: 全局模拟时钟。
- **超参数 (Hyperparameters)**:
    - `PRIMARY_NEST_SIZE`, `RESERVE_NEST_SIZE`: “鸟巢”模型的大小。
    - `MIGRATION_PENALTY`: 迁移惩罚值。
    - `LOOKAHEAD_TIE_TOLERANCE`, `LOOKAHEAD_WEIGHT_B`: 前瞻性分析的触发阈值和权重。
    - `URGENCY_WEIGHT`, `AT_RISK_WEIGHT`: 优先级计算中的权重系数。
    
    这些超参数是在本地测试中反复调优得到的，对算法性能有重要影响。

## 5. 编译与运行

1.  **编译环境**: C++17 或更高版本，使用 g++ 编译器。
2.  **编译命令**:
    ```bash
    g++ -O2 -std=c++17 -o scheduler main.cpp
    ```
3.  **运行方式**:
    ```bash
    ./scheduler < input.txt > output.txt
    ```
    其中 `input.txt` 是赛题提供的输入文件，`output.txt` 是程序生成的调度方案。

## 6. 致谢

感谢大赛主办方提供这样一个富有挑战性和实际意义的赛题。也感谢我的队友们在比赛过程中的共同努力。