静态调度算法池的设计与实现

《静态调度算法池的设计与实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、韩建枫:静态调度算法池的设计与实现静态调度算法池的设计与实现①韩建枫汤(天津大学系统工程研究听天津300072)摘要并行计算中很多调度算法的优异性能均以对调度问题的诸多限制为前提。本文针对辞态调度算法，尝试建立一种机制和结构，以模块形式增减、管理多种调度算法，并根据一个具体的应用问题选择最适合的调度算法进行调度。基于任务图的实验结果表明，采用荃于池的调度方式具有比池内某单一调度策略更优异的执行性能。关键词调度算法，池模型，PSS1)处理机模型可抽象为五元组P‘二(P,L,S,0引言I,R)。其中:P二}风iI;ic-[1,MI}表示所有处理由于并行计算的调度问题

2、为典型的NP完全问机的集合，M代表有效处理机数目;L二{I[i,j];i.j题{’，所以「1前研究出的调度算法多为各式启发性E[1.M],l[i,j]E10,11}表示P[i]到P[j〕是否具算法和包含各类约束条件的近似算法。它们大多呈有直接连接;S={s[i];iE[1,M]}表示P[i]的运现出约束条件多兀化和调度目标多元化等特点。因算速度;I二Ia[i];iC-[1,M]}表示P[i]进行数据此，在一个开放的并行计算环境中，迫切需要建立一通讯时启动I/0设备时的时间开销;R二{r[i,j];套包含多种调度策略的模型结构。它可以存储、组i,jE[1,M丁表示

3、P[i〕到司月的数据传输速率。织、增删多种不同类型而又相互独立的调度算法，并2)任务模型可抽象为任务属性和有向无环图可根据当时的系统信息和用户需求选择其中最适宜DAG，并以四元组TC二(V,E,A,D)表示。其中:V的调度算法对指定的作业进行调度。二{U[i];iE[1,N3{表示所有任务的集合，N代表一此调度系统[z在追求负载平衡目标下，根据任务总数;F,'二{c[i,j];i,jE[1,69],e[i,j]E{0,系统的当前负载情况选择不同的调度算法。还有一11;表T。「门到:〔川是否存在偏序关系;A=Ia些调度系统’在追求容错调度目标下，根据系统作[i];

4、iE[l,N]表示第。[i]个任务的计算量;D=业类型选择不同的调度算法。现在流行的商品化的Id[i,j];i,jC-[1,69]}表示d[i]到d口]间需要传作业管理系统如ISFI4,NQE.DQS,PBS等也具有多递的通讯量。该模型的三元组形式TG=(V,E,A)种调度策略虽然这些调度系统[2-41在多调度策略也可用来描述多作业模型。的应用方面做r不同程度的尝试，但调度策略种类1.2调度算法模型很少[’·，,qm度目标单一;有些调度策略局限于一一种任务调度算法可定义为一组按一定时序建些简单策略4，其调度级别也停留在作业级，在调度立TG到PG映射关系的策略。任

5、务调度结果可表策略的增减和选择方面同样缺乏最基本的自主性，示为一个带时序的TG到P‘映射的子集。由于调这大大减少了其所能包容的算法数量。本文首先给度问题属NP完全问题，且TG到PG存在巨大的映出了处理机模I、任务模型、调度算法的理论模型和射空间，因此各调度算法为追求其在某一目标下的建立在调度算法模型上的各类约束条件模型;定义效率，往往首先通过各种约束条件对完整的映射空了调度算法的人41参数;然后在此基础上详细介绍间进行约束，然后在此基础上实现各自调度算法了静态调度算法池PSS(PoolofScheduling'sStrate-这类约束通常表现为如下形式的组合:①

6、对尸‘进g,es，下文简称池)的实现技术。行约束如“机群”、“同构”等约束形式;②对TG进行约束如“忽略通讯时间”、“具有树状应用结构’‘等1池模型约束形式;③对映射选择的约束，如“负载平衡目1.1并行计算处理机平台和任务模型标”、“调度长度最小化”、“最小执行费用目标”等约一个完整的并行计算环境可抽象为处理机模型束形式和运行在其上的任务模型f2]表示。定义1对应某个具体调度算法，保证其调度囚狱自然科学从金伙69974026)资助项目。男19711年呀，博七牛;研究方向:并行计算和并行调度算法;联系人171高技术通讯·增刊2002.08定义5设调度算法A,B分别

7、具有有效人Cl参高效性的基于PC,TG或映射选择上的各类约束条数集。和你如果acp，则称A较B退化，如果。cR,件的组合为该调度算法的人口参数。则称A较B进化;如果。二R，则称A与B同代。定义2调度算法人口参数中关于映射选择约2.3.3池对象束的参数为目标参数定义3调度算法人口参数中关于TG和PC约川数据结构:算法档案。(2)过程:包括增加(步骤一)、选择(图1)、状态束的参数为基本参数。定义4调度算法人口参数中关于TG和尸‘约提取、减少、进化、退化等过程。束项组合及分析产生的参数为条件参数。步骤一:静态调度算法池的增加步骤:1.3池模型Stepl:根据该静态调

8、度算法调度原理，以处理1