DAG任务图的一种调度算法

并行程序的调度技术是开发并行计算机系统的计算潜能的关键问题。本文讨论了4种典型的调度算法的缺陷，提出了一种新的调度算法CPFMBF，它采用的策略是：优先调度关键路径节点，其次调度b-level值大的节点，再次调度节点的关键路径影响度大的节点。对照分析及在几种具代表性的工程应用任务图上的实验结果证明CPFMBF算法的调度性能普遍好于其它算法。     

构造串行程序对应的并行任务(DAG)图

目前在并行计算研究领域中很大一部分工作是将串行程序并行化,如何发掘串行程序中存在的并行性,一个好的方法就是构造其对应的并行任务(DAG)图,对并行任务图的分析,调度和最终实现并行计算的工作已经有很多人做过,但是由串行程序构造DAG图的工作相对很少。论文分析了串行程序中存在的依赖关系,并以此为依据,提出了一种由现有的串行程序或者串行解决方案构造对应的并行任务(DAG)图的算法。     

串行算法并行化处理的数学模型与算法描述

并行计算是指同时使用多种计算资源解决计算问题的过程,节省了大量计算时间,极大地提高计算效率.目前各领域大量的串行程序已经相当成熟,所以如何通过一种转换,将现有大量的串行程序转化成并行程序,是提高程序运行速度的突破口.为了将串行程序并行化,以提高程序的运行效率,充分利用已经非常成熟的大量串行程序,文中从图论出发,建立并讨论了串行算法并行化的三个数学模型:有向带权图模型、集合划分模型、标记AVL树模型.通过这些数学模型,基于图论的思想方法,文中讨论了串行算法并行化的可行性,并提出了串行程序并行化的算法思想     

串行程序的依赖关系分析和向量化

本文提出了两种新的数据依赖关系分析方法——系数判别法和实分析方法,其中,系数判别法在GCD方法基础上,给出数组项之间精确的依赖关系,并直接给出依赖的方向.实分析方法没有目前其他分析方法所要求的下标为循环控制变量的线性函数的限制.并且,很自然地解决了Coupled subscr-ipts及隐关系的分析问题.另外,本文探讨了破除数据依赖关系的方法及向量化的问题.文中的算法均己在UNIX环境下实现.     

DAG图拓扑排序的动画实验模型设计

传统抽象的程序演示实验难以体现数据结构的本质.本文通过比较传统程序实验和具体化的多媒体动画实验,逐步演示抽象复杂的DAG图拓扑排序实现步骤,为掌握数据结构及其它课程提供直观有效的实验参考模型.     

基于区间编码的图结构XML数据上DAG匹配算法

图结构的XML数据被越来越多地应用在实践中,相关的问题也随之而生 .传统的XML树模型处理算法和图结构模型处理技术并不能够有效地处理图结构XML数据上的DAG查询 .提出了一种基于可达性区间编码的GraphJoin算法,利用区间桶这种数据结构,直接对图结构XML数据上的DAG查询进行全局匹配 .理论分析和实验结果表明,这种算法在查询时间和执行效率上好于现有的技术.     

串行线性赋值循环程序的终止性判定

对于并行赋值的线性循环程序,已有文献通过矩阵特征值方法来判定其终止性,但该方法并不适用于常见的串行赋值程序。该文通过把串行赋值程序转换为并行赋值的程序,再利用矩阵特征值和特征向量来对程序的终止性作出判定,从而扩大了该方法的应用范围。     

一种基于模糊聚类的网格DAG任务图调度算法

