任务规划算法（精选9篇）
任务规划算法 篇1
0引言
随着遥感卫星技术水平的不断发展, 针对遥感卫星应用需求的研究也不断深入, 已经由原来的点目标瞬时成像发展到区域目标等复杂目标的成像。区域目标通常不能被星载遥感器的一个瞬间视场或一个扫描条带覆盖, 必须先将其分割成较小的条带, 再将这些小条带分配给相应的卫星进行遥感成像。合理的分割方法和精心设计的任务规划算法是完成区域目标成像的关键技术, 本文对现有的区域分割方法进行了改进, 提出了一种新的动态划分方法, 在此基础上提出了一种邻域求解算法, 解决了区域目标遥感的任务规划问题。
1区域目标的动态划分方法
如前所述, 区域目标通常不能被星载遥感器的一个瞬间视场或一个扫描条带覆盖, 其常常表现为一个由多边形或封闭曲线包含的大范围区域[1]。针对区域目标的成像, 通常是由多颗遥感卫星多次成像完成的, 因此首先必须根据不同卫星的光照条件、分辨率、图像类型、时间窗和遥感器灵巧程度等约束条件, 将区域目标划分为单个卫星一次成像 (或开机) 就能完成的条带集合。
现有区域目标的划分方法[2,3]主要有依据卫星观测的单景进行划分、采用预定义的参考系统进行划分以及采用固定宽度的条带进行划分。欧空局Lema
但是, Lema
分割过程沿着区域目标和观测范围的重叠部分由西向东进行 (如图1所示) , 在垂直轨道方向以偏移参数Δλ为间隔由西向东逐条地布置条带, 使相邻2个条带的西侧边界 (平行于卫星轨道方向) 间距等于偏移参数Δλ, 直到条带集合完全覆盖区域目标位于观测范围内的部分。其中, 条带的长度 (轨道方向) 根据条带与区域目标边界的交点位置决定。
2区域目标任务规划的邻域搜索算法
将区域目标进行动态划分后, 就构造出了每个卫星针对区域目标的候选观测任务集合, 因为划分的时候允许候选条带之间有重叠, 因此划分生成的候选观测任务数量大大增加, 而且偏移参数设置的越小, 重叠量越大, 相应的候选观测任务数量也越多, 区域目标规划问题的解空间也就越大, 这虽然有利于找到较优的解, 但同时也使算法求解效率降低, 因此必须针对区域目标的任务规划问题设计能快速得到高质量解的求解算法。
鉴于此, 本文综合贪婪规则、随机模式和变邻域等因素设计了贪婪随机变邻域搜索算法 (Greedy Randomized Variable Neighborhood Search, GRVNS) 。整个求解阶段划分为以下3个阶段:
① 初始解构造阶段。
主要任务是按照给定的规则构造出一个可行解作为局部搜索的起点, 这一阶段的工作需要考虑解的合法性;
② 局部搜索阶段。
该阶段是模型求解的主要部分, 它是一个反复迭代的过程, 每一步迭代过程都是首先根据具体算法的需求以及不同阶段的优化目标选择合适的邻域结构, 然后基于当前解构造出指定类型的邻域, 接着在邻域中按照预定的规则改进当前解并更新最优解候选集, 如此反复迭代直到满足终止规则;
③ 微调阶段。
主要任务是在获得最优解候选集之后逐个地处理最优解候选集中的解, 剔除因为场景重叠而产生的冗余活动, 直到所有候选解都不包含冗余活动, 此时再从候选最优解中选择一个观测成本最小的解作为最优解。
该算法最大的特点是在局部搜索阶段采用了分级优化策略, 将局部搜索过程划分为多个阶段, 并根据不同的阶段性目标采用不同结构的邻域, 并在每一步迭代过程以随机模式调整邻域中候选解的先后顺序, 同时在判断是否接受候选解时采取了贪婪规则, 只接受比当前解质量优的候选解。这种算法具有使用简单、求解速度快、解质量稳定等优点, 很大程度上改进了一般启发式算法容易陷入局部最优的不足。
2.1邻域
GRVNS算法采用变邻域分级优化的思想, 在不同阶段根据不同阶段性目标采用relocatetoS (Sol) 和exchange (Sol) 两种邻域结构。
2.1.1 relocatetoS (Sol)
该邻域的功能是基于当前解Sol, 将占用虚拟资源S0的活动转移到真实资源的活动序列中, 如图2所示。
构造要素包括:源资源S0、需重新分配的活动j、目的资源resj、目的位置标记posj。其中目的位置标记posj是指活动j转移到目的资源resj时所要插入并紧跟的活动, 即图中的活动i。当目的位置标记posj=0时, 表示活动j要作为资源resj活动序列的起始活动。在候选解的构造过程中, 首先将源资源S0上与活动j有关的活动时序关系都破坏, 如prevj与j、j与nextj、i与nexti等, 并建立新的活动顺序关系, 如i与j、j与nexti、prevj与nextj。
在搜索过程中采用这一种邻域结构, 解的整体收益将始终保持着非减的变化趋势。
2.1.2 exchange (Sol)
该邻域的功能是基于当前解Sol将分别位于虚拟资源和真实资源上的活动进行位置互换, 如图3所示。构造要素包括:虚拟资源S0、资源S0上待交换的活动j、资源resj、资源resj上待交换的活动i。
在候选解的构造过程中, 首先破坏previ与i、i与nexti、prevj与j、j与nextj之间的顺序关系, 交换活动i和j, 并建立previ与j、j与nexti、prevj与i、i与nextj之间的顺序关系。
该结构邻域实质是交换已安排执行的活动和未安排执行的活动, 它不能保证解对应的整体收益一直保持非减的趋势。因此, 如果要求解的整体收益在搜索过程中始终保持增长的趋势, 需要在求解算法中设置相应的迭代规则。
该邻域可用于对卫星成像方案的多目标优化过程, 既可以通过交换活动促使整体收益增长, 又可通过在保持整体收益不变的条件下, 用低成本的活动置换高成本的活动实现解质量的提高。
2.2候选解的接受准则
GRVNS算法在判断是否接受候选解时采取了贪婪规则, 总是以当前搜索阶段的优化目标为评价标准, 接受邻域中比当前解质量更好的局部最优解。比如在以最大化整体收益为优化目标的搜索阶段, 只接受邻域中整体收益比当前解更高的局部最优解, 而在以最小化观测成本为优化目标的搜索阶段, 只接受邻域中解整体收益与当前解相等且观测成本比当前解更小的局部最优解。
在同一阶段, 无论是以最大化整体收益为优化目标, 还是以最小化观测成本为优化目标, 都有可能在当前优化目标下面临多个质量无差异的候选解, 此时可以采取随机模式在这些候选解中选择一个来更新当前解。
2.3终止规则
GRVNS算法局部搜索过程的终止规则为:判断以最大化整体收益和最小化观测成本为优化目标的迭代过程是否都完全结束, 若是, 则停止局部搜索过程, 并进入冗余活动的识别和剔除阶段。其中判断relocatetoS (Sol) 或exchange (Sol) 邻域的迭代过程是否终止的规则如下:
① 当邻域为空集时, 终止当前邻域的迭代过程;
② 当迭代过程是以最大化整体收益为优化目标时, 判断当前邻域是否无法提供整体收益比当前解更高的候选解, 若是, 则终止当前邻域的迭代过程;
③ 当迭代过程是以最小化观测成本为优化目标时, 判断当前邻域是否无法提供与当前解整体收益相等但是观测成本更低的候选解, 若是, 则终止当前邻域的迭代过程。
2.4最优解信息的保留
由于GRVNS算法的局部搜索过程分阶段地以最大化整体收益和最小化观测成本为优化目标进行迭代, 其每一步迭代都是以邻域中比当前解质量更好的局部最优解来更新当前解, 当前解的质量在整个局部搜索过程中总是稳步提高的, 因此只需要在整个局部搜索过程中保留唯一的最优解信息。
2.5算法描述
GRVNS算法的详细流程如下:
第1步:初始化iIter, 令阶段标记iIter=0, 表示首先以最大化整体收益为优化目标搜索relocatetoS (Sol) 邻域;
第2步:将所有候选观测活动都编入虚拟资源的活动序列, 并以随机的顺序排列, 构造出初始解Sol, 并令最优解Solbest=Sol;
第3步:基于当前解Sol, 构造所有候选解都通过可行性分析的邻域N (Sol) :如果阶段标记iIter=0, 则构造relocatetoS (Sol) 邻域, 否则构造exchange (Sol) 邻域;
第4步:若N (Sol) =ϕ, 转第9步, 否则转第5步;
第5步:以随机模式调整邻域N (Sol) 中所有候选解的先后顺序, 使候选解以随机顺序排列, 得到邻域rN (Sol) ;
第6步:若阶段标记iIter≤1, 以最大化整体收益为优化目标, 在邻域rN (Sol) 中按候选解先后顺序比较各候选解的整体收益, 并选取整体收益最大的解Sol′;若阶段标记iIter=2, 以最小化观测成本为优化目标, 在邻域rN (Sol) 中按候选解先后顺序比较总执行时间, 并在整体收益不降低的条件下选取总执行时间最小的解Sol′。如果同时有多个候选解符合条件, 从中选取最早访问的那个解。如果没有符合条件的解, 转第9步;
第7步:当同时满足条件iIter≠2且解收益profit (Solbest) <profit (Sol′) , 或者同时满足条件iIter=2且总执行时间Cost (Sol′) <Cost (Solbest) , 令Solbest=Sol′, 并转第8步, 否则转第9步;
第8步:更新当前解Sol=Sol′, 转第3步;
第9步:如果阶段标记iIter<2, 令iIter=iIter+1, 转第3步, 否则转第10步;
第10步:输出最优解Solbest。
3实例分析
为检验GRVNS算法的有效性, 通过实例对GRVNS算法和简单贪婪算法进行了性能比较。
3.1简单贪婪算法
简单贪婪算法与GRVNS算法的区别在于不采用变邻域策略以及随机模式, 具体表现在:
① 在以最大化整体收益为优化目标进行搜索时, 直接在relocatetoS (Sol) 和exchange (Sol) 邻域混合组成的搜索空间中寻找局部最优解;
② 构造完邻域之后没有以随机模式调整邻域中所有候选解的先后顺序。
3.2GRVNS算法与简单贪婪算法的性能比较
测试算例共有6个, 规划周期均为1 d, 其中编号simp1、simp2的算例是单星对单个区域目标的简单算例, mid1、mid2是多星对单个区域目标的中等规模算例, comp1、comp2是多星对多个区域目标的复杂算例。所有算例都是在Xeon (TM) 2.8 GHz、3.81 GB内存的工作站上运算。比较结果如表1所示, 其中CPU代表算法的计算时间。
从表1可以看出, 当问题规模较小时 (simp1、simp2) , 这2种算法获得的解在质量上基本没有差异, GRVNS算法的求解速度相对较快;对于中等规模以及规模较大的问题, GRVNS算法不仅具有较快的求解速度, 而且解的质量普遍比简单贪婪算法获得的解要好。
4结束语
针对区域目标等复杂目标的成像问题研究是当前遥感卫星应用的热点。本文将区域目标的分解与分配综合起来考虑, 首先提出了一种基于卫星观测能力的动态区域划分方法, 这种方法能根据不同的卫星遥感器对区域进行可行划分。在此基础上, 综合贪婪规则、随机模式和变邻域等因素, 设计了贪婪随机变邻域搜索算法进行求解。通过一组测试实例, 对比分析了该算法与简单贪婪算法的性能, 结果表明对各种规模的问题, 算法都能较快得到比较好的解。
参考文献
[1]阮启明.面向区域目标的多星协同规划技术研究[D].长沙:国防科技大学, 2006:23-32.
[2]WALTON J.Models for the Management of Satellite-based Sensors[D].Massachusetts Institute of Technology, 1993:23-30.
[3]LE^MAITRE M, VERFAILLIE G.Selecting and Scheduling Observations of Agile Satellites[J].Aerospace Science and Technology, 2002 (6) :367-381.
任务规划算法 篇2
用科学发展观指导规划编制，重点是“五个统筹”。
二、主要任务
（一）创新总体规划的内容、强化空间指导和约束功能。
（二）突出针对性和可操作性。
（三）合理确定规划期，水资源等可规划至2020年。
（四）对竞争性产业的规划，如需进入规划，要提出布局方案、政府扶持方式和扶持资金量。
（五）加强空间规划。
（六）探索规划整合，改革州县规划。
三、规划要处理好以下关系
（一）继承和创新的关系。
（二）发展好和快的关系。
（三）（四）行政区域与统一市场的关系。
任务规划算法 篇3
敏捷卫星是近年来出现的新一代对地观测卫星,由于保密的原因,国内外公开的相关敏捷卫星任务规划问题的文献资料不是很多。典型的主要有法国Lemaitre等人针对新一代敏捷卫星Pleiades的任务规划问题研究,提出了约束规划模型,比较了约束规划、贪婪、动态规划以及局部搜索等四种算法,并指出了各自的适用范围[1]。Panwadee针对敏捷卫星任务规划问题建立了多目标优化模型,提出了遗传算法的求解策略[2]。在国内研究中针对敏捷卫星的常规任务规划问题,陈宇宁,等分析了灵巧卫星调度问题的约束条件,构建约束满足模型,提出了基于蚁群算法的调度求解策略[3]。李玉庆构建了任务规划调度的数学模型,并采用了模拟退火算法和遗传算法相结合的混合遗传算法求解策略[4]。对于非敏捷卫星任务规划,美国的Wolfe等学者采用了三种算法求解对地观测卫星任务规划问题,研究表明遗传算法求解效率优于优先级调度算法和具有前看功能的求解算法[5]。由此可见,在解决卫星任务规划非线性NP-hard问题时,智能优化算法在求解敏捷卫星任务规划问题时具有很多优势。
在深入分析敏捷卫星任务规划特点的基础上,首先对敏捷卫星任务规划问题进行了抽象描述;然后构建了基于多目标的敏捷卫星任务规划模型;最后提出了蚁群算法和免疫遗传算法相结合的混合遗传求解方法。
1 问题描述及模型构建
1.1 敏捷卫星观测方式
敏捷卫星观测视角可以围绕翻滚、俯仰和偏航三个轴变化,具有三维观测自由度,它可以进行完成滚动、俯仰、偏航的星上动作,因此其具有很强的姿态机动能力。敏捷卫星有可能在能力允许的范围内沿任意走向对目标进行观测,因此敏捷卫星的灵活性和观测效率由于姿态敏捷的控制而得到了很大的提高,如图1所示[6,7]。敏捷卫星切换速度快,在俯仰轴14秒内可达到45度,平均速度可达到了3.2度每秒[8]。敏捷卫星能够进行俯仰,其可视时间窗口也相对比较宽泛,其可以在可见时间窗口内较自由地选择可见时间窗对观测目标进行观测。而非敏捷卫星不能做出俯仰的姿态,因此其只有在经过地面目标上空时才可见观测目标[9,10]。它们的观测方式对比如图2所示。正是由于敏捷卫星观测方式的复杂性,导致其任务规划求解对比于传统的非敏捷卫星任务规划问题更为复杂。
1.2 敏捷卫星对地观测组织实施
敏捷卫星对地实施过程是将包含有任务类型、任务目标优先级以及任务图像分辨率等要求的多用户任务需求,经过智能辅助分析后形成规范化的任务集;以敏捷卫星和地面站部署的现有资源集为基础,充分考虑敏捷卫星携带传感器类型、存储容量、俯仰角以及侧视角范围等一系列约束条件,在一定的规划时间范围内统一规划有限的敏捷卫星资源,将待观测任务集合理地安排到各个敏捷卫星上执行完成观测任务;然后将任务规划方案提交给地面测控中心进行操控实施调度,通过地面测控与观测目标的数据接收处理、评估后将用户所需的数据发送给敏捷卫星需求用户。卫星任务规划可以大大提高敏捷卫星的对地观测效率,可以满足更多的敏捷卫星用户需求。如图3所示敏捷卫星对地观测组织实施流程。
1.3 模型假设
敏捷卫星任务规划问题是一个极为复杂的问题,涉及到的决策对象繁多,还需要考虑对象间的关系错综复杂,而在解决问题时不可能考虑到所有的约束条件;为了更贴近实际,解决关键问题,需要对任务规划问题简化并适当做出一些假设,而这些假设都是与卫星任务规划调度实际紧密结合的,假设也是合理的[11]。
(1)每个敏捷卫星只携带一个星载传感器。
(2)同一颗敏捷卫星同一时刻只能执行一个元任务,而且只要开始执行一个元任务,则不能中断。
(3)敏捷卫星可靠性高,工作时故障发生的可能性很低;同时也不考虑天气、云层等有关气象条件对目标观测的影响。
(4)除周期性任务外,每个元任务在敏捷卫星规划的一个周期内只执行一次。
1.4 模型构建
1.4.1 目标函数
敏捷卫星任务规划的目标是在某一确定的时间段内,在满足卫星约束的前提条件下以尽量少的资源消耗完成尽可能多的任务、获得最大的综合收益,同时也希望各个敏捷卫星间负载更加均衡,达到尽量好的卫星成像效果。因此其敏捷卫星任务规划问题是一个多目标优化问题。任务规划目标函数数学表述如下。
目标1:任务收益率最大,即
目标2:任务完成率最大,即:
目标3:资源使用均衡度最大,即尽可能满足各可用载荷上负载均衡,工作时长均匀一些。即:
资源使用均衡度公式如下:
其中,max SWT=mjax(SWTj)。wi为观测任务ti的收益,PRI(ti)为观测任务ti的优先级,N为观测任务集中的任务总数。Tetij代表观测任务ti的结束时间,Tstij代表观测任务ti的开始时间。对于上述三个目标可以利用加权法实现。
maxf1=αM1+βM2+γM3,其中α,β,γ为影响因子,α+β+γ=1。
1.4.2 主要约束条件及数学描述
(1)可见时间约束
式(1)和式(2)要求观测任务起始时间必须在卫星与观测目标的可见时间窗内执行,其可见时间长度必须要大于任务的执行时长。其中,ETik为观测任务ti的可见时间窗的结束时间,Tstij为可见时间窗ti的开始时间。DuraT(ti)为观测任务的持续时间。
(2)俯仰角和侧摆角约束
式(3)和式(4)是侧摆角与俯仰角的约束条件,要求在任务转换时敏捷卫星在有限的时间内能够达到下次观测任务时所需要满足俯仰角和侧摆角的约束条件。其中,FAgij和BAgij分别为敏捷卫星j中观测任务ti在STjik时刻的俯仰角和侧摆角;ajf和ajb分别为敏捷卫星j进行姿态调整俯仰和侧摆两个姿态时的角加速度。
(3)太阳高度角约束
式(5)是太阳高度角约束,要求卫星执行任务时刻应该满足最小太阳高度角要求。其中,Ai(Ai∈(0,90])是任务ti在STjik时刻的太阳高度角。SEAmin是满足成像要求的最小太阳高度角。
(4)能量约束
式(6)是能量约束,卫星侧摆俯仰以及照相时所消耗的能量敏捷卫星应该能满足,其应该小于卫星最大能量。其中,ηi为敏捷卫星j观测单位时间内所消耗的能量;ρi表示敏捷卫星j在姿态调整时单位角度内所消耗的能量;πj卫星j在阳照区单位时间内的充电量;SNLij表示执行观测任务ti前敏捷卫星j可用的能量;SNLi表示敏捷卫星j最大的可用能量。
(5)存储容量约束
存储容量约束式(7)要求敏捷卫星在一个轨道圈次内执行观测任务ti时星上可用的存储容量满足成像要求。其中,SSRjt代表敏捷卫星j在t时刻的存储容量;imageSSR(tj)表示为执行观测任务ti所需要的存储容量;MaxSSRj代表敏捷卫星j的最大存储容量。
2 免疫遗传蚁群混合求解算法
从敏捷卫星任务规划模型中可以得出其目标函数具有非可导性、非连续;任务规划中的一些先验信息较少或者不存在;因此其为求解带来了一定的难度。遗传算法对于解决多数组合优化和调度问题,处理复杂约束问题和非线性问题具有众多优势。
同时针对蚁群算法具有初始解好,易陷入局部最优,收敛速度慢,求解精度不高等特点,并结合遗传算法的优点[12]。本文提出了将蚁群算法与免疫遗传算法相结合的求解算法,其能够克服每个算法的缺点,充分发挥各自的优势。
2.1 混合求解算法流程
设计的求解算法基本思想是将蚁群算法每次迭代中所产生的全部解的集合作为初始种群,对初始种群进行免疫遗传算法的多次进化迭代操作,尝试寻找相对于当前全局最优解更优秀的解,如图4所示求解算法流程图。
2.2 状态转移规则及信息素的更新
针对敏捷卫星任务规划的特点,借鉴蚂蚁系统的思想,本文在蚁群算法中的状态转移规则如下:一只处于节点r的蚂蚁应用式(8)选择将要移动到的下一个j节点[13]。
式(8)中,q为[0,1]均匀分布的随机变量,q0(0≤q0≤1)是一个参数;ηij是距离tij的倒数,tij是任务执行间隔时间的影响;Y的选择主要依据式(9)中的概率分布函数。
式(9)中,alldk(Ti)为蚂蚁k下一步可执行任务的集合;τij是信息素分布,PRI(ti)为观测任务的优先级影响。α,β,γ分别为各个影响因素作用强度的权重。
信息素局部更新策略:当蚂蚁从任务T(t0)出发,依照状态转移寻优策略选择下一个任务节点,若找不到,则返回;若找到,则构造可执行任务序列TSequ,将其目标值与当前全局最优任务执行序列TSequB的目标进行比较,若小于,则TSequ所有边上的信息素挥发,τNij=(1-ρ)τijOld,ρ为信息素挥发率;若大于,则更新全局最优解TSequB=TSequ。为加快收敛速度,每次依据式(10)只对最优任务序列上的信息素浓度进行更新。
式(10)中,,R为设定的参数。
2.3 混合求解算法基本操作
2.3.1 染色体编码结构
编码是遗传算法的关键,编码结构的选择会对求解空间产生直接的影响。编码方案是确定染色体串与问题的搜索空间中的点之间的映射关系。本文采用二进制编码方式构造染色体。敏捷卫星成像目标任务只有完成或不能完成两种状态,长度为N的等长0—1二进制编码构造染色体被选择采用。每一个二进制序列被称之为一个染色体段,因此整个二进制序列所代表的敏捷卫星成像任务的集合即为任务规划的结果。染色体串的每一位取值代表了该观测目标是否被选取,每个基因位对应着一个敏捷卫星观测元任务。
其中,将X={x1x2…xi…xN}。
为种群中的一个染色体,其染色体编码结构如图5所示。
2.3.2 遗传操作
选择:选择基于适应度比例的选择策略,即常用的轮盘赌法,个体i被选中的概率为,其中fi为个体i的适应度值;N为种群个体数目。
交叉:采用多点交叉的方法来进行,如图6所示。多点交叉比单点交叉具有更好的鲁棒性,具有更好的重组能力,不但可以解决过早收敛的问题,而且可以加快算法对整个解空间的搜索速度。
变异:每个个体的变异概率采用公式(11)来计算:
式(11)中,fmin和favg分别表示当前种群中个体适应度值的最小值和平均值,fi代表第i个个体的适应度值,P[i]代表第i个体变异概率。
3 实例分析
实例为10颗星,600个元任务的仿真场景,应用STK软件及Matlab2011a软件,卫星轨道数据来源于AGI公司于2010年6月发布的全球卫星轨道数据库,任务分布主要集中在重点热点地区,任务生成方法采用文献[14]的方法。为表述更加清晰,选择在实际应用中最广泛的点目标观测需求为例展开研究。仿真中的参数设置为:免疫遗传操作最大代数MAXGEN=1 300,交叉概率pc=0.95,变异概率pm=0.08,疫苗接种概率pv=0.5;蚂蚁数AntCount=40。所设计的算法与遗传算法和免疫遗传算法进行了对比,在内存为4 G,Intel-i5双核心CPU的环境下将每个算法运行15次,取平均值,对任务收益率、负载均衡度以及综合收益率几个方面进行了比较分析。运行结果统计处理后如表1、图7、图8所示。
从表1中可以看出在达到约98%最佳解性能时,遗传算法所用时间最多,免疫遗传算法次之,IA-COGA算法所用的时间最少,与GA相比节省了约373 s,可见其求解效率很高。
为运算结果对比更加清晰,加入了求解敏捷卫星任务规划的规则算法,主要有先来先服务(FIFS)和优先级规则算法(Priority),由于规则方法执行时间极短,因此本文将其画成直线与其它算法形成直观的对比,便于分析。从图7中可以得出IACOGA算法综合指标最高,其任务收益率高于其它算法;其次是IGA算法得到的结果,较接近IACOGA算法求得的值;GA算法、IGA算法以及IACOGA算法最终都超过了FIFS算法和Priority算法,相比较而言GA得到的理想解是最不理想的。从图8中可以得出IACOGA算法的任务均衡度也是最高的,优于其它两种算法。
综合来看,在算法初期,IGA算法曲线起点较高,但随着时间的推移,曲线上升幅度很小,很平缓。GA算法曲线初始起点较低,一段时间内上升幅度较大,但到最后曲线很是平缓,其方差波动也较大。IACOGA算法曲线起点较高,曲线上升也较快,其方差波动也较小,因此所设计的混合遗传算法具有较佳性能。
4 结束语
十三五规划主要任务 篇4
城市管理规划工程。充分发挥规划在城市管理中的龙头作 用，增强城市管理的前瞻性、规划性、计划性。将城市管理纳入 城市发展规划当中，确保城市骨理利学、可持续发展。城巾管理制度建设工程。将迎xx期间形成的、行之有效的 临时管理制度延伸作为城市管理长效管理制度，确保xx后刑期 城市管理水平持续提升。
打造数字化城市管理工程。以区城市管理视频监控系统为平台，进一步提引城市管理监管、控制和执法效能。以区指挥中心 控制平台为载体，向街道、杜区延伸，形成区、街、社区联网，缩短“六乱“、环卫保洁、市政设施、除害防病等案件流转耗时，提高城巾管理案件处理效率：城管视频监控系统与环卫监管视频 整合使用，城市管理检查引十；卫分片巡查相结合，多层次、多叫 段、全方位落实督导、管事、纠偏、处罚措施，形成网格化巡查 体系。
城巾管理运行机制工程。理顺城巾基础管理和综十执法的关系，推进管理与执法相分离的大部制要求：优化部门协同机制，理顺管理系统各环节：及时有效解决问题和监督考核讦价的良好机制：健全城巾管理应急机制，增强预防和处理突发事件能力。
创卫长效巩固工程。严格按照创卫要求加强日常管理工作，落实长效管理，巩固创卫成果，确保圆满完成迎接国家创卫复检丁作任务。环境秩序执法保障工程。合理调配城管力量，健全执法协调机制，保障城管执法执行有力。在严控和查处违法建设、整治城市“六乱”、清理违法户外广告、工地文明施工和余泥渣土排放管理方面，监督有力，按章执法。
市容环境提升工程。抓好主干道城市管理样板路建设，提高产外广告和扪牌设置水平和质量，建立健全广外广告和扪牌管理制度、资源开发、安全监测体系；完善城市夜间灯光环境建设，强化城巾夜间灯光环境管理。
公共服务保障工程。以人为本，提升城市管理公共服务整体水平，加强城市管理配套设施的设计和建设，使环卫保沽作业更亲民便民，方便社会各方经常性参与城市管理，逐步养成良好的文明习惯；坚持病媒生物防制措施到位，无重大疫情流行。
垃圾分类处理工程。冈地制宜选择适合我区实际的分类模式，全面开展垃圾分类处理，推进城市午活垃圾减量化、资源化、无害化，推动再牛资源的充分利用。
环卫设施升级改造和配套建设工程。推进车场、公厕、压缩站等现有环卫设施的升级改造，加快餐厨垃圾综合处理及有害垃圾处理设施建设，不断提高环境卫牛保障能力；通过升级改造、配套建设和购置一批环卫设施设备，促进环卫设施设备向“数量充足、设置科学、功能完善、运行正常、整洁美观”的口标方向发展。
社区环境改善里子丁程。通过以环境改善促进社区管理，保 障工程经费投入，促进街道把；主要精力集中到社区管理、环境整 治和社区服务-卜来。城区水环境卫午保障工程。以打造东濠涌主题水公园休闲长廊为重点，提高区辖内河涌两岸及水面卫生保济质量；将保济船改装为仿古船，与岭南水脉文化相仂、调，进一步提升尔濠涌的观赏性和知名度。环卫保济现代化丁程。个面提高机械化清扫水平，对一级马路，高架桥、快速路全而实行机械化清扫保洁，对二级马路或相对较窄的路面，实行分段清扫的方式进行机械化清扫或人工清扫的作业方式进行保洁，推行机械化冲洗、清扫为主、人士保洁为
辅的道路清扫作业新模式：引进先进的机械化洁扫、保济设备，利用卫星定位GPS技术，以“电子地图”为显示载体，对所属机械清扫、垃圾清运车辆进行实时监控，优化午辆清运路线，降低车辆运行成本，准确及时地处理各种突发情况。
城市管理综合考讦丁程。按照考讦机构正规化、考讦依据法制化、考评制度文件化、考评过程程序化、考评痕迹表格化、考计手段现代化、考计结果透明化的工作思路，采取专业部门考核和社会监督相结合、所队网格式检查和部门专项检查、定性考核和定量考核相结合、样本抽查相结合的方式，实现精确、敏捷、高效、全时段、全方位覆盖的城市管理绩效考核模式。
任务规划算法 篇5
互联网技术的发展,硬件技术和通信技术的进步共同加快了计算机领域的进步。20世纪80年代出现了并行计算,支持同步的算法、程序和体系结构的开发。随后出现了分布式计算,它要求各个处理机之间能够协同计算,通过处理机间的通信共同解决问题。网格计算技术[1]的发展则迎合了21世纪并行与分布式计算技术的发展趋势,它是以资源共享为目的,支持对可计算资源的远程和并发的访问,用高速网络连接的地理上分布的可计算资源所组成的一个具有单一系统映像的高性能计算和信息服务环境。
网格资源包括计算资源、存储资源和通信资源。对于网格用户而言,它向网格系统提交任务,由网格调度程序按照某种调度策略把用户提交的任务分配给网格系统中的可用资源。如何使这些资源高效地完成计算任务是网格系统的研究重点之一。
由于在网格环境下的任务调度主要考虑的是一组相互独立、任务之间没有通信和数据依赖的元任务(metatask)映射。现有的任务调度算法可以分为在线模式(on-line)和批模式(batch-mode)两种。在线模式是任务一到来就加以映射,而批模式则是把任务收集起来等映射事件到来后才对这些任务进行集中映射。相比而言,批模式得到了大量的资源信息,从而可以做出更合理的任务映射策略。在这里讨论的是批处理模式的任务调度,即调度程序的执行周期到时再集中映射。
以时间跨度(makespan)为优化目标的任务—资源映射是一个NP完全问题,解决这类问题常用启发式算法。经典的批模式算法有Min-min、Max-min、Suffrage、遗传算法、蚁群算法等。T.Braun[3]等人通过对一些常用的算法进行了比较,在一定规模时遗传算法所求出的时间跨度要优于其他算法一些,但随着规模扩大,其收敛性降低[4],因此本文提出了将遗传算法和Min-min算法相结合的改进遗传算法的任务调度优化模型,该算法也适合大规模任务的调度,并进行了仿真实验。
1 问题描述
任务调度问题的实质[2]就是在一个有n个需要调度的任务、m个可用的资源(主机或集群) 的网格环境下,把n个子任务J={J1,J2,…,Jn}以合理的方式调度到m个资源R={R1,R2,…,Rm}上去,目的是得到尽可能小的总执行时间,提高系统吞吐量等。具体描述如下:
(1) J是n个需要调度的任务集合,Ji表示第i个任务。每个任务的任务量大小用百万指令(MI)表示,且每个任务只能一个资源上执行完成。
(2) R是m个可用的资源集合,Rj表示第j个资源。每个资源的计算能力用百万指令每秒(MIPS)表示。
(3) n个任务在m个不同资源上的预测执行时间ETC( Expected Time to Compute)是一个n×m的矩阵。矩阵中的每一行代表某一个任务在m台资源上的不同执行时间,每一列代表在同一台资源上n个任务的不同执行时间。ETC(i,j)表示第i个任务在第j个资源上的执行时间。
(4) 资源j的最早可用时间为STARTTIME(j)。
(5) 把任务i所需的数据从存储系统传输到资源j上的传输时间为TRANS(i,j)。
(6) 第i个任务在第j台资源上的预测最小完成时间为MCT(i,j),则MCT(i,j)=STARTTIME(j)+TRANS(i,j)+ETC(i,j)。
(7) 任务i的最小完成时间为Ci,当任务分配给第j个资源时,Ci=MCT(i,j)。
(8) 所有任务都执行完成的时间为时间跨度(makespan),即makespan=Max{Ci,i=1,2,…,n}。
2 设计与实现
遗传算法(GA)是Holland于1975 年受生物进化论的启发而提出的,并行性和全局解空间搜索是GA的两个最显著的特点。网格任务调度问题是一个NP问题,在一定规模时,用遗传算法进行网格任务调度能得到很好的性能。Min-min算法是一种实现起来很简单的算法,算法的执行时间也很快,具有较好的时间跨度。遗传算法随着调度规模的扩大,在一定调度时间限制内,它的收敛性会逐渐降低。因此,本文提出一种将Min-min算法和遗传算法相结合的改进遗传算法。
2.1 Min-min算法
Min-min算法的主要思想如下(仍然考虑n个任务,m个执行单元的情况):
(1) 对集合中每一个等待分配的任务T,分别计算出分配该任务到m台机器上的最小完成时间,这就得到了一个n×m的MCT矩阵。
当需要调度的任务集合非空时,反复执行以下操作直至集合为空:
(2) 利用MCT矩阵,对集合中每一个等待分配的任务分别找到能够最短时间完成该任务的执行单元及最短完成时间,在所有的最短完成时间中找出最小的最短完成时间对应的任务a,设其对应的主机为b,把任务a分配到机器b上。
(3) 从任务集合中把任务a删除,同时更新MCT矩阵。
2.2 染色体的编码与解码
染色体的编码形式有很多种,可以采用直接编码(直接对子任务的执行状态编码)或者间接编码。本文采用间接编码方式,对每个子任务占用资源编码。染色体的长度等于子任务的数量,染色体中的每一位都是正整数,每一位的位置编号代表子任务的编号,而该位置上的正整数值代表该子任务所占用资源的编号。假设有10个子任务,3个可用资源,则染色体串长为10,每个基因的值则为随机产生的3个资源的编号,则可以随机产生了下面的一个染色体编码:
{2,1,3,2,2,3,1,1,3,1}
这个染色体代表第一个任务由第二个资源上运行,第二个任务由第一个资源执行,以此类推,第十个任务由第一个资源执行。染色体以数组形式存放。
产生了一个染色体后,还必须对其进行解码,得到不同资源上任务的分布情况。将任务按照占用的资源分类,生成多组按照资源编号分类的任务序列,每个序列的编号就是某一个资源的编号,序列中的元素就是在该资源上执行的任务,这样我们就得到了所有任务在多个资源上运行的分布情况。以上面的染色体为例,解码后产生3个资源的任务序列:
R1:{2,7,8,10} R2:{1,4,5} R3:{3,6,9}
这样就可以计算出每个资源完成该资源上分配的所有任务花费的时间,最大花费时间即为时间跨度。
2.3 初始种群生成与适应度函数
在网格环境下,对任务调度的实时性有较高的要求,为提高算法收敛的速度以及改善算法的结果,要求初始种群既具有随机性的个体,又具有一些比较优秀的个体。本调度算法是在Min-min算法基础上,采用遗传算法对其性能进行提高,又可以避免单独采用遗传算法对大规模任务资源匹配的低收敛性。我们可以先将用Min-min算法产生的染色体作为初始种群的优秀个体,再随机产生其他个体。
遗传算法在进化搜索中基本不利用外部信息,仅以适应度函数为依据,利用种群中每个个体的适应度值来进行搜索。因此适应度函数的选取至关重要,直接影响到遗传算法的收敛速度以及能否找到最优解。由于网格调度的目标是时间跨度尽可能小,因此适应度可定义为:
fitness(i)=1/makespan(i)
即染色体i的适应度值等于该染色体的时间跨度的倒数。若时间跨度越小,则适应度值越大,被选择的可能性越大。
2.4 个体选择
选择操作是决定父代种群中哪些个体,以及能以多大可能性被挑选来复制或遗传到下一代的进化操作。选择算子以对个体的适应度评价为基础,其主要作用是对搜索提供导向:挑选最优秀个体,使算法避免无效搜索且能快速搜索到问题的最优解。
假设本算法的种群大小为popsize,为了保留优秀个体,先选择Min-min算法产生的个体和父代中的最优个体,其他的popsize-2个个体采用轮盘赌法[5]进行选择。个体的选择概率为:
Pi=fitness(i)/∑fitness(j)
需要进行popsize-2轮选择。每一轮产生一个[0,1]均匀随机数,若该数位于某个体累积概率下的那个区间,则选择该个体。
2.5 交叉与变异
交叉的目的是为了在下一代产生新的个体,通过交叉操作,遗传算法的搜索能力能够得以飞跃地提高。这里的交叉算子采用多点交叉,对于m个交叉点的多点交叉,随机选择m个交叉位置,在交叉点之间的变量间续地相互交换,产生两个新的后代,但在第一位变量与第一交叉点之间的一段不做交换,交叉点的个数根据染色体的长度进行选择。多点交叉具有很强破坏性,可以促进解空间的搜索。
变异本身是一种局部随机搜索,与选择操作结合在一起,保证了遗传算法的有效性,是遗传算法具有局部的随机搜索能力,同时使得遗传算法保持种群的多样性,以防止出现非成熟收敛。
这里变异算子实质上就是将某个子任务迁移到另一个资源上执行,为了防止某个子任务在迁移后,执行的时间增大而造成种群退化,规定迁移后子任务占用的资源不是随机产生,而是在除了该子任务目前占用的资源外的资源集合中,选择使该子任务执行时间最短的资源,将其迁移到该资源上执行。
2.6 算法流程
(1) 随机产生n个任务,m个资源,根据任务的任务量大小和资源的计算能力生成一个n×m的初始MCT矩阵。
(2) 根据Min-min算法生成一条对应该调度的染色体。
(3) 随机产生大小为M的初始种群,根据每个资源上的子任务的执行序列,计算每条染色体的适应值。
(4) 选择染色体进行交叉操作和变异操作,计算新生成染色体的适应值,生成新的种群。
(5) 判断是否满足遗传算法的终止条件,如果满足,则停止计算,输出最小时间和对应的染色体;如果不满足,则返回(4)。
3 仿真结果与分析
本文的实验是对gridsim、遗传算法、Min-min算法深入研究的基础上进行的,任务的长度范围、资源的执行能力范围、任务分配给某一资源的执行时间等是模仿gridsim计算得到的,数据跟现实的情况比较相似。该算法用到的主要参数有:解的群体规模为20,交叉和变异概率分别为0.8和0.2,任务个数为表2中的几种,资源个数为10,算法终止条件设为到达一定的进化终止代数,最大进化代数设为100,如果算法连续20代没有找到更好的解我们则认为算法基本收敛。
图1描绘了三种算法时间跨度随任务数大小的变化曲线。从图中我们可以看出:改进GA相对于Min-min算法在性能上会普遍有所提高;对于GA,当任务数较少时(小于40个),性能对于Min-min算法也会提高,较小还高于IGA,随着任务数的增加,性能会逐渐下降,甚至还低于Min-min算法。所以GA不太适合用于大规模的网格任务调度,而本文提出的这种改进遗传算法对网格任务调度普遍适用。
4 结束语
用遗传算法和Min-min算法作为网格任务调度算法已经得到广泛的应用。当规模较小时,遗传算法被证明是一种最有效的启发式调度算法,但随着资源数和任务数的不断增加,遗传算法的性能逐渐降低,到达一定规模时甚至还低于Min-min算法,这样不仅性能得不到提高,而且还会增加调度时间。本文提出一种将Min-min算法和遗传算法相结合的改进遗传算法,这种算法对于大规模任务调度性能也比较高。
由于本文在设计时没有将经济因素考虑在内,下一步的工作可以将开支预算与时间期限考虑在内,再结合本算法,可用于基于经济模型的网格任务调度。另外,模拟退火算法局部搜索能力比较强,遗传算法全局搜索能力较强,将两者结合搜索能力会尽一步提高,性能可能会有所提高。
参考文献
[1]Foster I,Kesselman C.The Grid-Blueprint for a New Computing Infra-structure.Morgan Kaufmann Publishers,1998.
[2]Abraham A,Buyya R,Nath B.Nature’s heuristics for scheduling jobs on computational grids.In The8th IEEE International Conference on Advanced Computing and Communications India,2000.
[3]Braun T,Siegel H,Beck N.A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems.Journal of Parallel and Distributed Computing,2001,61(6):810-837.
[4]Carretero J,Xhafa F.Using genetic algorithms for scheduling jobs in large scale grid applications.In Workshop of the European Chapter on Metaheuristics EUME2005,Metaheuristics and Large Scale Optimiza-tion.Vilnius,Lithuania,2005(5):19-21.
网格中任务调度算法研究 篇6
1 网格中任务调度算法概述
在异构的网格系统中,根据任务一机器的映射策略在任务执行前是否可以调整,可将这些启发式任务调度算法分为静态调度算法和动态调度算法两大类。
1.1 静态任务调度算法
静态调度算法[1,2]是指所有的机器一任务映射策略在执行任务调度前就已经全部确定。现在网格计算中,常用的静态调度算法有OLB(Opportunistic Load Balancing)、MET(Minimum Execution Time)、MCT(Minimum Completion Time)、Min-min、Max-min、Duplex(Min-min算法与Max-min算法的结合)、GA(Genetie Algorithms)、SA(Simulated Annealing)、GSA(Genetic Simulated Annealing)、Tabu(禁忌调度算法)、A*(基于u叉树算法)、蚁群优化等。
1.2 动态任务调度算法
动态调度算法[1]是指,部分机器一任务映射策略在执行任务调度期间根据实际情况进行确定。现有的动态调度算法可以分为两类:在线模式(on-Line mode)和批模式(Batch mode)[3]。在线模式是指,每当网格调度器收到一个用户提交的任务,立即为之选择适合的计算系统,并将任务发送到该计算系统。而在批模式下,每当网格调度器收到一个任务,不是立即映射到计算系统,而是检查是否凑够一批任务,当凑够一批任务时,才为这些任务确定各自适合的计算系统。
1.3 静态和动态任务调度算法比较
静态算法相对较为简单,调度算法运行开销低,对数据的依赖性小,因而静态调度算法是网格计算中最早被研究的算法。由于此类调度算法有充足的时间投入调度计算,因而在实时性要求不高的计算系统中,使用该类算法可能更好。动态调度算法能够有效的解决负载评估、作业选择和作业迁移等问题,因此,在异构平台中,动态调度带来的负载均衡优势更加明显。但是动态调度算法解决上述问题时需要付出较高的系统开销。本文研究的是静态算法中遗传算法在网格任务调度的应用。
2 遗传算法在任务调度中的应用
2.1 遗传算法概述
2.1.1 遗传算法基础术语
1)种群(Population)和个体(Individuals):遗传算法处理的是染色体,或者叫基因型个体,通常以一串结构信息来表现一定数量的个体组成了种群(Population)。
2)种群规模(Population Size):种群中个体的数目。
3)适应度函数(Fitness Function):各个个体对环境的适应度值叫适应度。对于优化问题,适应度函数即为目标函数。遗传算法要求适应度函数为可以加以比较的非负函数。
4)编码(Coding)、译码(Decoding)操作:遗传算法必须包含两个必须的资料转换操作,即把搜索空间中的参数或解转换成遗传空间中的染色体或个体,称为编码操作;反之,称为译码操作。
5)选择(Selection)、交叉(Crossover)、变异(Mutation)算子:这三个算子是遗传算法的三个主要操作算子,遗传算子(Genetic Operatoin)是遗传算法的特点。
2.1.2 遗传算法的基本过程
一般遗传算法主要步骤:
1)随机产生一个有确定长度的特征字符串组成的初始种群。
2)对该字符串种群迭代执行下面两步,直到满足停止准则为止。
(1)计算种群中每个个体字符串的适应值。
(2)应用复制、交叉和变异等遗传算子产生下一代种群。
把在后代中出现的最好的个体字符指定为遗传算法的执行结果,这个结果可以表示问题的一个解。
2.2 遗传算法的实现过程
以下从染色体的编码和解码、种群的产生、适应度函数、遗传操作对遗传算法的实现进行分析网:
2.2.1 编码和解码
二进制编码方法是遗传算法中常用的一种编码方法,它使用的编码符号集由二进制符号。和1组成的二值符号集{0,1},它所构成的个体基因是二进制符号串。
二进制编码符号串的长度与问题所要求的求解精度有关。
假设某一参数的取值范围是[A,B],等分成2l-1个子部分,记每个等分的长度为,则它能够产生2l种不同的编码,参数的对应关系如下[4]:
假设某一个的编码是:X:xlxl-1xl-2…x1x2
则上述二进制编码所对应的编码公式为:
二进制编码优点:编码、解码操作简单易行;交叉、变异等遗传操作便于实现;符合最小字符集编码原则。缺点是长度较大,对于一些多维、高精度要求的连续函数优化问题,使用二进制编码来表示个体时将会有一些不利之处。
2.2.2 产生种群
产生初始种群方法通常有两种。一种是完全随机方法产生,它适合于对问题解无任何先验知识的情况;另一种是由某些先验知识转变为必须满足的一组要求,然后在满足这些要求的解中再随机地选取样本。在网格任务调度问题中,产生初始种群的方法即属于后者。
2.2.3 适应度函数
为了体现染色体的适应能力,引入了对问题中的每个染色体都能进行度量的函数,叫做适应度函数(fitness function)。通过适应度函数来决定染色体的优劣程度,它体现了自然进化中的优胜劣汰原则。对于优化问题,适应度函数就是目标函数。例如Tsp(Travelling Salesman Problem)问题目标是路径总长度为最短,自然地,路径总长度就可作为Tsp问题的适应度函数:
其中wn+1=w1,d(wj,wj+1)表示两个城市间的距离(路径长度)。
适应函数要有效地反映每个染色体与问题的最优解染色体之间的差距。若一个染色体与问题的最优染色体之间的差距较小,则对应的适应度函数值差就较小,否则就较大。适应度函数的取值大小与求解问题对象有很大关系。
2.2.4 遗传操作
简单遗传算法的遗传操作主要有三种:选择(selection)、交叉(crossover)、变异(mutation)。
选择操作也叫做复制(reproduction)操作,根据个体的适应度函数值所度量的优劣程度决定它在下一代是淘汰还是被遗传。一般地,选择将使适应度较大(优良)的个体有较大的存在机会,而适应度较小(低劣)的个体继续存在的机会也较小,例如通常采用的轮盘赌选择机制,∑fi表示群体的适应值之总和,fi表示群体中第i个染色体的适应度值,它产生后代的能力为其适应度值所占份额fi/∑fi。
交叉操作的简单方式是将被选择出的两个个体P1和P2(如图1所示)作为母体个体,将两者的部分码值进行交换。假设有如图1所示的8个位长的两个个体。
产生一个在1~7之间的随机整数c,假设现在产生的是3,将P1和P2的低三位交换:P1的高五位与P2的第三位组成10001001,这就是P1和P2的一个后代Q1个体;P2的高五位与P1的低三位组成数串1101110,这就是P1和P2的另一个后代Q2个体。其交换过程如图2所示。
变异操作的简单方式是改变数码串的某个位置的数码只有0和1这两种可能,有如下二进制编码表示:
其码长为8,随机产生一个1}8之间的数k,假如现在k=5,对从右往左的第五位进行变异操作,将原来的0变为1,得到如下数码串(第五位的数字1是经变异操作后出现的):
二进制编码表示的简单变异操作是将0与1互换,0变为1,1变为0。
现在对tsp的变异操作作简单介绍:随机产生一个l~n之间的数k,决定对回路中的第k个城市的代码w,做变异操作,又产生一个l~n之间的数w替代wk,并将wk加到尾部,得到:w1w2…wk-1wwk+1…wnwk
这个串有n+1个数码。注意,数w在此串中重复了,必须删除与数w重复的数以得到合法的染色体。
3 结束语
遗传算法利用简单的编码技术和繁殖机制来表现复杂的现象,从而解决非常困难的问题。它不受搜索空间的限制性假设的约束,由于它固有的并行性,遗传算法非常适用于大规模并行计算,已在优化、机器学习和并行处理等领域得到了越来越广泛的应用。
摘要：该文首先分析比较了网格中任务调度的动态和静态算法,然后对遗传算法在任务调度中的应用进行了讨论,并给出了具体实现步骤,提供了一定的借鉴意义。
关键词：网格,任务调度,遗传算法
参考文献
[1]Braun T,Siegel H,Beck N,et al.A comparison study of static mapping heuristics for a class of meta-tasks on heterogeneous computing systems[C].8th IEEE Heterogeneous Computing Workshop(HCW'99),1999:1529.
[2]Singh H,Youssef A.Mapping and scheduling heterogeneous task graphs using genetic algorithms[C].5th IEEE Heterogeneous Computing Workshop(HCW'96),1996:8697.
[3]都志辉,陈渝,刘鹏.网格计算[M].北京:清华大学出版社,2002:9-11.
基于负载平衡的任务调度算法 篇7
关键词：任务调度,完成时间,负载平衡
当今计算机技术已进入以网络为中心的计算时代,大量的应用都围绕着网络进行,对服务器的性能和可靠性提出越来越高的要求。例如,随着Internet的飞速发展和用户的剧烈增长,比较热门的Web站点会因为被访问次数急剧增长而不能及时处理用户的请求,导致用户长时间地等待甚至遭到拒绝,大大降低了服务质量。对于CPU密集型的应用,比如说带有数据库操作的Web服务,服务器性能瓶颈问题则更加突出。为了解决服务器的性能问题,分布式计算的概念就应用而生。
分布式计算研究如何把一个需要非常巨大的计算能力才能解决的问题分成许多小的部分,然后再分配给许多计算机进行处理这些小的部分问题,最后把这些小部分问题所对对应的计算结果综合起来得到最终的结果。由此可见,分布式计算所需的资源不仅有计算资源、存储资源还要有通信资源。那么如何使用这些资源高效的完成计算任务是分布式系统的研究重点之一。这就涉及到了计算任务的调度的问题。对于普通用户而言,它仅向分布式系统提交任务,但如何快速的完成这些任务,这就是调度程序要做的事情了。因此,分布式调度程序就是按照某种调度策略把用户提交的任务分配给分布式系统中的可用资源的重要模块,也是分布式计算的核心。
从上述分析可以看出,任务调度应该包括任务映射和调度两个方面。任务映射是逻辑地为每个任务匹配一个最合适的机器,以便最小化应用程序的执行时间或完成时间。任务调度则将任务传输到其映射的机器上运行。但本文所讲的任务调度主要强调的是前者即任务到资源的映射。以最小完成时间为优化目标的任务调度问题一直以来都是NP完全问题[1],针对这类问题科学家做了大量努力,但至今未能见到一个有效的解决办法,然而随着计算机技术的发展并考虑到计算机计算能力的提高,所以在工程实践应用中解决这类问题时,常采用贪心法又叫静态启发式算法,这类算法基本思想就利用计算机的快速性来进行穷举,但随着问题规模的增加其效能会降低太快,所以在实际应用中常采用动态启发式算法,针对于异构计算环境中原子任务的调度,动态启发式算法又分为在线模式启发式算法和批模式启发式算法。但这二个算法优点和缺点都比较明显,前者会导致负载不平衡,而后者会导致分配时间增加。为此,本文提出了一种算法来结合二者的优点从而保证任务调度的快速性和负载平衡性。
1 调度模型的建立
为了较好的描述分布式计算中的任务调度问题,我们采用数学模型的方法进行形式化的描述。分布式环境中资源的范围很广泛,它指加入到分布式系统中、所有可被共享的资源。所到达的任务可能是计算型也可能是数据存储型。为了描述问题的简单,本文所指的任务包括两类子任务:计算子任务和数据传输子任务。计算子任务是该任务中需要消耗计算资源的部分;传输子任务代表获得计算所需输入的数据通信即该任务中需要消耗存储资源和通信资源的部分。不考虑任务之间的依赖性。有如下定义:
1)参与调度的任务集合为T={t1,t2…tn},其中ti代表的是任务i。
2)参与调度的异构机器集合为H={h1,h2…hm},其中hj代表的是机器j。
3)定义任务ti在机器hj上的期望执行时间eij为机器hj在不考虑其它负载情况下执行任务ti所需要的时间。
4)定义任务ti在机器hj上的期望完成时间cij为任务ti映射到机器hj上执行完的时间。
5)定义机器hj的期望就绪时间为rj,则向量r存储了所有机器的期望就绪时间。
6)据(3)(4)(5)的定义有cij=rj+eij。
7)定义系统中有f个文件服务器或者数据仓库,S={s1,s2……sf}。
8)定义矩阵data,dataij表示子任务vi向文件服务器或数据仓库sj存取数据所需要的数据传输时间。
2 算法描述
2.1 Min-min
Min-min算法是一种实现起来很简单的算法,算法的执行时间也很快,具有较好的性能。该算法的目的是将大量的任务指派给不仅完成它最早,而且执行它最快的机器。算法的思想是首先映射小的任务,并且映射到执行快的机器上。执行过程为:计算要参与映射事件的任务集中每个任务在各个机器上的期望完成时间,找到每个任务的最早完成时间及其对应的机器;从中找出具有最小最早完成时间的任务,将该任务指派给获得它的机器;指派完成后,更新机器期望就绪时间并将已完成映射的任务从任务集合中删除。重复上面的过程,直到所有的任务都被映射完。该算法形式化描述如下:
假定T为所有未调度的任务的集合。
(1)判断任务集合T是否为空,不为空,执行(2);否则跳到步骤(7);
(2)对于任务集中的所有任务,求出它们映射到所有可用机器上的最早完成时间cij;
(3)根据(2)的结果,找出最早完成时间最小的那个任务ti和所对应的机器hj;
(4)将任务ti映射到机器hj上;并将该任务从任务集合中删除;
(5)更新机器hj的期望就绪时间rj;
(6)更新其他任务在机器hj上的最早完成时间;回到(1)。
(7)此次映射事件结束,退出程序。
Min-min算法完成一次映射事件的时间复杂度为O(n2m),其中n为一次映射事件需要完成映射的任务总数,m为可用的机器总数。
2.2 Max-min
Max-min启发算法非常类似于上面提到的Min-min启发算法。同样要计算每一任务在任意可用机器上的最早完成时间。不同的是Max-min算法首先调度大任务。任务到资源的映射是选择最早完成时间最大的任务映射到所对应的机器上。时间复杂度同Min-min一样也为O(n2m),其中n为一次映射事件需要完成映射的任务总数,m为可用的机器总数。
在Min-min算法中,每次都是选择小任务映射到执行快的机器上,这种映射会使得更多的任务映射到某一台或几台机器上,从而使得整个分布式系统中可用机器的负载不平衡。而Max-min算法同Min-min相反,它首先调度大的任务,一定程度上平衡负载。因此综合这两种算法的思想提出一种新的算法,该算法在对任务集合执行一次映射事件的过程中,会根据当前系统的负载平衡情况,动态的选择Min-min算法和Max-min算法中的一种来进行任务资源的映射。在本文中,称这种改进的新算法为MM算法。
2.3 MM算法
MM算法的思想借鉴于SA(Switching Algorithm)算法,SA是异构计算环境下,用来对任务进行在线模式映射的一种启发式算法。
分布式计算环境中,任一资源mi的期望就绪时间为ri,设所有机器的最大期望就绪时间为rmax,最小的期望就绪时间为rmin;设变量μ表示系统中机器间的负载平衡指数,μ=rmin/rmax,显然μ∈[0,1]。rmin=rmax=0,表明当前系统中所有机器都处于空闲状态,等待着任务的映射;μ=0,表明当前系统中存在处于空闲状态的机器;μ=1,表明当前系统中任务的分配基本处于平均状态。在算法中,为了轮回的调用Min-min和Max-min算法,设定了两个边界值rlow和rhigh。映射事件开始时,初始化变量μ=1。首先使用Min-min算法,当变量μ的值下降到rlow时,改用Max-min算法;当变量μ的值上升到rhigh时,在改用Min-min算法。如此轮回调用这两个启发式算法,直到此次映射事件结束。
另外Min-min算法和Max-min算法所执行的均是原子任务到资源的映射。在分布式系统中,一个计算任务所需要的数据往往是存放在另一个地方的数据库或数据仓库中,也就是说将一个任务分为计算子任务和数据传输子任务更为合理。但此处我们不将任务划分为更多的子任务,不考虑更多任务之间的依赖关系。对于分布式环境中包含计算子任务和数据传输子任务这样的任务,在调用Min-min启发算法或Max-min启发算法的过程中,需要同时考虑任务的数据传输和计算在存储资源和计算资源上的综合性能,所以需要修改这两个算法中求最短完成时间的部分。将传输和计算子任务看作一个整体,计算总的完成时间,并统一调度[7],即确定使之最快完成的一对(存储和计算)资源。
MM算法的执行过程如下:
(1)初始化变量μ=1;初始化机器的期望就绪时间向量r;给变量rlow和rhigh设定初值;
(2)定义变量μ1,该变量代表系统机器间负载平衡走向;初始化μ1<=0;
(3)任务调度集合T是否为空,T不为空,执行步骤(3);否则到步骤(7);
(4)若μ1<=0,μ>rlow,调用Min-min映射算法进行任务的映射;
若μ1<=0,μ=rlow,改用Max-min映射算法进行任务的映射;
若μ1>0,μ>rlow,调用Max-min映射算法进行任务的映射;
若μ1>0,μ=rhigh,改用Min-min映射算法进行任务的映射;
(5)更新向量r;
(6)更新变量μ和μ1,回到步骤(3);
(7)算法结束。
2.4 算法分析
MM算法是在不影响Min-min的最小完成时间的前提下,为了降低由该算法所引发的系统中机器间负载不平衡问题而提出的。在MM算法中,对于每一任务在映射前,都要首先判断系统的当前负载平衡指数,最坏的情况下需花费O(m)(m为系统中计算资源总数),在每次映射中,调用Min-min或Max-min的时间复杂度均为O(mfn2),其中m为系统中计算资源总数、f为系统中存储资源总数。
3 结束语
本文介绍了异构计算环境下适用于原子任务调度的经典的批模式的启发算法:Min-min和Max-min。针对Min-min算法可能引发的负载不平衡,采用轮回调度Min-min和Max-min的策略,生成了一种新的映射算法MM。在分布式计算环境下,资源更是处于一种异构的环境,并且计算资源和存储资源等往往处于一种分布的状态。更多的任务不在是原子任务,而是包含计算和数据传输两部分。考虑任务的数据传输和计算在存储资源和计算资源上的综合性能,在MM算法中,修改了Min-min算法和Max-min算法中求最早完成时间的方法。对计算资源和存储资源进行统一调度,更好的适应于分布式计算系统。最后在Matlab 7的仿真平台下进行模拟实验,仿真结果表明该算法确实可行有效。当然对于任何启发式算法,其性能都受很多因素的影响。比如任务到达的速度,任务中长短任务的比例,任务中计算和数据传输比例等,所以值得改进的地方也还有不少,重点研究各个因素对MM算法性能的影响。
参考文献
[1]王磊,黄文奇.求解工件车间调度问题的一种新的邻域搜索算法[J].计算机学报,2005,28(5):60-67.
[2]张德富,李新.求解作业车间调度问题的快速启发式算法[J].计算机集成制造系统-CIMS,2005(2):89-93.
[3]谢志强,刘胜辉,乔佩利.基于ACPM和BFSM的动态Job-Shop调度算法[J].计算机研究与发展,2003,40(7):79-85.
网格环境中任务调度算法的研究 篇8
随着网络在人们日常生活和工作中的日益普及,以及因特网的飞速发展,在网络中聚集了大量的可用资源,比如计算资源、存储资源、仪器设备等等。而这其中被闲置的、浪费的资源不计其数,因此,为了解决这一资源浪费问题,一种新的技术———网格技术出现了。它试图将这些资源进行整合,构成一个高性能的计算环境,实现计算资源共享和协同工作,使用户以最小的投入获得最大的计算效率和处理能力。但网格环境极奇复杂,不确定的因素太多,比如处理机之间通信的延迟、网格资源的动态性和异构性等等,故而拥有一个良好的任务调度算法才能保障网格中各类资源的协同工作,这样用户在调用算法时才能得到满意的结果,拥有好的体验。
1. 传统算法的分类
网格环境是一个异构系统,故而它的任务调度问题就显得非常关键,很明显它属于NP完全问题,因此,任务调度成为了网格计算中讨论的焦点,引起了很多学者的关注。传统的调度算法根据其思想的不同主要分为4类。
1.1 表调度算法
它的基本思想是首先确定各节点的优先级,并按照优先级将节点进行排序,之后用排序的结果来构造调度列表,最后按照以下两个步骤重复循环地操作,直到任务图中的节点全部被调用完[1]:1)按顺序从调度列表中取出一个节点;2)把此节点分配到处理机(此处理机具有使它的启动时间最早的能力)上。经典的算法主要有ETF(Earliest Task First)、MCP(modified Critica Path)、DLS(Dynamic Level Scheduling)等。
1.2 基于任务复制的调度算法
它的基本思想是将要执行的一些任务重复地分配到某些处理机上,想通过此方式来减少处理机之间的通信开销,换句话说,此算法的思想是想利用处理机的空闲时间来复制前驱任务,借此来减少需要传输的数据量,最终达到缩短处理器等待的时间[2]。经典算法主要有DSH(Duplication Scheduling Heuristic)、BTDH(Bottom-up Top-down Duplication Heuristic)、CPFD(Critical Path Fast Duplication)等。
1.3 基于任务聚类的调度算法
它的主要思想是把等待执行的所有任务分配到集群上,这些集群是没有数量限制的。假如在同一个聚类中有多个任务被分配到了,那就表示在同一个处理机上会对它们进行处理,在进行了聚类制作之外,最后还要在每个处理机上对聚类中的任务按时间的先后进行排序[3]。经典的算法主要有DSC(Dominant Sequence Clustering)、DCP(Dynamic Critical Path)等。
1.4 基于随机搜索的调度算法
它的基本思想不是简单的、纯粹的随机搜索,而是通过有指向性的随机选择来搜索问题的解。此类技术可以将前期搜索结果与特定的随机搜索特点进行整合,从而产生新的结果。经典的算法主要有遗传算法。遗传算法的调度结果一般情况下都是比较好的,但它的时间复杂度往往也比较高,并且在算法执行过程中需要确定相关的控制参数。另外在实际应用中不同的任务最优控制参数也是不同的,要找到能让大多数任务执行后有较好调度结果的控制参数很难。在当前的网格环境下,主要研究的是独立的任务调度,这与实际的网格环境(异构环境)特征不相符,此类的经典算法主要有Max-Min和Min-Min等。当然也有一些算法考虑到了异构环境下任务间的约束问题,如DLSLMT等。
2. 算法的对比与分析
2.1 ETF算法
ETF(Earliest Task First)是表调度的一个代表性算法。此算法首先计算出某个进入就绪状态的节点在每个处理机上的最早启动时间,通过将这些时间进行比较,选出那个最早启动时间的节点处理机,如果有多个时间是相同的、并且是最早的,那么选择静态b-level更大的。ETF算法要经历两个过程:一是确定任务图中各任务的优先级;二是要选择出适合的处理机来执行具有最高优先级的任务。ETF算法能够早早地计算出任务的最早启动时间,这是它最大优点;不足之处是它的每一次调度不能有效地减少任务图中当前的调度长度。另外,网格是分布式的异构环境,其中的资源是动态变化的,节点可能会随机地增多或剔除,通常情况下,处理机增多,理应会缩短任务的完成时间,但在调用ETF算法时,在处理机增多的情况下,任务的完成时间也不会减少。
2.2 DSH算法
DSH(Duplication Scheduling Heuristic)算法是基于任务复制调度的代表性算法[4]。此算法的思想是把每一个处理机上正在调度任务的启动时间与某个被调度任务的完成时间之间的间隔作为任务复制的间隔,算法尽最大可能地复制某个正在被调度任务的前驱任务到此间隔,直到间隔被填满或者被调度任务的启动时间不再被改善。此算法在同构环境中对于处理机间的通信延迟有所改善,它在执行任务的同时还要不断地复制其它任务,并且要对这些任务进行备份和存储,所以它的执行效率不是很高,在实际的网格环境中很难实现,因此,它只限于理论研究。
2.3 FCBSH算法
FCBSH算法是经过了改进的聚类算法。它的核心思想是最大限度地减少每个任务的完成时间[5]。但任务的完成时间由两个因素来决定,一是任务的起始时间,二是任务的执行时间。其中任务的起始时间由其前驱任务的执行情况和所在处理单元网络位置以当前任务的执行情况和所在处理单元网络位置决定。因此,将一个任务分配到目标系统中哪个处理单元来执行,对后续任务的执行情况影响很大。此算法有效地缩短了选择处理机的时间,而把大块的时间用于任务的处理,减少了一些时间开销。当然,此算法也有缺陷:它没有考虑网格环境(异构环境)下节点可以自由添加和退出,此外它还忽略了通信延迟及链接竞争等情况,因此它是一个理想状态下的算法。
2.4 遗传算法
遗传算法(Genetic Algorithm)是模拟生物进化而来的一种随机搜索算法。它通过模拟生物进化过程,根据遗传学机理和自然选择理论,挑选和生物遗传论中类似概念的变异因子和遗传因子,以父类杂交诞生子类,子类经过筛选变异再诞生子类的思想,进行算法模拟,从而能够动态地、先进地解决许多棘手算法问题,具有动态性和灵活性的特点。
遗传算法的求解过程,通过选择、交叉、进化流程迭代的动态的产生问题的近似解,与传统算法追求最优解不同,其所期望的结果是满意解。这就让遗传算法在工程使用中有了很强的实用性。而传统的遗传算法比较简单,只是对任务的粒度进行了理想化的划分,忽略了任务间的联系及通信开销,且为局部收敛[6]。近年来,国际学术界对其进行的一系列改进,可谓数目繁多,应用于网格的遗传算法也已经逐渐走入了人们视野,例如:J.Herrera(2005)等人提出的面向网格遗传算法、D.Lim(2006)等人提出的基于网格计算的多层并行遗传算法等。不难看出,遗传算法在网格上的发展和应用将会继续发展下去。
3. 算法存在的问题
经上文对几种经典算法的分析与对比,不管是国际的,还是国内的,都存在一些没有解决的问题,应用过程中将它们进行了理想化。而在现实的网格环境(异构环境)中,随时都有可能出现不可预料的问题,它们主要表现在以下几方面。
(1)现有算法都没有考虑网格环境中各节点执行任务的时间和处理机之间的通信延迟,认为它们是固定的、没有变化的,或是按线性关系进行变化。而现实的网格环境中,这些都可能随机地发生变化,并且变化是无规律的、复杂的,能够准确地描述这些变化的算法到目前为止还没有出现。
(2)现有算法的执行都是基于或多或少假设条件下进行的,例如任务之间的联系是确定的,处理机处在同构环境中并且连接完好,链路畅通无冲突,任务能够在任何处理机上执行等,而在实际的网格环境下,情况非常复杂,任务之间的联系是随机的、不确定的,处理机也处在异构环境中,传递信息或数据时链路冲突也是随时可能发生的,正因为有这诸多的因素存在,现有算法在实际应用时就会受到很多限制。
(3)众所周知,DAG图调度的本质就是一个Max———Min问题[7],也就是要均衡最大化任务的并行度和最小化任务间的通信时间,而对这个均衡点起关键性作用的因素就是DAG图的粒度选择,当前所有调度算法对各任务的粒度划分是相同的,完全没有考虑实际情况的多样性。
(4)目前也出现了很多基于某某算法的改进算法,但这些算法在改进的过程中,往往是以牺牲某一方面性能为代价的,改进能力有限,没能很好地均衡调度算法的核心参数。
(5)在异构的网格环境中,现有算法在某种程度上忽略了节点的动态性,节点是可以随机加入或退出的,这样就会存在这种情况:正在执行任务的节点突然退出了,但算法却没有给出一种对任务运行状态进行保存的容错机制,而是忽略不计或重新分配任务并执行。
4. 总结
经过对各类型经典算法的对比与存在问题的分析,现有网格环境中任务调度算法还没有达到预期效果,因此还有很多工作要做,结合分析情况,可以从两个方面来入手:一是全面、充分地了解实际的网格环境,分析它的特性,设计一个真实、可用的、非理想状态的通用算法,在算法中要充分地考虑网格环境的异构性、动态性、节点之间通信延迟的随机性,以及任务粒度划分的不可预料性等等;二是要均衡考虑任务执行时的核心参数,设计的算法要能使得任务调度的结果达到全局最优。
因此,在复杂多变的网格计算环境中建立一个并行的应用模型,并设计一个通用的任务调度算法是一个非常艰巨的任务。笔者后期将继续阅读国内外的相关文献,力求在这一方面有所突破。
摘要：本文通过对四种不同的任务调度形式及相应的经典算法进行分析对比,总结出了当前网格环境中任务调度存在的问题,指出了后期研究网格任务调度的方向。
关键词：任务调度,算法,网格
参考文献
[1]Lan Foster,Carl Kesselman,Sleven Trecke.The Analomy of the Grid Enabling Scalable Virtual Organizations|J|.|nl|J Supercomputer Applications,2001:1-25
[2]Annie s,Wu,Han Yu,Shiyuan Jin等.An incremental genetic algorithm approach to multiprocessor scheduling.IEEE Transactions on Parallel and Distributed Systems,2004,15(9):824-834
[3]段立荣,曹礼宇.网格中任务调度机制研究.山西科技,2006,5:58~61
[4]林剑柠,吴慧中。一种基于任务复制调度算法研究,小型微型计算机系统,Vo 1127 No.7 July 2006
[5]杜晓丽,蒋昌俊,徐国荣,丁志军。一种基于模糊聚类的网格DAG任务图调度算法,软件学报,Vol.17,No.11,November 2006
[6]李力,薛胜军,网格任务调度机制的研究,现代计算机(专业版),2008.4
基于任务划分算法的基准程序研究 篇9
随着多媒体应用的不断发展, 无论是在教学、娱乐、咨询还是军事领域, 多媒体技术都被广泛地应用, 特别是图像和视频方面。由于通用处理器的灵活性, 大多数多媒体任务在通用处理器上通过软件编程的方式实现, 并得到了很好地应用。但对于实时性较强的嵌入式系统, 在CPU性能不高的情况下, 多媒体任务的处理会占据大量CPU资源, 而且处理的实时性不是很强。为了提高多媒体任务处理的效率, 同时也为减轻通用处理器的运算压力, 针对多媒体任务处理的可重构媒体处理器应运而生。它们作为通用处理器的协处理器, 与微处理器一起构成了可重构计算系统, 能很好地解决多媒体处理问题。
可重构计算 (Reconfigurable Computing) 是一种新的计算系统范例, 综合了通用处理器和ASIC的长处, 通过对可重构硬件进行配置, 使之由一个通用的计算平台转化为一个专用的硬件系统, 以完成具体的计算任务, 相当于计算任务同时在时间和空间上展开, 兼顾灵活性和计算高性能, 因此在多媒体处理[2]、嵌入式系统[3]、密码学[4]、图像压缩[5]等计算密集型应用中发挥了巨大的优势, 成为当前的研究热点。在提供强有力的计算平台的同时, 可重构计算也提出了一些新的研究课题, 面向数据流图 (DFG) 的任务划分就是其中之一。
1 任务划分
可重构计算系统的典型结构包括一个微处理器和可编程硬件。由于可重构硬件能够提供的资源是有限的, 当计算任务所需的资源大于硬件资源时, 就要对任务进行划分, 任务划分即把一个任务在时间上划分成相互关联的子任务 (称作模块) [6], 每个模块分时复用硬件资源, 从而完成整个任务。
任务划分建模:
可重构系统的高层综合中, 通常采用有向无环图作为中间表达形式, 例如, 数据流图 (DFG) 、控制流图 (CFG) 、信号流图 (SFG) 等。任务划分也采用DFG图作为任务的中间表达形式, 进行建模。因此, 任务划分问题从根本上可以归结为一种任务图划分问题。
1) 定义1:任务的DFG图是一个有向无环图 (DAG) , 定义为四元组G=
2) 定义2:={P1, P2, ……PN}是DFG G=
图1是一个待划分任务的DFG图。图中每个节点表示一个操作, 每条边代表节点之间的依赖关系。在满足面积约束、前后依赖约束的情况下, 该任务被划分成6个模块, 分别用P1、P2、P3、P4、P5、P6表示。由图可见, 模块1、2、3之间没有依赖关系, 模块4依赖于模块1, 模块5依赖于模块2和3, 而模块6依赖于模块4和模块5。在执行该任务时, 要保证时间上的先后性, 即让模块1、2、3先于模块4、5执行, 模块4、5先于模块6执行;同时, 保证任务之间的并行性, 让尽可能多的任务能够同时进行。这样可以实现在资源受限的动态重构的系统上, 执行规模较大的应用。任务划分实例如图1所示:
通过上例可以得出, 在进行任务划分的时候, 需要考虑很多因素, 细分下来有如下几点:
1) 模块数量。模块数量和配置次数有关, 模块越多, 配置所需时间越长, 则总执行时间就越长;
2) 模块并行度。每个模块中可以并行的操作越多, 其关键路径越短, 系统总处理时间就越少, 效率就越高;
3) 模块间通信。模块之间的通信量体现为模块之间的边数。边数越多, 表示模块之间依赖关系越强, 用于块间传递数据的时间越久, 影响总的执行时间。
2 性能基准程序的原理和方法
性能基准程序是以单个良好定义的任务或者一组任务形式出现的, 用来度量计算机系统或构件性能的一个测试。这些任务被称为工作负载[7]。在基准程序法中, 必须明确规定所选用的基准程序及其特性、运行方式, 并规定评估指标体系。
2.1 基于任务划分的性能基准程序
任务划分是可重构系统高层综合的一个步骤, 目前没有针对这一特定应用的性能基准程序, 不同的算法提出者采用不同的基准程序对算法性能进行评定, 给任务划分算法的横向比较带来了一定的困难。考虑借鉴已有基准的构造方法, 结合任务划分算法的主要性能指标和多媒体的典型应用, 按照如下原则选取基准程序:
1) 具备基准程序的基本特性
(1) 可再现性; (2) 代表性; (3) 可扩展性; (4) 可观测性:可通过基准的划分结果, 对算法进行比较。
2) 具有流媒体运算的典型性
复杂的流媒体、音视频应用一般包括几个子任务, 每个子任务都有不同的特点。这些任务分为低层、中层、高层。其中低层任务占整个处理的绝大部分, 以MPEG-2视频编码为例, 包括DCT、ME等底层操作占了整个任务的89%。因此, 我们从流媒体应用的低层任务中选择基准程序, 按照计算量从小到大, 选择不同的基准程序 (体现在DFG图中就是节点数量的多少) , 从而体现出任务规模对于划分模块数这一指标的影响。
3) 具有内在并行性
选择的基准具有内在并行性, 适合于在可重构阵列上执行。考虑在任务规模相同的情况下, 选择并行度不同的基准程序, 以便反映出不同的并行度对于任务划分的任务执行时间和块间通信的影响。
2.2 所选基准定性分析
所选的有限脉冲响应滤波器 (FIR) 、快速傅里叶变换 (FFT) 、离散余弦变换 (DCT) 等基准程序都是多媒体音、视频信号编码/解码, 压缩/解压缩中常用的计算, 具有一定的代表性。对其中一些基准进行如下的定性分析:
1) FIR
数字滤波器通常应用于修正或改变时域或频域中信号的属性, 在通信、模式识别、语音和图像处理等领域都有着广泛的应用。FIR (有限脉冲响应) 滤波器是数字滤波器中最常用的一种, 它具有很好的稳定性, 并且容易分析。
带有常系数的FIR滤波器是一种线性时不变数字滤波器。N阶或者长度为N的FIR输出对应于输入时间序列x[k]的关系由一种有限卷积数量形式给出, 具体形式如下:
在实际应用中, 对多媒体信号的处理通常要求具有实时性和灵活性, 而现有的软件和硬件实现方式则难以同时满足这两方面的要求。随着可编程逻辑器件的发展, 可以通过可重构器件实现FIR滤波器, 利用FIR对信号处理中的相频特性就可以实现实时性的要求, 又兼顾了一定的灵活性。
2) DCT
离散余弦变换与傅里叶变换很相似, 在傅里叶变换的展开式中, 如果被展开的函数是偶函数, 那么其傅里叶级数中只包含余弦项, 再将其离散化可导出余弦变换。这个原理可以应用到图像中, 图像是由很多像素构成的, 每个像素都会带有X, Y坐标, 利用点阵将像素翻译为亮度值或者灰度值。在进行RGB图像压缩时, 需要进行三遍压缩, 利用坐标变换得到像素的三维表示方法, 通过DCT变换将空间表达式转化为频谱表达式或者频率域, 将像素信息集中到少数的频率分量, 从而达到数据压缩的目的。
设源图像像素点坐标为x (i, j) , 变换后矩阵元素为X (u, v) , 0≤i, j, u, v≤7。二维DCT变换的数学定义为:
3) FDCT
有DCT分析可看出, 二维DCT的运算量很大, 耗费很多的运算时间, 因此对快速离散余弦变换进行研究很有必要。二维DCT的一个重要特性是可分解性, 即二维的DCT运算可以分解一维DCT来运算。目前的快速DCT算法都是先按行进行8次8点的一维DCT来运算, 再按列进行8次8点的一维DCT。8点的一维DCT需要64次乘法和64次加减法, 一个8×8大小的块需要作8+8=16次一维DCT, 一共是1024次实数乘法和加减法才能完成。这是行列分解后基本的运算量。8点的一维DCT运算的数学定义为:
0≤i, u≤7其中, x (i) 为输入序列, X (u) 为输出序列。
3 结论
任务划分可将任务在时间上划分成相互关联的子任务, 每个子任务分时复用硬件资源, 在完成整个任务的同时, 还可以提高硬件资源的利用率。本文在考虑任务划分的3个优化目标的基础上, 借鉴已有的基准程序构造方法, 并结合多媒体应用的特点, 提出了任务划分算法的基准程序的构造方法。采用此方法, 选取了一组基准程序, 并对FFT、FIR、DCT和FDCT等基准进行了定性分析。
摘要：为了提高任务在可重构系统上的执行效率和硬件资源利用率, 需要对任务进行划分, 划分成多个子任务, 子任务分时复用硬件资源。本文在对任务划分建模的基础上, 提出了评估任务划分算法的指标体系, 并借鉴已有的基准构造方法, 结合任务划分算法的主要性能指标和多媒体应用的特点, 给出了评估任务划分算法的基准程序的构造方法。
关键词：可重构计算,任务划分,数据流图,基准程序
参考文献
[1]Estrin G, Bussel B et al.Parallel Processing in a Restructurable Computer System[J].IEEE Transactions onElectronic Computers, 1963, 12 (6) :747-755.
[2]Barat F, Jayapala M, de Beeck P O, et al.Reconfigurable instruction set processors:an implementation platform for interactive multimedia applications.In:Conference Record of the Thirty-Fifth Asilomar Conference, Asilomar, IEEE CS Press, January2001:481-485.
[3]Campi F, TomaM, LodiA, et al.A VLIW processor with reconfigurable instruction set for embedded applications[J].IEEE Journal of Solid-State Circuits, 2003, 38 (11) :1876-1886.
[4]M Rencher, B L Hutchings, Automated target recognition on SPLASH2.In:Proceedings of IEEE Symposium on Field-Programmable CustomComputing Machines, Napa Valley, IEEE CS Press, April 1997:481-485.
[5]S Hauck, W D Wilson.Runlength compression techniques for FPGA configurations.In:Seventh IEEE Symposium on Field-Programmable Custom Computing Machines, California, IEEE CS Press, April 1999:286-297.
[6]孙康.可重构计算相关研究[D], 浙江大学, 2007.
[7]江建慧.嵌入式系统性能评估的基准程序法[J].机械与电子, 2002 (124) .
[8]汪泓澄.嵌入式系统的性能基准程序及任务时限违背率[D].同济大学, 2006.
【任务规划算法】推荐阅读：
任务规划10-05
城市总体规划任务09-08
小区规划任务书07-07
公园规划设计任务书11-25
修建性规划设计任务书07-05
建筑及规划设计任务书07-20
概念规划设计任务书10201-01
重庆双桥天星地块规划设计任务书05-09
县物价局工作规划和主要任务07-05