HEFT算法：异构计算中的任务调度方法

在并行计算、云计算、边缘计算和异构芯片中，我们经常会遇到这样的问题：一个应用不是一个单独任务，而是一组有依赖关系的子任务；这些子任务可以运行在不同处理器上，但每个处理器的速度并不一样。

例如：

• 图像处理流水线中，解码、滤波、特征提取、分类之间有先后依赖。
• 科学计算工作流中，某些矩阵运算必须等前面的数据准备完成。
• CPU、GPU、FPGA 同时存在时，不同任务适合的执行设备不同。
• 边缘计算中，任务可以放在本地设备、边缘服务器或云端执行。

这类问题的核心是：

哪些任务先执行？
每个任务放到哪个处理器上执行？
怎样让整个工作流尽快完成？

HEFT（Heterogeneous Earliest Finish Time，异构最早完成时间）就是一个经典的异构任务调度启发式算法。它不保证一定得到全局最优解，但因为思想清晰、计算复杂度相对较低、效果通常不错，所以经常作为异构计算调度问题中的基线算法。

一句话概括：

HEFT 先根据任务到出口任务的“平均关键路径长度”给任务排序，再按照这个顺序把每个任务放到能最早完成它的处理器上。

1. 为什么需要 HEFT

假设我们有 4 个任务：

T1 -> T2 -> T4
T1 -> T3 -> T4

其中 T2 和 T3 都依赖 T1，T4 必须等 T2 和 T3 都完成后才能执行。

如果只有一个处理器，调度问题比较简单：按依赖顺序一个个执行就行。

但如果有多个处理器，而且处理器性能不同，问题就复杂了：

任务	CPU 执行时间	GPU 执行时间
T1	8	4
T2	6	9
T3	7	3
T4	5	6

可以看到：

• T1 和 T3 在 GPU 上更快。
• T2 和 T4 在 CPU 上更快。
• 如果父任务和子任务被放到不同处理器上，还可能产生数据传输时间。

所以调度器不能只看某个任务在哪个处理器上跑得最快，还要考虑依赖关系、通信代价、处理器空闲时间和全局完成时间。

HEFT 就是为这种“有依赖的异构任务调度”设计的。

2. HEFT 解决的问题长什么样

HEFT 的输入通常包括四类信息。

第一类是任务集合：

$$
V = {v_1, v_2, \dots, v_n}
$$

每个 $v_i$ 表示一个任务。

第二类是任务依赖关系。通常用一个有向无环图（Directed Acyclic Graph，DAG）表示：

$$
G=(V,E)
$$

如果存在边 $(v_i, v_j)$，表示任务 $v_j$ 必须等待任务 $v_i$ 完成，并拿到它产生的数据之后才能开始。

第三类是处理器集合：

$$
P = {p_1, p_2, \dots, p_m}
$$

每个处理器可以是 CPU 核、GPU、FPGA、边缘节点或云服务器。

第四类是代价信息：

• $w_{i,k}$：任务 $v_i$ 在处理器 $p_k$ 上的计算时间。
• $c_{i,j}$：任务 $v_i$ 到任务 $v_j$ 的平均通信时间。

HEFT 的目标通常是最小化整个任务图的完成时间，也就是 makespan：

$$
\text{makespan}=\max_i \text{finish}(v_i)
$$

直观地说，就是让最后一个任务尽早完成。

3. HEFT 的整体思路

HEFT 分成两个阶段：

1. 任务排序阶段：计算每个任务的向上排序值 $rank_u$，按照从大到小排序。
2. 处理器选择阶段：按排序后的任务列表依次调度，每个任务选择最早完成它的处理器。

可以把 HEFT 理解成一种列表调度（List Scheduling）：

先把任务排成一个优先级列表
再按列表顺序逐个安排到处理器上

它的关键就在于两个问题：

• 排序时，怎样判断一个任务更重要？
• 分配时，怎样判断一个处理器更合适？

HEFT 分别用“向上排序值”和“最早完成时间”来回答这两个问题。

4. 平均计算代价

因为处理器是异构的，同一个任务在不同处理器上的执行时间可能不同。

为了在排序阶段先不纠结具体放到哪个处理器上，HEFT 会先计算每个任务的平均计算代价：

$$
\overline{w_i}=\frac{1}{m}\sum_{k=1}^{m}w_{i,k}
$$

其中：

