基于GPU调度的流水作业优化算法研究

《基于GPU调度的流水作业优化算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Ｎｏｒｔｈｅａｓｔｅｒｎｊ；＇／Ｕｎ＾ｉｖｅｒｓｉｔｙ硕士学位论文ＴＨＥＳ＇ＩＳＦＯＲＭＡＳＴＥＲＳＤＥＧＲＥＥ论文题目基于ＧＰＵ调度的流水作业优化算法研究作者唐梦债学院软件学院专业软件工程指导教师任涛教授于鹏高级工程师备注二零一六年十二月分类号密级ＵＤＣ学位论文基于ＧＰＵ调度的流水作业优化算法研究作者姓名：唐梦倩指导教师：任涛教授东北大学软件学院于鹏高级工程师东软集团：申请学位级别硕士学科类别：专业学位学科专业名称：软件工程．论文提

2、交日期：２０１６２：２０１６年１２月论文答辩日期年１月：学位授予日期：答辩委员会主席李丹程评阅人：于海于鹏东北大学２０１６年１２月ＡＴｈｅｓｉｓｉｎＳｏｆｔｗａｒｅＥｎｇｉｎｅｅｒｉｎｇＲｅｓｅａｒｃｈｏｆＦｌｏｗＳｈｏｐＯｔｉｍｉｚａｔｉｏｎｐＡｌｏｒｉｔｈｍｏｎＧＰＵＳｃｈｅｄｕｌｉｎｇｇＢＴａｎＭｅｎｉａｎｙｇｇｑＳｕｅｒｖｉｓｏｒ：ＰｒｏｆｅｓｓｏｒＲｅｎＴａｏｐＳｅｎｉｏｒＥｎｇｉｎｅｅｒＹｕＰｅｎｇＮｏｒｔｈｅａｓｔｅｒｎＵｎｉｖｅｒｓｉｔｙＤｅｃｅｍｂｅｒ２０１６

3、独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研宄所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签名：．曰期：ＵＩ学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据

4、库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：□一年一半年口年半□两年ｙ学位论文作者签名：Ｈ导师签名：ｐ签字日期：／厂丨签字日期：＆丨入／Ｉ东北大学硕士学位论文摘要基于ＧＰＵ调度的流水作业优化算法研究摘要ＧＰＵ的计算性能随着半导体工艺的发展得到飞速提升，在某些方面甚至远远超过了通用ＣＰＵ。ＧＰＵ被越来越多的应用到天文、医疗等各个领域，成为重要的计算资源。ＧＰＵ中的数据传输和负载执行过程可以抽象为流水作业模型，因此针对该模型的优化算法研究对ＧＰＵ性能的提升具有十分积极的作用。本文主要研究了三

5、类流水作业调度问题，针对各类问题的特点设计了不同的优化算法进行求解，并通过数值仿真实验对算法性能进行了验证：。本文的主要内容如下首先，将拉格朗日松弛算法应用于静态流水作业极小化完工时间平方和问题。针对该问题建立了数学规划模型，并对模型进行了调整以适用于拉格朗日松弛算法，。通过松弛工件顺序约束、工件分配约束和机器顺序约束将问题转化成更为简单的完工时间子问题和位置分配子问题。利用求导和枚举的方法分别解决这两个子问题，然后通过次梯度算法来更新拉格朗日乘子，并在解的可行化过程中加入了禁忌搜索算法来改进可行解的质量。通过数值仿真实验验证了拉格朗日松弛

6、算法的有效性。＝其次，针对动态流水作业极小化完工时间ｉｔ次方和问题认２，，３应用分枝）定界算法求解小规模问题。根据问题的特点设计了新的剪枝规则和下界以提高计算效率，针对中等规模问题，通过分枝定界算法提供初始种群，采用离散差分进化算法进行求解，并使用多点插入的交叉方式来加快搜索速度。通过数值仿真验证了分枝定界算法和离散差分进化算法的有效性。然后，研究了带有学习效应的动态流水作业极小化完工时间平和问题。考虑了线性函数、幂函数，并建立了问题的数学、指数函数三种形式的学习效应函数规划模型以便利用ＣＰＬＥＸ求解。同样采用分枝定界算法和差分进化算法进

7、行求解，针对带有学习效应的问题设计了剪枝规则和下界。针对分枝定界算法中没被剪枝的节点对应的子序列，用ＳＰＴＡ启发式规则将未排工件进行排序从而得到完整序列，然后将这些完整的序列用作差分进化算法的初始种群。数值仿真验证了分枝定界算法和差分进化算法的有效性。关键词：流水作业；；完工时间Ａ次方和；学习效应拉格朗日松弛；分枝定界ＩＩ￡页士学位论文Ａｂ东北大学ｓｔｒａｃｔＲｅｓｅａｒｃｈｏｆＦｌｏｗＳｈｏＯｔｉｍｉｚａｔｉｏｎｐｐＡｌｇｏｒｉｔｈｍｏｎＧＰＵＳｃｈｅｄｕｌｉｎｇＡｂｓ