分布式多处理器环境下任务调度方法研究
发布时间：2021-06-20 10:12
针对操作系统下多任务与大任务的高性能执行的要求,分布式多处理器系统为解决最终问题（多任务与大任务的高性能计算）提供硬件层面上的基础支持,但是,如何将这种硬件能力转变成计算性能的提升,并充分利用分布式并行计算能力,这便需要有高效的适应多任务和大任务高性能执行要求的调度模型。一个好的调度模型能够高效实现任务与计算资源的映射,解决共享资源的竞争问题,实现任务时间跨度的最小化以及提升硬件资源的利用率,这也是当前分布式多处理器系统研究领域所面临的挑战之一。本文针对多任务与大任务的高性能执行的要求,以分布式多处理器系统为目标环境,研究相关性任务调度问题,从任务分解、时间跨度优化、通信竞争、动态优先级计算以及最优虚拟核分配等方面展开研究。在理论上,发现分布式多处理器系统的调度特性与规律,并进行相应的算法设计与实现,在方法上,给出创新的调度模型与算法,解决目前调度算法对于任务相关性考虑不足、以及对分布式多处理器体系结构的考虑不足等问题,给出面向任务执行性能最优的调度方法。在应用上,首先使所给出的新方法应用于操作系统一级或者支撑操作系统的环境上,支持多任务与大任务在分布式多处理器系统上的高度并发,形成透...
【文章来源】：华南理工大学广东省 211工程院校 985工程院校 教育部直属院校
【文章页数】：152 页
【学位级别】：博士
【部分图文】：
TilePro64的微结构示意图[21]
华南理工大学博士学位论文2MAX{O(em),O(vmv)}，其中v为v的最大度。当任务节点较多、通信边数和处理节点数量较多时，HEFD算法的调度性能将会变差。文献[53]在HEFT算法的基础上，引入双折叠遗传算法思想，提出混合遗传算法（HGA）。该算法通过启发式获得解决方案，并种植在初始群体中，其提供了达到最佳（完工）解决方案的方向。修改后的双折叠遗传算子严格搜索并在较短的时间内将算法收敛到最佳解。该算法是一种启发式算法和遗传算法的组合，将每个染色体由两部分组成，左半部分表示资源分配，其长度等于DAG中的节点数。从1到P的处理器编号代表基因，其中P是可用处理器的最大数量。后半部分的大小也是DAG内的节点数，表示要调度的任务的顺序。每条染色体代表有效的时间表，但不得违反优先约束条件，否则染色体将无效。染色体左半部分是随机生成的，而右半部分使用HEFT算法的来确定任务的向上权重。图1-5中所示的示例染色体中的任务序列将是b-level的降序。任务优先级列表为{1346275}，，，，，，。如果根据染色体前半部分中显示的处理器分配将任务映射到处理器上，则生成的调度长度将为51个时间单位，相应的时间表如图1-6所示。图1-5HGA算法中染色体表示[53]图1-6示例染色体的相应时间表[53]HGA算法中使用适应度函数来评估每一代中的每个调度，染色体x的适应度可以定义为：f(x)=c/makespan(x)，其中c是常量，完工时间定义为：().()exitmakespanx=FTt。.()exitFTt是出口节点的结束时间。12
华南理工大学博士学位论文2MAX{O(em),O(vmv)}，其中v为v的最大度。当任务节点较多、通信边数和处理节点数量较多时，HEFD算法的调度性能将会变差。文献[53]在HEFT算法的基础上，引入双折叠遗传算法思想，提出混合遗传算法（HGA）。该算法通过启发式获得解决方案，并种植在初始群体中，其提供了达到最佳（完工）解决方案的方向。修改后的双折叠遗传算子严格搜索并在较短的时间内将算法收敛到最佳解。该算法是一种启发式算法和遗传算法的组合，将每个染色体由两部分组成，左半部分表示资源分配，其长度等于DAG中的节点数。从1到P的处理器编号代表基因，其中P是可用处理器的最大数量。后半部分的大小也是DAG内的节点数，表示要调度的任务的顺序。每条染色体代表有效的时间表，但不得违反优先约束条件，否则染色体将无效。染色体左半部分是随机生成的，而右半部分使用HEFT算法的来确定任务的向上权重。图1-5中所示的示例染色体中的任务序列将是b-level的降序。任务优先级列表为{1346275}，，，，，，。如果根据染色体前半部分中显示的处理器分配将任务映射到处理器上，则生成的调度长度将为51个时间单位，相应的时间表如图1-6所示。图1-5HGA算法中染色体表示[53]图1-6示例染色体的相应时间表[53]HGA算法中使用适应度函数来评估每一代中的每个调度，染色体x的适应度可以定义为：f(x)=c/makespan(x)，其中c是常量，完工时间定义为：().()exitmakespanx=FTt。.()exitFTt是出口节点的结束时间。12
【参考文献】：
期刊论文
[1]后E级时代高性能处理器架构的探索（英文）[J]. Xiang-hui XIE,Xun JIA. Frontiers of Information Technology & Electronic Engineering. 2018(10)
[2]基于FPGA的片上网络通信架构设计[J]. 谢宁波,张乐乾,高健超. 科技与创新. 2018(13)
[3]基于任务分解模型的离散数据格网化并行优化[J]. 王家润,谢海峰. 计算机工程与设计. 2018(06)
[4]一种面向片上众核处理器的虚拟核资源分配算法[J]. 沈阳,齐德昱,周娜琴,王新阳. 华南理工大学学报(自然科学版). 2018(01)
[5]基于SIMICS的ICP系统模块仿真技术研究[J]. 戴小氐,王婷,崔西宁. 航空计算技术. 2017(02)
[6]异构系统双关键级分布式功能的动态调度[J]. 刘樑骄,谢国琪,李仁发,杨柳,刘彦. 计算机研究与发展. 2016(06)
[7]基于任务和用户属性的工作流任务分配算法[J]. 姜劲松,杨波,缪志敏,朱宝山. 计算机仿真. 2015(12)
[8]通信竞争的混合关键级系统多DAG动态调度策略[J]. 刘樑骄,谢国琪,李仁发,杨柳,谢勇. 计算机研究与发展. 2015(11)
[9]分布式系统下的DAG任务调度研究综述[J]. 田国忠,肖创柏. 计算机工程与科学. 2015(05)
[10]异构众核系统及其编程模型与性能优化技术研究综述[J]. 巨涛,朱正东,董小社. 电子学报. 2015(01)
博士论文
[1]分布式异构环境中任务调度算法研究[D]. 刘林东.华南理工大学 2019
[2]分布式环境下异构多处理机的相关任务的调度方法研究[D]. 周娜琴.华南理工大学 2017
[3]多DAG共享资源调度的若干问题研究[D]. 田国忠.北京工业大学 2013
[4]面向动态异构众核处理器的任务调度研究[D]. 孙涛.中国科学技术大学 2013
[5]异构并行分布式系统可信调度理论与方法研究[D]. 唐小勇.湖南大学 2013
硕士论文
[1]基于Simics的双余度飞控计算机数字模型的设计与实现[D]. 朱思宇.电子科技大学 2018
[2]基于2D-Mesh互连的片上网络容错技术研究与设计[D]. 杭彦希.解放军信息工程大学 2017
[3]基于NoC的多核处理器架构设计[D]. 穆瑞卿.长春理工大学 2017
[4]GriDoc文档可视化管理器与客户端数据存取驱动器的设计与实现[D]. 许诺.华南理工大学 2016
[5]面向动态异构多核处理器的公平性任务调度研究[D]. 高晓川.中国科学技术大学 2015
[6]计算机网络带宽测量技术研究[D]. 裴玉欢.国防科学技术大学 2007
本文编号：3238999
【文章来源】：华南理工大学广东省 211工程院校 985工程院校 教育部直属院校
【文章页数】：152 页
【学位级别】：博士
【部分图文】：
TilePro64的微结构示意图[21]
华南理工大学博士学位论文2MAX{O(em),O(vmv)}，其中v为v的最大度。当任务节点较多、通信边数和处理节点数量较多时，HEFD算法的调度性能将会变差。文献[53]在HEFT算法的基础上，引入双折叠遗传算法思想，提出混合遗传算法（HGA）。该算法通过启发式获得解决方案，并种植在初始群体中，其提供了达到最佳（完工）解决方案的方向。修改后的双折叠遗传算子严格搜索并在较短的时间内将算法收敛到最佳解。该算法是一种启发式算法和遗传算法的组合，将每个染色体由两部分组成，左半部分表示资源分配，其长度等于DAG中的节点数。从1到P的处理器编号代表基因，其中P是可用处理器的最大数量。后半部分的大小也是DAG内的节点数，表示要调度的任务的顺序。每条染色体代表有效的时间表，但不得违反优先约束条件，否则染色体将无效。染色体左半部分是随机生成的，而右半部分使用HEFT算法的来确定任务的向上权重。图1-5中所示的示例染色体中的任务序列将是b-level的降序。任务优先级列表为{1346275}，，，，，，。如果根据染色体前半部分中显示的处理器分配将任务映射到处理器上，则生成的调度长度将为51个时间单位，相应的时间表如图1-6所示。图1-5HGA算法中染色体表示[53]图1-6示例染色体的相应时间表[53]HGA算法中使用适应度函数来评估每一代中的每个调度，染色体x的适应度可以定义为：f(x)=c/makespan(x)，其中c是常量，完工时间定义为：().()exitmakespanx=FTt。.()exitFTt是出口节点的结束时间。12
华南理工大学博士学位论文2MAX{O(em),O(vmv)}，其中v为v的最大度。当任务节点较多、通信边数和处理节点数量较多时，HEFD算法的调度性能将会变差。文献[53]在HEFT算法的基础上，引入双折叠遗传算法思想，提出混合遗传算法（HGA）。该算法通过启发式获得解决方案，并种植在初始群体中，其提供了达到最佳（完工）解决方案的方向。修改后的双折叠遗传算子严格搜索并在较短的时间内将算法收敛到最佳解。该算法是一种启发式算法和遗传算法的组合，将每个染色体由两部分组成，左半部分表示资源分配，其长度等于DAG中的节点数。从1到P的处理器编号代表基因，其中P是可用处理器的最大数量。后半部分的大小也是DAG内的节点数，表示要调度的任务的顺序。每条染色体代表有效的时间表，但不得违反优先约束条件，否则染色体将无效。染色体左半部分是随机生成的，而右半部分使用HEFT算法的来确定任务的向上权重。图1-5中所示的示例染色体中的任务序列将是b-level的降序。任务优先级列表为{1346275}，，，，，，。如果根据染色体前半部分中显示的处理器分配将任务映射到处理器上，则生成的调度长度将为51个时间单位，相应的时间表如图1-6所示。图1-5HGA算法中染色体表示[53]图1-6示例染色体的相应时间表[53]HGA算法中使用适应度函数来评估每一代中的每个调度，染色体x的适应度可以定义为：f(x)=c/makespan(x)，其中c是常量，完工时间定义为：().()exitmakespanx=FTt。.()exitFTt是出口节点的结束时间。12
【参考文献】：
期刊论文
[1]后E级时代高性能处理器架构的探索（英文）[J]. Xiang-hui XIE,Xun JIA. Frontiers of Information Technology & Electronic Engineering. 2018(10)
[2]基于FPGA的片上网络通信架构设计[J]. 谢宁波,张乐乾,高健超. 科技与创新. 2018(13)
[3]基于任务分解模型的离散数据格网化并行优化[J]. 王家润,谢海峰. 计算机工程与设计. 2018(06)
[4]一种面向片上众核处理器的虚拟核资源分配算法[J]. 沈阳,齐德昱,周娜琴,王新阳. 华南理工大学学报(自然科学版). 2018(01)
[5]基于SIMICS的ICP系统模块仿真技术研究[J]. 戴小氐,王婷,崔西宁. 航空计算技术. 2017(02)
[6]异构系统双关键级分布式功能的动态调度[J]. 刘樑骄,谢国琪,李仁发,杨柳,刘彦. 计算机研究与发展. 2016(06)
[7]基于任务和用户属性的工作流任务分配算法[J]. 姜劲松,杨波,缪志敏,朱宝山. 计算机仿真. 2015(12)
[8]通信竞争的混合关键级系统多DAG动态调度策略[J]. 刘樑骄,谢国琪,李仁发,杨柳,谢勇. 计算机研究与发展. 2015(11)
[9]分布式系统下的DAG任务调度研究综述[J]. 田国忠,肖创柏. 计算机工程与科学. 2015(05)
[10]异构众核系统及其编程模型与性能优化技术研究综述[J]. 巨涛,朱正东,董小社. 电子学报. 2015(01)
博士论文
[1]分布式异构环境中任务调度算法研究[D]. 刘林东.华南理工大学 2019
[2]分布式环境下异构多处理机的相关任务的调度方法研究[D]. 周娜琴.华南理工大学 2017
[3]多DAG共享资源调度的若干问题研究[D]. 田国忠.北京工业大学 2013
[4]面向动态异构众核处理器的任务调度研究[D]. 孙涛.中国科学技术大学 2013
[5]异构并行分布式系统可信调度理论与方法研究[D]. 唐小勇.湖南大学 2013
硕士论文
[1]基于Simics的双余度飞控计算机数字模型的设计与实现[D]. 朱思宇.电子科技大学 2018
[2]基于2D-Mesh互连的片上网络容错技术研究与设计[D]. 杭彦希.解放军信息工程大学 2017
[3]基于NoC的多核处理器架构设计[D]. 穆瑞卿.长春理工大学 2017
[4]GriDoc文档可视化管理器与客户端数据存取驱动器的设计与实现[D]. 许诺.华南理工大学 2016
[5]面向动态异构多核处理器的公平性任务调度研究[D]. 高晓川.中国科学技术大学 2015
[6]计算机网络带宽测量技术研究[D]. 裴玉欢.国防科学技术大学 2007
本文编号：3238999
本文链接：https://www.wllwen.com/shoufeilunwen/xxkjbs/3238999.html