• $w_{i,k}$ 表示任务 $v_i$ 在处理器 $p_k$ 上的计算时间。
• $m$ 表示处理器数量。
• $\overline{w_i}$ 表示任务 $v_i$ 在所有处理器上的平均执行时间。

例如：

任务	CPU	GPU	平均计算代价
T1	8	4	6
T2	6	9	7.5
T3	7	3	5
T4	5	6	5.5

这个平均值不是最终执行时间，而是用于估计任务在 DAG 中的重要程度。

5. 平均通信代价

如果任务 $v_i$ 和任务 $v_j$ 之间有依赖，并且它们被分配到不同处理器上，就可能需要传输数据。

HEFT 在计算任务优先级时，会使用平均通信代价 $\overline{c_{i,j}}$。

在很多简化例子中，可以直接给每条边一个平均通信时间。例如：

依赖边	平均通信代价
T1 -> T2	2
T1 -> T3	2
T2 -> T4	3
T3 -> T4	1

如果父任务和子任务被放在同一个处理器上，实际调度时通信代价通常可以看成 0；如果放在不同处理器上，就需要加上对应通信代价。

这也是 HEFT 相比简单“最快处理器优先”更合理的地方：它不会只看计算速度，还会考虑跨处理器传输数据的成本。

6. 向上排序值：任务离终点还有多远

HEFT 排序阶段最重要的概念是向上排序值（upward rank），通常写作 $rank_u(v_i)$。

它可以理解为：

从任务 $v_i$ 出发，沿着依赖边走到出口任务，平均还需要多少计算和通信代价。

出口任务指的是没有后继任务的任务。对于一个出口任务 $v_i$，它的向上排序值就是自己的平均计算代价：

$$
rank_u(v_i)=\overline{w_i}
$$

对于普通任务，递推公式是：

$$
rank_u(v_i)=\overline{w_i}+
\max_{v_j \in succ(v_i)}
\left(\overline{c_{i,j}}+rank_u(v_j)\right)
$$

其中：

• $succ(v_i)$ 表示任务 $v_i$ 的直接后继任务集合。
• $\overline{w_i}$ 是任务 $v_i$ 的平均计算代价。
• $\overline{c_{i,j}}$ 是从任务 $v_i$ 到任务 $v_j$ 的平均通信代价。
• $\max$ 表示只取最“长”的后继路径。

为什么要取最大值？

因为调度的总完成时间往往由关键路径决定。一个任务如果位于很长的后继链条上，那么它越早执行，越可能缩短整体完成时间。

7. 手工计算向上排序值

继续使用这个 DAG：

T1 -> T2 -> T4
T1 -> T3 -> T4

平均计算代价为：

任务	平均计算代价
T1	6
T2	7.5
T3	5
T4	5.5

平均通信代价为：

依赖边	平均通信代价
T1 -> T2	2
T1 -> T3	2
T2 -> T4	3
T3 -> T4	1

先计算出口任务 T4：

$$
rank_u(T4)=5.5
$$

再计算 T2：

$$
rank_u(T2)=7.5+(3+5.5)=16
$$

再计算 T3：

$$
rank_u(T3)=5+(1+5.5)=11.5
$$

最后计算 T1：

$$
rank_u(T1)=6+\max(2+16,;2+11.5)=24
$$

所以排序结果为：

任务	向上排序值
T1	24
T2	16
T3	11.5
T4	5.5

HEFT 会按照从大到小的顺序调度：

T1 -> T2 -> T3 -> T4

注意，这个顺序不违反依赖关系。T4 虽然排在最后，也正好需要等待 T2 和 T3 完成。

8. 最早开始时间和最早完成时间

排序之后，HEFT 会按任务优先级逐个选择处理器。

对于任务 $v_i$ 和处理器 $p_k$，需要计算两个时间：

• 最早开始时间（Earliest Start Time，EST）。
• 最早完成时间（Earliest Finish Time，EFT）。

最早开始时间由两个因素共同决定：

1. 处理器 $p_k$ 自己什么时候空闲。
2. 任务 $v_i$ 的所有父任务结果什么时候能传过来。

可以写成：

$$
EST(v_i,p_k)=
\max
\left(
avail(p_k),
\max_{v_h \in pred(v_i)}
\left(finish(v_h)+comm(v_h,v_i)\right)
\right)
$$

其中：