针对网格环境中,任务调度的目标系统具有规模庞大、分布异构和动态性等特点,提出一种基于模糊聚类的网格异构任务调度算法.以往的很多调度算法需要在调度的每一步遍历整个目标系统,虽然能够获得较小的makespan,但是无疑增加了整个调度的Runtime.定义了一组刻画处理单元综合性能的特征,利用模糊聚类方法对目标系统(处理单元网络)进行预处理,实现了对处理单元网络的合理划分,使得在任务调度时能够较准确地优先选择综合性能较好的处理单元聚类,从而缩小搜索空间,大量减少任务调度时选择处理单元的时间耗费.此外,就绪任务优先级的构造既隐含考虑了关键路径上节点的执行情况对整个程序执行的影响,又考虑了异构资源对任务执行的影响.实验及性能分析比较的结果表明,定义的处理器特征能够实现对处理器网络的合理划分,而且随着目标系统规模的增大,所提出的算法优越性越来越明显.     

基于任务延迟的云计算资源调度算法研究

云计算是基于互联网发展起来的新型计算模式,对网际间各个节点的计算能力达到了充分利用;为了提高用户对云计算的使用效率,一般要为用户任务进行合理的全局资源调度和本地资源调度;对于全局资源调度,提出了一种改进的DAG图方法,充分考虑了任务撤销后对全局资源调度的影响;对于本地资源调度,提出了一种基于任务延迟的资源调度方法,充分考虑了立即调度不能执行时,如何合理地配置本地计算资源和等待时间的问题;实验结果表明,提出的方法能较好地提高全局资源调度和本地资源调度的效能。     

概率构造算法与遗传算法融合的可重构计算系统硬件任务划分

提出一种概率构造算法与遗传算法融合的算法,通过引入表示划分结果多样性的度量方法,利用概率构造算法产生具有多样性的较优的初始群体,并在此基础上利用遗传算法寻求最优解.实验结果表明,该算法能够获得比已有的基于列表的划分算法更优的划分结果,比采用完全随机初始群体的遗传算法缩短了运行时间.     

基于串归约的网格工作流费用优化方法

针对截止期限约束下有向无环图DAG(directed acyclic graph)表示的工作流费用优化问题,提出两个新的费用优化算法:时间约束的前向串归约算法FSRD(forward serial reduction within deadline)和时间约束的后向串归约算法BSRD(backward serial reduction within deadline).算法利用DAG图中串行活动特征给出串归约概念;基于分层算法对串归约组的时间窗口重定义,并提出动态规划的求解策略实现组内费用的最优化.两种归约算法综合考虑DAG图中活动的串并特征,改变分层算法中仅对单一活动的费用优化策略,实现了串归约组的时间收集和最优利用.模拟实验结果表明: BSRD和FSRD能够显著改进相应分层算法的平均性能,且BSRD优于FSRD.     

基于任务复制的静态调度算法研究

任务调度是分布实时系统中的一个关键问题。基于任务复制的静态调度算法是任务调度问题中的研究热点。通过概括任务复制静态调度算法的算法模型以及基本术语后,详细分析比较了几种典型算法。还考虑了优化条件、调度长度、处理器数目以及时间复杂度等研究方向。最后,结合国内外研究现状,提出以减少处理器数目为研究目标。     

基于图模型的自动驾驶推理任务调度

随着车载传感器设备数量的增多,交通设施和城市地标的快速变化、人车混行的复杂路况,对自动驾驶车辆实时反应的能力要求不断地提高.如何通过带有安全性保证的调度策略来应对物理环境中源源不断产生的传感器实时源事件输入,如何及时地控制传动系统来处理源事件并进行推理操作及其响应以规避危险是值得研究的问题.为此,将自动驾驶汽车视为安全攸关系统,提出了一种硬实时推理任务调度方法,首先为自动驾驶的推理过程建立了基于可并行有向无环图的推理任务模型;其次,提出了自动驾驶推理任务调度算法及其准入算法,保证了所调度的推理任务都能在满足硬实时约束的情况下完成自动驾驶推理操作及其响应动作.最后,进行了模拟实验,实验结果验证了该调度及其准入控制算法的有效性.实验结果表明:推理任务调度算法比直接调度算法和模型转换算法在调度成功率上分别高出9.62%和7.31%,该推理任务准入控制算法比Baruah的准入控制算法在任务集准入率上平均高出7.15%.     

