网格调度.ppt

1、网格调度,网格调度,概念,调度模型,机器选择,常用调度算法,1 网格调度概念,问题：为什么需要网格调度？ 1. 一方面，应用领域需要计算机解决的问题越来越复杂、规模越来越大。 2. 另一方面，网格系统包括各种异构资源，每种资源都有自己的特性。 3.如果映射大部分任务在不合适的机器上运行，将花费大量的额外开销，并引起计算系统机器性能的严重下降。,1 网格调度概念,任务子任务1 机器1 子任务2 机器2 子任务3 机器3 网格调度首先把应用程序分解为多个任务或子任 务，根据任务的需求，发现满足条件的计算资源，然 后根据主要因素或选择策略选择一个最合适的资源，以便最小化应用程序的执行时间或完成时间。

2、,2 网格调度模型,2 调度模型（1）,应用程序分析模块 应用程序类型：计算密集型、通信密集型和计算通信相对均衡型。 类度分析可以确定程序中并行任务的多少、并行化任务的特点等。 资源特性分析模块 首先分析网格资源静态信息，得到不同资源的CPU体系结构、操作系统和应用接口等方面的异同信息。 然后调用网格计算中间件的资源监测模块，监测计算资源的可用性以及计算资源的动态特性，如计算资源的开启状态，节点可用内存大小等。,2 调度模型（2）,应用程序分解模块 1.首先利用“应用特性描述表”分解一个应用程序成很 多子任务，这些子任务之间通常会包括依赖或优先约 束关系。 2.然后基于“机器特性描述表”将分解

3、的子任务构成适 合不同机器特性的若干任务集合，目标是让任务能够 在适合自己的运行节点上运行。 机器选择 1 复杂的应用问题往往包含多方面的异构型，不同性质 的应用适合在不同的体系结构上运行。 2.将网格资源划分为若干个资源子集，并选择一个或多 个合适的子集为一个具体应用执行。,2.调度模型（3）,任务映射 1.在选定的机器集合上，为应用程序的各个任务匹配机器。 注意：匹配是一个逻辑上的过程，任务映射是一个静态的预分配过程，并不进行任务的传输。适合在批处理调度系统和静态调度系统中使用。 任务调度 1.将任务发送到指定机器上的执行队列内，是任务映 射的结果。进入执行队列的任务会被宿主机自动启 动执

4、行。 在动态调度系统中，任务映射、调度和执行均包含在任务调度之中。,2 调度模型（4）,任务映射和任务调度模块统称为任务调度器。 机器选择模块和任务调度器统称为网格调度器。 根据网格调度器的位置，将应用程序调度模型分成两种:中心式和分布式。,2 中心式网格调度模型,中间的网格调度器跟踪所有计算资源上的负载信息，独立的在计算资源范围内为应用作业找到合适的节点集合。,N个用户 1个网格调度器 K个虚拟群,2 分布式网格调度模型（1）,第一种：基于两层结构的调度模型 组成：N个LAN+1个WAN。 调度策略：每个LAN实现一个内部调度器和一个外部调度组件。当一个外部调度组件收到一个计算请求，它基于“

5、竞标、拍卖”选择一个LAN，再由LAN内的内部调度器进行调度。,2 分布式网格调度模型（2）,第二种：多个网格调度器和一个中心管理节点 当一个网格节点收到作业时，中心管理节点根据搜索开销，确定作业迁移到周围那些网格调度器是可行的，从中选择最适合的网格调度器。 此种方法的负载平衡属于静态的，适用于作业提交点服从均匀分布的情况。,2 分布式网格调度模型（3）,第三种：树形结构 1） 将所有节点构成一棵树。 2）根节点的性能是为最大，任一节点性能不大于其父结点。 3）任意中间节点需要了解其子树包含的计算能力，根节点需要掌握网格全局的调度信息。 4）任一中间节点的失败，均会导致该结构分裂成2个独立的调

