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

《基于综合调度关键路径的多核任务调度研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、工学硕士学位论文基于综合调度关键路径的多核任务调度研究韩英杰哈尔滨理工大学2014年3月国内图书分类号：TP316工学硕士学位论文基于综合调度关键路径的多核任务调度研究硕士研究生：导师：申请学位级别：学科、专业：所在单位：答辩日期：授予学位单位：韩英杰谢志强工学硕士计算机应用技术计算机科学与技术学院2014年3月哈尔滨理工大学ClassifiedIndex：TP316DissertationfortheMasterDegreeinEngineeringResearchofTaskSchedulingAlgorithmBasedonCriticalPathforMulti．．core

2、Candidate：Supervisor：HanYingjieXieZhiqiangAcademicDegreeAppliedfor：MasterofEngineeringSpecialty：ComputerAppliedTechnologyDateofOralExamination：March，2014University：HarbinUniversityofScienceandTechnology㈣趔黜一哈尔滨理工大学硕士学位论文原创性声明本人郑重声明：此处所提交的硕士学位论文《基于综合调度关键路径的多核任务调度研究》，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间独立进

3、行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人已发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。作者签名：叼链豸氅叁日期：功，弘年；月≥7日哈尔滨理工大学硕士学位论文使用授权书《基于综合调度关键路径的多核任务调度研究》系本人在哈尔滨理工大学攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨理工大学所有，本论文的研究内容不得以其他单位的名义发表。本人完全了解哈尔滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有关部门提交论文和电子版本，允许论文被查阅和借阅。本人授

4、权哈尔滨理工大学可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。本学位论文属于保密n，在年解密后适用授权书。不保密冈。(请在以上相应方框内打√)储龋匏选嗍如膨年岁月31日新躲琢引屯吼训年岁㈣日哈尔滨理工大学工学硕士学位论文基于综合调度关键路径的多核任务调度研究摘要多核处理器任务调度主要研究如何通过一定的调度算法将任务分配到多个并行的计算内核上执行，使任务完成总时间得以缩短。这一问题早己被证明是NP完全的问题。各国学者们针对该问题进行了研究，并提出了相应的调度算法，但这些算法依然存在着进一步完善的空间。本文主要在多核处理器任务分配方向进行研究，对传统任务调度算

5、法进行了改进，具有一定的理论价值和实际意义。针对目前大多数多核处理器任务分配优化算法没有考虑关键路径上节点对任务完成时间有重要影响，导致任务完成总时间延迟的问题，提出了基于关键路径和任务复SE](CPTD)的单任务调度算法。CPTD算法通过复制任务图中fork节点的方式将任务图转化为与之相对应的产品加工树；再在生成的产品加工树中找到关键路径，并采取使关键路径上节点的紧前节点尽早调度的方式，使关键路径上节点尽早开始执行。针对关键路径上的某一节点开始执行时，当前任务图中的关键路径可能已经产生了变化，如不重新查找关键路径不能保证下一待调度节点仍为关键节点的问题，提出了基于动态关键路径的多

6、核调度算法。该算法通过将任务图转换为产品加工树，并在加工树中按层序将产品加工树分解成子树，在子树中查找关键路径，并且优先调度关键节点形成调度序列。当该子树调度完毕后，将其整体虚拟为一个任务节点，加入上一级子树中进行调度，直到产品加工树中所有节点调度完毕为止。针对目前大多数适应多核处理器的调度算法不能够根据处理器内核数量调整调度序列数量，导致处理器当前剩余内核不足时任务不能够得到及时有效的调度的问题，提出了适应处理器内核紧缺的多核调度算法。该算法先将任务图分解为调度序列；后合并对总执行时间影响最小的序列，使调度序列数适应处理器当前剩余内核数。关键词多核；产品加工树；关键路径；单任务：

7、任务复制哈尔滨理工大学工学硕士学位论文ResearchofTaskSchedulingAlgorithmBasedonCriticalPathforMulti．coreAbstractThemainpurposeoftheresearchofmulti．coretaskschedulingalgorithmiShowtoshortenthetotaltaskexecutiontime．Thisproblemhasalreadybeenprovedtobeentirel