（计算机应用技术专业论文）基于gpu加速的细粒度并行蚁群算法.pdf

大连理工大学硕士学位论文 摘要 蚁群优化算法( a n tc o l o n yo p t i m i z a t i o na l g o r i t h m ，a c o ) 源于对蚂蚁觅食行为的研究， 是一种基于群体智能方法的演化计算技术，在实际工程中表现出巨大的潜力。但在数值 建模和优化计算等许多领域中，处理大量数据和求解大规模复杂问题时，a c o 算法依 然需要大量的计算时间，而并行a c o 算法由于能较大幅度缩减问题求解的时间，因此 成为一个研究热点。当前并行a c o 算法主要在并行机上运行或用多线程技术模拟，主 要存在下述不足：进程间通信损耗限制了粒子规模；大多数研究人员没有硬件环境，无 法使用并行机解决问题；多线程技术是在c p u 上用串行模拟并行，不能真正提高性能。 近年来，计算机图形处理器( g r a p h i c sp r o c e s s i n gu n i t ，g p u ) 绘制流水线的高速度和并 行性以及近年来发展起来的可编程功能，使其在通用计算领域的应用有着巨大的潜力。 c u d a 是n v i d i a 公司推出的g p u 编程的统一计算设备架构。在统一计算设备架构下， g p u 执行的模式是并发的线程。多个线程可以组成一个线程块。一个线程块中的线程能 存取同一块公用的存储空间，而且可以快速进行同步的动作。 本文针对传统并行蚁群算法在实际应用中的不足，结合g p u 的高速并行性，提出 了一种基于g p u 加速的细粒度并行蚁群算法( g p u a c o ) ，将并行a c o 求解过程转化为 c u d a 内核，使用c u d a 线程块模拟蚂蚁个体，使a c o 算法在g p u 中加速执行。本 文主要以最大最小蚂蚁系统和蚁群系统的并行实现为例，详细描述了算法设计思想和程 序实现过程，提供了各自应用于对称t s p 问题的实验结果，与相应串行算法在相同计算 环境下的实验结果做出比较，并针对实验结果分析了g p u a c o 算法的特点。实验结果 表明本文算法在取得了较好的优化效果的同时，解决了细粒度并行的蚁群规模限制问 题，提高了算法的运算速度。 关键词：蚁群算法；并行处理；g p u ；细粒度 大连理1 二大学硕十学何论文 ap a r a l l e la n tc o l o n yo p t i m i z a t i o na l g o r i t h mb a s e do nf i n e - g r a i n e d m o d e lw i t hg p u a c c e l e r a t i o n a b s t r a c t a n tc o l o n yo p t i m i z a t i o na l g o r i t h m ( a c o ) i sa ne v o l u t i o n a r yc o m p u t a t i o nt e c h n i q u e i n s p i r e db ys o c i a lb e h a v i o ro ra n tc o l o n y i th a sp r o v e nt ob eap o w e r f u lg l o b a lo p t i m i z a t i o n m e t h o da n ds h o w sg r e a tp o t e n t i a li np r a c t i c e h o w e v e r ，i ts t i l ln e e d sp l e n t yo fc o m p u t i n gt i m e w h e ni tp r o c e s s e sm u c hd a t aa n dw h e nl a r g e s c a l ec o m p l i c a t e dw o r ki si n v o l v e di nw h i c h m a t hm o d e l i n ga n do p t i m i z a t i o na r eh i g h l yd e m a n d e d ，w h e r e a sp a r a l l e la c oc o m e si n t o b e i n ga n db e c o m e sah i tb e c a u s ei tc a n r e d u c ew o r k i n g o u tt i m ed r a m a t i c a l l y p a r a l l e la c o a l g o r i t h mi sm o s t l yr u no np a r a l l e lm a c h i n ea n ds i m u l a t e db ym u l t i - t h r e a dt e c h n o l o g y ， h o w e v e r ，e x i s t st h ef o l l o w i n gd r a w b a c k s ：t h ec o n s u m p t i o no nc o m m u n i c a t i o nb e t w e e n p r o c e s s e sc o n f i n e st h ep o p u l a t i o no fa n tc o l o n y ；m o s tr e s e a r c h e r sd o n th a v et h ep a r a l l e l m a c h i n ee q u i p m e n t s ，t h e r e f o r ec o u l d n tm a k eu s eo fp a r a l l e la c oa l g o r i t h mt os o l v e p r o b l e m s ；m u l t i t h r e a dt e c h n o l o g yc o u l d n tr a i s er u n n i n gp e r f o r m a n c eb e c a u s ei tr u n so n c o m m o np cw h i c hs e r i a l p a r a l l e ls i m u l a t i o n t h eh i g h l yp r o c e s s i n gp o w e r ，p a r a l l e l i s ma n dp r o g r a m m a b i l i t ya v a i l a b l en o w a d a y so n t h ec o n t e m p o r a r yg p up r o v i d ea ni d e a lp l a t f o r mo nw h i c ht h eg e n e r a l p u r p o s ec o m p u t a t i o n c o u l db em a d e a i m i n ga tt h o s ep r o b l e m si np a r a l l e la c oa l g o r i t h m ，w er a i s e daf i n e - g r a i n e da c o a l g o r i t h mb a s e do ng p ua c c e l e r a t i o n ，w h i c hc o n v e r t st h ep r o c e s so fw o r k i n g - o u ti n t ot h e e x e c u t i o no fk e r n e l sb a s e dc u d au s i n gat h r e a db l o c kt os i m u l a t ea na n t ，s p e e d su pi t s r u n n i n ga n dp r o v i d e so r d i n a r yu s e rw i t hf e a s i b l ea c oa l g o r i t h m t h ee x c u t i v em o d e lo fg p u u s i n gc u d a i sp a r a l l e lt h r e a d s t h r e a di st h es m a l l e s tu n i to fc u d a m a n yt h r e a d sc o m p o s e at h r e a db l o c k t h et h r e a d si nt h es a m eb l o c kc a na c c e s ss h a r e dm e m o r ya n dc a ns y n c h r o n i z e r a p i d l y i nt h i sp a p e r ，a sa ne x a m p l e ，w em a i n l yd i s c u s sm m a s a n da c s sp a r a l l e l i z a t i o na n d d e s c r i b et h ea l g o r i t h m sd e s i g na n dp r o g r a m m i n g f u r t h e r m o r ，w ep r e s e n tal o to fr e s u l t so f a p p l y i n gt os y m m e t r i ct r a v e l i n gs a l e s m a np r o b l e m s ，a n dg i v ec o m p a r i s i o n sw i t ht h er e l e v a n t s e q u e n t i a lv e r s i o nw h e nr u n n i n gu n d e rt h es a m ec o m p u t i n ge n v i r o n m e n t ，a n da n a l y s i st h e p r o p e r t i e so fp a r a l l e la c oa l g o r i t h m t h es i m u l a t i o nr e s u l t ss h o wt h a to u ra l g o r i t h ma c h i e v e s ag o o do p t i m i z a t i o ne f f e c ta n di ta l s oi n c r e a s e st h ea n tp o p u l a t i o ni nt h ef i n e g r a i n e d p a r a l l e l i s mw h i l es p e e d i n gu pi t sr u n n i n g k e yw o r d s ：a n tc o l o n yo p t i m i z a t i o na l g o r i t h m ；p a r a l l e lp r o c e s s ；g p u ；f i n e - g r a i n e d i i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目、j 莹 堑堡垒型坠鱼旦塑堕望坚堑童堡兰彗l 靼五一 作者签名：一皿壶也一一 日期：型! 堑一年l 月二尘日 大连理工大学硕七研究生学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题卧蔓立鱼1 2 ：童塑塑髦醯红坚叠篓堕 ： 作者签名：勉曼丝日期：竺! ：篁年竺月j 堕日 导师签名：盏缉暨扯 日期：兰盟年二立日 大连理工大学硕十学位论文 引言 蚁群算法( a n tc o l o n yo p t i m i z a t i o na l g o r i t h m ，a c o ) 是继模拟退火算法、遗传算法、禁 忌搜索算法、人工神经网络后又一种应用于组合优化问题的启发式搜索算法【lj ，用来求 解优化问题的近优解。蚁群算法是一种概率搜索算法，它利用生物信息激素作为蚂蚁选 择后序行为的依据。每只蚂蚁会对一定范围内其他蚂蚁散布的信息素做出反应，依据信 息素的强度在每一个道口对多条路径选择做出概率上的判断并执行选择，由此观察并影 响他们以后的行为。蚁群算法通过由候选解组成的群体的进化过程来寻求最优解，特别 适合于在离散域优化问题的解空间进行多点非确定性搜索，已应用于旅行商问题、二次 分配问题等多个经典离散组合优化问题，称为组合优化等n p h a r d 问题的一种非常有潜 力的演化算法。 对于中小规模的应用问题，a c o 算法得到了广泛的应用，并取得了很好的优化效果， 而对于大规模或超大规模的优化问题，a c o 算法往往需要大量的计算时间而显得力不 从心。并行a c o 算法由于能较大幅度缩减问题求解的时间，因此成为一个研究热点【2 岱j 。 细粒度并行蚁群算法是并行蚁群算法中一个重要模型，具有提高全局搜索能力、抑 制早熟和保持最大并行性等优势。当前关于并行蚁群算法的研究主要在并行机上运行或 用多线程技术模拟，在细粒度并行方面存在以下不足： ( 1 ) 在并行机上实现f g p a c o ，需要为每个蚂蚁运行单独的进程，而复杂问题几百 甚至更多的蚂蚁规模导致了进程间很大的通信损耗，大多数并行机难以承受，所以当前 的并行蚁群算法多采用粗粒度模型1 3 1 ； ( 2 ) 多线程技术是在c p u 上用串行来模拟并行，并不能真正提高速度； ( 3 ) 大多数研究人员很难接触到上述并行机，同时并行机的管理和使用也相对复杂。 近年来，图形处理器高速发展，提高了计算机图形处理的速度，同时g p u 的高速 浮点运算能力、并行计算和可编程功能为通用计算提供了良好的并行计算平台【9 1 ， n v i d i a 公司统一计算设备架构为研究人员利用g p u 进行数据并行处理提供了更便捷 的方法。通过g p u 进行并行优化算法的加速，是解决上述f g a c o 面对问题的一种可 行的方法。李建明提出了一种基于g p u 的细粒度并行遗传算法【l0 1 ，将并行遗传算法的 求解过程转化为g p u 纹理渲染过程，通过g p u 约减技术减少c p u 与g p u 的数据交换， 取得了较好的加速比。h o n gl i 提出了基于g p u 的并行鱼群算法i l ，得到了很好的优化 效果。但该算法通过c u d a 架构的每个线程来模拟鱼群的个体，没有充分挖掘g p u 并 行计算能力。 在上述方法基础上，本文提出一种改进的基于g p u 加速的细粒度并行蚁群算法， 基于g p u 加速的细粒度并行蚁群算法 通过使用c u d a 架构的线程块模拟蚂蚁个体，充分利用了g p u 并行计算能力。该方法 增大了细粒度并行的蚂蚁规模，较好地保持算法抑制早熟的特性，提高了算法运行速度， 并且为普通用户的并行蚁群算法工作提供了一种可行的途径。 本文的工作集中在以下几个部分： ( 1 ) 以c u d a 编程模型为基础，建立基于线程块的蚂蚁个体模型： ( 2 ) 采用g p u 硬件加速并行求解蚂蚁状态转移； ( 3 ) 实现了g p u 中a c s 信息素局部更新策略。 本文共分为4 章，第1 章介绍了目前蚁群算法及其并行化的研究现状和趋势。第2 章介绍了g p u 通用计算的相关知识。第3 章详细论述了本文提出的基于g p u 加速的细 粒度并行蚁群算法，采用最大最小蚂蚁系统( m a x m i na n ts y s t e m ，m m a s ) 和蚁群系统( a n t c o l o n ys y s t e m ，a c s ) 进行实验仿真。第4 章对实验结果进行分析。最后对本文提出的算 法进行总结和展望。 大连理t 大学硕士学位论文 1蚁群算法及其并行的发展 仿生优化算法是人工智能研究领域中一个重要的分支，其中包括模拟生物界中自然 选择和遗传机制的遗传算法、模拟蚂蚁群体觅食行为的蚁群算法以及模拟鸟类群体捕食 行为的微粒群算法等。 蚁群算法是最初由意大利学者d o r i g om 于1 9 9 1 年首次提出，其本质上是一个复杂 的智能系统，它具有较强的鲁棒性、优良的分布计算机制、易于与其他方法结合等优点。 如今这一新兴的仿生优化算法已经成为人工智能领域的一个研究热点【l2 1 。目前对其研究 已渗透到多个应用领域，并由解决一维静态优化问题发展到解决多维动态组合优化问 题。如今在国内外许多学术期刊和重要国际会议上，蚁群算法已经成为交叉学科中一个 非常活跃的前沿性研究问题。 1 1t s p 问题 t s p 问题是典型的n p h a r d 优化问题，蚁群算法被提出就是用于解决t s p 问题，因 此也作为本文研究算法的应用问题。一般t s p 可以描述为带权完全图g = ( m 彳) ，为城 市节点集，彳为边集。事实上非完全图也可以描述为完全图，只需令那些不存在的边的 权值足够大。每条边( f ，j ) a 赋予权值城市f 与歹之间的距离d ，f ，j n ，目标是找该图 的哈密尔顿回路，其长度最短，且遍历每个节点仅一次。所以t s p 问题的最优解应该是 所有城市节点号 1 ，2 ，门 的一个置换刀，并且f ( z r ) 最小，如公式( 1 1 ) 所示。 ，n 。- ，i f ( z c ) = 办( f ) 州+ 1 ) + 办( 咖( 1 ) ( 1 1 ) i = 1 1 2 基本蚁群系统 基本蚂蚁系统( a n ts y s t e m ，a s ) 包括解的构造和信息素更新两个阶段，所有边的信息 素初始化为一个稍大于预期的蚂蚁一次释放的信息素值，粗略估计为“= m c ”，其中 m 为人工蚂蚁的个数，c 肋为最近邻居法生成的一条路径的长度。初始化后将蚂蚁置于 随机选择的城市，蚂蚁依据如下路径选择概率规则前进。对于蚂蚁k ，在t 时刻其从城 市f 选择，前进的概率如公式( 1 2 ) 所示。其中a l l o w e d k = n t a b u 女) ，t a b u 为蚂蚁k 已 访问过城市节点集合，乃( f ，j ) 为，时刻边( f ，) 上信息素强度，7 7 ，= 1 d , j ，成为启发因子 或可见度，z ，为城市f 、，之间的距离，口，反应y - 者的相对重要程度。 基于g p u 加速的细粒度并行蚁群算法 p ：( ，) =器矿徊脚 2 ， f 膻( f ) 】。 7 7 庸( f ) 】卢 vj “”“ ( 1 2 ) 0o t h e t w s e 蚂蚁根据上述公式从初始节点依次遍历所有节点，回到初始节点，从而得到一个解， 此过程称为一代，这样m 只蚂蚁就能得到m 个解。之后是信息素更新阶段，每只蚂蚁 会在经过的边上留下给定量的信息素，作为下一代蚂蚁构造解的依据，规则如公式( 1 3 ) ， r o ( t + 1 ) = ( 1 - p ) r ( f ) + 苟 v ( i ，) a( 1 3 ) k = l 其中p 称为蒸发因子，可使蚂蚁在探索过程中忘记以前做出的较差的决策， k 在边( f ，j ) 上一次释放的信息素，如公式( 1 4 ) 所示， ：= 弋| c 二乏皂2 毫k a r ：为蚂蚁 ( 1 4 ) 其中c 。为蚂蚁k 在r 到f + 1 内找到的路径丁的长度。可以看出，c 。越小，路径丁上得 到的信息素增量越大多，因而下次被选择的概率越大。 1 3a s 扩展 实验表明随着问题规模的增大，相对于其他启发算法而言，基本a s 的性能较差。 下面的算法针对其不足，分别提出了自己的改进方法，并取得一定效果【1 3 。1 7 1 。 1 3 1 带精英策略的蚂蚁系统 带精英策略的蚂蚁系统( e l i t i s ta n ts y s t e m ，e a s ) 作为最早的改进a s ，它增强了对当 前最好解的利用，而状态转移规则仍按照公式( 1 2 ) 。对t s p 而言，有当前最短路径丁拈， 长度为c h ，算法中每一代完成后要在该路径上有一个额外的信息素增量e c h ，如公式 ( 1 5 ) 所示， r u ( t + 1 ) = ( 1 一p ) 乃( ，) + a r ：+ e a r ；s ( 1 5 ) 其中p 作为权重系数，表明这种利用程度，芎如公式( 1 6 ) 所示， 瞄= k 砒t f ( i 眺, j ) 产 ( 1 6 ) 有结果表明选择合适的系数e ，即能使解的质量和算法性能得到提高。 大连理1 ：= 大学硕士学位论文 1 3 2 基于排序的蚂蚁系统 基于排序的蚂蚁系统( r a n k _ b a s e da n ts y s t e m ，r a s ) 该算法除了当前最好解之外，提 出了一代中若干好解的概念，定义为代中所有蚂蚁找到的路径中最短的前( w 一1 ) 条， 信息素增量只发生在这些路径和当前最短路径中，并且根据路径的长短分别给予不同的 信息素增量，这些增量的产生只由相应的w 只蚂蚁来完成，而其他蚂蚁不释放信息素。 规则如公式( 1 7 ) 所示， 乃= t 0 + ( w - r ) a r ；+ w a r ；5 ( 1 7 ) 其中丁：= 1 c 7 ，a t i ；s = 1 c 缸，实验结果表明r a s 稍优于e a s ，远好于a s 。 1 3 3 最大最小蚂蚁系统 最大最小蚂蚁系统( m a xr a i na n ts y s t e m ，m m a s ) 对a s 主要有四点改进。首先，它 只允许一代中最好的或者是到目前为止最好的一直蚂蚁释放信息素；其次，每条边上的 信息量限制在一个特定的区间 f 嘶，f m 积 中；第三，各条边上的信息量初始化为区间上 界r m 舣，并且使用较小的蒸发因子；第四点是当认为算法已经收敛或者没有更好的解产 生时，将所有边上的信息素重新初始化。信息素更新规则如公式( 1 8 ) 所示， f l f = ( 1 一p ) r f ，+ r ：酬 ( 1 8 ) 其中f ：耐= l c 胁，负责更新信息素的是当前最好( b e s t s o f a r ) 或者一代中最好 ( i t e r a t i o n b e s t ) 的蚂蚁，更新方式分别为露“= 1 c 瓠和f = 1 c 玷。大量实验结果表 明m m a s 的效率和求解能力明显好于上述各种算法。 1 3 4 蚁群系统 蚁群系统( a n tc o l o n ys y s t e m ，a c s ) 与a s 的不同体现在下面三点。首先状态转移规 则有所改动，称为伪随机转移规则，如公式( 1 9 ) ；其次，信息素的全局更新仅限于当前 最短路径，如公式( 1 1 0 ) ；第三，增加了局部信息素更新以扩大对接空间的搜索，如公 式( 1 。1 1 ) 。 a c s 使用了与以上a c o 算法不同的状态转移规则 = ( a r gm a x k 6 芎i 一“r 。磊 ( 1 9 ) 基于g p u 加速的细粒度并行蚁群算法 ，为节点f 的蚂蚁的下一个目标节点，g 为均匀分布于【0 ，1 的随机变量，9 0 为给定参 数，代表按公式( 1 2 ) ( 口= 1 ) 进行。g 。控制对已有信息的利用和对接空间搜索的力度对 比。 a c s 的全局信息素更新同m m a s f 。o + 1 ) = ( 1 一p ) f ，o ) + p a r ； v ( i ，) t 缸( 1 1 0 ) 其中f 如= 1 c 船，a c s 只允许当前最好的蚂蚁全局更新信息素。 a c s 在解的构造过程中，还增加了局部信息素更新，即每只蚂蚁在经过任意一条边 都会在该边留下给定量的信息素，规则为 f = ( 1 一五) f f ，+ 旯r o ( 1 1 1 ) 实验表明，兄= 0 1 时的结果较好，吒= ( r l * l b 删) ， ，2 为问题中城市节点的个数。 这种局部更新的作用在于减少边( f ，) 上的信息素，即扩大算法对解空间的搜索范围，防 止过早收敛现象。 a c s 与其他a c o 算法还有一个很重要的区别在于，无论是释放还是蒸发，它只修 改蚂蚁经过的边上的信息素，蚂蚁未经过的边信息量不变，换句话说就是完全通过全局 和局部信息素更新公式来控制所有边的信息量，而其他算法对蚂蚁没有走过的边，依然 会根据整发因子给它一个负增量。 大量实验表明，m m a s 和a c s 取得的结果明显好于其他a c o 算法，而m m a s 对 大部分实例来说稍好与a c s 。在算法运行的初期，m m a s 得到的解比其他算法得到的 都差，但随着时间的进行，m m a s 却能使解的质量越来越好，而a c s 在算法运行的初 期就能迅速找到很好质量的解，但最后的解没有m m a s 好。可见，m m a s 在前期更注 重对解空间的探索，对已获得经验的利用则集中在最后，而a c s 是同时进行的。 事实上，m m a s 与a c s 对信息素的处理上有一定的相识之处，就是都采用了对信 息素的边界限定策略。前者显式的规定了一个信息素区间 f 。f 一】，从而增大了对解 空间的收索覆盖度，有效的防止了早熟，提高了解的质量。而a c s 对信息素是一种隐 式的界定。由公式( 1 1 0 ) 和公式( 1 1 1 ) 不难看出，f ；，= f 。，1 c 缸】。 1 3 5 其他改进算法 国内目前对a c o 算法也有少量研究，段海滨【1 8 】提出了一种利用云模型定性关联规 则来有效限制基本蚁群算法陷入局部最优解的方法；随后借助最优解保留、相遇搜索和 信息素自适应控制策略以及自然界的小生境思想对基本蚁群算法进行了系列改进，以提 高改进后蚁群算法的全局收敛性能。吴斌【1 9 】提出了基于蚁群算法的分段求解算法，应用 一6 一 大连理工大学硕士学位论文 并行计算的优势提高了蚂蚁的搜索速度。赵宝江【2 0 】提出了一种基于自适应路径选择和信 息素更新的蚁群算法，根据优化过程中解的分布状况，自适应地调整路径选择策略和信 息素更新策略。 1 3 6 各种蚁群算法的比较 同a s 算法相比，以上算法的共同之处在于加强了对最优解的利用。这一节，我们 将几种蚁群算法求解t s p 问题时的结果进行一个比较。比较结果见表1 1 。 表1 1m m a s ，a c s ，e a s 以及a s 算法求解不同t s p 问题的结果比较 t a b 1 1t h er e s u l t so fm m a s ，a c s ，e a sa n da ss o v l i n gd i f f e r e n tt s pp r o b l e m s 从表1 1 可以看出，在求解t s p 问题时，m m a s 算法具有最好的性能，其次是a c s 算法。一般情况下，e a s 算法要好于a s 。 图1 1 是这四种算法在求解t s p 问题时的典型收敛情况。 图1 1m m a s ，a c s ，e a s 与a s 算法典型收敛曲线的比较 f i g 1 1 t h ec o n v e r g e n c ec h iv eo fm m a s ，a c s ，e a sa n da s 基于g p u 加速的细粒度并行蚁群算法 1 4 并行a c 0 的研究现状 可以说，a c o 天然是并行的，其生态属性及设计思想决定了它的并行性。另外， 其他启发式搜索算法现有的并行模型或策略为蚁群算法的并行化奠定了坚实的基础。 并行策略一般可分为细粒度( f i n e g r a i n e d ) 和粗粒度( c o a r s e g r a i n e d ) 两种。细粒度并 行指分配给单个处理器较少的计算实体，但随之而来的是处理器间频繁的信息交互。粗 粒度方法则相反，单个处理器负责较大规模甚至是整个种群的运算，因而减少了处理器 间的信息传递。 并行机实现时往往需要在计算与通信之间寻求一种平衡，蚁群算法的并行机实现主 要集中在最优的并行化。所谓最优的并行化是指使用适量的处理机以最小的代价使得并 行化蚁群算法性能达到当前情况下的最好，或者说当并行化蚁群算法性能不变时，应竭 力减少计算和通信的成本。、 在研究蚁群算法并行机实现问题时，需要解决对蚁群算法并行化过程中并行计算模 型的选择以及对蚁群算法的分解、映射方法的改进等问题，还需要解决在对蚁群算法并 行化过程中粒度处理标准的问题，从而使并行处理过程具有较好的可扩展性，并具有良 好的负载均衡性。目前主要存在如下几个问题： ( 1 ) 在不考虑处理机间差异、选择同步更新方法的情况下，如何确定问题规模与加 速比之间的关系；在处理机增多的情况下，如何选择处理机的最佳数目以使计算时间减 少。 ( 2 ) 在不考虑处理机间差异、选择同步更新方法的情况下，且当处理机一定时，如 何选择最优的蚁群规模m 以使效用函数的值最大。 ( 3 ) 在不考虑处理机间差异、选择异步更新方法的情况下，且当问题规模一定时， 如何分配处理机数目和每个处理机上的蚁群规模以使效用函数值最大。 ( 4 ) 当并行机实现时，局部迭代若干次后需要交换信息。局部迭代次数的增大也会 使得蚁群算法早熟的概率增大，而局部迭代次数减d , 贝e j 会增加通信时间，因此还要努力 解决如何有效避免蚁群算法的过早停滞和减少通信开销之间的平衡问题。 大连理1 二大学硕士学位论文 2 基于g p u 的通用计算 2 1基本概念 基于g p u 的通用计算( g e n e r a lp u r p o s eg p u ，g p g p u ) 指的是利用显卡来实现一般意 义上的计算，而不单纯是图形渲染l 2 。 一块工作频率为3 0 g h z 的p e n t i u m4 处理器，其晶体管数目为1 2 5 亿个，即使算 上s s e 指令集的s i m d ( 单指令多数据流，这种情况下是浮点运算吞吐能力的最理想状 况) ，也只有6 g f l o p s 的峰值浮点处理能力。与c p u 相比，g p u 具有高度并行的硬件结 构，设计了更多的晶体管用于数据计算而非数据高速缓存和流控制。以n v i d i a8 8 0 0 g t s 为例：它有6 8 1 ，0 0 0 ，0 0 0 个晶体管，这些晶体管构成1 2 8 个流处理器这些流处理器 分为1 6 组，每组8 个流处理器构成个多处理器。每个多处理器有1 6 k b 的芯片内存， 可以使数据更接近a l u 以提高读写操作的速度。对一般目的的应用而言，理论的计算 峰值可达8 4 5 6 g f l o p s ，如图2 1 所示。最新的g p u s 具有多个a l u 和非常高的显存 带宽，可以提供几乎让人难以置信的强大的运算能力，不仅能用于图形处理，也可以用 于非图形处理的处理。 由于具备强大的并行处理能力和极高的存储器带宽，因此g p u 可以被当作一个“流 处理器”( s t r e a mp r o c e s s o r ) ，用于诸如科学运算、数据分析、线性代数、流体模拟等需 要大量重复的数据集运算和密集的内存存取的应用程序。这主要得利于以下几个优势： ( 1 ) 一定的并行性：这一功能主要是通过多个渲染管道和r g b a 4 个颜色通道同时 计算来体现的，另外在一个时钟周期内最多可以同时获取1 6 个甚至更多的纹理。顶点 着色器( v e r t e xs h a d e r ) 程序的多个渲染管道意味着一个时钟周期可以并行处理多个顶 点，而对于像素着色器( p i x e ls h a d e r ) 程序同样如此。相对于并行机而言，显卡提供的并 行性虽然很弱，但它在十分廉价的基础上为很多应用提供了一个很好的并行方案，尤其 是对于图形本身的应用来说。 ( 2 ) 高密集的运算：由于显卡内部的内存接口位宽大于c p u 上的位宽，如g e f o r c e f x 的内存位宽达2 5 6 位，显然高于c p u 上3 2 位的位宽，这样整个计算的带宽大大提 高了。g p u 相对于c p u 来说，更适合传输大块的数据，虽然c p u 上有c a c h e 可以加 速整个计算过程，但c p u 上的c a c h e 相对于显卡显存来说太小，一般只有6 4 k b ，而现 在的显存大多都在6 4 m b 以上。 ( 3 ) 减少了g p u 与c p u 的数据通信：尤其是当整个应用针对图形生成的时候，不 再需要在c p u 与g p u 之间进行多次数据交换，从而可以将c p u 解放出来做其他的处 基于g p u 加速的细粒度并行蚁群算法 理任务。这些优势使得g p u 比c p u 更适用于流处理计算，因此g p u 也被认为是一个 s i m d 的并行机或者流处理器，可以用于处理大规模数据集，使应用得到加速。相比之 芝 2 k o 薏 芸 孤加枷蛔跏n 盯跏硒 洲洲绷绷嬲绷 耵z l ig e f o v 毽6 t x 2 0 季2 _ , f o r e e 9 8 。雹1 5 8 0 - c 照f o r e e 诒。r 3 t x 舒l _ f 。悠7 9 g x g 珀_ c , e f o r 滢7 8 0 0 g i x 蛳4 0r l l5 e 幻f 强6 孚3 0 罐圩毒 3 5 _ & f 溯蕾f x 鲐s 。脚a 阱弱- g e f o r 瞧f x 豁 1 2 0 t o o 8 0 i a n d w 硪知 g a s 6 0 4 0 2 0 o 撇 i j l l m l a l l 7 7 1 i , 7 1 1 # 7 昭w o o d k a 1 斌 2 0 0 32 0 0 42 0 0 52 0 0 62 0 0 7 图2 1g p u 与c p u 的浮点计算速度 f i g 2 1f l o p so f g p ua n dc p u 下，c p u 本质上是一个标量计算模型，而计算单元偏少，主要针对复杂控制和低延迟而 大连理工大学硕十学位论文 非高带宽进行了若干优化。 正是由于这些优势，使得g p u 比c p u 更适用于流处理计算。在这种形势下，g p g p u 技术出现了，它利用显卡来进行更多领域中的计算，而不只是单纯的绘制。目前，a m d 和n v i d i a 两大图形芯片厂商都提出了自己的g p g p u 方案。 以g e f o r c e 3 为代表的可编程g p u 发布后，g p g p u 进入了一个高速发展的全新时 代。相比固定的流水线，目前硬件的可编程顶点和片段单元不管是运算精度，支持的指 令数还是寄存器个数都有了很大提高。 ， 更重要的是基于s h a d e rm o d e l3 0 的顶点和像素着色器版本的硬件开始支持动态流 控制的循环和分支还有子函数操作。比如，现在的像素着色程序最多允许同时访问1 6 个独立的纹理，并且支持长度不受限制的指令数，寄存器个数也大大增加。而且提供了 4 通道3 2 位浮点精度的运算和存储格式，对于通用计算来说，这就更容易完成更为复杂 的运算。 图2 2 显示了当前的g p u 的渲染流水线架构，其中粗框部分表示具备可编程能力： 图2 2 当前显卡的渲染流程 f i g 2 2 r e n d e rf l o wo fc u r r e n tv i d e oa d a p t o r 其中可编程的顶点着色器( v e r t e xs h a d e r ) 负责处理顶点数据流( 包括位置、颜色，光 照等) 。由于顶点处理操作都是在空间的几何点上进行，因此v e r t e xs h a d e r 对于通用计 算而言非常适合于几何操作类的计算。可编程片段着色器( f r a g m e n tp r o c e s s o r ) 或称像素 基于g p u 加速的细粒度并行蚁群算法 着色器( p i x e ls h a d e r ) 在几何处理和转换完成后，负责为每个像素“画上正确的色彩， 它的i s a ( 系统体系结构) 类似于d s p 或s s e 指令集，由f l o a t 4 的s i m d 执行单元和寄存 器组成。 2 2g p u 通用计算的应用 近年来，随着g p u 性能的大幅度提高以及可编程特性的发展，人们首先开始将图 形流水线的某些处理阶段以及某些图形算法从c p u 向g p u 转移，如局部光照计算，凸 凹映射绘制等。除了计算机图形学本身的应用，还涉及到其它领域的计算，以至于基于 图形硬件的通用计算( g p g p u ) 这几年来成为g p u 的应用之一，并成为一个研究热点【2 2 1 。 g p g p u 的应用研究进展很快，其涉及的领域也在不断扩大。2 0 0 4 年在洛杉矶举行 了第一次g p 2 会议( a c mw o r k s h o po ng e n e r a l - p u r p o s ec o m p u t i n go ng r a p h i c sh a r d w a r e ) ， 以讨论这方面的应用。h t t p ：w w w g p g p u o r g 提供了这方面最全面的信息，并作了详细 分类。下面列出了一些目前已经存在的应用： ( 1 ) 代数计算； ( 2 ) 几何处理； ( 3 ) 偏微分方程数值求解，如流体模拟，冰晶体生成； ( 4 ) 数据库操作； ( 5 ) 频谱变换和滤波，图像处理，如香港中文大学开发的离散小波分析程序包； ( 6 ) 碰撞检测、运动规划； ( 7 ) 优化计算； ( 8 ) 声音合成，如b i o n i c f x 软件； ( 9 ) 其他应用还在不断涌现。 基于g p u 的通用计算是随着图形芯片的发展而发展起来的。虽然以前的显卡主要 只是针对图形本身的应用，如光照计算、深度检测、光栅化、反走样等等，但针对其他 更为通用的应用也有出现，如利用颜色来标示物体序号等。但真正全面开展起来是因为 可编程性的普及。随着2 0 0 1 年g e f o r c e 3 的出现，顶点级可编程开始普及，即v e r t e x p r o g r a m 。虽然这个时候像素级上还只是固定的几条指令，但这方面的应用已经开始全 面展开。到了2 0 0 2 年h a r r i s 等人开始利用t e x t u r es h a d e r 结合r e g i s t e rc o m b i n e r 来求解 扩散方程，而到了2 0 0 3 年像素级可编程性出现，很多人开始利用像素程序来求解一般 代数问题，甚至偏微分方程组( p d e s ) 求解和优化。显然，随着时间的推移，g p u 在通用 计算的应用将越来越广泛。 h o f f 等人在求解辐射度方程的时候利用图形硬件的多边形光栅化过程和深度缓冲 大连理丁大学硕十学位论文 检测来计算二维和二维的通用v o r o n o i 图。他们利用颜色来标示每个位置，通过光栅化 重构出距离函数，而深度缓冲用来进行距离比较从而得到最近或者最远的位置。 在光线跟踪方面，p u r c e l l 等人将整个场景采用均匀网格来表示，将所有三角形的顶 点组织到三幅纹理中，并建立一个三角形链表纹理，这样将整个光线跟踪的算法放到 g p u 上来执行。 m o r e l a n d 等人将图像处理从时域空间转换到频域空间，利用g p u 实现快速傅里叶 变换，通过灵活组织索引避免重新排序。而h o p f 利用g p u 来做三维卷积运算和小波变 换，两者都是利用o p e n g l1 2 以上版本提供的颜色矩阵和卷积操作来实现的。t r e n d a u 等人利用硬件提供的颜色融合和o p e n g l1 2 以上版本提供图像子集的卷积和颜色矩阵 等运算功能计算折射散射效果。r u m p f 等人利用图形硬件求解传热和各向异性扩散有限 单元方程，从而实现图像处理的功能。 j a m e s 等人利用现有的有限元包分析出变形物体的自振频率，然后采用模态分析的 方法利用顶点编程将物体各个振型进行叠加从而得到新位置，这样可以将以前在c p u 上进行的计算全部转移到g p u 上去。 另外在碰撞检测方面，g o v i n d a r a j u 采用两遍绘制的方法来计算潜在碰撞集合( p c s ) ， 而在此后的研究中更是采用了多个g p u 来加速可见性的计算，两者都利用了硬件遮挡 查询操作来加速。 在代数运算方面，l a r s e n 等人利用多纹理技术实现了矩阵乘法。h a l l 等人更进一步 充分利用硬件的可编程性对矩阵乘法运算做了很多优化工作使得性能大大提升。 t h o m p s o n 基于顶点编程开发了一个框架系统用来进行矢量的运算，并在此基础上实现 矩阵乘法和3 - s a t 问题的求解。k r i l g e r 等人利用像素程序来做基本代数运算，然后在 此基础上实现共扼梯度法和高斯一赛德尔迭代法，从而完成p d e s 的求解。b o l z 等人实 现了基于像素编程的稀疏非结构化矩阵的共扼梯度法和正交网格的多重网格法，并用于 加速几何处理和流体模拟。m o r