专题栏目:ARVRMR虚拟现实

网格调度算法是什么?

仿真网格中的一个关键问题是按照某种策略将一个仿真应用的各个任务合理地调度到网格计算结点上运行,以达到计算资源、网络资源优化配置的目的调度算法是网格计算的热点研究内容之一,出现了大量网格任务调度算法,对仿真网格调度算法的设计可以提供有益的参考。总的来说,这些调度算法所关注的任务之间的关系可以表示为3种类型:有向无环图(Directed Acyclic Graph,Dg)、任务交互图(Task Interactive GraphTIG)和独立任务。

DAG图描述的任务之间有先序关系和交互关系,图中节点的权表示任务的处理时间或者计算量,边的权表示任务间的通信时间或者通信量,边的方向表示任务之间的先序关系。TIG图是一种无向图,两个节点之间的边表示该两个节点对应的任务在执行时有通信关系,任务可以并发运行而不用关心任务之间的先序关系一个应用分解为相互独立并且不能再分割的任务称为独立任务。在这3种类型的任务调度算法中,独立任务调度算法是最基本的,许多面向DAG和TI表示的任务的调度算法是在独立任务调度算法的基础上进行改进,以便处理任务之间的先序关系或者交互关系。比如通过对DAG图分层,同一层中的任务之间没有先序关系,可以并行执行;再如基于遗传算法的DAG任务调度,与基于遗传算法的独立任务调度的主要区别在于对染色体编码时扩展基因片以反映任务之间的先序关系,在遗传操作时保持任务之间的先序关系。这些独立任务调度算法是网格任务调度算法的典型代表。

按照调度任务的方式,常见的网格任务的调度算法被分为两类:静态调度算法和动态调度算法。静态调度算法是指在任务执行之前组成该任务的所有子任务是已知的,调度策略也是确定的。动态调度算法则是在任务执行过程中有新任务到达,任务的调度策略也可能发生改变,比如自适应式任务调度方法会根据当前的资源状况和任务执行情况改变任务调度器的参数。动态调度算法又可以进一步分为批处理任务调度(Batchmode)和在线任务调度(On line mode)在线任务调度是指任务一到达调度器就将其度到某台机器上运行。批处理任务调度是指任务到来并不立即调度到机器,而是把任务收集起来组成一个任务集合,只有当预先定义的在特定时刻发生的调度事件到达时才对任务集合中的任务一起进行调度。

(1)在线动态任务调度算法

动态随机负载均衡算法(Opportunistie Load Balancing.OB)把一个任务随机分配给下一个可使用的机器,而不考虑任务在该机器上的期待执行时间。该算法的目的是要尽量使所有的机器处于工作状态。

最小执行时间调度算法(Minimum Execution Time,meT)将一个到达的任务分配给具有最小执行时间的机器,而不考虑该机器的可用性,MET的目标是把每一个任务分配给对其而言是最好的机器,即具有最小期待执行时间的机器,可能导致机器之间严重的负载不均衡。

最小完成时间调度算法(Minimum Completion TimeCt)将一个到达的任务分配给对于该任务而言具有最早完成时间的机器。该方法并不能够保证将一个任务分配给对于该任务而言具有最小执行时间的机器上运行,但其结合了OLB算法和MET算法的优点,避免了OLB算法和MET算法中很差的调度结果的出现。

开关调度算法(Switching Algorithm,SA)考虑到MCT算法的任务调度结果是使整个系统尽可能的达到负载均衡,而MET算法在系统内的机器之间的性能差异比较大时会使系统负载严重不均衡,因此结合MCT算法和MET算法的优缺点,在任务调度过程中设置两个值a1和a2,满足a<a2,SA算法首先使用MCT算法调度任务,直到系统的负载均衡指标值增加到a2,然后使用MET算法调度任务,当系统的负载均衡指标值减少到a1时,再使用MCT算法调度任务,如此循环,直到所有的任务都被调度。

R最优调度算法(k--precent best,KPB):对于一个由m个计算结点组成的网格系统,当一个任务到达调度器时,k最优任务调度算法从m个计算结点中选择kXm(1/m≤k≤1)个对于该任务而言具有最小执行时间的计算结点组成一个计算结点子集合,然后将该任务调度到该计算结点子集合中具有最小完成时间的机器上运行。如果k=1/m,则该算法退化为MET算法如果k=1,则该算法退化为MCT算法。

(2)批处理动态任务调度算法

批处理任务调度算法一次处理一个任务集合,只有当一个调度事件发生时(比如达到预先定义的两次调度事件的时间间隔,或者任务集合中的任务数量达到预先定义的数目)才开始对该任务集合中的任务进行调度.

