多核环境任务分配问题复杂性及求解模型研究

发布时间：2020-09-03 18:34

　　 传统任务分配问题是以最小化计算代价和处理器间通信代价之和为研究目标的。然而,随着计算机硬件获得巨大的性能提升,多核处理器成为主流,传统任务分配理论面临前所未有的巨大挑战。在由多核处理器构建的集群环境中,不仅需要考虑计算节点间通信,还需要考虑计算节点内通信(处理器间通信和核间通信)。研究表明,NAS基准测试平台中超过50%的消息是通过计算节点内通信完成的。在此背景下,本文提出了多核环境任务分配问题,目标是最小化计算代价,计算节点间通信代价和计算节点内通信代价(包括处理器间通信代价和核间通信代价)。 多核环境任务分配问题的研究面临两方面的重大挑战。挑战之一,传统任务分配问题是NP-hard问题,多核任务分配问题与之相比更为复杂,但是该新问题一定也是NP-hard问题吗?在多核集群环境下,随着核数越来越多,节点内通信代价也越来越大,通信代价的量变会不会导致质变?也就是说通信代价的变化会不会导致问题复杂性发生本质的变化,即使得NP-hard问题变为P问题?这些问题是算法复杂性研究的难点,具有重要的理论意义和实际意义。挑战之二,在传统任务分配问题的精确求解模型研究中,最好的结果是通过数学规划方法得到的。在多核任务分配问题研究中,如何使用数学规划方法建立高效的精确求解模型? 本文研究正是围绕这两个挑战性问题展开的,在以下三个方面做出了重要贡献。首先,本文研究了多核环境任务分配问题的复杂性。首次证明了多核环境下新的任务分配问题是NP-hard问题,即使在任务通信图是二部图并且是平面图时,该结论依然成立。其次,本文使用最小费用流理论定量分析了通信代价的变化对问题复杂性的影响。得出的结论是,多核环境任务分配问题的复杂性是由通信代价决定的,并且随着节点内通信代价持续增大到一定程度,会使原来的NP-hard问题变为P问题。最后,本文建立了多核环境任务分配问题的0-1整数二次规划模型,并提出了两种线性松弛策略,为进一步设计高效的模型求解算法打下了坚实的基础。
【学位单位】：大连理工大学
【学位级别】：硕士
【学位年份】：2009
【中图分类】：TP332
【部分图文】：

学研究、工程计算以及商业计算等领域得到了越来越多的应用。并行分具发展前景，但同时也提出了大量富于挑战性的课题，任务调度就是其的问题。度问题是研究如何将一组计算任务合理地或最优化地分配到分布式系统。如果这个问题得不到解决，则有可能导致分布式计算效率低下，更有甚并行计算效率不如单机计算，乃至计算失败。度具有广泛的应用基础，除并行计算领域外，任务调度问题还是其他诸注的问题。例如，网格，云计算，PZP，普适计算，流媒体，交通领域，工程等。因此，从应用角度来说，任务调度问题作为诸多领域共同面对具有重要的研究意义。以不受优先关系的约束而相互作用或进行通信，这类任务的调度问题称是属于略微简化了一点的调度问题。任务分配问题不需要强调任务在分行次序，在一个或多个处理机组成的分布式系统中，相互作用的任务应个处理机上，以充分利用系统资源。

【相似文献】

相关期刊论文 前10条

1 刘淑华;张嵛;付帅;吴洪岩;;基于粒子群蚁群算法的多机器人任务分配方法[J];东北师大学报(自然科学版);2009年04期

2 陈庆枝;;无线传感器网络任务分配的粒子群优化算法[J];广西工学院学报;2009年03期

3 陈庆枝;;无线传感器网络任务分配的粒子群优化算法[J];苏州科技学院学报(工程技术版);2009年03期

4 汪毅;郭立峰;;基于遗传算法的雷达网任务分配[J];微计算机信息;2006年22期

5 韩泉叶;李王君;;一种MAS任务分配及资源竞买算法的探讨[J];甘肃科学学报;2006年03期

6 倪谣;周德云;马云红;贺宝财;;基于MILP模型的多无人机对地攻击任务分配[J];火力与指挥控制;2008年11期

7 严建峰;李伟华;刘明;;多Agent系统任务分配的研究[J];计算机工程;2009年11期

8 杨克巍;李兴兵;李孟军;岑凯辉;;基于集合覆盖理论的Agent协作问题研究[J];系统工程学报;2009年06期

9 叶菁;陈国龙;吴运兵;朱丹红;;无线传感器网络任务分配的遗传优化算法[J];计算机工程与应用;2010年35期

10 石刚;井元伟;邹德旋;;主从式免疫克隆选择算法求解任务分配问题[J];信息与控制;2011年03期

相关会议论文 前10条

1 鄢超波;赵千川;;任务分配问题的研究进展与算法比较[A];第二十七届中国控制会议论文集[C];2008年

2 郭建军;戴葵;王志英;;一种多核处理器存储层次性能评估模型[A];第八届全国信息隐藏与多媒体安全学术大会湖南省计算机学会第十一届学术年会论文集[C];2009年

3 柳林;郑志强;;多机器人任务分配技术及其在机器人足球中应用[A];2004中国机器人足球比赛暨学术研讨会论文集[C];2004年

4 蒋汉平;李腊元;;基于多核处理器的NAT-PT的软件架构的研究[A];中国通信学会第五届学术年会论文集[C];2008年

5 张炜;冯权友;曾超;窦文华;;一种基于光互连技术的存储墙问题解决方案[A];中国电子学会第十六届信息论学术年会论文集[C];2009年

6 赵宏伟;许锦洲;;一种基于在线仿真的多无人机任务调度方法研究[A];2009年中国高校通信类院系学术研讨会论文集[C];2009年

7 潘送军;胡瑜;李晓维;;多核处理器瞬态故障敏感性分析[A];第五届中国测试学术会议论文集[C];2008年

8 卢宇彤;杨学军;所光;;一种面向多核系统的并行计算任务分配方法[A];第八届全国信息隐藏与多媒体安全学术大会湖南省计算机学会第十一届学术年会论文集[C];2009年

9 叶媛媛;闵春平;沈林成;朱华勇;;基于混合遗传算法的多UCAV协同任务分配方法[A];2005年全国自动化新技术学术交流会论文集[C];2005年

10 叶媛媛;闵春平;沈林成;朱华勇;;基于混合遗传算法的多UCAV协同任务分配方法[A];2005全国自动化新技术学术交流会论文集（二）[C];2005年

相关博士学位论文 前10条

1 李晖;高性能计算机若干关键问题研究[D];中国科学技术大学;2009年

2 祖丽楠;多机器人系统自主协作控制与强化学习研究[D];吉林大学;2006年

3 马巧云;基于多Agent系统的动态任务分配研究[D];华中科技大学;2006年

4 杨永明;群体机器人系统协同行为研究[D];吉林大学;2009年

5 姜健;多移动机器人协作方法研究[D];哈尔滨工业大学;2008年

6 孙国玺;多变异拟子—基因共同进化算法的理论及应用研究[D];华南理工大学;2006年

7 董炀斌;多机器人系统的协作研究[D];浙江大学;2006年

8 朱敬华;无线传感器网络QoS保障技术的研究[D];哈尔滨工业大学;2009年

9 钟一文;智能优化方法及其应用研究[D];浙江大学;2005年

10 柳林;多机器人系统任务分配及编队控制研究[D];国防科学技术大学;2006年

相关硕士学位论文 前10条

1 潘东;多核环境任务分配问题复杂性及求解模型研究[D];大连理工大学;2009年

2 熊s

本文编号：2811808