• $avail(p_k)$ 表示处理器 $p_k$ 当前最早可用时间。
• $pred(v_i)$ 表示任务 $v_i$ 的前驱任务集合。
• $finish(v_h)$ 表示父任务 $v_h$ 的完成时间。
• $comm(v_h,v_i)$ 表示父任务结果传到当前处理器的通信时间。

最早完成时间就是：

$$
EFT(v_i,p_k)=EST(v_i,p_k)+w_{i,k}
$$

HEFT 会把任务放到让 $EFT$ 最小的处理器上。

9. 调度阶段的小例子

还是使用前面的任务执行时间：

任务	CPU	GPU
T1	8	4
T2	6	9
T3	7	3
T4	5	6

任务顺序为：

T1 -> T2 -> T3 -> T4

9.1 调度 T1

T1 没有前驱任务，可以直接开始。

• 放 CPU：$EFT=0+8=8$
• 放 GPU：$EFT=0+4=4$

所以 T1 放到 GPU，时间为 $0 \sim 4$。

9.2 调度 T2

T2 依赖 T1。假设 T1 -> T2 的通信代价为 2。

• 放 CPU：T1 在 GPU，跨处理器通信，最早开始 $4+2=6$，完成 $6+6=12$。
• 放 GPU：同处理器不需要通信，但 GPU 到时间 4 才空闲，完成 $4+9=13$。

所以 T2 放到 CPU，时间为 $6 \sim 12$。

9.3 调度 T3

T3 也依赖 T1，通信代价为 2。

• 放 CPU：CPU 已经安排了 T2，如果简单按尾部追加，需要等到 12，完成 $12+7=19$。
• 放 GPU：GPU 在时间 4 空闲，同处理器无通信，完成 $4+3=7$。

所以 T3 放到 GPU，时间为 $4 \sim 7$。

9.4 调度 T4

T4 同时依赖 T2 和 T3。

假设：

• T2 -> T4 通信代价为 3。
• T3 -> T4 通信代价为 1。

如果放 CPU：

• 来自 T2：同处理器，数据到达时间 $12$。
• 来自 T3：GPU 到 CPU，需要通信，数据到达时间 $7+1=8$。
• CPU 在时间 12 空闲，所以 $EST=12$。
• $EFT=12+5=17$。

如果放 GPU：

• 来自 T2：CPU 到 GPU，需要通信，数据到达时间 $12+3=15$。
• 来自 T3：同处理器，数据到达时间 $7$。
• GPU 在时间 7 空闲，但必须等 T2 数据到达，所以 $EST=15$。
• $EFT=15+6=21$。

所以 T4 放到 CPU，时间为 $12 \sim 17$。

最终 makespan 为 17。

10. 插入式调度是什么意思

严格来说，HEFT 的处理器选择阶段常使用插入式调度（insertion-based scheduling）。

这意味着：给某个任务选择处理器时，不一定只能把任务追加到该处理器最后，也可以检查已有任务之间是否存在足够大的空隙。

例如某个处理器上已有任务：

0 ~ 3 执行 A
8 ~ 12 执行 B

如果当前任务最早可以在时间 4 开始，执行时间为 3，那么它可以插入到 $4 \sim 7$，而不是等到 12 以后再执行。

插入式调度能更充分利用处理器空闲片段，尤其是在任务依赖和通信导致空洞较多时，会比简单追加更好。

11. HEFT 算法步骤

HEFT 的完整流程可以概括为：

1. 根据任务图和处理器执行时间，计算每个任务的平均计算代价。
2. 根据任务依赖边，计算平均通信代价。
3. 从出口任务开始，递归计算每个任务的 $rank_u$。
4. 按照 $rank_u$ 从大到小得到任务优先级列表。
5. 依次取出列表中的任务。
6. 对每个候选处理器计算该任务的 $EST$ 和 $EFT$。
7. 把任务分配给 $EFT$ 最小的处理器。
8. 更新处理器时间表和任务完成时间。
9. 所有任务都调度完成后，得到最终 makespan。

伪代码可以写成：

for each task:
    compute average computation cost

for each edge:
    compute average communication cost

compute upward rank for each task
task_list = tasks sorted by decreasing upward rank

for task in task_list:
    best_processor = None
    best_finish_time = infinity

    for processor in processors:
        est = earliest_start_time(task, processor)
        eft = est + computation_cost(task, processor)

        if eft < best_finish_time:
            best_processor = processor
            best_finish_time = eft

    schedule task on best_processor

