IEEE INFOCOM2025开源文|好文荐读！HyperJet：分布式边缘计算中超图任务的联合通信与计算调度

摘要

分布式边缘计算（DEC）因其在通信延迟、并行计算效率和能耗方面的卓越性能，已成为一种新的计算模式。随着生成式人工智能任务的激增，DEC 对并行计算效率提出了更高的要求。安排多个任务同时处理，而不是逐个处理，可以提高并行效率。多个任务具有多重依赖性，即序列依赖性、属性相似性和属性相关性。利用传统图的双向边来表示多重依赖关系会导致数量爆炸。超图的超边可以连接任意数量的顶点，可以极大地解决上述问题。然而，目前的研究很少涉及多依赖关系，这就带来了挑战，包括无法表示和捕获多依赖关系超图。为了有效地表示多重依赖关系，我们采用超图构造来表示任务属性，并利用超图分割来明确和细化任务属性的相关性，从而提高并行效率。为应对捕捉多重依赖关系的挑战，我们采用了超图神经网络调度机制，在卷积矩阵中有效获取高阶属性相关信息，提供丰富的多重依赖关系上下文信息，为调度任务的决策提供支持。使用实际跟踪进行的评估表明，任务调度的并行效率提高了 18.07%

问题背景

分布式边缘计算（DEC）的价值与挑战：DEC 融合边缘计算与并行计算，在通信延迟、并行效率和能耗优化上优势显著，可将自动驾驶、直播流等场景的任务分配到边缘资源池加速处理。但生成式 AI 任务激增使 DEC 对并行效率要求更高，传统 “逐一处理任务” 模式难以满足需求。
任务多依赖特性与传统模型局限

多依赖类型：多任务间存在三类关键依赖 —— 序列依赖（任务执行顺序）、属性相似性（如多任务相似码率）、属性相关性（如分辨率与码率因用户设备类型关联），合称 “多依赖”。
传统 DAG 模型缺陷：传统有向无环图（DAG）仅能表示序列依赖，若用双向边表示属性相似性与相关性，会导致边数量爆炸（如图 5 所示，任务数 4000 时 DAG 双向边超 3800 条，而超图边仅 40 条），大幅增加复杂度，无法支撑高效并行调度。

IEEE INFOCOM2025开源文|好文荐读！HyperJet：分布式边缘计算中超图任务的联合通信与计算调度插图

系统模型

（一）系统架构

核心组件：包含M个用户设备（UD）、N个资源池（RP，边缘服务器），UD生成任务请求，任务可在本地执行或调度至RP，计算节点涵盖UD与RP，需优化CPU频率、传输功率等资源参数。
任务定义：每个任务表示为（\(D_i, R_i\)），\(D_i\)为任务大小，\(R_i\)为执行结果大小，通过指示器\(z_i\)（0=本地执行，非0=调度至对应RP）确定执行位置。

（二）关键子模型

1. 通信模型：UD与RP间分上行（任务传输）和下行（结果返回）通信，采用正交子信道避免干扰，传输速率基于香农公式计算，考虑带宽、传输功率、信道增益与噪声方差。

2. 任务延迟模型

– 个体任务延迟：含传输延迟（仅调度至RP时存在，分上下行）与计算延迟（任务大小与计算节点CPU频率的比值）。

– 依赖任务延迟：任务需在所有父任务完成后启动，完成时间为“设备/RP可用时间”“父任务最大完成时间”中的最大值，叠加自身计算与传输延迟，总延迟为无后续任务的最大完成时间。

3. 能耗模型：分计算能耗（与CPU频率的三次方、计算延迟正相关）和传输能耗（传输时间与对应方向功率的乘积），仅调度至RP时需考虑传输能耗。

（三）优化目标

最小化“延迟-能耗加权和”，公式为：

核心方法

（一）超图驱动的多依赖表示

超图构建（解决无法表示问题）

定义：超图\(H=(V, E_{hy})\)，顶点\(V\)对应任务，超边\(E_{hy}\)可连接任意数量顶点，避免边数量爆炸。
超边构成-\(E_{DAG}\)：将DAG的序列依赖转化为2-均匀超边，保留执行顺序信息。-\(E_a^{Nw}\)：网络属性超边，按带宽、分辨率、码率、移动性等属性分组，每组任务构成一个超边（如相似码率任务组成码率超边）。-\(E_{Dist_k}\)：k跳邻居超边，捕捉任务的局部连通性依赖，扩展任务关联范围。

IEEE INFOCOM2025开源文|好文荐读！HyperJet：分布式边缘计算中超图任务的联合通信与计算调度插图2

超图划分（优化属性相关性）

目标：采用k路划分算法（KaHyPar），在平衡各分区任务数量的前提下，最小化“跨分区超边数”，保留超边内属性关联性，形成全局属性依赖信息超边\(E_{pt}\)。
作用：细化属性间的全局关联，为后续调度提供更精准的依赖信息，相比仅构建超图，可使奖励提升5%。

（二） HGNN的多依赖捕捉

HGNN实现（解决“无法捕捉”问题）

核心功能：通过超图卷积聚合超边关联的任务特征，捕捉高阶属性相关性，输出包含多依赖信息的任务嵌入。
卷积过程：分“顶点特征变换-超边特征收集-顶点特征聚合”三步，引入顶点/超边度对角矩阵做对称归一化，避免梯度消失/爆炸，激活函数采用ReLU。
任务嵌入更新公式：\(X_y^h = \sigma\left(D_v^{h-1/2} H^h W^h D_e^{h-1} H^{h^T} D_v^{h-1/2} X_{y-1}^h \Theta_{y-1}^h\right)\)，其中\(H^h\)为关联矩阵，\(W^h\)为超边权重，\(\Theta\)为特征变换矩阵。