基于多线程的并行分支定界算法框架及其应用

《基于多线程的并行分支定界算法框架及其应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号UDC密级学位论文基于多线程的并行分支定界算法框架及其应用作者姓名：李景阳指导教师：原慧琳副教授张瑞友副教授东北大学信息科学与工程学院申请学位级别：硕士学科类别：工学学科专业名称：系统工程论文提交日期：2014年6月论文答辩日期：2014年6月学位授予日期：2014年6月答辩委员会席：王雷震副教授评阅人：张家生王晗东北大学2014年6月万方数据AThesisinSystemEngineeringMulti-threadbasedParallelBranchandBoundAlgorithmFrameworkanditsApplicationByLiJin

2、gyangSupervisor：AssociateProfessorYuanHuilinAssociateProfessorZhangRuiyouNortheasternUniversityJune2014万方数据独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签名：毒景陶日期：20J乎．D6．▲g学位论文版权使用授权书本学位论文作者和指导教

3、师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口一年口一年半口两年∥学位论文作者签名：喜歌阻签字日期：二oIto6．上6导师签名：压致妖签字日期：№6昨；．砀万方数据东北大学硕士学位论文摘要基于多线程的并行分支定界算法框架及其应用摘要随着信息产业技术的快速发展，多核处理器成为处理器市场上的主流产品，开发并行程序，充分利用多核处理器的多个内核成为程序开发的趋势。并

4、行算法作为并行程序开发的核心，是算法研究的一个新的方向。但并行算法的设计与实现比向来都比较复杂，所以研究具有通用性的并行算法框架具有现实意义。本文针对求解优化问题中常用的分支定界算法进行研究，将分支定界算法分割成与问题相关和与问题无关的部分，进而设计基于多线程的并行分支定界算法框架。应用并行分支定界算法框架对板坯出库问题进行求解，并通过实验验证了算法框架的高效性。基于多线程的并行分支定界算法框架共有三个模块，分别是结点定义模块、相关接口模块和并行分支定界算法求解模块。结点定义模块和相关接口模块对应分支定界算法中与问题相关的部分，开发人员在使用框架求解具体问题时，需要对

5、这两个模块中的结点类型和相关接口函数进行定义。求解模块对应分支定界算法中与问题无关的部分，该模块为并行分支定界算法的核心。其主要内容为并行环境参数的设置，分支定界算法的并行化等内容，开发人员在使用框架时不需要对模块的内容进行编辑。综上所述，本文提出了基于多线程的并行分支定界算法框架。算法框架采用Windows多线程编程技术中的Win32API实现算法的并行化，可以有效的提高CPU使用率。使用并行分支定界算法框架求解问题时，将会提高算法设计的重复利用性，减少了开发人员的工作量，具有一定的实际应用价值。关键词：多线程；并行算法；分支定界：算法框架II万方数据东北大学硕士学

6、位论文AbstractMulti--threadbasedparallelbranchandboundalgorithmframeworkanditsapplicationAbstractWiththerapiddevelopmentofinformationtechnologyindustry,multi-coreprocessorsbecomemainstreamproducts．Itisatendencyinprogramdevelopmentthatdevelopingparallelprogramsandutilizingmultiplecoreinmult

7、i—coreprocessorsadequately．Asthecoreofaparallelprogramdevelopment，parallelalgorithmhasbecomeanewresearchdirection．However,duetothedesignandimplementationofparallelalgorithmshasalwayscomplicated．So，ithaspracticalsignificancetoresearchaparallelalgorithmframeworkwhichisversatility