12. Python 手写实现

下面写一个简化版 HEFT。

为了让代码更容易理解，这里先使用“追加式调度”，也就是每个任务只能排在处理器已有任务之后，不做空隙插入。核心思想和 HEFT 一致，只是少了插入空洞的细节。

from functools import lru_cache


tasks = ["T1", "T2", "T3", "T4"]
processors = ["CPU", "GPU"]

computation_cost = {
    "T1": {"CPU": 8, "GPU": 4},
    "T2": {"CPU": 6, "GPU": 9},
    "T3": {"CPU": 7, "GPU": 3},
    "T4": {"CPU": 5, "GPU": 6},
}

successors = {
    "T1": ["T2", "T3"],
    "T2": ["T4"],
    "T3": ["T4"],
    "T4": [],
}

predecessors = {
    "T1": [],
    "T2": ["T1"],
    "T3": ["T1"],
    "T4": ["T2", "T3"],
}

communication_cost = {
    ("T1", "T2"): 2,
    ("T1", "T3"): 2,
    ("T2", "T4"): 3,
    ("T3", "T4"): 1,
}


def average_computation_cost(task):
    total = sum(computation_cost[task][p] for p in processors)
    return total / len(processors)


@lru_cache(None)
def upward_rank(task):
    avg_compute = average_computation_cost(task)

    if not successors[task]:
        return avg_compute

    longest_child_path = max(
        communication_cost[(task, child)] + upward_rank(child)
        for child in successors[task]
    )

    return avg_compute + longest_child_path


rank = {task: upward_rank(task) for task in tasks}
task_order = sorted(tasks, key=lambda task: rank[task], reverse=True)

processor_available_time = {p: 0 for p in processors}
task_schedule = {}

for task in task_order:
    best_processor = None
    best_start_time = None
    best_finish_time = float("inf")

    for processor in processors:
        data_ready_time = 0

        for parent in predecessors[task]:
            parent_processor = task_schedule[parent]["processor"]
            parent_finish = task_schedule[parent]["finish"]

            if parent_processor == processor:
                transfer_time = 0
            else:
                transfer_time = communication_cost[(parent, task)]

            data_ready_time = max(data_ready_time, parent_finish + transfer_time)

        start_time = max(processor_available_time[processor], data_ready_time)
        finish_time = start_time + computation_cost[task][processor]

        if finish_time < best_finish_time:
            best_processor = processor
            best_start_time = start_time
            best_finish_time = finish_time

    task_schedule[task] = {
        "processor": best_processor,
        "start": best_start_time,
        "finish": best_finish_time,
    }
    processor_available_time[best_processor] = best_finish_time

print("向上排序值：")
for task in task_order:
    print(task, rank[task])

print("\n调度结果：")
for task in task_order:
    item = task_schedule[task]
    print(
        task,
        "->",
        item["processor"],
        f"{item['start']} ~ {item['finish']}",
    )

makespan = max(item["finish"] for item in task_schedule.values())
print("\nMakespan:", makespan)

可能输出：

向上排序值：
T1 24.0
T2 16.0
T3 11.5
T4 5.5

调度结果：
T1 -> GPU 0 ~ 4
T2 -> CPU 6 ~ 12
T3 -> GPU 4 ~ 7
T4 -> CPU 12 ~ 17

Makespan: 17

这和前面的手工分析一致。

13. HEFT 的时间复杂度

HEFT 的复杂度主要来自两个阶段。

排序阶段需要计算任务的向上排序值。对于 DAG 来说，可以通过递归记忆化或逆拓扑顺序完成，复杂度大致与任务数和边数相关：

$$
O(|V|+|E|)
$$

调度阶段中，每个任务都要尝试每个处理器。若使用简单追加式调度，复杂度大致为：

$$
O(|V||P|)
$$

如果使用插入式调度，还需要检查处理器时间表中的空隙，复杂度会更高。假设每个处理器上的已调度任务数量最多为 $|V|$，调度阶段可能达到：

$$
O(|V|^2|P|)
$$

即便如此，相比穷举所有任务与处理器组合，HEFT 仍然非常高效。

14. HEFT 的优点

HEFT 的优点很明显：

