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

大连理工大学硕士学位论文 摘要 模拟退火算法( s i i l l u l a t e d 加m e a l i n ga 】9 0 r i t l l i l l ，s a ) 来源于固体退火原理，是一种 通用概率算法，用来在一个大的搜寻空间内寻找问题的最优解。由于在解决大规模优化 问题时，s a 算法通常需要大量的计算时间，因此并行s a 算法逐渐成为人们研究的热 点。目前关于并行s a 算法的研究主要在大型并行机上运行或利用多线程技术进行模拟， 这些方法存在以下不足：进程间通信的消耗限制了线程规模；多线程技术是在c p u 上 用串行模拟并行，不能真正提高性能；大多数研究人员很少有机会使用上述并行机，而 且并行机使用也比较复杂。 近几年，图形处理器( g i a p k c sp r o c c s s i n gu i l i t ，g p u ) 高速发展，其高速浮点运算 能力、并行计算和可编程功能为通用计算提供了良好的并行计算平台，n v i d 认公司推 出的g p u 编程的统一计算设备架构( c o m p u t eu i l i f i e dd e v i c e 觚h i t e c t i l r e ，c u d a ) ，为 研究人员利用g p u 进行数据并行处理提供了更便捷的方法。 本文针对传统并行s a 算法在实际应用中的不足，利用g p u 的高速并行性，提出了 一种基于g p u 加速的细粒度并行模拟退火算法( g p u s a ) 。该算法充分利用n v i d 队 g p u 的统一计算设备架构，将一条串行执行的m a r k o v 链拆分为若干个m a r k o v 链并行 执行，即c u d a 线程块并行计算过程，使等温状态下的重复抽样过程完全在g p u 中加 速执行，在取得较好优化解的同时，显著地提高了算法的运算速度。本文主要以m a r k o v 链的并行实现为例，详细描述了算法设计思想和程序实现过程，提供了应用于对称t s p 问题的实验结果，与相应串行算法在相同计算环境下的实验结果做出比较，并针对实验 结果分析了g p u s a 算法的特点。实验结果表明本文算法在取得了较好的优化效果的同 时，显著地提高了算法的运算速度。 关键词：g p u ；模拟退火算法；细粒度；并行处理 基于g p u 加速的细粒度并行模拟退火算法 ap a r a l l e ls i 舢l a t e d 山m e a l i n ga l g o r i t h mb a s e do nf i n e g r a i n e dm o d e l w 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 s i i i 】【u l a t e da i m e a l i n ga l g o 打吐m ( s a ) ，d e r i v e dl 沁mt h ep r i n c i p l eo fs o l i da n n e a l i n 岛i sa g 饥e r a lp r o b a b i l i s t i ca l g o r i t l l 】 i la n du s e dt o 矗n dt h eo p 幽脚s o l 埘o no fm ep r o b l e mi i ll a r g e s e a r c _ hs p a c e a si nt h es e 仕l e m e n to fl a r g e s c a l eo p t i m i z a t i o np m b l e m s ，s aa 1 9 0 r i t l l mu s u a l l y r c q u i r e sal o to fc o m p u t i n gt i m e ，p a r a l l e ls aa l g o r i t l l m 孕a d u a l l yb e c o m e sr e s e 卸c hh o t s p o t a tp i - e s e n tp a r a l l e ls aa l g o r i t l l mi s i n o s t l ym o np a r a l l e lm a c t l i n e0 rs i m u l a t e db y m u l t i - t l l r e a dt e c h n o l o g y ，h o w e v e x i s t i n gm ef o l l o 诵n gd e 6 c i 肌c i 懿：1 1 1 ec o l t l i l l u i l i c a t i o n c o n s 明1 p t i o n b e 研e e np r o c e s s e sc 0 n 6 n 鼯m ep o p u l a t i o no fm r e a d s ；m 1 】l t i t l i r e a d i n g t e d m o l o g yc o u l d n tt m l yi i l l p r 0 v ep e f f o 姗a n c eb e c a u s ei tj u s tm n so nc o m m o nc p u w i t l l s 甜a l p a r a l l e ls i i i l u l a t i o n ；m o s tr c s e a r c h e r sc a i ln o tb ea c c e s s a b l et oa b o v ep a r a l l e lm a c h i n e e q u i p m e n t s ，a n di ta l s os e e m sm u c hm o r ec o m p l e xt ou s et h 锄 i i lr e c e l l ty e a r s ，g p uh a sar a p i dd e v e l o p m e n t ，o 、) l ，i n gt 0i t sh i 曲s p e e dn o a t i n gp o i n t o p e r a t i o i l s ，p a m l l e l i s ma i l dp r o 铲觚蚰a b i l i 坝p r 0 v i d e i n g 觚i d e a lp a r a l l e lp l a t f o n i lf o r g e n e r a l p u l 印s ec o m p u t a t i o n a d d i t i o n a l l y ，c o m p u t eu n i f i e dd 州c em i t e c t u r e ( c u d a ) ， l 踟【1 c h e db yn v i d 认c o 印o r a t i o n ，g v e sr e s e a r c h e r sam o r ec o n v 枷e n tw a yt od a t ap 撇l l e l p r o c e s s i n g t l l ep 印a i m i n ga t 1 0 s ep r o b l 锄si np a r a l l e ls aa l g o r i t h m ，r a i s e saf i n e - 铲a i n e ds a a l g o r i t h mb a s e do ng p u a c c e l e r a t i o n t h i sm e t h o dc o n v e r t sn l ep r o c e s so fw o r k i n 争o u ti n t o m ee x e c u t i o no f k e n l 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 em a r k o vc h a i n ，s p e e d s u pi t sn m n i n ga i l dp r o v i d e so r d i n a 巧u s e r sw i t l laf e a s i b l es aa l g o r i t l l l n t h ee x c u t i v em o d e l o fg p uu s i n gc u d ai sp a r a l l e l t h r e a d s ，锄dt h et h r e a d si nt l l es 锄eb l o c kc a i la c c e s ss h a r e d m e n l o 巧a 1 1 dc a i ls y i l c i 啪i l i z er 印i d l y t l l i sp 印e r ，t a l ( i n gt h ep a r a l l e l i z a t i o no fm a r k o vc h a i n f o re x a m p l e ，d e s 嘶b e sm ea l g o r i t m sd e s i g na n dp r o 伊a m m i n g m e a l l w l l i l e ，i t 西v e sm a i l y r e s u l t sa p p l y i n gt os y m m e t r i c 仃a v e l i n gs a l e s m a np b l e m s ，a n da n a l y s e st h ep r o p e n i e so f p a r a l l e ls aa l g o r i t h mb a s e do nt h ec o m p 撕s o nw i t hm er e l e v a l l ts e q u e n t i a lv e r s i o n 7 r h e a i l a l y t i c a lr e s u l t sd e m o n s t r a t et 1 1 a tt h ep f o p o s e da l g o r i m ma c h i e v e sag o o do p t i m i z a t i o ne f f e c t 锄di n c r e a s e st 1 1 e p o p u l a t i o ns i z em t 1 1 ef i n e 一黟a i n e dp a r a l l e l i s mw h i l es p e e d i n gu pi t s e x e c u t i o n k e yw o r d s ： g p u ；s aa l g o r i t h m ；f i n e g r a i n e d ；p a r a e ip r o c e s s i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：美i 鱼巳芝立里建叠馏牲弛亟握拯& 丛粤逗 作者签名：j l 二豸一 日期：卤争年_ _ 坐月笋日 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题 作者签名： 导师签名： 大连理_ 亡大学硕士学位论文 己l言 丁i 目 s a 算法最早是由n m 咖p o l i s 等人提出的，是一种可行、有效的全局优化的算法【艟】， s a 算法用于解决组合优化问题的想法，是基于物理中固体物质的退火过程与一般组合 优化问题间的相似性。s a 算法已在物流配送、组合优化问题等领域有着广泛应用，并 且在组合优化中取得了很好的效果【3 。5 】，能解决传统的优化方法难于解决的许多问题。 对于中小规模的应用问题，s a 算法得到了广泛的应用，并取得了很好的优化效果，而对 于大规模或超大规模的优化问题，s a 算法往往需要大量的计算时间而显得力不从心。 并行s a 算法由于能较大幅度缩减问题求解的时间，因此成为一个研究热尉鸺】。 细粒度并行模拟退火算法是并行模拟退火算法【9 j 2 】中一个重要模型。目前并行模拟 退火算法的研究主要是在并行机上执行或利用多线程技术来进行模拟实现，在细粒度并 行方面存在以下不足： ( 1 ) f g p s a 的实现在并行机上需要为每个m a r k o v 链运行设置单独的进程，但对 于大规模问题需要设置更多的m a r k o v 链，这样就导致了进程间大量的通信损耗，在这 种情况下多数并行机承受，因此目前的并行模拟退火算法多采用粗粒度模型【3 】； ( 2 ) 多数研究人员很少有机会使用上述并行机，同时对于非专业人员来说使用和 管理并行机也比较困难； ( 3 ) 多线程技术并不能本质上提高计算速度，因为其只是在c p u 上用串行来模拟 并行。 近年来，g p u 的高速浮点运算能力和并行计算以及可编程功能，使其在通用计算领 域的应用有着巨大的潜力，为通用计算提供了良好的并行计算平刨1 3 】。n v i d i a 公司统 一计算设备架构( c u d a ) 为研究人员利用g p u 进行数据并行处理提供了更便捷的方 法。通过g p u 进行并行优化算法的加速，是解决上述f g a s a 面对问题的一种可行的方 法。李建明提出了一种基于g p u 的细粒度并行遗传算法【1 4 】，主要是使用g p u 纹理渲染 来实现并行遗传算法的求解过程，利用约减技术降低了c p u 与g p u 之间的通信消耗， 从而取得了比较好的效果。h o n g “提出了基于g p u 的并行鱼群算法【1 5 】，在优化效果方 面得到了改善。但是该算法的鱼群的个体是利用c u d a 架构的每个线程来模拟的，并 不能充分利用g p u 并行性。 根据在以上方法，本文提出基于g p u 加速的细粒度并行模拟退火算法，利用c u d a 架构的线程块模拟m a r k o v 链个体，尽量发挥g p u 并行计算能力。该方法增大了细粒度 并行的m a r k o v 链规模，提高了算法运行速度，同时为普通用户实现并行s a 算法提供 了一种可行的途径。 基于g p u 加速的细粒度并行模拟退火算法 本文的工作集中在以下几个部分： ( 1 ) 根据统一计算设备构架提供的编程模型，在分析传统做法采用一个线程 处理一个智能体的方式基础上，认为如果采用这种方式处理本文算法，效率会太低。也 就是说，我们必须打破传统做法，设计适合本文算法的并行模型，即建立基于线程块的 m a r k o v 链个体模型。 ( 2 ) 在本文算法并行设计时，充分利用g p u 硬件资源，实现加速并行求解新路径。 ( 3 ) g p u 中的芯片内存访问速度快，但芯片内存的容量有限，c p u 的内存空间大但 是访问速度慢。如果计算需要的数据量很大，则需要进行多次读取数据操作，这样访问 延时会影响算法的速度。所以如何合理分配利用g p u 内存是在算法优化过程中的重点 工作。 本文共分为4 章，第l 章介绍了目前模拟退火算法及其并行的发展。第2 章介绍了 g p u 通用计算的相关知识。第3 章详细论述了本文提出的基于g p u 加速的细粒度并行 模拟退火算法，并进行实验仿真。第4 章对实验结果进行分析。最后对本文提出的算法 进行总结和展望。 一2 一 大连理工大学硕士学位论文 1模拟退火算法起源及其发展 在自然科学、社会科学等领域以及人们的日常生活中广泛存在着大量的求最小或最 大的问题，即所谓的最优化问题。特别是近代，在计算机科学、管理科学、分子物理学 和生物学以及代码设计、电子工程和图象处理等科技领域中，大量的组合优化问题需要 解决。用数学语言来说，就是要决定一组参量，使其对应的目标函数达到最小值或最大 值。我们很容易想到的就是穷举然后求极小，但这种方法在实际应用中存在着很大的不 足。对于组合优化问题中的n p 完全问题( n o n d e t e 肌砸s t i cp o l y i l o m i a lc o m p l e t e p r o b l 锄) ，其求解所需的时间随问题规模的增大而成指数级增长，当规模过大时就会 因为时间的限制而失去可行性。 模拟退火算法是l ( i r k p a t r i e k 于1 9 8 3 年应用于组合优化问题的一种亚启发式算法， 它在解决高维空间、高复杂度及非线性问题的优化中具有全局最优、效率高及易于并行 计算等优点，有很强的解决实际问题的能力。近年来在大规模、超大规模集成电路设计、 模式识别、自动控制、电信【1 睨0 1 、神经网络等许多领域【2 1 。2 3 1 受到重视，应用范围不断扩大， 已经成为了一个研究热点【2 4 l 。目前对其研究已渗透到多个应用领域，并由解决一维静态 优化问题发展到解决多维动态组合优化问题。如今在国内外许多学术期刊和重要国际会 议上，模拟退火算法已经成为交叉学科中一个非常活跃的前沿性研究问题。 1 1t s p 问题 旅行商问题( n a v e l i n gs a l e s m a i lp r o b l e m ，以下简称t s p ) ，它可简单地描述为： 对于个城市，它们之间的距离已知，有一旅行商要从某一城市出发走遍所有的城市， 且每一个城市只能经过一次，最后回到出发城市，问如何选择路线可使他所走过的路程 最短。t s p 问题表面看很简单其实不然。当t s p 问题的规模为个城市时，可行解 集中的路径数为( 一1 ) ! 2 ，要从( 一1 ) ! 2 个可行解中找出哪条路径最短，若以路径 间的比较为基本操作，则需进行( 一1 ) ! 2 1 次比较。如果使用每秒运算一亿次的计算 机，当，z 等于1 0 的时候只需o o o l 8 秒，而当等于2 0 的时候就需要1 9 年，当等于 3 0 的时候所需时问则猛增到1 4 1 0 ”年。显然，这样一来算法就失去了可行性。t s p 问 题是典型的n p 困难优化问题，模拟退火算法是局部搜索算法的扩展，从理论上来说， 它是一个全局最优算法，具有受初始条件影响很小、全局寻优能力很强的特点，算法通 过对物理退火过程的模拟，求出问题的最佳解。 根据模拟退火算法的特性，可以用于解决t s p 问题，因此研究s a 算法在优化中的 应用显得尤为重要，本文就应用s a 算法解决t s p 问题【2 职6 】作为本文研究算法的应用问 一3 一 基于gp l _ 加速的细粒度井行模拟退火算法 题。一般t s p 问题可以描述为带权完全图g = ( ，r ) ，为城市节点集，月为边集。事 实上非完全图也可以描述为完全图，只需要令那些不存在的边的权值足够大。每条边 ( j ，) r 赋予权值，城市f 与之间的距离d 。f ，我们的目标就是找到该图的哈密 尔顿回路即其长度虽短，并且访问每个节点一次且仅有一次。所以t s p 问题的最优解 应该是所有城市节点号 1 ，2 ，” 的一个置换口，并且，忙) 虽小，如公式( 11 ) 所示。 盟 ，( 石) = d ，( 。) 。( 件1 ) + d ，n ( 1 ) ( 1 1 ) # 1 1 2 模拟退火算法的起源 s a 算法的思想最早是由nm e 昀p o l i s 等人提出的。在1 9 8 3 年由s 1 ( i 蛳“c k 等人 和v c 廿n y 分别提出把它用于组合优化领域，目前已在各个领域中得到了广泛的实际应 用口m ”。s a 算法用于解决组合优化问题的想法，足基于物理中固体物质的退火过程与 一般组合优化问题间的相似性，图l l 描述了组合优化与固体降温的相似性。 固体降温离散函数求最小值 幽l 1 组台优化与州体降温的相似性 h g1 1 t h es i m i l a n h o f 1 1 “ga n do p n m i z a l l o n 在对固体物质进行退火处理时，通常先把固体加热至足够高的温度，同体中的粒子 运动加剧而使固体的总内能变大。然后随着温度的逐渐下降，粒子也逐渐减慢运动而渐 趋有序状态。若温度下降的速度足够慢，则固体物质的总内能一定能够达到最小。在加 热过程中，固体物质的粒子随着温度变大而逐渐由有序状态变为尤序状状态，并且固体 物质的总内能也逐渐增大。在降温过程中，只要温度下降地足够慢，固体粒子会慢慢变 大连理工大学硕士学位论文 得有序，并且在每个温度下都能够达到平衡态，最后在常温时达到基态，此时固体物质 的总内能减为最小。 在固体加热过程中，固体中粒子的运动逐渐加快，固体的总内能也随着增大，从而 粒子更加剧烈的运动使其离开原来位置，随温度的升高粒子由原来的有序状态变为无序 状状态，如图1 2 所示。 a f f r n u c l e u s 图1 2 粒子运动规律 f i g 1 2 7 n l ed i s c i p l i n a d a no fp a r t i c l em o t i o n 在等温过程中，与周围环境交换热量不变，固体内能本能地由高内能向低内能的方 向进行，当固体内能达到最小时，系统达到平衡状态，即固体粒子变成有序状态。在降 温过程中，粒子热运动减弱，粒子逐渐趋于有序，最后在常温下达到基态，同时内能也 减为最小。 表1 1 物理退火与组合优化的相似性 t a b 1 1t l l es i m i l a r i 够o fa n n e a l i n ga n do p t i m i z a t i o n 物理退火组合优化 粒子状态 能量最低态 冷却过程 等温过程 解 最优解 控制参数的下降 m e t m p o l i s 抽样过稃 一5 一 基于g p u 加速的细粒度并行模拟退火算法 物理固体退火与组合优化的相似性归纳如表1 1 所示，用固体退火模拟组合优化问 题，将内能e 模拟为目标函数值厂，温度丁演化成控制参数f ，即得到解组合优化问题的 s a 算法：由初始解f 和控制参数初值f 开始，从初始解的领域中随机产生一个新解，接 受准则允许目标函数在一定范围内接受使目标函数恶化的解，算法持续进行“产生新解 一计算目标函数差一判断是否接受新解一接受或舍弃”的迭代过程，固体在某一恒定温 度下趋于热平衡的过程，经过大量的解变化后，可以求出给定控制参数丁值的时候优化 问题的相对最优解，然后逐步衰减f 值，重复执行上述迭代过程。当算法终止时的当前 解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退 火过程由一组称作冷却进度表( c o o l i n gs c h e d u i e ) 的参数控制，包括控制参数的初始值 丁以及衰减因子口、每个f 值时的迭代次数( 称为一个m a r k o v 链的长度) 和终止条件 g o 1 3 模拟退火算法的流程 s a 算法从高温开始，采用m e 仃o p o l i s 接受准则在解空间进行随机搜索，随着温度 的逐渐下降重复抽样过程，每温度下的抽样都达到稳定，当算法结束时所求得的最优解 就作为全局近似最优解。其中，所求问题的一个解s ；与固体物质的一个微观状态f 以及 其目标函数厂( s ，) 与固体物质的能量e 相对应。假设随着算法逐渐减少的控制参数r 与 固体退火过程中的温度变化相对应，从而在每个丁取值下，算法采用m e t r o p o l i s 接受准 则，连续执行“产生新解一判断是否接受一接受或舍弃”的迭代过程，直到达到该温度 下的稳定状态。算法实现步骤如下： ( 1 ) 参数初始化：给定控制参数r 的初始值瓦及随机产生初始解状态s 。以及厂( s 。) ， 在同一温度下采用相同的迭代次数厶= 木咒2 ( 七= 1 ，2 ，) 其中1 为一整数，如 = 1 0 0 ，刀为城市数，温度衰减系数口，令当前温度r = 瓦，终止条件g 。令s ，= ， 并计算目标函数值厂( j ；) 。 ( 2 ) 参数丁= r ( 后) 时，按照下面过程进行厶次试探查询： 根据当前解足领域产生一个随机向量z 。( 对于连续变量) 或随机偏移量，l ( 对 于离散变量) ，则得到一个当前解领域的新的试探点墨- ： 其中s 为当前解得路径序号，尼为在当前解基础上产生的随机序号。 ( 1 2 ) m 鹋=竺 甄乩 大连理工大学硕士学位论文 在( 0 ，1 ) 区间范围内产生一个均匀分布的随机数口，根据m 咖p 0 1 i s 接受准则，计 算在当前路径足和温度互下的接受概率p ： p ：j 1 ， 邢 ) = 厂( s 女) 如果随机数护小于p ，则接受新解，最= 最，厂( 文) = 厂( 瓯) ，否则当前解不变； 试探查询小于厶次，跳转到步骤( 1 ) ，否则执行步骤( 3 ) 。 ( 3 ) 若不满足迭代终止条件，则跳转到步骤( 4 ) ；否则算法结束，当前解即为所 求得问题的近似最优解。 ( 4 ) 根据温度衰减函数产生下一个温度控制参数瓦+ 。，及m a r k o v 链长度厶+ 。，跳转 至步骤( 2 ) ，进行下一温度的稳定状态下的求最优解。 图1 3 跳出局部解 f i g 1 3 o u to f l o c a ls o l u t i o n 其中m e t r o p o l i s 接受准则是模拟退火算法收敛于全局最优解的关键，为了扩大搜索 的解空间，在判断时候接受新解时加入了随机扰动，即若厂( 瓯) m 刀如m ( o ，1 ) ( 1 4 ) 这也就是所谓的m 咖p o l i s 接受准则以一定的概率接受恶化解的过程。如图1 3 所示，若 此时当前解处于d 点处，假如在不接受恶化解得前提下，在逐渐寻找最优解的过程中， 基于g p u 加速的细粒度并行模拟退火算法 只接受比当前解好的新解，则最终求出的最优解黝点处的解，即局部最优解而不是b 点处的全局最优解，这是我们所不希望的。所以，我们采用m e 仃o p 0 1 i s 接受准则以一定 的概率接受恶化解的过程，就很可能把在搜索最优解的过程中从d 点处的解，越过c 点 处的解最终求得召点处的全局最优解，这样就可以避免陷入局部最优解，抑制了早熟现 象。 1 4 模拟退火算法的研究现状 s a 算法由瞄舳砌c k 等人将模拟退火的思想成功引入组合优化领域，并广泛应用 于计算机科学、物流分配等领域，同时模拟退火算法在理论上已得到证明，其可以达到 全局最小值，因此模拟退火算法迅速得到专家与学者的青睐，从而能也引起了众多学者 广泛的研究兴趣，模拟退火算法得到了突飞猛进的发展。相对于遗传算法、蚁群算法等 算法来说，模拟退火算法研究并不是很多，而且大部分研究工作就是研究算法的实际效 果和效率问题它的实际应用，很少进行对其理论性作深入的研究。下面部分进行讨论一 下几种在文献中经常被提到的模拟退火算法【2 。m 9 1 。 s a 算法在迭代的过程中，以一定的概率接受比当前解差的解，即在一定限度范围 内接受使目标函数恶化的解，从而算法可以有效的跳出局部极小值，防止出现早熟现象。 但是，对于大规模的问题，该算法不能确保曾经求得的最好解就是最后得到的最优解。 我们可以改进针对上述问题，即设置了变量，记住搜索过程中求得的最好解，这可以提 高所求解的效果，这种改进的算法就称为有记忆的模拟退火算法【3 0 1 。 该算法描述如下：设置变量x 和厂( x ) ，分别记住目前遇到的最好解和最优目标函数 值。算法刚丌始时将初始解而和其目标函数厂( ) 分别赋值给x 和厂( x ) 。在搜索过程汇 中，当接受新解为当前解时，就将其目标函数值( 以) 与( x ) 进行比较，若( t ) 小于 厂( x ) ，则用以和厂( ) 替换x 和厂( 工) 。重复上述过程直到算法结束，最后则全局近似最 优解存在当前解与记忆变量中，选择较小者即为所求的全局最优解。 s a 算法天然隐含着并行性，考虑到串行算法的速度不是特别快，而且又因为模拟 退火算法中的m a r k o v 链的无后效性，我们可以将经典的传统模拟退火算法中的一条 m a r k o v 链分裂成多条m 破o v 链，从而取得了可扩展的并行性，打破了经典模拟退火算 法的瓶颈，使得多个退火同时进行，这就是实现了模拟退火算法的并行化。 以下部分讨论s a 算法求解问题的并行化实现【3 。假设我们己经有了一种模拟退火 的模型，即己给出一些模拟退火参数的取值以及变化规则，按照某种分布在区域d 上随 机选取个初值并进行计算，从而就可以得出个结果，分别记作p 1 ，缈：，妒”，在理 论上来说，可以把它们看成是独立同分布的随机向量，并且其任意分量 大连理工大学硕士学位论文 仍7 0 = 1 ，2 ，埘；- ，= 1 ，2 ，) 则是独立同分布的随机变量， e ( 妒7 ) = x 。按照上述方法可以记作： 瓦= 专静 从而可以合理地近似得出 ( 1 4 ) 墨2 = 寺( 仍一菇) 2 ( 1 5 ) 根据中心极限定理，我们可以推出： 蟑( 1 6 ) s i n 近似服从n ( o ，1 ) 正态分布，其中x 的第f 个分量记为工；，于是我们可以计算出x 的置信概率为( 1 一口) 的区间估计， 歹一击 x n o a tb ，o u tn o a tr e s u l t ) r e s u l 卢a 十b ； ) v o i dm a i n ( v 0 i d ) s t r e a md e c l a r a t i o n s n o a ta ： n o a tb ： n o a tr e s u l t ； f l o a ta = av e c t o r f l o a tb = bv e c t o r f l o a tr e s u l t 1o o ； i i l i t i a l i z et h es t r e 锄s s t r e 锄r e a d ( a ，a ) ； s 拓e 锄r e a d ( b ，b ) ； f o o ( a b ，r e s u l t ) ；f o r ( i n ti - o ；i 其中b r o o k 【4 1 】支持所有带附加流数据的c 语法，流数据存储于g p u 的存储器中， 而核函数也在g p u 上执行。计算碎片颜色的运算一般包括集合向量数学操作以及从纹 理中提取存储数据，纹理是一种存储表面材料颜色的位图。最终绘制的场景可以显示在 输出设备上，或是从g p u 的存储器重新复制到宿主处理器中。可编程顶点处理器和碎 片处理器提供了许多相同的功能和指令集。 基于g p u 加速的细粒度并行模拟退火算法 但是，大部分g p u 编程人员只将碎片处理器用于通用计算任务，因为它通常提供 更优的性能，而且可以直接输出到存储器。利用碎片处理器进行计算的一个简单例子是 对两个向量进行相加。首先，我们发布一个大三角形，其所包含的碎片数量和向量大小 相同。产生的碎片通过碎片处理器进行处理，处理器以单指令多数据流( s i m d ) 的并 行方式执行代码。进行向量相加的代码从存储器中提取两个待加的元素，并根据碎片的 位置进行向量相加，同时为结果分配输出颜色。输出存储器保存了向量和，这个值在下 一步计算中可以被任意使用。可编程碎片处理器的i s a 类似于d s p 或p e l l t i 啪s s e 的指 令集，由四路s i m d 指令和寄存器组成。这些指令包括标准数学运算、存储器提取指令 和几个专用图形指令。 g p u 除了在计算机图形学本身的研究应用外，还广泛应用到其它领域的计算，从而 基于图形硬件的通用计算( g p g p u ) 成为g p u 的应用的一个研究热点【3 6 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 印o s ec o m p u t i n go n 黟a p h i c sh a r d w a r e ) ，以讨论这方 面的应用。h t t p ：n 硼r g p g p u o r g 提供了这方面最全面的信息，并作了详细分类。下面列 出了一些目前已经存在的应用： ( 1 ) 向量和矩阵计算 ( 2 ) 数据挖掘和数据库操作 ( 3 ) 偏微分方程求解，如云的仿真动画 ( 4 ) 非线性最小二乘优化问题 ( 5 ) 频谱变换和滤波，如香港中文大学开发的离散小波分析程序包 ( 6 ) 在视频处理方面 基于g p u 的通用计算是随着图形芯片的发展而发展起来的。虽然以前的计算机图 形处理器主要只是针对图形本身的应用而设计，如光照计算、深度检测、图形视频处理 等等，但是针对其他除计算机图形学领域以外的更为通用的应用也有出现。但g p u 的 真正发展是因为可编程性的普及。随着2 0 0 1 年g e f o r c e 3 的出现，顶点级可编程开始普 及，到了2 0 0 2 年h a r r i s 等人开始利用t e x 衄es h a d e r 结合r e g i s t e rc o n l 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 l l d 等人将图像处理从时域空间转换到频域空间，利用g p u 实现快速傅里叶 变换，通过灵活组织索引避免重新排序。而h o p f 利用g p u 来做三维卷积运算和小波变 换，两者都是利用o p e n g l1 2 以上版本提供的颜色矩阵和卷积操作来实现的。1 r e n d a l l 等人利用硬件提供的颜色融合和o p e n g l1 2 以上版本提供图像子集的卷积和颜色矩阵 等运算功能计算折射散射效果。r 硼叩f 等人利用图形硬件求解传热和各向异性扩散有限 单元方程，从而实现图像处理的功能。j 锄e s 等人利用现有的有限元包分析出变形物体 的自振频率，然后采用模态分析的方法利用顶点编程将物体各个振型进行叠加从而得到 新位置，这样可以将以前在c p u 上进行的计算全部转移到g p u 上去。 另外在碰撞检测方面，g o v i n d a m 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 问题的求解。l 1 9 e r 等人利用像素程序来做基本代数运算，然后在 此基础上实现共扼梯度法和高斯一赛德尔迭代法，从而完成p d e s 的求解。b 0 1 z 等人实 现了基于像素编程的稀疏非结构化矩阵的共扼梯度法和正交网格的多重网格法，并用于 加速几何处理和流体模拟。m o r a v a i l s z k v 利用d i r e c t x 9 下的h l s l 实现了稠密矩阵的系 列代数运算，并在此基础上实现了共扼梯度法和线性优化问题求解。h i l l e s l a n d 等人将 最速下降法和共扼梯度法求解带有简单约束和规则化的非线性最小二乘优化问题映射 到最新的图形硬件上，并应用到复杂的图象建模问题上。 g o o d n i 出等人实现了基于像素程序的多重网格算法，用来求解边界值问题( 热传 导问题、流体力学问题) 。飚m 等人将冰晶体生长过程采用g p u 来实施物理计算，整 个物理方程组的计算在g p u 上执行。l e f o h n 等人将l e v e l s e t 的等值面数据压缩为一个 动态稀疏纹理格式，针对不同边界情况采用不同的像素程序来进行计算l e v e l s e t 的 p d e s 。另外通过将下一个活跃的片段信息压缩成一个位矢量消息，从而将该消息传递给 c p u 以决定它需要传送给g p u 的顶点和纹理坐标，此外，他们还充分利用了硬件的自 动m i p m a p p i n g 技术来低采样截止到一个像素。 g p u 甚至被用来进行声音的合成运算，g 锄a s u t r a 的研究使声音合成时c p u 和a p u 能够达到一个良好的均衡，并出现基于g p u 的商业声音合成软件。 基于g p u 加速的细粒度并行模拟退火算法 除此之外，m i c h a e l 把g p u 运算与元编程联系起来，之后又用代数的思路对g p u 运算进行研究，并实现了一个库s h ，能够借助c + + 的模板技术简化g p u 运算程序 的编写。但是由于目前图形处理器硬件结构和编程接口处于高速发展之中，变化相当迅 速，因此这两种语言现在还没有成熟到应用推广阶段。 2 3g p u 用于通用计算的限制 毕竟g p u 最初是为了图形渲染而生，其还不能完全达到通用计算，即g p u 的通用 性还不能成为真正的通用处理器。即使现在g p g p u 的前景一片光明，由于挑战与机遇 永远是并存的，所以目前g p g p u 仍然面临着很多的问题。其中最主要的问题有以下几 点： ( 1 ) 图形处理。g p g p u 在图形处理过程中，要把非图形渲染的问题映射到图形渲 染的处理过程，即要通过图形处理a p i 来实现基于g p u 的通用计算，这个处理过程对 于不熟悉图形渲染的用户无疑是一个障碍问题，如果要求用户学习图形渲染的理论知识 也不是必须的，因为他们要解决的问题本身根本就不涉及图形渲染的相关知识。 ( 2 ) 不具备进行散列操作的能力。g p u 的动态随机存储器能够像内存一样进行读 操作，从显存的任意地址读取数据，也就是说，g p u 能够进行数据的聚集操作；但是 g p u 并不能像c p u 一样，向显存的任意地址写入数据，即g p u 没有数据散列的能力， 这无疑很大程度上降低了g p g p u 的处理问题的范围和灵活性。 ( 3 ) 带宽有限。数据在显存和内存之间传输的带宽，是很多利用g p u 处理的问题 的一个瓶颈，这就降低了g p u 强大运算能力。 2 4g p u 通用计算的发展方向 g p g p u 早在d i r e c t x9 0 时代就已经初现雏形，但只有在d i r e c t x1 0 时代，新的g p u 才真正促进了g p g p u 的成熟和高速发展。在硬件方面，以n v i d 认g e f o r c e8 8 0 0g t x 为例，通过集成多达6 8 1 亿枚晶体管，其具备了万亿次浮点处理能力，峰值带宽达到了 8 6 4 g b p s 。同时，8 8 0 0 采用统一着色器架构，内含1 2 8 个标量3 2 位浮点精度流处理器， 完全支持s h a d e rm o d e l4 o ，在可编程性上获得了很大的提高，因此也为g p g p u 在新时 代的应用带来了更多的可能性。 但实现基于g p u 的通用计算【3 6 】并不仅仅是靠晶体管数量的堆砌竞赛就能实现的。 从软件开发环境来看，g p u 本身是为图形渲染而设计，只能处理图形渲染指令，而科学 计算指令属于通用指令，两者之间存在显著差异，如果要让g p u 来进行科学计算，就 必须对科学计算程序进行改写。这就要求程序员必须熟悉g p u 硬件架构，然后再进行 编程。而且，g p g p u 或基于g p u 的通用计算，一直要求使用诸如o p e n g l 类的图形 人连理工大学硕士学位论文 a p i ，这种方案会在通用平行计算中遇到提取错误的问题。因此，传统的应用软件很难 进行写入、纠错和优化操作。 2 0 0 6 年，微软发布了最新一代d i r e g d ( 1 0 的统一渲染架构。通过一个整合的流着色 流水线阵列来完成目前v e n 既s h a d c r 、p i x ds h a d 盯以及新引入的几何着色器所有的工作。 相对于s h a d 盯的基本模型来说，传统g p u 流水线中p i x ds b a d 盯和v 咖时i a d 付非常相 近，但是，在流水线中，它们有各自单独有一块完全不同、资源难以共享的区域。而 g p u 通用计算往往都只是使用运算能力强大的像素着色器部分来进行操作，而顶点着色 器的资源就完全没有使用，这样就造成巨大的运算能力浪费。 g e o m e t r ys h a d e r si nd x l 0 f r 彻c p u 2 6 5 t g l l t ha d j a c e n c y 图23d i r e c t xl o 中的儿何s h a d e r 示意图 f