调度优化：从单目标到多目标的探索

### 调度优化：从单目标到多目标的探索 #### 1. 可分负载调度基础 可分负载模型是许多调度问题的一种简单而有用的简化方式。以星形平台上独立任务的分布式计算执行为例，在不做任何简化时，这是一个可处理的问题，但已知的解决方案只是部分的，且计算复杂度较高。同时，通信和计算使用的线性成本函数以及同质通信模型，限制了这种方法的实际意义。 使用可分负载理论可以简化问题并完全解决它。通过可分负载简化，我们可以采用更复杂的模型，处理异构通信链路，或者在通信和计算中考虑延迟。这种新模型更现实，并且由于可分负载方法，仍然是可处理的。然而，一旦添加延迟或返回消息，问题的复杂度会迅速增加。 ##### 1.1 多轮算法的最大效益 多轮算法给原本就困难的问题带来了新的挑战。评估这类算法能在多大程度上改进解决方案是有价值的。有如下定理： **定理**：对于任何星形主从平台，若通信成本和计算成本均遵循线性或仿射模型，任何多轮调度对最优单轮调度的改进因子不会大于 2。 **证明**：设 S 是使用有限 K 轮的最优多轮调度。平台中有 m 个工作节点，主节点在第 k 轮为工作节点 i（1 ≤ i ≤ m）分配的负载比例为 αi(k)，S 的总完成时间记为 T。我们构建一个新的单轮调度 S′，主节点一次性向工作节点 i 发送比例为 $\sum_{k = 1}^{K} αi(k)$ 的负载（消息发送顺序任意）。在 S′ 下，主节点的通信时间不会超过 S。因此，在时间 T 之前，所有工作节点都将完成负载接收。并且，在 S′ 下，每个工作节点处理负载的时间不会超过 S（负载大小相同）。所以，单轮调度 S′ 的完工时间不大于 2T。 ##### 1.2 返回消息的影响 之前的讨论假设计算需要输入数据，但产生的输出可忽略不计，因此未考虑将输出传输回主节点。对于产生大输出（如加密密钥）的计算，这种假设可能过于严格。 现在考虑返回消息，假设输入和输出消息大小相同，即如果主节点 M 向工作节点 Pi 发送输入需要 ciαiWtotal 时间单位，那么 Pi 完成计算后将结果发送回 M 也需要相同的时间。通信介质假设为双向的（如今大多数网卡都是全双工的），主节点 M 可以同时发送和接收数据。 在最初的线性成本模型和单轮分配框架中，所有工作节点都参与工作，并且能够找到分配数据的最优顺序。但考虑返回消息后，会出现两个新问题： - 返回消息的顺序可能与分配顺序不同。 - 多个工作节点可能在整个计算过程中处于空闲状态。 有两种简单的排序策略： - FIFO 策略：返回消息的发送顺序与输入消息相同。 - LIFO 策略：返回消息的发送顺序与输入消息相反。 实际上，存在一些例子表明，返回消息的最优顺序既不是 FIFO 也不是 LIFO，或者最优完工时间是在有空闲处理器的情况下达到的。最佳的 FIFO 和 LIFO 分配很容易计算，因为所有处理器都参与工作，它们按照通信时间的非递减顺序服务，并且在初始消息和返回消息之间不会空闲。此外，在总线形平台的情况下，所有 FIFO 调度都是最优的。 单轮数据分配会导致较长的等待时间，而多轮分配可以改善这一缺点。遗憾的是，线性成本模型的任何最优多轮分配都需要无限轮数。因此，需要仿射成本模型来获得现实的解决方案，但此时问题变得非常难以解决甚至近似。 以下是一个简单的表格总结不同调度策略的特点： | 调度策略 | 特点 | | --- | --- | | 单轮调度 | 计算复杂度相对低，但可能有长等待时间 | | 多轮调度（线性成本） | 理论上可优化，但需无限轮数 | | 多轮调度（仿射成本） | 更现实，但问题难解决 | | FIFO 策略 | 顺序相同，总线形平台最优 | | LIFO 策略 | 顺序相反 | #### 2. 多目标调度的动机与基础 现代系统的复杂性不断增加，仅用一个变量来描述具有多个用户的异构系统的性能是片面的。多目标调度旨在同时优化多个目标，能够明确地对各种性能指标进行建模、优化，并找到它们之间的权衡。 ##### 2.1 一个故事引发的思考 曾经，一家软件公司的经理让一位开发者（“兔子”）实现一个在并行超级计算机上运行快速的程序。这个程序非常出色，兔子在多年的性能竞赛中获胜，客户也很满意。并且，兔子多年来成功地将程序适配到了不同代的并行平台上。然而，随着系统逐渐演变为由长距离连接的异构组件组成，兔子的程序虽然仍然最快，但无法应对处理器崩溃的问题，而这种情况在大规模异构计算机上越来越频繁。 与此同时，另一位开发者（“乌龟”）编写了一个非常简单的程序，该程序几乎能在所有崩溃情况下提供解决方案，它只使用最可靠的处理器。当然，这个解决方案速度较慢，但客户仍然满意。兔子努力开发了一个新版本的程序，其可靠性略低于乌龟的程序，但速度仍然快得多，客户对此也很满意。然而，几个月后，主要客户开始处理需要更高可靠性的关键应用程序，这次兔子太累了，无法再开发新版本的代码。逐渐地，兔子的代码被