并行系统中的资源管理与多处理器任务调度

# 并行系统中的资源管理与多处理器任务调度 ## 1. 并行系统调度问题概述 在并行系统中，任务调度面临着多种复杂情况。以下是一些特定条件下的调度问题： 1. 任意数量处理器，无优先级约束、无截止日期、无释放时间。 2. 任意数量处理器，存在入树或出树优先级，无截止日期、无释放时间。 3. 两个处理器，任意优先级，无截止日期、无释放时间。 然而，当处理器数量和优先级约束都为任意情况时，即使是可抢占任务，该问题也属于强NP难问题。 传统调度理论起源于多处理器系统中紧密耦合处理器较少的时期，那时处理器可视为全连接，通信开销可忽略不计。如今，并行系统常为包含众多通过网络连接的处理元素的多计算机系统，通信时间不可忽视。通信系统受多种互连特性影响，例如每个处理元素能否同时进行通信和计算、能否通过多个端口同时通信，以及消息传输可采用存储转发、电路交换等多种路由方法。因此，通信系统是多处理器计算机系统的重要组成部分，现代调度算法应将其纳入考虑。 ## 2. 资源管理的关键技术 ### 2.1 任务分配 调度可看作是任务分配和排序的过程。在某些情况下，分配比排序更重要。例如，图像处理应用可能由多个模块组成，这些模块在多处理器计算机系统中同时存在，连续帧流通过模块和处理器。为使通信路径较短且计算密集型模块由快速处理器执行，需要对模块进行良好的分配。由于不考虑活动的实际排序，优先级约束图简化为表示任务在运行时“累积”交互的无向图，即任务图。 下面更精确地描述分配问题。考虑一个并行应用，其模块（任务）相互通信，该应用将在一组通过网络连接的处理器上执行。定义如下： - \(X_{ik}\)：当任务 \(i\) 在处理器 \(k\) 上执行时，\(X_{ik}=1\)，否则 \(X_{ik}=0\)。二进制变量矩阵 \(X_{ik}\) 定义了任务到处理器的分配，需要确定其值。 - \(G_{ij}\)：从任务 \(i\) 传输到任务 \(j\) 的数据单元数量。 - \(C_{kl}\)：处理器 \(k\) 和 \(l\) 之间移动一个数据单元的互连相关通信成本。 - \(t_{ik}\)：任务 \(i\) 在处理器 \(k\) 上执行的成本。 问题是最小化以下目标函数： \[ \sum_{k = 1}^{m}\sum_{i = 1}^{n}(t_{ik}X_{ik}+\sum_{l = 1}^{m}\sum_{j = 1}^{n}\alpha_{ij}C_{kl}X_{ik}X_{jl}) \] 约束条件为： \[ \sum_{k = 1}^{m}X_{ik}=1, \quad i = 1, \cdots, n \] 上述目标函数的第一部分 \(\sum_{k = 1}^{m}\sum_{i = 1}^{n}t_{ik}X_{ik}\) 表示总计算成本，另一部分表示总通信成本。第二个方程保证每个任务恰好由一个处理器执行。该目标函数适用于无关处理器，但对于相同和均匀处理器，当所有工作都在最快处理器上执行时可达到最小值。因此，对于相同和均匀处理器，可将负载最重处理器的工作时间作为目标函数进行最小化： \[ \max_{i = 1}^{n}\left\{\sum_{k = 1}^{m}(t_{ik}X_{ik}+\sum_{l = 1}^{m}\sum_{j = 1}^{n}\alpha_{ij}C_{kl}X_{ik}X_{jl})\right\} \] 分配问题通常通过枚举搜索（如分支限界法）、针对该问题定制的启发式算法和元启发式算法来解决。 ### 2.2 任务嵌入 任务到处理器和互连网络的映射也称为嵌入。不过，文献中所考虑的嵌入问题与上述分配问题不同。设 \(G=(V, E)\) 为任务图，\(H=(P, N)\) 为一个图，其中节点 \(P\) 表示处理器，边集 \(N\) 表示互连网络。更精确地说，\(G\) 到 \(H\) 的嵌入 \(\langle I, b\rangle\) 包括将 \(G\) 中的节点映射到 \(H\) 中的处理器的映射 \(I\)，以及将每条边 \(e=(u, v)\in E\) 映射到连接 \(I(u)\) 和 \(I(v)\) 的路径 \(b(e)\) 的映射 \(b\)。嵌入的成本函数可以是： - 扩张：定义为任何 \(b(e)\) 的最大长度。 - 扩展：等于 \(\frac{|V|}{|P|}\)。 - 拥塞：是 \(N\) 中所有边 \(e'\) 上 \(\vert\{e\in E:e'\in b(e)\}\vert\) 的最大值，即分配给某条边 \(e'\) 的不同路径 \(b(e)\) 的最大数量。 一般来说，嵌入问题在计算上是困难的。例如，将循环图 \(G\)（环）嵌入到节点数 \(|V| = |P|\) 且拥塞为 1 的图 \(H\) 中，等价于哈密顿回路问题。 ### 2.3 负载均衡 负载均衡常被认为等同于调度，但这里并非如此。负载均衡是一种通过在处理器间均匀分配计算来最小化应用执行时间的方法。计算过程中创建的任务会产生额外负载，必须将其分配到处理器上。因此，负载均衡几乎必然涉及在线调度问题，因为无法假设对传入任务有完全的了解。负载均衡的第一步是负载共享，其目标是为每个处理器提供至少一些负载。 在实施任何负载均衡方法之前，需要解决几个问题： 1. **处理器负载度量**：可以是每个处理器的线程数、分配用于处理的数据单元数、处理器或内存利用率，或平均响应时间。例如，在并行分支限界算法中，负载可以用分配给处理器的搜索树节点数或从已分配给处理器的节点中预计出现的节点数来表示。不过，研究表明复杂的负载度量并不比简单的度量更有效。 2. **数据依赖**：当负载元素之间没有依赖关系时，可以任意移动它们。但在许多实际应用中存在依赖关系，需要采取措施避免相关（如相互通信）的负载元素过度分散。 负载均衡方法根据发起者的不同而有所差异： - 可以由工作耗尽的处理器发起。 - 也可以由出现新负载的处理器发起。 关于负载移动的决策可以全局进行，即利用整个系统状态的信息；也可以分布式进行，即基于本地可用信息。全局方法可扩展性差，中央“负载均衡器”容易成为瓶颈；而分布式方法由于信息不足可能导致负载不平衡。最后，还需要确定要传输的负载量，常见的两种分布式计算方法如下： - **最近邻平均法**：设 \(\lambda_i\) 表示负载均衡前处理器 \(P_i\) 的负载，\(\lambda_i^*\) 表示负载均衡后处理器 \(P_i\) 的负载，\(\Delta_i\) 表示 \(P_i\) 的邻居集合。该方法旨在使处理器的负载等于其自身和邻居的平均负载，即 \(\lambda_i^* = \frac{\lambda_i + \sum_{j\in\Delta_i}\lambda_j}{\vert\Delta_i\vert + 1}\)。为实现这一目标，处理器 \(P_i\) 向处理器 \(P_j\) 传输的数据量为 \(\frac{(\lambda_i - \lambda_i^*)q_j}{\sum_{j\in\Delta_i}q_j}\)，其中 \(q_j = \max\{0, \lambda_i^* - \lambda_j\}\)。 - **扩散法**：处理器 \(P_i\) 向 \(P_j\) 发送 \(\alpha(\lambda_i - \lambda_j)\) 个数据单元，其中 \(\alpha\in(0, 1)\)。经过负载均衡步骤后，处理器 \(P_i\) 拥有的数据单元数为 \(\lambda_i^* = \lambda_i + \alpha\sum_{j\in\Delta_i}(\lambda_i - \lambda_j)\)。 ### 2.4 循环调度 在许多应用中，循环被认为是并行性的自然来源。关键调度问题是确定块大小，即每次循环分配给处理器的循环数。需要考虑两个重要因素：实际循环执行时间的不可预测性，以及访问工作“分配器”（循环索引是关键部分）的开销。设 \(t\) 表示循环总数，\(m\) 表示处理器数量。以下是一些常见的循环调度方法： | 调度方法 | 描述 | 优点 | 缺点 | | --- | --- | --- | --- | | 静态块调度 | 每个处理器分配 \(t/m\) 个循环执行 | 访问循环调度器的开销低 | 处理器间负载平衡差 | | 自调度 | 每个处理器一次分配一个循环，空闲时获取新的迭代进行执行 | 负载平衡好 | 访问调度器的开销大，与循环数量成正比 | | 块自调度 | 每个处理器一次分配 \(k\) 个循环 | 结合了自调度和一定的批量处理优势 | - | | 引导自调度 | 请求工作的处理器分配剩余未分配循环的 \(1/m\) | 如果循环均匀，可实现良好平衡和低开销 | 循环不均匀时可能导致负载不平衡，计算末期可能出现调度器访问冲突 | | 梯形自调度 | 首次分配的工作块大小为 \(N_s\)，后续块按步长 \(d\