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

大连理工大学硕士学位论文 摘要 粒子群优化算法( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 源于对鸟群捕食行为的研究，是 一种基于群体智能方法的演化计算技术。在实际工程中表现出巨大的潜力。但在数值建 模和优化计算等许多领域中，处理大量数据和求解大规模复杂问题时，p s o 算法依然需 要大量的计算时间，而并行p s o 算法由于能较大幅度缩减问题求解的时间，因此成为 一个研究热点。当前并行p s o 算法主要在并行机上运行或用多线程技术模拟，主要存 在下述不足：进程间通信损耗限制了粒子规模；大多数研究人员没有硬件环境，无法使 用并行机解决问题；多线程技术是在c p u 上用串行模拟并行，不能真正提高性能。 近年来，计算机图形处理器( g r a p l l i c s p r o c c s s i n g u n i t ，g p u ) 绘制流水线的高速度和 并行性以及近年来发展起来的可编程功能，使其在通用计算领域的应用有着巨大的潜 力。本文针对传统并行粒子群算法在实际应用中的不足，结合g p u 的高速并行性，本 文提出了一种基于g p u 加速的细粒度并行粒子群算法( g p u p s o ) ，将并行p s o 求解过 程转化为g p u 纹理并行渲染过程，使得p s o 算法在g p u 中加速执行，在取得了较好 的优化效果的同时，解决了细粒度并行的粒子规模限制问题，提高了算法的运算速度。 变形物体的碰撞检测一直是机器人、虚拟现实、动画仿真等领域中一个非常关键的 问题。本文针对传统层次包围盒算法在变形物体的碰撞检测中每一帧更新数据量大，效 率低的难点问题，将基于g p u 加速的并行粒子群算法( g p u p s o ) 应用到碰撞检测领域， 实现了一种基于粒子群优化和g p u 加速的变形物体碰撞检测算法，有效地减小了搜索 空间，提高了算法效率。该方法将空间物体问距离计算转化为二维离散三角面片中最近 三角面片对的寻优问题，并使用g p u p s o 算法对其进行求解。实验数据表明，该算法 在计算最近距离和获取碰撞位置时得到了较准确的实验结果，同时速度较快，是一种可 行的变形物体碰撞检测方法。 关键词：p s 0 ；g p u ；变形物体；碰撞检测 大连理工大学硕士学位论文 p a r a l l e lp a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h mb a s e do n g p u - a c c e l e r a t e dw i t hi t sa p p l i c a t i o n s a b s t ra c t p a r t i c l es w a r mo p t i m i z a t i o n ( p s 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 ei n s p i r e d b ys o c i a lb e h a v i o ro f b i r df l o c k i n g 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 nm e t h o d a 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 f c o m p u t i n gt i m ew h e ni t p 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 s i n v o l v e di nw h i c hm a t h m 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 lp s oc o m e si n t ob e i n ga n d b e c o m e sah i ts i n c ei tc a nr 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 lp s oa l g o r i t h mi s m 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 e f o l l o w i n gd r a w b a c k s ：n 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 np r o c e s s e sc o n f i n e st h e p a r t i c l e - s c a l e s ；m o s tr e s e a r c h e rd o n th a v et h ep a r a l l e lm a c h i n ee q u i p m e n t s ，t h e r e f o r e c o u l d n tm a k eu s eo fp a r a l l e lp s oa l g o r i s mt os o l v ep 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 y c 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 nc o n l m o np cw i t l s e r i a l p a r a l l e l s h n u l a t i o n g r a p h i c sp r o c e s s i n gu n i t ( g p u ) h a sb e e nd e v e l o p i n gr a p i d l yi nr e c e n ty e a r s ，a n da sa r e s u l t v a r i o u sa p p l i c a t i o n sa s s o c i a t e dw i mc o m p u t e rg r a p h i c sa d v a n c eg r e a t l y a tt h es a m e t i m e ，t h eh i # d 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 u p 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 es u c ha sd i g i t a l i m a g ep r o c e s s i n gc o m p u t a t i o nc 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 lp s o a l g o r i t h m , w er a i s e daf i n e - g r a i n e dp s oa l g o r i s 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 s t h ep r o c e s so f w o r k i n g - o u ti n t ot h ep r o c e s so f t e x t u r e - r e n d e r i n gb a s e do ng p u ，m a k i n gp s o g r e a t l ya c c e l e r a t e di ni t a sa c h i e v i n gag o o do p t i m i z a t i o ne f f e c t , i ta l s oi n c r e a s e st h ep a r t i c l e p o p u l a t i o ni nt h ef i n e - g r a i n e dp a r a l l e l i s m ，s p e e d su pi t sn m n i n ga n dp r o v i d e so r d i n a r yu s e r w i t haf e a s i b l ep s 0s o l u t i o n c o l l i s i o nd e t e c t i o no fd e f o r m a b l eo b j e c t si so n eo ft h em o s ti m p o r t a n tp r o b l e m si nt h e f i e l d so fr o b o t i c s ，c o m p u t e ra n i m a t i o n , a n dv i r t u a lr e a l i t y , e t c w ep r o p o s e dac o l l i s i o n d e t e c t i o na l g o r i t h mb a s e dp a r t i c l es w a r mo p t i m i z a t i o n ( p s o ) a n dg p uf o rs o l v i n gt h e p r o b l e m sa sl a r g eu p d a t i n gd a t ap e rf r a m ea n dl o we f f i c i e n c yi nc o l l i s i o nd e t e c t i o nf o r d e f o r m a b l eo b j e c t s t h ep s oa l g o r i t h mi su s e df o rc o m p u t i n gt h ed i s t a n c eb e t w e e nt w o n e a r e s to fa l lt h et w o - d i m e n s i o n a ld i s e r e t et r i a n g u l a rp a t c h e si n s t e a do ft w oo b j e c t s ，a n d m t m 。m m 。l n gt h es e a r c h i n gs p a c ea n di n c r e a s i n gt h ee f f i c i e n c y 1 1 1 ep a r a l l e lp a r t i c l es w a r m a l g o r i t h mb a s e dg p u i sa d v a n c ea tt h es e i n et i m e , a n di sm a p p e dt h ep r o c e s so ft h et e x t u r e 基于g p u 加速的并行粒子群算法及其应用 r e n d e r i n gi ng p u ，a n di s u s e df o rt h er e s u l t si nc o l l i s i o nd e t e c t i o n i ti ss h o w nd e a r l yi n e x p e r i m e n tt h a tt h ea l g o r i t h mo b t a i n sf i g h t e rr e s u l t si nc o m p u t i n gt h em i n i m u md i s t a n c ea n d g e t t i n gt h ec o l l i s i o np o s i t i o n i ti sf e a s i b l e k e yw o r d s ：p s o ；g p u ；d e f o r m a b l eo b j e c t s ；c o l l u s i o nd e t e c t i o n i v 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同z - 作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名： 叁堑翌：! ：查堂堡土婴丝堂垡丝奎一 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名 导师签名 五题一 眩塾翌障一 塑堡年月阜日 大连理工大学硕士学位论文 引言 粒子群优化算法的基本思想即是源于对鸟群捕食行为的研究。算法最早由k e n n e d y 和e b e r h a r t 于1 9 9 5 年提出【l 】，同遗传算法类似，它也是一种基于群体的优化工具，系统 初始化为一组随机解，通过迭代搜寻最优值。但是与遗传算法相比，粒子群优化算法没 有遗传算法用的交叉以及变异操作而是粒子在解空间随最优的粒子进行搜索，算法简 单、容易实现同时又有深刻的智能背景，既适合科学研究，有特别适合工程应用。国内 外研究表明，p s o 是解决复杂系统优化问题的一个有力工具。起初，p s o 算法主要用于 连续函数的优化，后来也应用于组合优化等离散系统的问题研究。此外，对粒子群算法 的改进也体现在很多方面。如：二进制的粒子群算法，w 随进化代数线性递减的粒子群 算法，参数自适应的粒子群算法，以及和其他智能算法相结合的粒子群混合算法等等。 虽然目前已经开发出了很多种类各不相同的改进型粒子群算法，其性能也不断地得 到提高。但在数值建模和优化计算等许多领域中，处理大量数据和求解大规模复杂问题 时，p s o 算法依然需要大量的计算时间，而并行p s o 算法由于能较大幅度缩减问题求 解的时间，因此成为一个研究热点。当前并行p s o 算法主要在并行机上运行或用多线 程技术模拟，主要存在下述不足：进程间通信损耗限制了粒子规模；大多数研究人员没 有硬件环境，无法使用并行机解决问题；多线程技术是在c p u 上用串行模拟并行，不 能真正提高性能。而采用粗粒度并行来避开粒子规模限制的方法，放弃了细粒度并行维 持群体多样性、抑制早熟和保持最大并行性的优势。本文以g p u 为工具，通过图形硬 件的加速处理，试图在保证粒子群搜索效果的同时，对并行粒子群算法进行加速处理， 缩减问题求解的时间。 3 d f x 公司于1 9 9 6 年发布了微机上第一款显卡：v o o d o o 。这款显卡的诞生使得图形 硬件迅速向单芯片发展，图形硬件的功能也越来越强大。在1 9 9 9 年，随着n v i d i a 公司 的产品g e f o r e e 2 5 6 的面世，g p u 这个概念开始进入计算机图形学。作为g p u 的标志性 功能，硬件t & l ( t r a n s f o r m i n ga n dl i g h t i n g ) 的引入使得正向绘制的图形流水线几乎全面 在硬件中实现。这使得c p u 从图形的绘制计算中完全解放出来。随着d i r e c t 3 d 8 0 的出 现，g p u 实现了顶点处理和象素处理的可编程特性。g p u 向通用型矢量计算迈出了关 键的一步。 今天的g p u 逐渐走向成熟，除了在晶体管的规模、时钟频率、并行度和带宽等指 标上有了很大的飞跃，可编程性更是让人们看到g p u 的应用前景蕴涵巨大的潜力，其 针对像素的运算甚至使利用g p u 来做通用计算成为可能 3 - 5 1 。通用计算的领域包括利用 基t - g p u 加速的并行粒子群算法及其应朋 g p u 来实现矢量、矩阵的基本代数运算及在此基础上的一些相对复杂的应用问题的求 解。g p u 已经进入计算的主流，其自身的很多特性已经越来越适合通用计算。 本文研究了基于计算机图形硬件( g p u ) 的并行处理技术，提出了一种基于g p u 加 速的细粒度并行粒子群算法( g p u p s o ) ，增大了细粒度并行p s o 的粒子规模，提高了算 法的运算速度，并取得较好的搜索效果。 随着计算机图形学的飞速发展，呈现在人们面前的三维世界越来越逼真，然而技术 的进步带来的不仅仅是漂亮的画面，物理模拟给人们带来的是真实的感受。物理模拟在 影视制作、计算机游戏等应用领域占据越来越重要的地位，它释放了人们的想象，给我 们带来了空前的互动性。作为物理模拟中的重要一部分，碰撞检测引起了人们越来越多 的关注。碰撞检测是整个物理模拟过程中计算负担最重要的部分，常常是瓶颈所在。而 对于可变形体的碰撞检测，这种瓶颈现象显得更为明显，因为与刚体碰撞检测相比较， 可变形体的碰撞检测有更多的问题需要考虑和处理：无法进行有效的预处理、可能存在 的自碰撞检测、精确获耿碰撞信息等等。 在变形体对象环境中，刚体对象与变形体对象间的碰撞会导致变形体对象的变形， 对象自身属性的改变也会导致其形状的变化，具体表现为组成对象的基本几何元素形状 的改变和数量上的增减【6 】。而在预处理阶段为对象构造的包围盒树是基于原始状态下对 象的基本几何元素集合的，而基本几何元素形状的改变导致原来的包围盒不再适用于当 前的对象，数量的增减导致原先的包围盒树中某些节点无效。为了得到正确的碰撞检测 结果，同时考虑到速度问题，重新构造包围盒树的代价太大，从而导致碰撞检测效率不 高。传本文针对这一问题，在实现g p u p s o 算法的基础上，我们提出了一种基于粒子 群优化和g p u 加速的变形物体碰撞检测算法。在取得较精确的检测效果的同时，得到 了很快的检测速度，同时可以通过参数灵活平衡检测精度与效率的关系。 本文第一部分介绍了传统粒子群算法的基本思想和流程和并行粒子群算法的概念、 基本思想、算法流程、设计及应用；第二部分回顾了g p u 的发展历史，介绍了图形处 理处理原理和体系结构，分析了g p u 的优缺点，讲述了对g p u 进行编程的着色器语言 以及如何用g p u 进行并行计算；第三部分和第四部分分别讲述了本文中提出的一种基 于g p u 加速的细粒度并行粒子群算法，以及将该算法应用到碰撞检测中来。第五部分 总结全文，指出不足以及今后需进一步研究的问题。 大连理工大学硕十学位论文 1粒子群优化算法 粒子群优化算法的基本概念源于对鸟群捕食行为的研究：一群鸟在随机搜寻食物， 在这个区域里只有一块食物，所有鸟都不知道食物在哪里。但是他们知道当l j i 的位置离 食物还有多远。那么找到食物的最优策略是什么呢? 最简单有效的就是搜索目前离食物 最近的鸟的周围区域。p s o 从这种模型中得到启示并用于解决优化问题。在p s o 中， 每个优化问题的潜在解都是搜索空间中的一只鸟，称之为“粒子”，即问题的解空间对 应于搜索空间粒子群。所有的粒子都有一个由被优化的问题( 如，函数) 决定的适应值， 每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子群们就追随当前的最优粒 子在解空间中搜索。p s o 初始化为一群随机粒子也就是随机解，然后通过迭代到最优解。 在每一次迭代中，粒子通过跟踪“两个极值”来更新自己。第一就是粒子本身所找到的 最优解，这个解称为个体极值，另一个极值是整个种群目前找到的最优解，这个极值是 全局极值。另外也可以不用整个种群而是用其中一部分作为粒子的邻居，那么在所有邻 居中的极值就是局部极值。 由于粒子群算法具有思想简单、易于实现、应用效果明显等有点而被众多应用领域 所接受，并在自适应控制、组合优化、模式识别、机器学习、人工生命、管理决策等领 域得到了广泛的应用。粒子群算法具有较强的鲁棒性，特别是对于一些大型、复杂优化 非线性系统，更显示出其独特和优越的性能。粒子群算法作为一门新兴学科，各种理论、 方法尚未成熟，有待进一步发展和完善。尽管在粒子群算法的研究和应用过程中会出现 许多难题，同时也会产生许多不同的算法设计观点，然而，目前粒子群算法的各种应用 实践已经展现出了其优异的性能和巨大的发展潜力，它的发展前景激励着各类专业技术 人员把粒子群算法的理论和方法运用到自己的工作实践中。 1 1 原始粒子群优化算法 1 1 1 算法的基本原理 自然界中一些生物的行为特征呈现群体特征，可以用简单的几条规则将这种群体行 为在计算机中建模f s j ，实际上就是在计算机中用简单的几条规则来建立个体的运动模型， 但这个群体的行为可能很复杂。在这个群体中每个个体的运动都遵循所建的规则，通过 这个模型来模拟整个群体的运动。p s o 算法的基本概念也是如此，它的产生基础是源 于对鸟群觅食行为的研究，以及在寻求一致的认知过程中，个体往往记住它们的信念， 同时考虑其它个体的信念。当个体察觉其它个体的信念较好的时候，它将进行适应性地 调整这一心理学假设来完成的。设想这样一个场景：一群鸟在随机搜寻食物，在这个区域 基y - g p u 加速的并行粒子群算法及其f 衄h j 晕只有一块食物，所有的鸟都不知道食物在哪晕，但是它们知道当| j 的位置离食物还有 多远。那么找到食物的最优策略是什么呢? 最简单有效的就是搜寻目前离食物最近的鸟 的周围区域。p s o 算法就从这种生物种群行为特性中得到启发并用于求解优化问题的。 p s o 算法与其他演化算法类似，也是根据周围环境的适应度将群体中的个体移动到 好的区域，因此有人认为它也属于演化计算的一种，不同之处在于它不像其它演化算法 一样对个体使用演化算子，而是将每个优化问题的潜在解都想象成d 维搜索空问中的一 个没有体积没有质量的微粒，我们称之为“粒子”( p a r t i c l e ) ，其中的每个粒子所处的位 置都表示问题的一个解。每个粒子有个适应值( f i t n e s s v a l u e ) ，是由优化目标决定的，用 于评价粒子的搜索性能，指导粒子种群的搜索过程，算法迭代停止时适应度函数最优的 解变量即为优化搜索的最优解。每个粒子都将在搜索空间中以一定的速度飞行，粒子速 度表示粒子在单位迭代次数位置的变化即为代表解变量的粒子在d 维空自j 的位移，通过 不断调整自己的位置来搜索新解。每个粒子都能记住自己搜索到的最好解( p a r t i c l e b e s t ) ，记作p b e s t ，表示单个粒子从搜索初始到当i j 迭代对应的适应度最优的解。以及 整个粒子群经历过的最好位置，即目前搜索到的最优解( g l o b a lb e s t ) ，记作g b e s t ，表示 整个粒子种群从搜索开始到当f j 迭代对应的适应度最优的解，其值是为每个粒子的当前 最好解p b e s t 中最适应的那个。每个粒子使用下列信息改变自己的当前位置： ( 1 ) 当前位置； ( 2 ) 当前速度； ( 3 ) 当前位置与自己最好位置之间的距离； ( 4 ) 当前位置与群体最好位置之间的距离。 优化搜索正是在这样一群随机初始化形成的粒子组成的一个种群中，以迭代的方式 进行的。 1 1 2 算法的数学描述 e b e r h a n 博士和k e n n e d y 博士最初的目的是在二维空间建立一种模型以图形化鸟群 的运动。而p s 0 算法正是从这种模型中得到启示并用于解决优化问题。鸟被抽象为没有 质量和体积的微粒( 点) ，并将其延伸到维空间，粒子i 在维空间里的位置表示为矢 量a 7 = 0 l ，x 2 ，柳) ，飞行速度表示为矢量v i = ( v ，v z ，v n ) 。每个粒子都有 一个由目标函数决定的适应值( f i t n e s s v a l u e ) ，并且知道自己到目前为止发现的最好位置 ( p b e s t ) 和现在的位置石，这个可以看作是粒子自己的飞行经验。除此之外，每个粒子还 知道到目前为止整个群体中所有粒子发现的最好位置( g b e s t ) ( g b e s t 是p b e s t 中的最好 4 大连理工大学硕士学位论文 值) 。这个可以看作是粒子同伴的经验。粒子就是通过自己的经验和同伴中最好的经验 来决定下一步的运动。 图1 1 粒子移动原理图 f i g 1 1m o v i n g p r i n c i p l e o f p a r t i c l e s 对于第k 次迭代，p s o 中的每一个粒子是按照下式进行变化的： v 。k + 1 = w x 吃+ c , r a n d o x ( p 一) + c 2 。r a n d ( ) x ( p g d 一商)( 1 1 ) x 。k + 1 = + 略1( 1 2 ) 在式( 1 1 ) 、( 1 2 ) 中，i = l ，2 ，m ，m 是该群体中粒子的总数；嵋：第k 次迭 代粒子i 飞行速度矢量的第d 维分量；磁：第k 次迭代粒子i 位置矢量的第d 维分量； ：粒子i 个体最好位置p b e s t 的第d 维分量；p 矗：群体最好位置g b e s t 的第d 维分量； c l ，c 2 ：权重因子；r a n d ( ) ：随机函数，产生 o ，l 】的随机数；w ：惯性权重函数。 公式( 1 1 ) 主要通过三部分来计算粒子i 新的速度：粒子i 前一时刻的速度，粒子i 当前位置与自己最好位置之间的距离，粒子i 当前位置与群体最好位置之间的距离。粒 子i 通过公式( 1 2 ) 计算新位置的坐标。粒子i 通过式( 1 1 ) 、( 1 2 ) 决定下一步的运动位 置。在图1 1 中，以两维空间为例描述了粒子根据公式( 1 1 ) 、( 1 2 ) 从位置p 到j p l 移 动的原理。 1 1 3 算法的设计步骤和流程 粒子群优化算法的设计步骤如下： ( 1 ) 确定问题的表示方案 粒子群算法在求解问题时，其首要步骤是将问题的解从解空间映射到具体有某种结 构的表示空间，即用特定的编码表示问题的解，这和遗传算法是类似的。粒子群算法的 一5 一 基丁：g p u 加速的并行粒子群算法及其应用 大部分研究均集中在数值优化领域中，其位置一速度计算模型适用于具有连续特征的问 题函数，因此，目前算法大多采用实数向量的编码方式，以粒子的位冕向量来表示问题 的解。 ( 2 ) 确定优化问题的评价函数 在求解问题时，必须根据问题的具体特征，选取适当的目标函数来计算适应值，适 应值是唯一能够反映并引导优化过程不断进行的参量。 ( 3 ) 选择控制参数 粒子群算法的控制参数通常包括粒子种群数量、算法执行的最大代数、惯性权重系 数其他一些辅助控制参数，如粒子位置和速度的控制范围等。 ( 4 ) 选择粒子群模型 目前，粒子群算法已经发展了多种位置一速度计算模型，如惯性权重p s o 模型、 二进制p s o 模型等等，在求解不同类型优化问题时，不同p s o 模型的优化性能也有差 异。 ( 5 ) 确定算法的终止准则 与其他进化算法一样，p s o 算法中最常用的终止准则时预先设定一个最大的迭代次 数，或者当搜索过程中解的适应值在连续多少代后不再发生明显改变时，算法终止。 图( 1 2 ) 是粒子群优化算法的流程图如所示： 粒子群优化算法的设计流程如下： s t e p l ：设定加速常数c l ，和c 2 ，最大进化代数等参数，将当前进化代数置为产l ， 初始化一群微粒( 群体规模为 7 ) ，包括随机位置和速度； s t e p 2 ：评价每个微粒的适应度； s t e p 3 ：对每个微粒，将其适应值与其经历过的最好位置p b e s t 作比较，如果较好， 则将其作为当前的最好位置p b e s t ； s t e p 4 ：对每个微粒，将其适应值与全局所经历的最好位置g b e s t 作比较，如果较好， 则重新设置g b e s n s t e p 5 ：根据公式( 1 1 ) 和公式( 1 2 ) 变化微粒的速度和位置； s t e p 6 ：检查结束条件，若满足，则结束寻优，如未达到结束条件( 通常为足够好的 适应值或达到一个预设最大代数力，则返回s t e p 2 。 从上述粒子群优化算法寻优过程可以看出其有如下特性：粒子群中的群体随着时间 的变化而进行空间位置的计算；粒子群中的群体对环境中的品质因素做出响应，这种品 质因素是通过p s o 中每个粒子的最好位置和种群中最优粒子来反映的；粒子群通过一 6 大 - f f j 埋i 大学硕士学位论文 定方式( 即通过对个体最优粒子的记忆和对全局最优粒子的学习的方式) 分配这种响应 而体现出种群的多样性，仅仅当粒子群中的最优粒子发生改变时，粒子群中粒子的行为 才发生改变，这正体现了粒子群的稳定性和适应性。 图1 2 原始粒子群优化算法流程 f i g 1 2p r i m a r y p a r t i c l es w a l t t lo p t i m i z a t i o nf l o w 1 1 4p $ 0 的实际应用 目前已经有些利用p s o 算法代替反向传播算法来训练神经网络的研究，研究表明 p s o 算法是一种很有潜力的神经元网络训练算法【9 】。用p s o 算法进化神经网络的一个成 功的例子是用于分析人的颤抖，包括帕金森病和原发性震鲋1 0 1 ，该进化神经网络能快速 和准确的辨别正常颤抖和病态颤抖。 p s o 算法也被成功地应用于电力系统领域【1 1 】，带有约束条件地和不同版本的p s o 算法相结合用来决定对连续和离散的控制变量的控制策略的问题。 p s o 和其它进化计算算法类似，能用于求解大多数优化问题，比如多元函数的优化 问题，包括带约束条件的优化问题【1 2 1 。此外，p s o 算法还在动态问题和多目标优化 问趔1 4 1 a e 得到应用。 基于g p u 加速的并行粒子群算法及其应用 虽然目前p s o 算法应用广泛，并且已经丌发出了很多种类各不相同的改进型粒子 群算法，其性能也不断地得到提高。但在数值建模和优化计算等许多领域中，处理大量 数据和求解大规模复杂问题时，p s o 算法依然需要大量的计算时间，而并行p s o 算法 由于能较大幅度缩减问题求解的时间，因此成为一个研究热点。 1 2 并行粒子群优化算法 1 2 1 算法的基本思想及流程 并行p s o 算法采用主一从及单程序流多数据流相结合的并行编程模式，主进程主 要完成种群随机初始化、任务的分发和根据适应值进行粒子的选择，从进程主要完成粒 子适应值的计掣15 1 。 初始化常量 毒 随机初始化所有粒子的初始位置x 。 二j ：= 1 二 ! 随机初始化所有粒子的初始速度v i ， 图1 3 并行p s o 算法流程图 f i g 1 3 f l o wc h a r to f p a r a l l e lp s o 首先进行初始化设置包括粒子数聊、惯性权重w 、学习因子c ，和c 2 的值以及所有粒 子的初始位置耳i = ( ，ij ，r u 压厘h l = ( “，1 ，t ) ，- - 1 ，2 ，3 ，m 。 大连理工大学硕士学位论文 然后由主进程为从进程发送每个粒子的位置z ，各个从进程并行计算每个粒子的适 应值名。计算完毕后，从进程将每个粒子的适应值返回主进程，主进程比较每个粒子的 适应值力与其值疋。的优劣，选择较好的个体极值，并通过比较选择整个种群的最优解， 然后更新每个粒子的位置与速度。并行p s o 算法采用公式( 1 1 ) 、( 1 2 ) 对粒子进行操作。 迭代的终止条件根据具体问题的一般选为最大迭代次数或粒子群目前搜索到的最 优位置满足预定最小适应阈值。图l - 3 为并行粒子群优化算法的流程图。 1 2 2 层次及代码粒度的选择 ( 1 ) 甚细粒度指令级并行 图1 4 所示，在现代并行计算机中存在着多层次的并行性【1 6 l ，其中指令级并行是代 码粒度【1 7 】最小的并行，一般代码长度为几十条指令。例如，先进处理器中的多指令发射、 c p u 和i o 操作的重叠以及内存交叉存取等都可视为指令级并行。指令级并行一般由硬 件处理器实现。 并行级别 任务级 控制级 数据级 指令级 消息 图1 4 并行层次与代码粒度 f i g 1 4 p a r a l l e ll e v e la n de x e c u t i o ng r a i n 代码粒度 粗粒度 中粒度 细粒度 甚细粒度 ( 2 ) 细粒度数据级并行 数据级并行属于细粒度并行，它比指令级并行所执行的代码粒度要大些，一般的代 码长度是几百条指令。最典型的数据级并行执行在循环操作上或指令块上，这种循环级 并行是并行或向量计算机上运行的最佳程序结构，通常由机器编译器负责实现这类并 行。 ( 3 ) 中粒度控制级并行 基于g p u 加速的并行粒子群算法及其应用 这一级的并行通常对应着过程、子过程，代码长度一般为几千条指令。检测这一级 的并行性比细粒度级要困难，涉及到过程问的相关分析，通常需要由程序员负责开发这 种并行性。 ( 4 ) 粗粒度任务级并行 任务级并行也叫做作业级并行，对应着并行机上并行执行的独立作业，其代码长度 可高达数万条指令。任务级并行一般由加载程序和操作系统负责处理。 总之，细粒度的并行性常在指令块或循环级上借助并行化或向量化编译器来开发： 中粒度并行性常要求程序员和编译器共同来开发；粗粒度的并行的开发则主要依赖于高 效的操作系统和所有并行算法的效率。在通信方面，共享变量的通信常用来支持细粒度 和中粒度并行计算：消息传递的通信常用来支持中粒度和粗粒度并行计算。一般而言， 粒度越细，并行性越高，通信和调度开销也越大；粒度越大，开发并行性的潜力越低， 而通信与调度开销也越小。 由于我们采用消息传递的通信机制来设计并行算法，p s o 算法中的每个粒子的适应 值的计算具有天然的并行性因此，并行p s o 算法采用中粒度控制级并行，尽量提高并 行性，同时减少通信的开销。 1 2 3 编程模式的设计 研究大量的现有的并行应用程序，常用的几种并行编程模式【l8 】有：主从式、单程序 流多数据流、数据流水线、分治策略和混合方法等。 ( 1 ) 主从式 主从式编程模型又称为任务播种模式，其基本思想是将一个待求解的任务分成一个 主任务( 主进程) 和一些从任务( 子进程) 1 1 9 1 。主进程负责将一个任务分解成些子进程； 然后负责收集各个子进程的求解结果；最后汇总得到问题的最终解。各个从子进程接受 主进程发送的消息；并行进行各自的计算；向主进程发送各自的计算结果。一般情况下， 只有主从进程之间有消息传递。 主进程将任务分配给各个子进程时，需要考虑的主要因素时负责平衡，一般可采用 静态负载平衡方法和动态负载平衡方法两种方法。静态负载平衡方法是任务的分配在计 算过程的初始阶段，允许主进程将任务分配给子进程之后自己也可以参与计算，任务分 。配可以一次完成也可以循环进行，如图1 5 所示；动态负载平衡方法是任务在运行过程 中自适应调整。主要适用于当任务数多于处理器数，或者任务数在程序运行初期不可知， 或者程序执行时间不可预计的情况。 大连理工大学硕士学位论文 图1 。5 静态从主式编程模式 f i g 1 5 s t a t i cm a s t e rs l a v ep r o g r a m m i n gm o d e l 分 配 任 务 收 集 结 果 主从式模式能够获得很高的计算速度，同时也具有一定扩展性。但是，在处理器数 日很大的情况下，主进程的集中控制会成为整个应用程序的瓶颈。改进的方法为可以将 一个主进程扩展为一个主进程集，分别控制不同的子进程集合，这样就提高了该模型的 可扩展性。 ( 2 ) 单程序流多数据流 计算 交换卜交换卜交换交换 结果 算 图1 6 单程序流多数据流编程模式 f i g 1 6s i n g l ep r o g r a mm u l t i p l ed a t ap r o g r a m m i n gm o d e l 基于g p u 加速的并行粒子群算法及其f 用 单程序流多数据流模式又称为单控制流多数据流模式，其基本思想是并行运行的各 个进程均执行相同的代码，但处理的数据不同。如图1 6 所示，首先要将应用程序的数 据预先分配给各个计算进程；然后各个计算进程并行地完成各自地计算任务，包括计算 过程中各进程自j 的数据交换；最后将各个计算结果汇集起来。 当将应用程序的数据分配给各个计算进程时，所要考虑的主要问题是计算的局部 性。在大型科学与工程计算中，很多物理问题其本身具有很规整的几何结构，这种固有 的特性使得计算过程中空间上的彼此交互不多，计算集中体现在局部空间上。 如果数据分配得好并且系统是同构的话，单程序流多数据流程序可以获得很高的效 率。如果进程具有不同的工作负载或者不同的能力，那么该模型需要一些负载平衡策略 的支持，从而在运行时调整数据的分配。单程序流多数据流模型对一些进程的故障很敏 感。通常情况下，一个进程的执行失败足以导致整个计算过程的阻塞，致使所有进程都 不能通过全局同步操作。 ( 3 ) 数据流水线 流水线技术是一种最简单、最常用的并行处理技术，其基本思想是将各个计算进程 组织成一条流水线，每个进程执行一个特定的计算任务，相应于流水线的一个阶段。如 图1 7 所示，一个计算任务在功能上划分成一些子任务( 进程) ，这些子任务完成某些特定 的计算工作，一旦前一个子任务完成，后继的子任务就可以立即开始。在整个计算过程 中各进程之间的通信模式非常简单，仅发生在相邻的阶段之间，并且通信可以完成异步 地进行。这种模型的效率直接取决于流水线上各个阶段负载平衡能力。 袱暖盯卜豫吾卜盛蓊卜输出 图1 7 数据流水线编程模式 f i g 1 7 d a t ap i p e l i n i n gp r o g r a m m i n gm o d e l 数据流水线编程模式常使用在数据规约或数字信号处理程序中。 ( 4 ) 分治策略 分治策略是一种很有名的问题求解技术，其基本思想是将一个大而复杂的问题分解 成若干个特性相同的子问题，然后独立的解决每一个子问题，最后将结果综合起来得到 最后的解。如果分得的子问题规模仍然很大，则可以反复使用分治策略，直至得到容易 求解的子问题。 分治策略的编程模式适用于递归并行程序设计中。 大连理工大学硕士学位论文 实际中，上述各种不同编程模式之间的界限并非那么清楚，在某些应用中，特别是 在大型的应用中，往往需要几种编程模式综合使用才能达到更好的效果。 1 2 4 任务分配方案 在并行程序设计中，任务的分配和通信是其核心问题。由于在优化过程中，种群的 数目是恒定的，并且各个节点的计算能力相当，所以可以采用块分配方法。所谓块分配 方法，是指将种群数目按照并行环境中启动的进程的个数分成若干个任务块，每个进程 负责一块任务的计算。假设种群数目为，优化参数个数为m 。适应值评价时，程序传 给评价函数个长度为m 的向量。计算结束后，评价函数返回个适应值。即并行的 任务是将一个n x m 的二维数组分配到各个进程，然后从各进程收集一个长度为的一 维数组。 例如对于种群数目为7 ( n = 7 ) ，进程数为3 0 拓e = 3 ) 的情况，分配方案如图1 8 所示： 麓；”鬻 p r o c e $ s o r o p r o e e s s o r l 圈p r o c e s s o r 2 图1 8 任务分配方案 f i g 1 8a s s i g n m e n td i s t r i b u t i o nm e t h o d 首先计算每个进程至少分配的粒子个数： a v e r a g e n u m b e r = l n s i z e j 如果启动的进程的个数不能整除粒子数目，将有 h e a v y p r o c e s s o r n u m b e r = n m o d s i z e 个进程分得a v e r a g e n u m b e r + 1 个粒子，如果规定编号小的进程分得更多的粒子， 则编号为r a n k 的进程分得粒子数为： 爿聊批埘切：j 砒懈m 砒h 1m k h e a v y p r o c e s s o r n u m b e r 。 【a v e r a g e n u m b e rr a n k h e a v y p r o c e s s o r n u m b e r 每个进程根据自己分得的粒子数目，进行相应的适应值的计算。 基tg p u 加速的并行粒子群算法及其应用 1 2 5 消息传递方法 并行程序设计模型是一种程序抽象的集合，它给程序员提供了一幅计算机硬件软件 系统透明的简图，程序员利用这些模型就可以为多处理机、多计算机和工作站机群等设 计并行程序。并行程序设计模型【2 0 】通常分为数据并行模型、消息传递模型