导读:本文包含了静态任务调度论文开题报告文献综述、选题提纲参考文献及外文文献翻译，主要关键词:多核,静态,算法,异构,拓扑,序列,处理器。
静态任务调度论文文献综述
宋宇鲲,韦龙龙,张多利[1]（2018）在《多核系统静态任务调度的启发式算法》一文中研究指出在任务调度研究领域,列表类调度算法的优化研究始终备受关注,针对经典列表调度算法难以获得理想调度解的缺陷,提出一种迭代型列表调度算法。该算法采用遍历宏块拓扑序列技术,扩大任务图拓扑序列搜索空间以得到更小的任务图调度长度。理论分析表明,对于任意的任务图,该算法得到的调度长度必不大于经典列表调度算法。以4种常见类型和随机类型的任务图样本证实,迭代型列表调度算法能够有效改善调度解,尤其在平均通信计算时间比超过1的情况下,调度性能的平均提升超过14.6%,最大提升达到102.8%。(本文来源于《电子测量与仪器学报》期刊2018年05期）
韦龙龙[2]（2018）在《通信约束下的多核系统静态任务调度算法的研究》一文中研究指出随着信息技术的发展,单核处理器时代渐渐退出了历史舞台,多核处理器的出现大大提高了计算机的性能。其中,一个高效的任务调度策略是提高多核处理器性能的关键。对于多核处理器的静态任务调度问题,经典列表调度(Simple List Scheduling,SLS)算法存在很多缺陷,因而难以获得较好的调度结果。本文通过理论分析和实例剖析了经典列表调度算法的不足,指出了经典调度算法的两个缺陷:经典列表调度算法在任务调度过程中,只考虑了任务优先级列表,而忽略了其它可能导致更短调度长度的任务拓扑序列;经典列表调度算法在为任务分配处理核时,所采用的贪心策略只能获取局部最优解而无法得到整体最优解。针对第一个缺陷,本文通过对传统遗传算法进行改进,应用在了列表调度中,提出了基于遗传算法的列表调度方案LSGA(List Scheduling Based On Genetic Algorithm)算法,通过一次一次的遗传和变异,有效地将众多的任务图拓扑序列纳入考虑范围之内。针对第二个缺陷,本文将蚁群算法映射在列表调度中,提出了基于蚁群算法的列表调度方案LSACO(List Scheduling Based On Ant Colony Optimization)算法,在为任务分配处理器内核的时候,通过一次一次的迭代,LSACO算法逐渐趋于最合理的处理器分配方案。针对片上网络通讯环境下的通信路径拥堵问题,本文从减少拥堵个数和减少拥堵时间的两个角度,对LSACO算法进行改进,提出了基于蚁群算法的多目标列表调度方案MLSACO(Multi-objective List Scheduling Based On Ant Colony Optimization)算法。MLSACO算法通过多目标系数加权的方案,不仅兼顾了任务调度长度,同时又缓解片上网络通讯环境下的通信路径的拥堵问题。本文选取了任务调度长度作为算法优劣的评判指标,又采用了四种常见类型的任务图和随机任务图,分别进行了四组性能统计测试。实验统计数据表明:在全互联的通讯环境下,LSGA算法和LSACO算法的调度结果要明显优于经典列表调度算法。同时,LSGA算法性能也优于ILS-Mb(Iterative List Scheduling with Macroblock)算法。尤其在通信权重比较大的情况下,LSACO算法的平均加速比可以达到119.9%。在片上网络的通讯环境下,MLSACO算法的调度性能也同样高于经典列表调度算法,而且可以有效的缓解片上网络通讯下的路径拥堵问题。实验数据表明,相比于经典列表调度算法,MLSACO算法缓解路径拥堵问题的概率普遍高于85%。(本文来源于《合肥工业大学》期刊2018-04-01）
陈慧丽[3]（2017）在《云计算环境下静态任务调度机制研究》一文中研究指出云计算使用分布式、并行化、虚拟化等多种技术将大量异构的计算资源统一结合在一起,形成一个庞大的虚拟资源池,为用户提供定制化的服务。云计算系统时刻要面临海量的数据和应用任务,如何实现对海量应用任务进行分配部署,使任务能以一种更合理的方式分配到各个计算节点上,从而降低计算时间、减少调度成本,同时确保计算节点之间负载均衡,保持集群的高利用率,已成为云计算领域中一个亟需解决的问题。本文以云计算中的静态任务调度为研究对象,分别对独立任务和依赖任务进行研究,并提出了相应的调度策略。以最小化任务总完成时间为调度目标,为云计算中的任务调度问题提出有效的解决方案。本文主要研究工作如下:(1)依据任务之间存在的关联关系,将任务抽象成独立任务和依赖任务,并分别建立相应的数学模型。针对独立任务调度,研究任务与资源之间的固有属性,并根据需求建立调度模型;针对依赖任务调度,根据任务在执行过程中存在的顺序约束关系将任务节点转换成有向无环图DAG模型,为后续调度机制的研究奠定基础。(2)针对独立任务调度,结合传统调度策略和启发式算法提出一种新的调度算法。传统PSO算法在粒子寻优过程中容易陷入局部最优解。为避免该不足,采用LBMM算法对任务进行预调度,将其结果作为初始粒子群的全局最优解,从而对粒子初始化操作进行优化;重新设计适应度函数并引入遗传算法(GA)中的交叉变异操作,扩展粒子的解空间,使粒子以更大概率搜索到最优解,并通过实验将改进后的算法与同类算法进行对比分析。(3)针对依赖任务调度,通过改进表调度算法,提出一种新的调度算法。根据DAG描述的依赖任务调度模型,充分考虑任务节点的层次性以及处理器性能的差异,在现有表调度的基础上优化任务的优先级确定过程,从出口任务开始递归确定各个任务的上行权重,从而确定各任务的执行先后顺序;在此基础上,采用插入策略和最早完成时间越小越优先的策略将任务分配给对应的资源,并通过实验验证算法的有效性。(4)设计并实现云计算平台任务调度系统。在该平台的核心调度器模块中加载本文提出的两种调度算法,针对云计算环境下的独立任务调度和依赖任务调度分别进行实例测试,验证本文提出算法的可行性。(本文来源于《武汉理工大学》期刊2017-05-01）
杨俊[4]（2016）在《多核系统静态任务调度问题研究》一文中研究指出由于传统单核处理器的性能已经遇到发展瓶颈,多核处理器应运而生并获得广泛应用。作为多核技术的一个重要方面,任务调度是备受关注的一类NPC(Non-deterministic Polynomial Complete)问题。对于多核处理器的静态任务调度问题,经典列表调度(Simple List Scheduling, SLS)算法难以获得满意的调度解。本文从经典列表调度算法缺陷——只考虑任务优先级列表而忽略其它对应于更好调度结果的任务图拓扑序列出发,以拓展任务图拓扑序列搜索空间为指导,提出了迭代型列表调度方法,并给出两种迭代型列表调度算法实现：ILS-Mb (Iterative List Scheduling with Macroblock)和ILS-RS (Iterative List Scheduling with Random Swapping).其中迭代型列表调度算法ILS-Mb通过遍历宏块拓扑序列扩大任务图拓扑序列搜索空间,迭代型列表调度算法ILS-RS则通过对换两个随机任务的优先级以生成新的任务图拓扑序列。ILS-Mb算法和ILS-RS算法的共同之处在于多次进行列表调度并根据调度长度最小化原则筛选最优调度解。本文进一步地结合粒子群算法采用多个初始最优解的基本思路提出组合型列表调度方法。组合型列表调度方法以多个最优任务图拓扑序列作为初始解避免单个任务图拓扑序列陷入局部最优解。迭代型列表调度方法和组合型列表调度方法的结合形成迭代-组合型列表调度方法,以更高的算法时间复杂度以期获取更小的调度长度。文中通过理论分析证明,对于任意的一个任务图,两种迭代型列表调度方法所得的调度长度必不大于经典列表调度算法。为证实本文提出的迭代型列表调度方法的良好性能,文中采用四种常见类型任务图生成大量的任务图样本进行两个部分的对比实验。统计结果首先表明：在全互联通讯环境迭代型的列表调度算法ILS-Mb和ILS-RS能够有效改善经典列表调度算法的调度解,尤其在通信代价比超过1的情况下,调度性能提升超过14.6%,最大的调度性能提升达到102.8%以上：在片上网络通讯环境ILS-Mb算法和ILS-RS算法的相对性能优势更加明显。统计结果指出迭代型列表调度算法的调度效果优于ALS (Advanced List Scheduling)和CPOP (Critical Path on Processor)算法。实验数据还表明ILS-Mb和ILS-RS算法对调度解初始值不具有敏感性。(本文来源于《合肥工业大学》期刊2016-04-01）
欧阳力多[5]（2015）在《基于元启发式算法的异构计算系统静态任务调度的研究》一文中研究指出异构计算系统将不同体系结构的处理单元组合起来,各个处理器选择适合自己的子任务进行处理,可以使系统的整体运算性能得到大幅提升。任务的分配调度需要依靠调度算法来支撑,高效的任务调度算法是提升异构系统整体性能的关键所在。异构多处理器环境下的任务调度问题被证明是NP完全问题,无法在多项式时间内得到最优解,针对该问题进行的广泛深入的研究,旨在提出更加高效的任务调度算法来升系统性能。启发式算法或元启发式算法被认为是解决该问题的有效方法。本文针对现有元启发式算法容易陷入局部最优,并且未充分利用处理器空闲时间等问题,在化学反应优化算法和遗传算法的基础上,将局部搜索和全局搜索相结合,并使用区间插入技术和任务复制技术,对异构计算环境下的任务调度问题进行研究,从而达到缩短调度长度的目的。论文具体工作如下:针对现有元启发式算法缺乏全局搜索能力的问题,本文在化学反应优化算法的基础上,对算法中的基本反应进行设计,提出了一种基于化学反应优化的元启发式任务调度算法。该算法首先反复利用拓扑排序对任务调度顺序进行排序,得到若干随机地满足拓扑结构的初始任务序列,然后利用化学反应优化算法的四种基本反应对初始任务序列进行重新地排列组合,目的是找出解空间内的最优解。任务到处理器的映射策略使用最早结束时间EFT,每个任务依次被分配到EFT最小的处理器上执行。为了验证算法的可行性和高效性,本文设计了一个用于验证和测试算法性能的仿真系统。实验结果表明,本文提出的算法与LSA算法和CPOP算法相比,具有更短的调度长度。针对现有调度算法在调度CCR较大的任务图时处理器利用率较低的问题,本文将区间插入技术和任务复制技术运用于遗传算法中,设计了一种基于遗传和任务复制的启发式任务调度算法。该算法首先记录所有任务的关键直接前驱任务,然后在遗传算法的每一轮迭代中,试探性地将当前任务的关键直接前驱任务冗余地复制到当前任务所对应的处理器上,如果能够使当前任务的AFT提前,那么确认该次复制有效,否则丢弃该冗余的前驱任务。通过这样的复制策略,能够有效地减少由于前后任务不在同一处理器而产生的通信开销,使得任务能够提前开始执行。仿真实验结果表明,改进后的调度算法,在调度长度、加速比、调度长度比率叁个方面明显优于HEFT算法和BGA算法。(本文来源于《湖南大学》期刊2015-04-07）
石祥龙[6]（2015）在《基于异构多核处理器的静态任务调度算法研究》一文中研究指出伴随着半导体制造工艺的发展,单位面积内所能集成的晶体管的数目已经达到极限,单核处理器碰到了无法逾越的障碍,多核处理器逐渐变成人们研究的热门和重点。多核处理器分为同构多核处理器和异构多核处理器,专家学者和界内人士普遍认为异构多核处理器将会是未来的主流处理器。任务调度的顺序将会直接影响处理器的性能,因此,异构多核处理器的任务调度研究已经成为研究热点。异构多核处理器的任务调度已经被证明是NP完全问题,目前还没有算法可以在多项式时间内求得最优解,现有算法大都是使用启发式的算法求得近似解,而其中的基于列表调度算法应用较为广泛。经典的基于列表调度算法有HEFT(Heterogeneous Earlier Finish Time)算法和HCNF(Heterogeneous Critical Node First)算法。HEFT算法按照ranku非递增次序调度任务,使用区间插入技术分配任务。HCNF算法优先调度关键任务,使用任务复制技术分配任务。以上算法存在调度结果不理想、处理器空闲时间段较多等问题,众多专家学者对此都提出了改进方案。综合考虑任务的约束依赖关系对调度结果的影响,使用区间插入技术和任务复制技术充分利用处理器的空闲时间段。本文吸取典型算法的优点,并综合专家学者的改进策略,在现有算法的基础上加以改进。为了评价改进算法的性能,本文通过具体的测试用例说明改进算法的具体实现过程,并对比调度结果,接着设计测试方案,调度随机生成的DAG任务图集,对实验结果进行分析比较。通过实验证明,改进算法可以在一定程度上缩短任务调度的长度,提高处理器的性能。(本文来源于《南京邮电大学》期刊2015-03-01）
李静梅,孙冬微,韩启龙[7]（2014）在《基于异构CMP的静态任务调度研究》一文中研究指出现有任务调度算法在选取任务优先级参数时仅仅考虑单一属性,且没有及时处理冗余任务,针对这一问题,提出一种异构CMP中列表与复制优化任务调度算法-HLDOTS算法.该算法首先对任务图中某些特殊的任务进行优化;综合考虑任务的多个属性来为任务分配优先级,构造调度列表;在任务分配阶段,采用基于插入的策略和任务复制技术将当前任务分配到最早执行完成该任务的处理器上;并逐层对调度结果中产生的冗余任务进行处理,将任务分配与冗余任务处理交替进行,避免了冗余任务对处理器资源的浪费,提高了处理器的资源利用率和任务调度效率.采用随机生成图进行模拟实验,实验结果表明,HLDOTS算法较HEFT算法、CPOP算法和HCPFD算法取得了更好的调度性能.(本文来源于《小型微型计算机系统》期刊2014年12期）
叶佳,周鸣争[8]（2014）在《物联网环境下具有顺序约束关系的静态任务表调度算法》一文中研究指出针对物联网异构调度环境下并行计算的静态任务调度问题,提出了一种基于最早完成时间策略改变调度顺序的表调度算法HDPTS。该算法针对现有表调度算法在调度前不能准确地确定调度顺序的问题,在IHEFT算法的基础上添加了一个动态优先级调度策略,当节点的前驱任务都已经完成调度任务时,就改变该节点的调度优先级。任务优先级的计算在所有前驱任务到达这个任务的最晚完成时间与所有资源上最大可以使用时间之间取最大值的基础上,同时考虑到分配到各个资源上的任务对后继任务的影响和资源上的负载情况,以及上行权重的计算值和对出口任务的影响,使得优先级计算更加合理,能够根据任务分配动态合理改变任务调度顺序。通过随机生成一个算例进行测试,结果表明HDPTS比IHEFT、HEFT在调度长度方面减少14.29%;对大量随机产生的特定结构的有向无环图(DAG)进行测试,测试结果显示HDPTS算法比IHEFT、HEFT和LDCP算法更有效。(本文来源于《计算机应用》期刊2014年09期）
孙冬微[9]（2013）在《基于异构CMP的静态任务调度算法研究》一文中研究指出随着CMP的出现,如何提升其运行效率和最大化并行性倍受国内外专家和学者的关注。系统性能的提升不仅与硬件平台有关,同时也离不开硬件平台上的优化软件设计,只有两者充分结合,才能充分发挥硬件平台自身及软件设计的优良性能。因此,CMP任务调度问题已经成为高性能CMP研究领域的热点之一。鉴于CMP平台的优良性能和未来发展趋势,本文将异构CMP上的静态任务调度算法作为研究对象,设计一种适合其硬件平台且性能较好的静态任务调度算法,该算法能够缩短全部任务执行完成时间,充分发挥出异构CMP的性能优势,提升CMP的执行效率。本文通过对CMP架构、任务调度技术及其现有四种经典异构CMP上的静态任务调度算法进行分析,并针对现有静态任务调度算法的不足,提出一种全局较优任务调度算法。新算法首先对任务图中某些特殊任务进行归并优化;然后通过任务分层、标记关键任务和任务优先级权值计算叁个过程顺序执行来构造任务调度列表;最后在任务分配的同时加入冗余任务处理过程,两个过程交替进行,直到所有任务调度完成。新算法保证逐层调度任务,考虑赋予关键任务较高优先级,缩短整个任务图的总完成时间。在任务分配时,采用区间插入和任务复制技术,通过在空闲时间段进行必要的插入和复制,复制当前任务的关键父任务来提前当前任务的最早完成时间,同时对冗余任务进行了检测、删除操作,充分利用处理器资源,提前后续任务的最早完成时间;且能及时删除调度结果中的冗余任务,避免处理器资源的浪费,缩短全部任务执行完成时间,最终提升了整个CMP的性能。为了验证全局较优任务调度算法的可行性和高效性,本文采用TGFF随机生成大量具有不同特点的任务图,在不同的硬件条件下对算法进行测试,并在Matlab平台编程实现该算法,验证新算法的调度性能。实验结果表明:新的算法继承了现有算法优先调度关键任务的优点,同时改善了现有算法的任务优先级选取过于单一所产生的局部较优调度结果的问题,且能有效的处理任务复制所带来的冗余;在任务执行过程中,任务间的并行性明显提高,任务总调度长度也明显减小,达到了算法改进的预期效果,实现了全局较优的调度性能,为异构CMP中任务调度问题的研究提供了一定的借鉴意义。(本文来源于《哈尔滨工程大学》期刊2013-12-01）
李静梅,孙冬微,吴艳霞[10]（2014）在《一种全局较优的静态任务调度算法》一文中研究指出针对现有任务调度算法优先级选取过于单一所产生局部较优调度结果的问题,从全局较优出发,提出一种先分层后分支决定优先级的静态任务调度算法—HGCOTS算法。该算法考虑了任务间较大的通信开销和冗余任务对异构CMP任务调度效率的影响,通过综合区间插入和任务复制技术最大限度地降低了任务间的通信开销,对冗余任务进行删除,明显提高了任务调度效率。使用随机生成图进行模拟实验,与其他算法相比,新算法具有更小的调度长度。(本文来源于《计算机应用研究》期刊2014年04期）
静态任务调度论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
随着信息技术的发展,单核处理器时代渐渐退出了历史舞台,多核处理器的出现大大提高了计算机的性能。其中,一个高效的任务调度策略是提高多核处理器性能的关键。对于多核处理器的静态任务调度问题,经典列表调度(Simple List Scheduling,SLS)算法存在很多缺陷,因而难以获得较好的调度结果。本文通过理论分析和实例剖析了经典列表调度算法的不足,指出了经典调度算法的两个缺陷:经典列表调度算法在任务调度过程中,只考虑了任务优先级列表,而忽略了其它可能导致更短调度长度的任务拓扑序列;经典列表调度算法在为任务分配处理核时,所采用的贪心策略只能获取局部最优解而无法得到整体最优解。针对第一个缺陷,本文通过对传统遗传算法进行改进,应用在了列表调度中,提出了基于遗传算法的列表调度方案LSGA(List Scheduling Based On Genetic Algorithm)算法,通过一次一次的遗传和变异,有效地将众多的任务图拓扑序列纳入考虑范围之内。针对第二个缺陷,本文将蚁群算法映射在列表调度中,提出了基于蚁群算法的列表调度方案LSACO(List Scheduling Based On Ant Colony Optimization)算法,在为任务分配处理器内核的时候,通过一次一次的迭代,LSACO算法逐渐趋于最合理的处理器分配方案。针对片上网络通讯环境下的通信路径拥堵问题,本文从减少拥堵个数和减少拥堵时间的两个角度,对LSACO算法进行改进,提出了基于蚁群算法的多目标列表调度方案MLSACO(Multi-objective List Scheduling Based On Ant Colony Optimization)算法。MLSACO算法通过多目标系数加权的方案,不仅兼顾了任务调度长度,同时又缓解片上网络通讯环境下的通信路径的拥堵问题。本文选取了任务调度长度作为算法优劣的评判指标,又采用了四种常见类型的任务图和随机任务图,分别进行了四组性能统计测试。实验统计数据表明:在全互联的通讯环境下,LSGA算法和LSACO算法的调度结果要明显优于经典列表调度算法。同时,LSGA算法性能也优于ILS-Mb(Iterative List Scheduling with Macroblock)算法。尤其在通信权重比较大的情况下,LSACO算法的平均加速比可以达到119.9%。在片上网络的通讯环境下,MLSACO算法的调度性能也同样高于经典列表调度算法,而且可以有效的缓解片上网络通讯下的路径拥堵问题。实验数据表明,相比于经典列表调度算法,MLSACO算法缓解路径拥堵问题的概率普遍高于85%。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
静态任务调度论文参考文献
[1].宋宇鲲,韦龙龙,张多利.多核系统静态任务调度的启发式算法[J].电子测量与仪器学报.2018
[2].韦龙龙.通信约束下的多核系统静态任务调度算法的研究[D].合肥工业大学.2018
[3].陈慧丽.云计算环境下静态任务调度机制研究[D].武汉理工大学.2017
[4].杨俊.多核系统静态任务调度问题研究[D].合肥工业大学.2016
[5].欧阳力多.基于元启发式算法的异构计算系统静态任务调度的研究[D].湖南大学.2015
[6].石祥龙.基于异构多核处理器的静态任务调度算法研究[D].南京邮电大学.2015
[7].李静梅,孙冬微,韩启龙.基于异构CMP的静态任务调度研究[J].小型微型计算机系统.2014
[8].叶佳,周鸣争.物联网环境下具有顺序约束关系的静态任务表调度算法[J].计算机应用.2014
[9].孙冬微.基于异构CMP的静态任务调度算法研究[D].哈尔滨工程大学.2013
[10].李静梅,孙冬微,吴艳霞.一种全局较优的静态任务调度算法[J].计算机应用研究.2014
论文知识图
