基于gpu加速的细粒度并行蚁群算法

《基于gpu加速的细粒度并行蚁群算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、大连理工大学硕士学位论文基于GPU加速的细粒度并行蚁群算法姓名：庞占龙申请学位级别：硕士专业：计算机应用技术指导教师：钱昆明20081218大连理工大学硕士学位论文摘要蚁群优化算法(Antcolonyoptimizationalgorithm，ACO)源于对蚂蚁觅食行为的研究，是一种基于群体智能方法的演化计算技术，在实际工程中表现出巨大的潜力。但在数值建模和优化计算等许多领域中，处理大量数据和求解大规模复杂问题时，ACO算法依然需要大量的计算时间，而并行ACO算法由于能较大幅度缩减问题求解的时间，因此成为一个研究热点。当前并行ACO算法主要在并行

2、机上运行或用多线程技术模拟，主要存在下述不足：进程间通信损耗限制了粒子规模；大多数研究人员没有硬件环境，无法使用并行机解决问题；多线程技术是在CPU上用串行模拟并行，不能真正提高性能。近年来，计算机图形处理器(Graphicsprocessingunit，GPU)绘制流水线的高速度和并行性以及近年来发展起来的可编程功能，使其在通用计算领域的应用有着巨大的潜力。CUDA是Nvidia公司推出的GPU编程的统一计算设备架构。在统一计算设备架构下，GPU执行的模式是并发的线程。多个线程可以组成一个线程块。一个线程块中的线程能存取同一块公用的存储空间，而

3、且可以快速进行同步的动作。本文针对传统并行蚁群算法在实际应用中的不足，结合GPU的高速并行性，提出了一种基于GPU加速的细粒度并行蚁群算法(GPUACO)，将并行ACO求解过程转化为CUDA内核，使用CUDA线程块模拟蚂蚁个体，使ACO算法在GPU中加速执行。本文主要以最大最小蚂蚁系统和蚁群系统的并行实现为例，详细描述了算法设计思想和程序实现过程，提供了各自应用于对称TSP问题的实验结果，与相应串行算法在相同计算环境下的实验结果做出比较，并针对实验结果分析了GPUACO算法的特点。实验结果表明本文算法在取得了较好的优化效果的同时，解决了细粒度并行

4、的蚁群规模限制问题，提高了算法的运算速度。关键词：蚁群算法；并行处理；GPU；细粒度大连理1二大学硕十学何论文AParallelAntColonyOptimizationAlgorithmBasedonFine-grainedModelwithGPU．AccelerationAbstractAntColonyOptimizationalgorithm(ACO)isanevolutionarycomputationtechniqueinspiredbysocialbehaviororantcolony．Ithasproventobeapowerfu

5、lglobaloptimizationmethodandshowsgreatpotentialinpractice．However，itstillneedsplentyofcomputingtimewhenitprocessesmuchdataandwhenlarge—scalecomplicatedworkisinvolvedinwhichmathmodelingandoptimizationarehighlydemanded，whereasparallelACOcomesintobeingandbecomesahitbecauseitcanr

6、educeworking—outtimedramatically．ParallelACOalgorithmismostlyrunonparallelmachineandsimulatedbymulti-threadtechnology，however，existsthefollowingdrawbacks：Theconsumptiononcommunicationbetweenprocessesconfinesthepopulationofantcolony；Mostresearchersdon’thavetheparallelmachineeq

7、uipments，thereforecouldn’tmakeuseofparallelACOalgorithmtosolveproblems；Multi—threadtechnologycouldn’traiserunningperformancebecauseitrunsoncommonpcwhichserial—parallelsimulation．Thehighlyprocessingpower，parallelismandprogrammabilityavailablenowadaysonthecontemporaryGPUprovide

8、anidealplatformonwhichthegeneral—purposecomputationcouldbemade．Aimin