基于综合调度关键路径的多核任务调度研究.doc

工学硕士学位论文 工学硕士学位论文师：哈尔滨理工大学 ： 作者签名：叼链豸氅叁哈尔滨理工大学硕士学位论文使用授权书吼训年岁日新躲琢引屯 针对关键路径上的某一节点开始执行时，当前任务图中的关键路径可能已经产生了变化，如不重新查找关键路径不能保证下一待调度节点仍为关键节点的问题，提出了基于动态关键路径的多核调度算法。该算法通过将任务图转换为产品加工树，并在加工树中按层序将产品加工树分解成子树，在子树中查找关键路径，并且优先调度关键节点形成调度序列。当该子树调度完毕后，将其整体虚拟为一个任务节点，加入上一级子树中进行调度，直到产品加工树中所有节点调度完毕为止。 哈尔滨理工大学工学硕士学位论文瑃 瑃琹 哈尔滨理工大学工学硕士学位论文 哈尔滨理工大学工学硕士学位论文目 哈尔滨理工大学工学硕士学位论文本章小结结论参考文献攻读硕士学位期间所发表的学术论文致谢 哈尔滨理工大学工学硕士学位论文琒提高处理器性能的方式遇到了功耗过大，散热问题严重，设计成本过高等问题甈，这种处理器结构将多个处理器内核集成到一个处理器，酷睿暮舜砥骱椭磷鸢嫦盗校舜瓮瞥龅目犷双核处理器数据处理性能比上一代的台式机处理器提高了。同时，多核处理器的价格也下落到人们可以接受的范围内，多核处理器逐渐占据了主导地位。处理器类型也依据其内核中是否搭载同一种芯片，而分成异构和同构两种类型。异构多核处理器中，芯片上所集成的处理器内核类型可以依据实际应用 哈尔滨理工大学工学硕士学位论文得到线性复杂度下的最优解的调度算法。正当各国学者热衷于追求线性复杂度多核处理器任务调度问题的国内外研究现状及分析尽最大可能分配到当前处于空闲状态的内核上执行，使各个处理器上的任务执等提出了离散搜索不平衡域算法引 哈尔滨理工大学工学硕士学位论文曹仰杰等提出了支持核资源动态分组的自适应调度算法【周本海等提出了一种基于多核处理器的动态共享缓存分配算法垤引，算法采 哈尔滨理工大学工学硕士学位论文，作为可靠性评价指标，根据弱点因子预测，进而达到降低容错技术开销的目的。算法幢引。该算法将任算法 哈尔滨理工大学工学硕士学位论文近年来，多核处理器已经普遍应用于各个领域，人们对其性能的要求也日益增长，然而多核处理器能否充分发挥其性能优势还需要相应的调度算法作为保障，因此对多核处理器任务调度算法的优化研究有着极其重要的意义。多核处理器调度算法始于并行系统调度算法的研究，而多核调度算法研究是完全问题不可能得到最优解，只能寻求近似最优解，这也就使得多核调度算法出现了多样性，产生了众多的分类。本文调度算法研究针对同构多核处理器来进行，所提出的调度算法属于多核处理器任务分配优化领域。 进行研究，力求通过一定的调度算法将任务按照其约束关系，合理的分配到处理器内核上执行，缩短任务的执行总时间，提高多核心处理器的性能。度算法的描述与分类，以及本文采用的多核处理器模型。务完成总时间。最后通过实例对算法进行进一步说明。 哈尔滨理工大学工学硕士学位论文多核处理器甈，是处理器就是采用的异构多核架构技术。 哈尔滨理工大学工学硕士学位论文 的执行起到关键的作用，因此优先调度执行这些节点对提前任务完成总时间有重要作用。 哈尔滨理工大学工学硕士学位论文为处理器芯片上集成的内核总数。处理器核心的计算和通信可以同时进行，同一个内核上的任务之间通信开销远小于内核之间的通信开销，因而可按没有通信开销来进行计算，而不同核心之间的通信开销是不容忽视的。任务在处理器内核上以非抢占的方式运行，即如果当前处理器内核上有某一个任务正在执行，那么直到该任务执行完毕为止，该处理器内核上都无法安排其他的任务来执行。 哈尔滨理工大学工学硕士学位论文个相同或不同类型的计算内核，从而提高处理器数据处理能力。按处理器内核琓琁取淙徽庑惴捎昧巳挝窀碨由于多核任务调度与综合调度在节点间有无通信开销的问题上有本质的区别，为了充分发挥拟关键路径法的优点，本文创新提出基于关键路径和任务复制的算法。该算法首先利用任务复制的方式将任务图转换为可减少通信开销的加工树，再通过提出的紧前节点组尽早完成策略，关键路径上的任务尽早开始，从而缩短完成该任务所需的时间。通过理论分析，算法可显著 哈尔滨理工大学工学硕士学位论文任务调度模型。这些任务之间大调度算法设计应用程序中的任务之间存在的数据依赖关系，使得前驱任务与当前任务不在同一内核上执行时，会产生通信开销，使任务开始时间延迟，为最大限度消 哈尔滨理工大学工学硕士学位论文算法首先在产品加工树中查找关键路径，找到关键路径后优先调度关键路径上的节点形成调度序列。查找关键路径的方法为：分别计算出加工树中各条路径的长度肪渡细鹘诘慵庸奔浜屯攀奔渥芎，如果路径长度最长路径不是唯一的，那么就选择包含任务节点数目最多的路径作为关键路径。关键路径上的节点通常有多个紧前节点序列，这些序列如果不能得到合理的调度，则有可能使关键路径上节点开始时间产生延迟。为了避免这种情况发生，本文提出一种紧前节点组尽早完成策略，该策略的主要思想为：判断当前节点的多个紧前节点序列是否可以合并到同一序列上执行，如合并后使得完成时间延迟则将这些紧前节点序列分别形成单独的调度序列，并分配到独立的内核上执行：否则，将这些紧前节点序列合并到同一序列上执行。 哈尔滨理二大学工学硕士学位论文步骤为形成的调度序列分配相应的处理器内核。步骤将调度结果以甘特图的形式表示出来。算法流程图如图所示。最多需要每个节点变换危匀挝裢甲;怀刹芳庸魇奔涓丛佣任狾。 哈尔滨理工大学工学硕士学位论文遍历任务图，复制节点形成图将图转换为产品加工树由叶节点起依次将关键路径上节点加入队列、灰灰灰籣一一在未调度节点装入处理器内核执行鞫韧瓿 子约束，即算法具有普遍意义。为方便读者理解本算法，下面以图这种随函函函函函五函 路径琓琓琓琓琓琓琓琓琓琓琓琓琓琓琓琓琓琓琓琓琓紧前序列琓，琓 哈尔滨理工大学工学硕士学位论文图算法对图任务图的调度结果图惴对图的调度结果点组尽早完成策略，将节点乃和死的调度序列合并，使得乃的开始执行时间 得以提前，通信时间得到较好的控制，进而任务执行时间可以得到缩短，并且时问复杂度本章小结 哈尔滨理工大学工学硕士学位论文 哈尔滨理工大学工学硕士学位论文 哈尔滨理工大学工学硕士学位论文如不能够分配到同一内核上，则通信开销可由下式定义：式中：H挝裢瓿勺苁奔洌煌嫖H挝窠诘鉒开始时间；岛为任务节问题分析 哈尔滨理工大学工学硕士学位论文权值。否尽早执行完毕将任务完成总时间产生较大影响。因为产品加工树中的叶节点拥有最高的优先级，当某一个叶节点调度完成后，产品加工树中其他节点的结构不会发生变化，而此时的关键路径却可能已经不再是调度开始时所确定的关键路径，此时为了保证下一个被调度的节点仍然是关键节点需要重新查找并确定关键路径口。为此，本文采用如下调度策略：按层序将产品加工树分解成子树，在子树中找到关键路径并优先调度其上的节点将整个加工子树形成调度序列。当该子树调度完毕后，将其整体虚拟为一个任务节点，加入上一级子树中进行调度，直到产品加工树中所有节点调度完毕为止。将子树虚拟为节点时，虚拟节点的权值为子树的执行时间，通信开销为子树根节点通信开销。对关键路径上节点进行调度时，为了尽量提前节点开始执行时间，本文算法拟合并紧前节点序列到同一序列上执行，如拟合并序列后完成时间延迟，则不予合并，并将序列分配到独立的内核上执行；否则，将紧前节点序列合并到同一序列。算法具体执行步骤设计如下：骤。 哈尔滨理工大学工学硕士学位论文如不大于绦蛳轮葱校裨蛱V敛街。步骤媒诘惴峙涞狡淝靶虻鞫刃蛄猩喜纬傻鞫刃蛄校讲街。算法复杂度分析况下被重复计算危醇扑懵肪冻鹊募臃问玎次，因此，这一步胛次。因此，本步骤所需要的时间复杂度应为。 哈尔滨理工大学工学硕士学位论文丶肪渡辖诘阋来渭尤攵恿衎拟合并紧前节点序列紧前节点序列分别形成调度序列峙涞阶钤缈J嫉男蛄猩闲纬傻鞫刃蛄衛 哈尔滨理工大学工学硕士学位论文鹾 哈尔滨理工大学工学硕士学位论文次序， 哈尔滨理工大学工学硕士学位论文时的通信时间。图算法对图任务图的调度结果 哈尔滨理工大学工学硕士学位论文关键节点，进而减少执行时间的延迟，提前任务结束时间。图惴酝任务图的调度结果本章小结本章所提出的调度算法主要针对第三章提出的调度算法不能动态调整关键路径的缺点进行算法的设计，实现了任务调度过程中某一节点调度完成后重新确定任务图中当前的关键路径，以使得下一个待调度的节点仍为关键路径上的节点。并且在调度节点序列时尽量合并关键节点的紧前节点序列，达到减少处理器内核资源消耗韵目的。经过理论分析并与现有算法进行比较，本章提出的算法能够节约处理器内核资源，减少内核之间不必要的通信开销，是对调度算法的改进，对多核调度算法的进一步研究有一定的促进意义。 度效果。但在处理器内核剩余不足时以上算法都无法进行有效的调度，这也是现今任务分配优化算法中普遍存在的问题。针对这一问题，本章参照第四章所提出的调度算法提出一种适应内核紧缺的单任务多核调度算法。算法分为两部分：首先基于任务复制和综合调度中动态关键路径策略将任务图分解形成初始调度序列；然后根据处理器剩余内核数对初始调度序列进行调整，形成最终调度序列，并分配到相应内核上执行。通过理论分析，所提出的算法在处理器剩余内核不足时仍能使任务得到有效调度。问题描述 哈尔滨理工大学工学硕士学位论文算法设计 哈尔滨理工大学工学硕士学位论文步骤饬礁龆恿泻喜纬尚碌亩恿校5讲街。二次多项式。 哈尔滨理工大学工学硕士学位论文层序遍历产品加工树将入度大于慕诘慵尤攵恿衋取出并删除队列鼻巴方岬鉚形成以为根节点的产品加工树在产品加工树中找到关键路径一紧前节点序列分别形成调度序列分配到最早开始的序列上形成调度序列与紧前节点形成调度序列节点分配完成 哈尔滨理工大学工学硕士学位论文查找通信最多的序列进行拟合并选出完成总时间最小的拟合并配对合并选出的队列分配到相应内核上执行图调度序列调整流程 函表庸鰽调度过程列表执行时间，后，在以及节点为根节点的加工子树调度完成后，将该子树虚拟为一个节点以 哈尔滨理工大学工学硕士学位论文次序，忍乃，次序琓琓 哈尔滨理工大学工学硕士学位论文时间。图处理器内核充足时调度结果猻 哈尔滨理工大学工学硕士学位论文间，以及对任务完成总时间影响如表所示。琓琓琓琓琓琓琓乃，乃，乃，乃，乃，乃执行时 哈尔滨理工大学工学硕士学位论文 通过对比以上调度算法执行甘特图可以看出，本文所提出的算法在处理器剩余内核不足时可调整调度序列，使任务能够及时完成，而算法没有够调整调度序列数以适应处理器剩余内核数，因此，当处理器核心不够多的时候任务将不能够执行：在处理器内核充足时本文提出的算法采用细化分解产品加工树，分级查找并优先调度关键路径上节点的方式使节点死，乃，乃，乃。分本章小结 哈尔滨理工大学工学硕士学位论文细化，使任务图中节点都能虚拟为一棵单独的加工树，方便对加工树中每个节 哈尔滨理工大学工学硕士学位论文器任务调度算法仍存在任务完成总时间延迟的问题，结合综合调度中拟关键路径