一种改进的并发程序静态切片算法

分析了Krinke切片算法对循环体内嵌套有线程的程序结构会产生切片不精确的现象,认为其原因是该算法对线程间数据依赖的定义过于粗糙,且对程序行为约束不够。该文提出一种新算法,在并发程序内部表示中,增加跨线程边界循环-承载数据依赖,并引入区域化执行证据约束程序行为。实例研究表明,该算法克服了Krinke算法的不精确现象。     

处理顺序约束的信息物理融合系统静态任务表调度算法

针对异构环境并行计算的静态任务调度问题,以最小化有向无环图 (Directed acyclic graph, DAG)的执行跨度为目标,改变HEFT (Heterogeneous earliest finish time)算法中任务上行权重的计算方法, 获得更加合理的任务顺序排列,提出了一种最早完成时间优先的表调度算法IHEFT (Improvement heterogeneous earliest finish time).该算法在计算任务的上行权重时, 分别计算该任务分配给不同资源的上行权重,取其最小值,比使用所有资源对该任务的平均处理时间进行计算的HEFT算法更为准确. 确定任务的处理顺序后采用最早完成时间越小越优先的策略将任务分配给最优资源,并使得任务的开始执行时间和结束时间满足DAG中有向边的通讯时间约束.通过使用部分文献中的算例数据以及随机生成满足一定结构要求的DAG进行算法测试,将IHEFT与HEFT, CPOP (Critical-path-on-a-processor)和LDCP (Longest dynamic critical path)进行了比较,结果显示IHEFT算法更有效,而且时间复杂度较低.     

一种新的优化串行直方图构造算法

串行直方图是基于频度排列对关系进行优化分区构造而成的,其连接结果大小估计是最优的,并可用于等值和范围查询结果大小估计。但是,串行直方图的构造算法复杂,影响了实际应用。本文从实用的角度出发,设计了一种构造优化串行直方图的算法BOS,该算法的时间复杂度大大降低,且估计精度接近最优直方图,从而使其具有较高的实用价值。     

基于有向无环图的成本-时间优化调度算法

网格计算环境下,基于有向无环图(DAG)的成本-时间优化调度算法运用经济规律把网格用户的任务映射到网格资源中运行.OGS算法考虑了任务间的优先关系,使得任务完成时间最小,但没考虑到在网格环境中所需的成本.Nimrod/G模型中提出基于时间和成本限制下的优化调度算法(DBC)考虑了时间和成本,但没考虑任务问的优先关系.本文综合考虑了成本-时间因素以及任务间的优先关系,在不增加完成时间的基础上,把任务映射到价格便宜的机器上,提出了基于有向无环图的成本-时间优化调度算法.通过仿真表明,相对OGS算法,该算法减少了所需成本.     

可重构计算的硬件任务调度算法

提出一种可以减少数据传输量的调度算法RDMS。通过在调度过程中综合考虑任务中数据的关联性、硬件任务的资源利用率及内部任务之间的通信量,采用动态编程方法,减少微处理器和FPGA可重构协处理器之间的通信量及FPGA可重构资源的消耗。实验结果表明,RDMS能提高映射在FPGA器件上硬件任务的整体性能,有效降低通信开销和重构开销。     

基于有向无环图的成本-时间优化调度算法

网格计算环境下,基于有向无环图（DAG）的成本-时间优化调度算法运用经济规律把网格用户的任务映射到网格资源中运行。OGS算法考虑了任务间的优先关系,使得任务完成时间最小,但没考虑到在网格环境中所需的成本。Nimrod/G模型中提出基于时间和成本限制下的优化调度算法（DBC）考虑了时间和成本,但没考虑任务间的优先关系。本文综合考虑了成本-时间因素以及任务间的优先关系,在不增加完成时间的基础上,把任务映射到价格便宜的机器上,提出了基于有向无环图的成本-时间优化调度算法。通过仿真表明,相对OGS算法,该算法减少了所需成本。