6、度空间。（从这一点上来说，树结构不是合理的拓扑结构）,2 分布式网格调度模型（4）,第四种：非完全分布的、无中心网格调度模型 特点：每个GS只和若干个GS相邻。结过n(n=1)步每个GS都能把任务调度到其余的GS中。 优点：容易扩充节点。一个GS失效时，不影响其他的GS调度。 缺点：需要复杂的调度策略、负载平衡与迁移机制。,3 机器选择,根据不同的性能指标要求（如执行代价、执行时间或通信成本等），为一个应用选择一个合适的异构/同构机器集合。 常用的机器选择方法 优化选择理论（OST） 增强优化选择理论（AOST） 异构优化选择理论（HOST） 基于模糊聚类的机器选择算法,3 优化选择理论(OS

7、T),OST算法用在可用机器数量不受限制前提下. 把程序应用代码分解成m个相同大小的、没有重叠的程序模块，每个模块内具有相同的内在并行性. OST的目标：为每个程序模块中的各个代码指派到特性匹配的机器上，以获得优化的性能。,3 增强优化选择理论(AOST),使用与OST相同的代码分解方法，但考虑到可用机器数量有限的情况。 为每种类型的程序代码提供服务的机器数量是有限的。 在OST和AOST中，一个应用分解的程序模块是顺序执行的。,3 OST/AOST算法应用,OST/AOST算法的应用分解过程,单指令多数据,多指令多数据,向量类型,3 异构优化选择理论（HOST）,是对AOST算法从两方面的扩

8、展。 为考虑了一个应用程序分解的程序模块可能存在并行性问题，并将程序模块间的依赖关系用有向图表示。 考虑了在不同机器上使用不同的任务映射技术来改进机器的选择性能。,3 异构优化选择理论（HOST）,作业,把作业分解成串行执行m个子作业，每个子作业分解成可并行执行的n个程序模块，每个程序模块分解成可并行执行的代码块。,3 机器选择算法优化（1）,不管是OST、AOST还是HOST算法都没有考虑到节点间的通信问题，而且调度器是中心式的。 网格计算环境的优化选择要分几种情况考虑 通常使用的性能指标 1.计算时间 2.通信时间,3 机器选择算法优化（2）,最大计算能力算法 1.目标是使得应用程序的总体

9、执行时间最小。 2.为应用的不同类型代码选择最合适的机器。 3.适合计算密集应用。 最大通信能力算法 1.目标是最大化有效通信能力。 2.使得任何两个被选择的节点间具有最小有效通信带宽。 3.适合通信密集应用。,3 机器选择算法优化（3）,优化的平衡通信与计算 考虑通信与计算两个计算性能指标，根据不同应用调节“计算/通信”因子（通常会优先考虑计算性能指标，然后再考虑通信性能指标）。 基于模糊聚类的机器选择 1.将上述三者有机结合起来，通过一个因子来控制机器选择的结果 2.将全部可用网格计算节点使用模糊聚类方法划分为不同的逻辑分组，每个分组称为一个逻辑机群。,3 基于模糊聚类的机器选择（1）,逻

10、辑分组表示机器性能贴近度，用“截值”实现。 直观的，可以用一个全连通图表示。从全连通图中去掉小于的边，得到的连通子图顶点就是逻辑机群。 针对计算性能或通信性能，都可以选取合适的值，同时考虑计算或通信性能时，贴近度矩阵的元素值可以采用海明贴近度公式进行计算。,3 基于模糊聚类的机器选择,当取值越大，组内性能就越接近。当=1时，每组内部节点性能相同；如果希望全部节点参与任务调度，可以取值为0.,2.5,3.0,3.8,2.0,3.5,4.1,54,49,58,66,7.8,7.5,（a）逻辑分组G1 （b）逻辑分组G2 （3）逻辑分组G3 G=2.0，3.0，3.5，2.5，4.1，54，3.8，

11、49，66，58，7.8，7.5 =0.8,4 调度算法,调度算法,独立任务调度算法,依赖任务调度的算法,经济学原理调度算法,动态任务映射算法,批模式任务映射算法,静态任务映射算法,调度算法分类,4 动态任务映射算法（MCT）,最小完成时间（MCT）启发式算法 1.分配任务给具有最小（或最早）完成时间的机器。 2.优点：机器间的负载将趋于平衡 3.缺点：不保证任务指派给执行最快的机器，从而潜在增加了全部任务的最大完成时间。,4 动态任务映射算法（MET）,最小执行时间（MET）启发式算法 1.分配任务给执行最快的机器。 2.优点：MET保证每个任务的执行都花费最少的时间。 3.缺点：大多数任务

