第9章静态负载分配.ppt

第9章静态负载分配 分布式系统 九 08 05 2 负载分配 分布式系统的资源管理模块 主要实现合理和透明地在处理器之间重新分配系统负载 以达到系统的综合性能最优 最小的总体系统执行时间最大的总体系统输出 大致分为静态负载分配和动态负载分配2大类情况 静态负载分配 进程运行前进行处理器分配 运行中不作调整 直到运行结束 确定性分配 动态负载分配 进程运行中动态进行处理器分配 且可以不断调整 负载均衡 分布式系统 九 08 05 3 负载分配分类 进程和处理器在负载分配时是M N 多对多 的关系 有多种负载分配算法分类 分布式系统 九 08 05 4 负载分配分类 其它的负载分配算法分类 单个和多个应用程序抢占式的和非抢占式的自适应的和非自适应的 分布式系统 九 08 05 5 静态负载分配 根据先验知识在执行前调度一个任务 进程 集合 使它们总体上在各个目标PE上有最小的执行时间 代价 静态负载分配问题也称为任务调度问题 它涉及到3方面的要素 处理器互连 任务划分和任务分配 负载分配有时即使加入执行开销和通信开销等假设仍然是一个NP完全问题 很难求得一个明确的最优解 我们总是用各种方法试图求得一个次优的解 或者加入一些特殊的约束以求得最优解 分布式系统 九 08 05 6 任务 进程 的图模型表示 任务优先图 任务优先图G是一个有向无环图 DAG x y 任务 优先顺序 x 任务在处理器上的执行代价y 在不同处理器上启动后续任务所需的时间 处理器间通信代价 分布式系统 九 08 05 7 任务的图模型表示 任务相互关系图 2个处理器的情况 x y z z 任务 通信 x y 任务在不同的处理器上的执行代价z z 在不同处理器上和在相同处理器上的任务间通信代价 通常z 可忽略 分布式系统 九 08 05 8 处理器互连 a Illiac网格方案 16个PE的系统 2维节点度数 4网络直径 n 1 n元 常规2维网格的一半 分布式系统 九 08 05 9 处理器互连 b 圆环方案 16个PE的系统 2维节点度数 4网络直径 2 n 2 分布式系统 九 08 05 10 处理器互连 c 超立方体方案 16个PE的系统 节点度数 n网络直径 nn维 每维2个节点n维立方体是2个n 1维立方体互连而成 分布式系统 九 08 05 11 处理器互连 d WK网络方案 16个PE的系统 1层WK网络 2层WK网络 节点度数 4网络直径 n 1n层的WK网络由4个 n 1 层的WK子网络组成 每个子网络是一个虚拟节点 分布式系统 九 08 05 12 任务划分 将一个大的任务 应用程序 分解成一些小的子任务类 每个子任务类作为分配给同一个PE执行 也称任务聚类 根据子任务类中基本任务单元 粒度 的大小 任务划分算法可分成 细粒度 中粒度 和粗粒度 粒度太大 会降低并行度 粒度太小 子任务进程的切换和它们间的通信代价会增加 任务划分的主要目标是尽可能地增加并行度和降低通信代价 寻找一个适中的粒度 分布式系统 九 08 05 13 任务划分 大体上有三种方法的任务划分 水平或垂直划分 根据任务优先图的关键路径 最长路径 垂直进行或任务分层水平进行 通信延迟最小划分 将通信频繁的基本任务节点归成一类 让其在同一个PE上执行 以最大限度地降低通信代价 此方法需要顾及并行任务串行化所带来的损失 任务复制 通过在PE上复制任务来降低通信代价 同时保留任务的并行性 此方法会增加PE的储存空间开销和PE间同步的开销 通常任务划分的子任务类数目等于PE的个数 以简化后续的任务分配 分布式系统 九 08 05 14 任务划分 线性和非线性 任务划分后 如果至少有一个子任务类中包含两个独立的任务 则划分是非线性的 否则划分是线性的 所有独立的任务被划分在不同的任务类中 如 T1 T2 T3 d1 d2 a 线性划分 T1 T2 T3 d1 d2 b 非线性划分 分布式系统 九 08 05 15 任务划分 衡量划分 任务优先图可以认为是许多分叉和合并操作的集合 a 分叉 c1 x v1 l1 b 合并 c2 v2 l2 cn vn ln c1 v1 l1 c2 v2 l2 cn vn ln x 分叉x 或合并x 的粒度是 g x min ck max lk 0 k n0 k n任务优先图G的粒度是 g G min g x x G 分布式系统 九 08 05 16 任务划分 衡量划分 如果g x 1 g G 1 合并或分叉 或图G 就是粗粒度的 否则操作或图就是细粒度的 如下图的非线性划分是粗粒度的 g x 2 4 3 2 T1 T2 T3 1 1 分布式系统 九 08 05 17 任务划分 衡量划分 可以证明 如果任务优先图G是粗粒度的 则其任何非线性的子任务类都可以转换 再划分 成具有更少或相等执行时间的线性分类 即 粗粒度的任务优先图其线性划分性能优于任何非线性划分 然而 如果任务优先图G是细粒度的 可能存在 也可能不存在一个非线性划分优于线性划分 分布式系统 九 08 05 18 任务划分 衡量划分 例 4 3 2 T1 T2 T3 1 1 a 线性划分 4 3 2 T1 T2 T3 1 1 b 非线性划分 b 是粗粒度的 其非线性划分b 的执行时间是9 线性划分a 的执行时间是7 分布式系统 九 08 05 19 任务分配 将任务划分后的子任务类分配给PE的过程 在n个子任务类和n个PE间作映射分配 共有Cnn n 种分配方法 根据PE的存储容量 处理能力和PE间的通信距离各映射分配方法会产生较大差异的效果 为了减少任务分配的复杂性 可以作一些假设 PE的存储容量无限每个PE有相同的处理能力忽略通信距离所造成的网络拥塞等 分布式系统 九 08 05 20 任务调度 静态负载分配 方法 基于任务优先图的任务调度算法 算法1 任务优先图是一棵树 算法2 只有两个处理器基于任务相互关系图的任务调度任务调度评测使用其它模型和技术的任务调度Stone网络流量技术实现最优任务调度算法实时定期任务调度速率单调优先调度期限驱动调度 分布式系统 九 08 05 21 基于任务优先图的任务调度 对任务优先图 可以用G V A 来描述 其中V是节点的集合 表示任务集 A是弧线的集合 表示任务间的优先关系 如 u v是V中的节点 任务 u v 是A中的弧线链接 对于每个节点 任务 和链接都定义了代价函数w 其中w u 0 表示任务u在处理器上执行的时间代价 所有处理器是相同的 w u v l l 是链接的代价 其中l 是在同一处理器内的通信时间代价 l是处理器间的通信时间代价 u和v分配在不同处理器 w u w u v u v 分布式系统 九 08 05 22 基于任务优先图的任务调度 几点约束 处理器的处理能力是相同的 不考虑处理器互连 即忽略网络拥塞 也即处理器间的通信代价对所有处理器是一样的 相对l l 是非常小的 可以忽略 因此w u v l w u w u v u v 分布式系统 九 08 05 23 基于任务优先图的任务调度 甘特图 GanttChart 任务分配表示 横坐标是处理器 纵坐标是时间 方块是任务的开始 持续和结束时间 T1 T2 T3 T4 T5 时间 0 分布式系统 九 08 05 24 基于任务优先图的任务调度 任务优先图的甘特图 GanttChart 任务分配表示例 T1 T3 时间 12 2 1 T1 1 4 2 4 T2 T3 T4 T5 1 1 2 2 T2 T5 T4 1 2 a 任务优先图 b 2个处理器的甘特图 分布式系统 九 08 05 25 基于任务优先图的任务调度 在不同处理器上分配任务时 通信的开销对任务调度有较大影响 如 T1 T2 T3 d d T1 d a 任务优先图 b 调度结果1 T2 T3 T1 T2 T3 c 调度结果2 T1 T1 T2 T3 d 调度结果3 分布式系统 九 08 05 26 基于任务优先图的任务调度 只有当通信代价较小时 将任务分配到不同的处理器是比较合适的 图c 任务调度总是尽量将任务分配到不同的处理器以增加并行度 同时尽量降低通信的开销 然而二者有时是无法满足的矛盾 需要某种程度的折中 有时采用任务复制的方法实现可以得到一个很好的效果 图d 分布式系统 九 08 05 27 基于任务优先图的两个最优调度算法 为了实现最优 两个算法各自有约束条件 算法1 任务优先图是一棵树 算法2 只有两个处理器 而且两个算法都假设通信代价可以忽略和优先图中每个任务节点的执行时间是一样的 两个算法都是最高级优先方法 即根据任务节点的等级来选择分配节点 分布式系统 九 08 05 28 最优调度算法1 具体算法 任务节点的等级等于它到根节点的距离加1 等级越高 优先级就越高 相同等级的节点中 所有先导节点都已执行的节点先被选中 若有多个节点符合条件2 则随机选择 T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12 T13 分布式系统 九 08 05 29 最优调度算法1 在3个处理器上实现的例 T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12 T13 T1 T4 T6 T8 T11 T13 T2 T5 T9 T12 T3 T7 T10 时间 0 a 任务优先图 b 算法实现的甘特图 分布式系统 九 08 05 30 最优调度算法1 使用一个就绪队列实现算法 就绪队列按优先级排列那些可以被选择分配给处理器的任务节点 T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12 T13 就绪队列状态 T1 T2 T3 T4 T5 T7 T9 T10 T12 T4 T5 T7 T9 T10 T12 T6 T9 T10 T12 T8 T12 T11 T13 等级54321 分布式系统 九 08 05 31 最优调度算法2 具体算法 将k个终止节点依次标记为1 k 标记越大 优先级越高 寻找所有后续节点均被标记的节点 根据这些节点的后续节点排列的字典升序依次标记这些节点 重复2 3直到所有节点标记完毕 根据优先级的高低顺序依次将任务分配给2个处理器 11 T9 9 10 T10 7 T11 6 T6 T7 8 T8 4 T4 5 T5 2 1 T1 T2 3 T3 分布式系统 九 08 05 32 最优调度算法2 例的标记结果 T1 T2 T3 T4 T5 T6 T11 T8 T7 T10 T9 11 T9 9 10 T10 7 T11 6 T6 T7 8 T8 4 T4 5 T5 2 1 T1 T2 3 T3 T9 T7 T11 T5 T3 T1 T10 T8 T6 T4 T2 a 任务优先图 b 算法实现的甘特图 2个处理器 时间 0 分布式系统 九 08 05 33 最优调度算法2 本算法有问题的 思考为什么需要是2个处理器的限制 还需要加入什么限制 算法才没有问题 提示比如 任务优先图中 去掉T10 算法会出现错误 分布式系统 九 08 05 34 基于任务相互关系图的任务调度 假设任务关系图由无向图Gt Vt Et 表示 其中Vt是任务节点集合 Et是边集合 处理器关系图由无向图Gp Vp Ep 表示 其中Vp是处理器集合 Ep是边集合 处理器间的通信通道 一般来说 如果任务划分已经完成 则 Vt Vp 我们进行映射分配M Vt Vp及执行时间估计 设w u 和w u v 分别是节点u和连接 u v 的代价 处理器p Vp的计算负载 Comp p w u M u pu Vt通信负载 Commp p w u v M u p M v u v Et 分布式系统 九 08 05 35 基于任务相互关系图的任务调度 一个应用程序总的计算和通信负载 Comp Comp p w u M u pp Vpp Vpu VtComm 1 2 Comm p 1 2 w u v M u p M v p Vpp Vp u v Et总的程序执行时间估计 T max Comp p Comm p p Vp 是依据每个PE的执行速度设定的调节比例 是依据每个通信信道的通信速度和通信进程间的距离设定的调节比例 分布式系统 九 08 05 36 基于任务相互关系图的任务调度 理想情况下 任务关系图中相邻的节点应被分配在相邻的处理器上 以减少处理器间长距离的通信 因此 评估映射质量的一个指标是任务关系图Gt的边映射到处理器图Gp的边的数目 这个数目称为映射的势 映射的势 Gt的边数 映射的势越大则越理想 分布式系统 九 08 05 37 基于任务相互关系图的任务调度 下例中 映射的势是8 共13条边 映射的势并不能完全反映出映射的质量 这主要表现在势以外的边所对应的处理器的距离 图中虚线的距离 1 3 4 5 6 2 7 8 9 1 2 3 4 5 6 7 9 8 分布式系统 九 08 05 38 基于任务相互关系图的任务调度 P203使用嵌入技巧来衡量利用任务相互关系图分配任务到处理器关系图时的理想程度 其目标 发现一个嵌入 有最小膨胀 最大扩大和最小拥塞 即上图中 虚线的数目最少 且最短 任务节点到处理器节点的数目最多 经过一个处理器边 通信链路 的任务边数最小 书中错误 P203 第8行 嵌入的负载 是Gt分配给Gp中任意 分布式系统 九 08 05 39 网络流量技术实现最优任务调度 Stone网络流量算法 一个在双处理器且处理器有不同处理能力的系统中对任务相互关系图的最优调度算法 图的分割 带权分割 分割为图中边的子集 1 删除这些边后使图不连通 2 这些边的任何子集都不满足上一点 带权图的分割为带权分割 分割后的2部分中各包含s和t的分割 称为s t分割或s t带权分割 分布式系统 九 08 05 40 网络流量技术实现最优任务调度 网络的分割 带权分割 边的流量不能超过边的容量 网络的流量不能超过分割的容量 除起始节点和终止节点 节点的流入流量等于节点的流出流量 起始节点只有流出 终止节点只有流入 分布式系统 九 08 05 41 网络流量技术实现最优任务调度 Ford Fulkerson最大流 最小割理论 最小的带权分割就是最大的网络流量 根据容量图 分布式系统 九 08 05 42 网络流量技术实现最优任务调度 确定了最大的网络流量就确定了最小的带权分割 确定网络最大流量的算法 使网络流量最大化的进程方法 P207 从任意一种流开始 寻找可能存在的增加路径 augmentingpath 在该路径上 对于前向链接 它有富余的容量 对于后向链接 它有反向的流量 消除这些增加路径 对于前向链接 增大实际的流量 对于后向链接 减少反向的流量 直到网络中没有增加路径为止 此时 网络的流量最大 它的一个分割 其各链接边的容量等于实际流量 就是最小带权分割 书中错误 P207 倒数第5行 除了 u2 t 路径 分布式系统 九 08 05 43 网络流量技术实现最优任务调度 利用网络最大流量就是图的最小带权分割技术 实现对2个处理器的最优任务分配 任务相互关系图 在2个处理器上的执行代价 表示不能在该处理器上执行 在不同处理器上的通信代价 分布式系统 九 08 05 44 网络流量技术实现最优任务调度 分别将2个处理器作为s和t加入任务关系图中 增加s和t到各任务的边 共2n条 边的权值为任务在该处理器上的执行代价 形成任务分配图 任务相互关系图 任务分配图 分布式系统 九 08 05 45 网络流量技术实现最优任务调度 利用网络最大流量算法在网络流量图中寻找最大网络流量 以s为起点 t为终点 初始实际流量设为0 T2 T1 T4 4 0 8 0 9 0 2 0 t T3 s 3 0 4 0 4 0 5 0 0 7 0 7 0 3 0 分布式系统 九 08 05 46 网络流量技术实现最优任务调度 得到的最大网络流量 就是最小网络分割 也即任务的最优分配 最小分割的权重 各分割边的权之和 即任务分配后的最小代价 执行代价和通信代价 之和 T2 T1 T4 4 0 8 3 9 0 2 2 t T3 s 3 3 4 4 4 4 5 4 6 7 2 7 7 3 0 如图的最小代价是16 分配方案是T1 T2 T3 T4均在一个处理器s上执行 最小分割 分布式系统 九 08 05 47 网络流量技术实现最优任务调度 前述是一个利用网络最大流算法得到最小分割的方法 适合在计算机环境下编程实现 人工计算相当麻烦 一个可行的人工计算方法 笨 的 穷尽的方法 T1 T2 T4 4 8 9 2 t T3 s 4 3 4 5 7 7 3 34 38 33 16 可能的分割 分配 T1 T1T2 T1T3T1T4T1T2T3T1T2T4 T1T3T4T1T2T3T4 比较各种分割的权重 分布式系统 九 08 05 48 实时定期任务调度 实时定期任务 Ti 定期 间隔周期ti 出现 每次运行时间为ci 在下一次出现前 期限 即n ti 前一次任务必须运行结束 实时 处理器的整体利用率 n ci tii 0 分布式系统 九 08 05 49 实时定期任务调度 实时定期任务调度2个算法 单处理器 多个独立实时定期任务 速率单调优先调度有高速率 间隔周期小 要求的任务有高优先权 优先权是固定分配的 期限驱动调度离结束期限最近的任务有高优先权 优先权是动态分配的 2个算法都是基于优先权和抢占式的 分布式系统 九 08 05 50 实时定期任务调度 一个实时定期任务集合是可调度的 说明任务集中所有任务的期限要求都可以满足 在不同的实时定期任务调度算法下 一个实时定期任务集可能可调度 可能不可调度 可以证明 对期限驱动算法 一个任务集可调度的充分条件是 n处理器的整体利用率 ci ti 1i 0对速率单调算法 一个任务集可调度的充分条件是 n处理器的整体利用率 ci ti n 21 n 1 i 0n为任务个数 如n 1时 限度为1 n 2时 限度为0 828 n 3时 限度为0 779 分布式系统 九 08 05 51 实时定期任务调度 如 2个实时定期任务开始于同一时间T1 c1 3 t1 5T2 c2 3 t2 8整体利用率是0 975 如下图 T1 T2 0 0 c1 c2 5 10