Min-min调度算法的思想是尽可能把每一个任务分配给最早可用且执行最快的机器,为此:①Min-min算法为任务集合中的每个等待分配的任务i计算将该任务分别分配到m个计算结点上运行时的最小完成时间(MCT);②设任务i在第j个计算结点上的MCT最小,记为MCT(i,j),则对于由t个任务组成的任务集合,可以得到一个由各个任务的最小MCT组成的包含t个元素的集合A={MCT(i,j)|i=1,2,…,t};③从集合A中选择最小的元素MCT(,),将任务分配到计算结点上运行;④从任务集合中移除任务;重复上述4个过程,直到任务集合中的所有任务调度完毕, Min-min算法是基于最小完成时间(MCT)的,但 Min min算法在每一次映射中考虑的是全部未分配的任务,而MCT算法在一次映射中只是考虑一个任务。

Maxmin调度算法与inmin调度算法的工作原理类似,不同之处在于Min-min算法选择具有最小MCT的任务,即从集合A中选择最小的元素a,而 Max-min算法选择具有最大MCT的任务,即从集合A中选择最大的元素a,分配到相应的计算结点上运行。

Sufferage调度算法为了完成由t个任务组成的任务集合T的调度过程,需进行若干次循环调度操作。在第k次循环调度操作中对由尚未成功调度的任务组成的集合T进行处理,处理过程为:①计算任务集合T各任务的最小完成时间,设任务i(i∈T)在第j个计算结点上的MCT最小,记为MCT(i,j);②如果T中不存在别的任务在计算结点j上取得最小MCT,则将任务i调度到计算结点上,如果T存在多个任务在计算结点j上取得最小MCT,即这些任务共同竞争计算结点j,则从竞争任务中选择一个具有最大 Sufferage值的任务并调度到计算结点上运行,竞争失败的任务组成集合T,由第k+1次循环调度操作处理。任务i的 Sufferage值义方法如下:找出使任务i具有最小完成时间MCT(i,)的机器j和次小完成时间MCT(i,p)的机器p,任务i的suf ferage值为 sufferage=mt(i,p)-(i,)重复上述循环调度操作,直到任务集合中的所有任务调度完毕。

(3)静态调度算法

静态随机负载均衡算法(Opportunistic Load Balancing,ol随机把一个任务分配给下一个可使用的机器。与动态OLB算法的不同之处在于:静态OLB算法以任务次序调度任务,动态OLB算法以任务到达的时间次序调度任务。

用户导向的分配算法(User--Directed Assignment UDA)以任意顺序把每一个任务分配给具有最小期待执行时间的机器,即将任务分配给对于该任务而言性能最好的上运行。该算法与MET算法类似,不同之处仅仅在于MET以任务到达的时间次序调度任务。

快速贪婪算法(Fast Greedy)以任意的顺序把每一个任务分配给具有最小期待完成调度任务。 时间的机器。该算法与MCT算法类似,不同之处仅仅在于MCT以任务到达的时间次序调度任务。

静态Min-min调度算法与动态Min-min调度算法类似,不同之处仅仅在于静态Min min调度算法的任务集合包含了系统中的所有任务。静态调度算法的一个前提是在调度前系统中所有的任务都是已知的。

静态Max-min调度算法与动态Max-min调度算法类似,不同之处仅仅在于静态Man-min调度算法的任务集合包含了系统中的所有任务。

贪婪算法(Greedy)对一个任务调度问题分别使用Min-min算法与Max-min算法同时执行,然后进行比较,使用结果较好的解决方案。

基于遗传算法(Genetic Algorithm,GA)的调度算法:遗传算法是一种用于搜索大的解空间的技术,在许多工程领域得到了广泛的应用。在网格调度算法的研究中,遗传算法的关键问题是根据调度问题的特征确定合适的目标函数以构造适应度函数,设计合适的染色体编码/解码方法。

模拟退火算法(Simulated Annealing,SA)是一种迭代技术,每次迭代仅考虑一个可行调度方案,该可行调度方案采用与遗传算法中的染色体相同的表示方式。为了对解空间进行较好的搜索,SA算法可能会接受一个较差的调度方案。接受较差调度方案的可能性与系统温度有关。系统温度随着迭代次数的增加而减少,随着系统温度的降低,较差的解被接受的概率会越来越小。

遗传模拟退火算法(Genetic Simulated Annealing,gsa)是A算法和SA算法的结合。总的来说,GSA算法与GA算法有着相似的执行步骤,只是在“选择”过程中,gsA算法采用了SA算法的冷却和系统温度的概念。

禁忌搜索算法(Tabu)是一个解空间搜索算法方法是使用一个Tabu列表保存已搜索过的解空间范围的路径,其目的是为了避免重复那些范围里的搜索路径。在禁忌索算法中,调度方案也用GA算法中的染色体表示。

A算法是一种基于树的搜索方法。以空解的根节点开始,随着树的生长,中间节表示局部调度方案,即一个任务子集调度到计算结点;叶结点表示整个调度方案,即的任务最终都被调度到计算结点。

答案来源:黄海 《虚拟现实技术》

发表评论

相关文章