12、在几个性能最好的机器上执行，会引起机器间的负载严重不平衡。,4 动态任务映射算法（SA）,切换算法（SA） 1.依赖负载在机器间的分布情况，周期性地使用MCT和MET算法 2.具体实现： 定义负载平衡指标P=最小的机器就绪时间/最大的机器就绪时间;设定一个阀值，通过比较P与其的关系，在MCT和MET间切换。,4 动态任务映射算法（KPB/OLB/UDA）,KPB（K-Percent Best Heuristic）算法 只使用全部可用机器的一个子集来进行任务映射。 机会均载平衡（OLB）算法 分配任务给下一个就绪的机器，而不考虑机器的期望 完成时间。 当映射任务给机器时，不考虑任务的执行时间，如

13、果 多个机器可供使用，可随机选择。 用户导向指派（UDA）算法 不考虑任务的到达顺序，而是将已经到达的任务指派 给具有最小期望完成时间的机器，而不考虑机器是否 可用。,4 批模式任务映射算法,在批处理模式调度算法中，调度集合在一个预先定义的间隔之后进行映射。 两种策略： 1.固定时间间隔策略：不管调度集合(SS)中用多少任务，只需要到达一个规定时间间隔后就对SS中的任务进行映射。 2.规定任务数策略：当SS中的任务数达到一定规定量或全部任务已到达SS时，就对SS进行映射。,4 批模式任务映射算法（1）,快速贪吃算法（Fast-Greedy） 根据到达顺序依次从SS中选择一个任务，计算该任务的期

14、望执行时间，然后将具有最小期望完成时间的机器指派给这个任务。如此重复，直到全部任务指派完毕。,4 批模式任务映射算法（2）,Min-min算法 1.目的：将大量的任务指派给不仅完成它最早，而且执行它最快的机器，以使全部任务完成时间最小。 2.过程：计算每个任务在各个机器上的期望完成时间，获得每个任务的最早完成时间及其机器，再将具有最小最早完成时间的任务指派给获得它的机器，指派完成后更新机器就绪时间，并删除已分配的任务，如此重复，直到全部任务都被分配为止。,4 批模式任务映射算法（3）,Max-min算法 先算出每一个作业在每个机器上的最早完成时间。在所有作业中，拥有最大最早完成时间的作业将被选

15、出来，分配到对应的机器执行，将这个作业删除，重复上述工作，直至所有作业都被分配。优先考虑长任务。,4 批模式任务映射算法（4）,最大时间跨度算法（Max-Int） 1.基本思想：最好的调度应该使得全部任务的完成时间最小。 2.吸取了Min-min和Max-min的优点。除了利用历史调度信息之外，还利用预测信息来减少调度任务的时间。,4 批模式任务映射算法（5）,老化算法 1.在批模式算法中，可能会出现一个任务总得不到执行的情况，则称之为“饥饿任务”，在实际应用中是不允许的。 2.为了减少饥饿任务，引入任务老化方法，将上次没有得到执行的任务在下次重新映射时让它变老，目标是提高该任务的执行优先级。

16、 3.在Min-min和Max-min算法中引入老化因子。,4 静态任务映射算法,静态启发式任务映射算法具有充足的时间利用启发式信息，提高算法的调度性能。 在实时性要求不高的计算系统中，使用静态映射算法可能更好。 静态算法要求参与映射的任务集合是预知的，在全部机器上的所有任务的期望执行时间的估计值也是已知的，并具有合理的精度。实际应用中的系统上述条件很难达到。,4 静态任务映射算法（1）,遗传算法（GA） 1.遗传算法可以用来解决并行处理问题，如调度问题、数据组织和分发、通信和路由等，是一种有效的解决最优化问题的方法。 2.发展成为一种通过模拟自然进化过程解决最优化问题的计算模型。,4 静态任

17、务映射算法（2）,模拟退火算法（SA） 1.模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。退火过程的最低能量的基态相当于全局最优解。 2.它的最大优点是能避免问题的解落入局部最小。,4 静态任务映射算法（3）,最陡爬山/最陡下降算法 1.最陡下降算法沿迭代点的负梯度方向进行搜索，开始优化速度较快，接近极小点时，优化速度极为缓慢。 缺点：只能获得局部最优解。 2.最陡爬山算法与上者相反，缺点一样。,4 依赖任务的启发式调度算法,目前，同构均一计算机系统上的任务映射和调度算法研究相对成熟，一些启发式映射策略已经用来调度依赖任务到同构机器集合上。 异构机器集合上的依赖任务调度算法则研究较少。分代算法（Generation Scheduling,GS）是典型算法代表。,4 分代调度算法,思想：将依赖任务集合转换成若干内部包含独立任务的任务集合。,形成调度问题 并初始化,独立任