• 思想简单，容易实现。
• 同时考虑任务依赖、处理器异构性和通信开销。
• 通过向上排序值近似抓住关键路径。
• 贪心调度速度快，适合作为基线算法。
• 在很多静态 DAG 调度问题上表现稳定。

所谓静态调度，是指任务图、执行时间和通信代价在调度前大致已知。HEFT 正适合这类场景。

15. HEFT 的局限

HEFT 也有一些明显局限。

第一，它是启发式算法，不保证全局最优。

HEFT 每次只选择当前任务的最早完成处理器，但有时当前看起来最优的选择，会影响后面更重要任务的安排。

第二，它依赖代价估计。

如果任务执行时间和通信时间估计不准，向上排序值和最早完成时间都会受影响。现实系统中，GPU 负载、网络拥塞、缓存状态都可能导致代价波动。

第三，它主要面向静态 DAG。

如果任务是动态到达的，或者运行时才知道新的依赖关系，就需要 HEFT 的动态变体，或者使用运行时调度算法。

第四，它的目标通常是 makespan。

但有些场景更关心吞吐量、能耗、成本、截止时间或公平性。此时需要修改目标函数，或者使用其他调度算法。

16. HEFT 和其他调度方法的关系

可以把 HEFT 放在任务调度算法的谱系中理解：

方法	核心思想	适用特点
FCFS	先来先服务	简单，但不考虑依赖和异构性
Min-Min	每次选全局最小完成时间的任务	适合独立任务，可能偏向短任务
Max-Min	优先调度最长任务	可缓解长任务拖尾
Critical Path	优先关键路径任务	强调依赖链
HEFT	向上排序值 + 最早完成时间	适合静态异构 DAG
CPOP	同时考虑向上和向下排序值	强调关键路径处理器选择

HEFT 的特点是把“任务优先级”和“处理器选择”分开处理：

rank_u 决定先调度谁
EFT 决定放到哪里

这让它既比简单规则更全局，又比复杂搜索算法更轻量。

17. 实践建议

在实际使用 HEFT 或实现类似调度器时，可以重点关注以下几点：

1. 先确认任务依赖图必须是 DAG，不能有循环依赖。
2. 计算时间和通信时间最好来自实际 profiling，而不是凭感觉估计。
3. 如果通信代价很高，尽量关注父子任务是否被频繁分配到不同处理器。
4. 如果处理器经常出现空洞，应该实现插入式调度，而不是简单追加。
5. 如果任务运行时间波动很大，可以考虑运行时重新调度或动态 HEFT。
6. 如果目标不只是 makespan，需要把能耗、成本或截止时间加入评价函数。
7. 先用小 DAG 手工验证，再扩展到真实工作流。

18. 总结

HEFT 是异构计算中非常经典的 DAG 任务调度算法。

它的核心可以概括为两句话：

• 用向上排序值 $rank_u$ 估计任务到出口任务的平均关键路径长度，从而决定任务优先级。
• 按优先级依次调度任务，每次选择能让当前任务最早完成的处理器。

从公式上看，它的关键是：

$$
rank_u(v_i)=\overline{w_i}+
\max_{v_j \in succ(v_i)}
\left(\overline{c_{i,j}}+rank_u(v_j)\right)
$$

以及：

$$
EFT(v_i,p_k)=EST(v_i,p_k)+w_{i,k}
$$

理解 HEFT 后，再看异构计算、边缘计算、工作流调度、云任务编排、CPU-GPU 协同调度等问题，会更容易抓住本质：调度不是单纯地把任务放到最快设备上，而是在依赖、通信和资源竞争之间做平衡。

参考文献

本文主要参考了以下资料：

1. Haluk Topcuoglu, Salim Hariri, Min-You Wu, “Performance-effective and low-complexity task scheduling for heterogeneous computing”, IEEE Transactions on Parallel and Distributed Systems, 2002.
2. Heterogeneous earliest finish time, Wikipedia: https://en.wikipedia.org/wiki/Heterogeneous_earliest_finish_time
3. Hamid Arabnejad, Jorge G. Barbosa, “List Scheduling Algorithm for Heterogeneous Systems by an Optimistic Cost Table”, IEEE Transactions on Parallel and Distributed Systems, 2014.
4. Luiz F. Bittencourt, Edmundo R. M. Madeira, “HCOC: a cost optimization algorithm for workflow scheduling in hybrid clouds”, Journal of Internet Services and Applications, 2011.