（计算机科学与技术专业论文）gpu加速高速粒子碰撞模拟.pdf

国防科学技术大学研究生院硕士学位论文 摘要 分子动力学( m o l e c u l a rd y n a m i c s ，简称m d ) 模拟作为一种重要的计算机模拟方法广泛 应用于生物，化学，材料科学等众多学科中。然而计算性能一直都是限制m d 使用的主要 障碍。近年来，g p u 作为一种新型的计算资源成为研究的热点。与传统c p u 相比，g p u 拥有更高的性能，更低的功耗和更高的性价比。因此，使用g p u 加速分子动力学模拟， 可以节约模拟的时间，提高模拟的规模，从而使分子动力学模拟能更广泛的应用到实际的 工程中去。 本文主要以高速碰撞的粒子模型为研究对象，基于n v i d i ac u d a 编程模型和b r o o k + 语言实现了g p u 加速的分子动力学程序，并针对g p u 的存储结构和多g p u 对算法进行 了优化，主要取得了如下成果： 1 、提出了一种优化的区域分解算法。本文改进了传统的区域分解算法，在通用处理 器和g p u 上分两次对分子动力学模拟中的计算任务进行分解，首次划分保证负载平衡， 第二次划分解决通信开销和数据复用问题。 2 、提出了一种改进的粒子索引方法。通过在通用处理节点上对粒子进行排序，使相 邻粒子的存储地址尽量靠近。当加速节点上的线程从全局内存上读取粒子信息时，能够呈 现出数据局部性的特点，可以减少了线程从全局内存中读取数据的次数，从而节省时间。 3 、针对g p u 的存储结构对程序进行优化。针对片上共享内存分体设计特点，实现了 单精度算法下线程间无冲突的共享内存访问，减少了流处理器的闲置时间。 4 、使用多g p u 对程序进行加速。采用常用的消息传递接c i ( m p i ) 协议实现通用处理器 之间的并行划分，从而实现了各节点间g p u 的并行计算，满足了更快速的分子动力学模 拟的要求。 本文对g p u 加速的分子动力学模拟正确性和性能进行了测试。结果表明，g p u 对m d 算法的加速有明显效果。当粒子规模为4 3 2 万时，经a m dh d 4 8 7 0 加速后的m d 程序的 性能提高了4 8 倍，而经t e s l ac 1 0 6 0 加速后，m d 程序性能提高6 5 倍。在使用多g p u 对 程序进行加速后，m d 程序的性能提高了1 1 2 倍。同时，经g p u 加速的m d 程序保证了 结果的正确性。 主题词：分子动力学模拟，g p u 计算，c u d a 编程模型，b r o o k + 语言，区域分解算 法，粒子索引方法 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t m o l e c u l a rd y n a m i c s ( m o l e c u l a rd y n a m i c s ，r e f e r r e dt oa sm d ) s i m u l a t i o nh a sb e e nw i d e l y u s e di nb i o l o g y ，c h e m i s t r y ，m a t e r i a l ss c i e n c ea n dm a n yo t h e rd i s c i p l i n e sa sa ni m p o r t a n tm e t h o d o fc o m p u t e rs i m u l a t i o n c o m p u t a t i o n a lp e r f o r m a n c e ，h o w e v e r ，h a sa l w a y sb e e nam a j o r o b s t a c l et ot h eu s eo fr e s t r i c t i o n so nm d w h e nc o m p a r e d 、析1t h et r a d i t i o n a lc p u g p uc a n a c h i e v eh i g h e rp e r f o r m a n c e ，l o w e rp o w e rc o n s u m p t i o na n dh i g h e rc o s t e f f e c t i v e t h e r e f o r e ，t h e u s eo fg p ut oa c c e l e r a t em o l e c u l a rd y n a m i c ss i m u l a t i o nc a ns a v em u c hs i m u l a t i o nt i m ea n d a c h i e v el a g e rs i m u l a t i o ns c a l e ，s ot h a tm o l e c u l a rd y n a m i c ss i m u l a t i o nc a nb em o r ew i d e l y a p p l i e dt ot h ea c t u a lp r o je c t s i nt h i sp a p e r ，w eh a v ea c h i e v e dg p ua c c e l e r a t e dm o l e c u l a rd y n a m i c sp r o g r a mb a s e do n c u d ap r o g r a m m i n gm o d e la n db r o o kp l u sl a n g u a g e o u rm a i nc o n c e mi st h eh i g h s p e e d c o l l i s i o nm o d e l o u rm a i nc o n t r i b u t i o n sa r ea sf o l l o w s ： 1 p r o p o s e da no p t i m i z e dd o m a i nd e c o m p o s i t i o nm e t h o d t h i sm e t h o di m p r o v e st h e t r a d i t i o n a ld o m a i nd e c o m p o s i t i o na l g o r i t h m w ec o m p l e t et w oc o m p u t i n gt a s k sd e c o m p o s i t i o n t w i c e ，o n c eo ng e n e r a l - p u r p o s ep r o c e s s o ra n dt h eo t h e ro ng p u t h ef i r s td e c o m p o s i t i o ni st o e n s u r el o a db a l a n c i n g ，a n dt h es e c o n do n ei st os o l v et h ec o m m u n i c a t i o no v e r h e a da n dd a t a r e u s ei s s u e s 2 p r o p o s e da ni m p r o v e d m e t h o do f p a r t i c l e i n d e x w eo r d e rt h ep a r t i c l e so n g e n e r a l - p u r p o s ep r o c e s s i n gn o d e s ，s ot h a tt h es t o r a g ea d d r e s so f t h ea d j a c e n tp a r t i c l e sc a nb ea s c l o s ea sp o s s i b l e w h e nt h et h r e a d so fs p e e dn o d er e a dp a r t i c l e sf r o mt h eg l o b a lm e m o r y ，t h e p a r t i c l ei n f o r m a t i o nc a nb es h o w nt h ec h a r a c t e r i s t i c so fd a t al o c a l i t y t h i sc a nr e d u c et h en u m b e r o ft i m e st h a tt h r e a d sr e a dd a t af r o mt h eg l o b a lm e m o r y 3 o p t i m i z i n gu s i n go fs t o r a g es t r u c t u r e so ng p u w eu s eo n - c h i ps h a r e dm e m o r yt o a c h i e v eac o n f l i c t f r e es h a r e dm e m o r ya c c e s so fs i n g l e p r e c i s i o n , t h u sr e d u c i n gt h ep r o c e s s o r s i d l et i m e 4 u s i n gm u l t i - g p ua c c e l e r a t i o no ft h ea l g o r i t h m w eu s ec o m m o n l yu s e dm e s s a g ep a s s i n g i n t e r f a c e ( m p i ) p r o t o c o lt oa c h i e v ep a r a l l e lb e t w e e nt h ed i v i s i o n so fg e n e r a l - p u r p o s ep r o c e s s o r s ， t h u sa c h i e v et h em u l t i g p up a r a l l e lc o m p u t i n g 1 1 1 i sc a nm e e tt h er e q u i r e m e n t so fe v e nl a r g e r a n df a s t e rm o l e c u l a rd y n a m i c ss i m u l a t i o n i nt h i sp a p e r ，w et e s tt h ea c c u r a c ya n dp e r f o r m a n c eo fo u rg p ua c c e l e r a t e dm o l e c u l a r d y n a m i c ss i m u l a t i o n r e s u l t ss h o wt h a tg p ua c c e l e r a t i o no ft h em da l g o r i t h mh a so b t a i n o b v i o u se f f e c t w 1 l i l et h es c a l eo fp a r t i c l e si s4 3 2t h o u s a n d s ，t h ea m dh d 4 8 7 0a c c e l e r a t e sm d p r o g r a m sp e r f o r m a n c eb y 4 8t i m e sa n dt h et e s l ac 1 0 6 0a c c e l e r a t e sm dp r o g r a m s p e r f o r m a n c eb y6 5t i m e s m u t i l g p u sa c c e l e r a t et h ep r o g r a m sp e r f o r m a n c eb y1 1 2t i m e s a l l t h e s ep r o g r a m se n s u r et h ev a l i d i t y k e y w o r d s ：m o l e c u l a rd y n a m i c s ，g p uc o m p u t i n g ，c u d ap r o g r a m m i n gm o d e l ， 第i i 页 国防科学技术大学研究生院硕士学位论文 b r o o k + l a n g u a g e ，s p a t i a ld e c o m p o s i t i o n ，p a r t i c l ei n d e x i n g 第i i i 页 国防科学技术大学研究生院硕士学位论文 表目录 表1 1使用c u d a 成功加速的应用列表3 表2 1c u d ag p u 上存储单元特征11 表3 1m d 中各任务执行时间统计表2 5 第1 i i 页 国防科学技术大学研究生院硕士学位论文 图1 1 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图2 7 图2 8 图2 9 图2 1 0 图2 1 1 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图3 8 图3 9 图3 1 0 图3 11 图3 1 2 图3 1 3 图3 1 4 图3 1 5 图3 1 6 图4 1 图4 2 图4 3 图4 5 图目录 g p u 和c p u 存储单元和处理单元的对比图2 指令分解示意图9 t e s l a 的系统结构图1 0 c u d ag p u 存储结构图1 0 复杂指令代码示意图1 2 蝴dg p u 的系统结构图1 3 c u d a 线程模型示意图1 5 j 蝴dg p u 的执行模型17 b r o o k + 抽象编程模型1 8 周期性边界条件图2 1 周期性边界条件示意图2 2 m d 算法流程图2 2 m d 算法中任务系统级分割2 6 通用处理节点上分解方法2 7 数据表传输示意图2 8 采用g p u 加速的m d 算法示意图2 8 线程间计算矩阵的分解示意图3 0 8 个线程间信息交换模型31 线程分块示意图3 1 粒子分解法中信息复用示意图3 2 作用力矩阵分解方法3 2 空间区域子空间分解方法3 3 线程间获取邻接块粒子信息方法3 4 二次划分示意图3 5 区域分解方法数据复用示意图3 6 使用c u d a 实现的算法示意图3 7 使用b r o o k + 实现的算法示意图3 7 通过冗余计算消除分支算法示意图3 8 v e r l e t ( 令g 近) 列表方法示意图3 9 单元链表方法示意图4 0 改进列表算法示意图4 l 并行化存取操作和内核计算示意图4 3 第l v 页 国防科学技术大学研究生院硕士学位论文 图4 6 最小化数据集优化的内核算法示意图4 4 图4 7 常见的g p u 集群组建方式4 5 图4 8 阻塞与非阻塞通信示意图4 6 图5 1不同瞬间时刻粒子分布图4 9 图5 2 使用h d 4 8 7 0 和c 1 0 6 0 加速相对原程序的加速比4 9 图5 3使用h d 4 8 7 0 与c10 6 0 计算性能对比图5 0 图5 4 使用c 1 0 7 0 加速程序相较原程序的对比5 0 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目：鱼型拉鎏高速撞壬焦撞搓赵 学位论文作者签名：呈韭 日期：2 。d 争。1 月岁。日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：鱼趔担速直逮趋壬焦撞搓越 学位论文作者签名：兰蜢 日期：a q 。呵年i z 月弓。日 作者舯撕张盖蛆 魄一年彬了勺日 国防科学技术大学研究生院硕士学位论文 第一章绪论弟一早 三百t 匕 近年来使用计算机图形处理单元( g r a p h i c sp r o c e s s i n gu n i t ，简称g p u ) 加速科学计算 的研究日益增多，这得益于g p u 高性能和高性价比。本章通过选择分子动力学模拟这一 科学应用为切入点，来研究g p u 在科学计算中的使用。 第一节介绍了使用g p u 加速科学运算成为研究热点的课题背景；第二节重点研究了 国内外研究者在g p u 通用计算领域和应用g p u 加速分子动力学模拟的相关工作；第三节 概括了使用g p u 加速分子动力学模拟的研究内容和创新；第四节给出全文的组织结构。 1 1 课题背景 伴随着p c 级微机的崛起和普及，多年以来g p u 以大大超过摩尔定律的速度高速发展。 如图1 1 所示。到2 0 0 8 年1 1 月，n v d i a 公司出品的t e s l as 1 0 7 01 u 系统已经拥有9 6 0 个 内核，其单精度浮点计算性能可以达到3 7 3 到4 1 4 t f l o p s 7 1 。这样的成绩在以往只能在 一些超级计算机上取得。与此同时，g p u 还具有性价比和计算密度高、低能耗等优势【4 列。 人们对g p u 在通用计算领域的应用前景寄予了前所未有的期望和热情。 传统的g p u 编程对非图形应用支持有限，只能通过图形接口编程，这需要编程人员 拥有专业的图形学背景。此外，传统的g p u 也没有提供双精度浮点支持。因此，g p u 在 科学计算中应用常常受到限制。近年来，基于g p u 的通用计算技术( g p g p u ) 已经取得重大 的突破，g p u 的厂商不断对g p u 的编程模型提供改进，使得g p u 的易编程性不断提高， 如n v i d i a 公司推出的c u d a ( c o m p u t eu n i f i e dd e v i c ea r c h i t e c t u r e ) 编程模型1 2 4 j 和a m d 公 司b r o o k + 语言【2 7 】。另一方面，n v d i a 公司和a m d 公司最新的g p u 都引入了对双精度的 支持，这使得那些精度要求高的应用也可以通过g p u 进行加速。如何利用g p u 强大的计 算能力已经成为一个重要的现实课题。 本文中采用分子动力学这一类科学计算为切入点，来研究使用g p u 加速通用科学计 算，主要出于两方面的考虑。 首先，分子动力学( m o l e c u l a rd y n a m i c s ，简称m d ) 方法是一类重要的计算机模拟方 法【2 5 1 。自从1 9 5 6 年由a l d e r 首次使用以来，现今已广泛使用在生物分子学，流体力学，材 料科学，医药等众多的行业中。m d 模拟能详细跟踪每个分子的运动，并通过分析速度、温 度等统计性质阐释理论中的难点、发现新的机理，日益受到重视。因此，加速m d 应用具有 工程的现实意义。 其次，从g p u 的结构来看，m d 模拟非常适合在g p u 上进行加速。如图1 1 所示， g p u 拥有大量能够并行运算且共享多级显存的处理单元【2 4 1 ，而处理单元独占的显存的容量 往往很小，这决定了g p u 擅长处理类似图形操作的计算密集型应用。m d 模拟正是典型的 第l 页 国防科学技术大学研究生院硕士学位论文 计算密集型应用。m d 中柱子的信息往往非常简单且容易向量化。m d 计算的密集体现在 两个方面。首先，m d 模拟的空间尺度小而粒子数量大，例如，边长为o3 5 u r n 的金属固体 模型拥有1 0 9 个原子 2 1 l ；其次，m d 模拟需要精确跟踪粒子的运动以保证数值模拟的稳定 性，其时间步长都很小，典型的时间步长为飞秒级，纳秒级别的现实模拟也需要上千时间 步。因此，m d 正是适合g p u 加速的典型应用。 1 一一 士 c p u g p u 图11g p u 和c p u 存储单元和处理单元的对比圈 目前，国内外研究者对使用g p u 加速通用科学计算的研究如火如荼。下一节将介绍国 内外学者在g p u 通用计算领域和应用g p u 加速分子动力学模拟的相关工作。 1 2 研究现状 由于g p u 并行流处理和可编程性的出现，越来越多的研究者开始用其做一些自然科 学相关的计算。这些计算涉及的范围很广，从图形输出流水线以外的非绘制处理，到几何 计算，碰撞检测 ”i ，运动规划【3 8 】，代数运算，优化计算i 枷，偏微分方程p d e s ( p a r t i a l d i f f e r e n t i a le q u a t i o n s ) 数值求解等，不一而足。本文关注的是如何利用g p u 来进行m d 模拟 的加速，因此本节中首先介绍g p u 在通用科学计算中的难点和相关研究，这些研究对g p u 加速m d 模拟有借鉴意义，主要围绕现阶段m d 模拟中使用g p u 的实例展开介绍。 121g p u 通用计算研究现状 目前，有大量成功运用g p u 进行加速的科学计算的实例，其中不乏一些大型商业应 用。g p u 厂商n v i d i a 在其旧站上公布了大量基于n v i d i ac u d a 的成功应用“t 如表 11 所示。可以看出，许多应用取得了相较于c p u 数十倍甚至数百倍的加速比。 澳门大学的吴恩华等人在文1 4 2 中总结了图形处理器到2 0 0 4 年为止在一些典型通用计 算中的应用。即使是在g p u 结构和编程模型日新月异的今天，这些应用仍然是非常典型 的g p u 加速应用。这些应用包括代数计算及流体模拟，数据库操作，频谱变换和滤波等。 文中使用像素程序结合纹理操作实现了一个城市气流流动的计算。通过结合模板缓冲器对 = 维场景进行剪切，形成一系列实心剖切截面以构成整个流动边界。这样，通过修正因子 来处理任意复杂的边界条件，整个计算过程与几何场景的复杂度无关。整个计算由4 步构 第2 页 国防科学技术大学研究生院硕士学位论文 成，先不考虑压强的影响求出一个中间速度分布，然后求解压强泊松方程，以修正速度场 满足质量连续性条件。在二维问题的求解上c p u 算法比对应的c p u 算法要高出十几倍。 文中还提出了一些g p u 应用在通用计算领域存在的问题，主要是硬件和软件两个方面。 g p u 在硬件结构上限制通用计算的最大问题是缺少大容量的局部存储。这是因为，g p u 的计算能力很大程度上来源于它将主要的集成电路功能贡献于流式处理计算。这与c p u 有 很大的不同，如i n t e lx e o n 微处理器，虽然具有相当于a t ir 3 0 0 ( 1 1 亿个晶体管) 的集成度 ( 1 0 8 亿) ，但是其中6 0 却用于快速存储单元。因此，如果g p u 局部存储大量扩充，这无 异于向一个独立的c p u 方向发展，这与g p u 本身用于图形绘制的初衷是相违背的，同时 成本也将相应的增加。这些工作在今天看来仍然具有很强的指导意义。 表1 1 使用c u d a 成功加速的应用列表 应用领域参考网站 加速比 地震资料处理 h t t p ：w w w h e a d w a v e c o m 6 6 1 0 0 软件无线电 h t t p ：w w w a c c e l e w a r e t o m 4 5 神经细胞模拟 h t t p ：w w w e v o l v e d m a c h i n e s c o m 1 0 0 m r i 处理 h t t p ：b i c t e s t b e c k m a n u i u c e d u 2 4 5 4 1 5 大气云层模拟 h t t p ：w w w c s c l e m s o n e d 州e s t e e l c l o u d s h t m l 5 0 n v i d i a 公司的m i c h a e lg a r l a n d ，s c o t tl eg r a n d 等，衣阿华州州立大学和美国能源部 a m e sl a b o r a t o r y 实验室的o s h u aa n d e r s o n 等在文【3 】中总结最新编程模型下的并行编程体 验。文中提出，在以往时钟频率的提高一直是处理单元性能提高的主要动力。而现在，并 行性的提高已经成为性能提升的主要手段，并且这一趋势还将继续下去。文中主要关注了 c u d a 编程模型下的多种应用。这些应用都具有较少的控制逻辑和很高的可并行性，并且 其使用的数据中具有易并行性。这些应用包括分子动力学模拟，线性代数，医用图形学， 流体动力学，地震影像模拟等。 伊利诺伊大学厄巴纳香槟分校的s h a n er y o o 等在文【6 】中总结了一些使用c u d a 进行 多线程g p u 编程的一些优化原则和性能测试方法。文中研究了g e f o r c e8 8 0 0g t x 显示卡 的处理单元的组织，特点和通用优化准则。他们提出，使用这c u d a 编程模型的要点在于 同时使用大量线程来最大化的利用g p u 众多的计算核心和隐藏全局内存的延迟。g e f o r c e 8 8 0 0g t x 拥有1 2 8 个执行单元，如果全部利用起来，需要数以千计的线程。此外，由于 对全局内存的存取存在较大的延迟，线程会因为无法及时获取数据而处于空闲等待的阶 段。c p u 解决这一问题的方法在于增加大量的缓存，而g p u 则与之不同，它使用了超量 的线程同时执行来隐藏这一延迟。因此，保持一个较高的计算存取比率是一个重要的原则。 g e f o r c e8 8 0 0g t x 还拥有寄存器和片上内存等快速存储器，需要合理利用这些存储器来减 少对带宽的需求并尽可能多的执行数据。由于c u d a 编程模型本质上是采用了s i m d ( 单指 令流多数据流) 这样一种形式，因此需要将大量线程分组来避免违反s i m d 原则带来的性能 下降和内存冲突。 第3 页 国防科学技术大学研究生院硕士学位论文 综上所述，基于g p u 的通用计算领域的相关研究很多，新的理论和方法更新迭代也 很快。这些研究对克服g p u 通用计算的难点有独到的地方，对g p u 加速m d 和本文的工 作有很强的借鉴意义。例如吴恩华等人在5 年前指出了g p u 在局部存储方面的限制，现 在仍然是需要解决问题之一。s h a n er y o o 等人对c u d a 编程的优化原则对本文工作也有重 要的借鉴意义。 1 2 2g p u 加速分子动力学模拟研究现状 m d 模拟建立在粒子运动的物理系统之上，每个粒子拥有质量，所处的位置用几何点 表示，分子运动满足牛顿力学方程，作用于每个粒子上的力是由粒子间相互作用势描述的。 为了达到更快更准确的模拟的目的，分子动力学相关的研究人员提出了很多加速计算的理 论。 s t e v ep l i m p t o n 等在文 4 1 1 中提出了三种并行算法：粒子分解算法，力分解算法以及区域 分解算法。这些并行算法的区别在于如何将力的计算分解到不同的计算核心上。文中发现， 这三种分解方法在计算力的部分开销都为o ( n p ) ，所不同的只是负载均衡和通信开销方面 的差别。粒子分解算法主要是将目标系统中的粒子编号并平均分配到各计算节点，每个计 算节点只负责当前进程分配到的粒子的计算，这种分解方法的主要优点是每个计算节点负 责的粒子固定，有利于减少同步开销并且能保证负载均衡，但是由于每个时间步结束后各 计算结点都需要更新所有粒子的位置和速度等信息，其通信开销为o ；力分解算法的主 要思想是将粒子受力计算的矩阵分解为子矩阵进行分割，其通信开销为o ( n 尸1 ，编程 复杂，不易做负载均衡；区域分解算法的主要思想是将目标系统划分为多个子系统，每个 计算节点负责一定数目的子系统内粒子的计算；由于区域分解算法是按物理结构来进行划 分的，每个计算节点只需要同邻接的子系统进行信息交换，因此其通信开销最小为o ( n p ) ， 但是由于系统内部粒子分布非均匀，因此需要设计良好的算法来保证同步和计算时的负载 均衡。 r o n a l ds e r o f a n o 等在文【5 】中尝试使用协处理器对m d 进行加速。文中提出了一种软 硬件结合的方法，硬件主要采用了f p g a 阵列。首先实现了一个通用处理器上的m d 模拟 程序，这个程序的特点是任务模块明确，便于分解。然后文中尝试对这些任务进行分析， 找出那些适合在协处理器上进行处理的任务。这些做的好处在于不用一次性的将整个程序 移植到协处理器上，程序取得了2 倍的加速比。 复旦大学的宋国梁等在文【4 l 】中将在计算生物分子中广泛应用的c h a r m m 力场应用于 w i n d o w sc o m p u t e rc l u s t e rs e r v e r ( w c c s ) 环境下，并实现了该力场及分子动力学模拟程序的 g p u 并行计算。对一些多肽链的动力学模拟结果显示，与c p u 计算相比，g p u 计算在计 算速度上有巨大的提升。与6 4 位a m d 的2 0 g h z 的c p u 相比，在n v i d i ag e f o r c e8 8 0 0 g t 显卡上的动力学模拟速度提高了至少1 0 倍，而且这个效率比会随着模拟体系及每块尺 第4 页 国防科学技术大学研究生院硕士学位论文 寸的增大而增大。模拟体系的增大使得g p u 并行单元的计算空载相对减少，块尺寸的增 大使缓存区尺寸相对减少，单块计算效率得以提高。将力场的计算和梯度的更新( 将力场计 算得到的力从内坐标转换为直角坐标) 两个任务分别交给g p u 和c p u 完成，由于在程序上 这两个部分是串行执行的，如果直接分配则会导致g p u 和c p u 相互等待解决方案是将 g p u 计算任务分成n 份，每完成其中一份即让c p u 开始异步执行梯度更新，这样双方仅 需要等待原来1 n 的时间。在测试样本中，该效率比最高可达到2 8 倍以上。利用g p u 计 算还对一条含有3 9 7 个原子的多肽链进行了分子动力学模拟，给出了氢键分布随时间的变 化结果。 u i u c 大学的c h r i s t o p h e r i 】等在文中提出了采用g p u 加速静电势能模型的映射，其中 包含了正则晶格中粒子间潜在的势能。对此静电势能的计算能够完全的应用到粒子置换的 过程中去，因此该算法可以广泛的应用到分子动力学模拟【l8 1 ，分子模型可视化和其他类分 子应用中去。算法还能有效的使用到求解n 体间的力和作用势能中去。文中使用n v i d i a g 8 0 核心的t e s l ac 8 7 0 显示卡和c u d a 编程模型加速了m d 应用中直接作用势能和截断 作用势能的模拟。对这两种势能的计算在很多分子动力学应用中都是最耗费计算资源的任 务。通过对比发现，直接使用粒子分解算法会带来较低的性能，因此，文中提出了一种基 于区域分解的算法，这种算法使得粒子数据能够有效的映射到c 8 7 0 的存储系统上去，能 够有效的提高数据的传输效率。最后，实现的程序很好的利用了c u d as p m d ( 单程序流多 数据流) 的特点，相比仅采用c p u 的优化代码，取得了1 2 到2 0 倍的加速“1 7 】。 中科院的陈飞国等在文【4 3 】中利用c u d a 和n v i d i at e s l ac 8 7 0 进行了分子动力学 ( m d ) 模拟的加速。在一片t e s l ac 8 7 0 上，取得了相对于i n t e lx e o n5 4 3 0 单核2 0 6 0 倍的 加速比，峰值性能达到了1 5 0g f l o p s 。通过方腔流及颗粒气泡接触等实例初步展示了此方 式从微观上模拟介观行为的能力。 通过对上述内容的了解，我们发现近年来在m d 中模拟中使用g p u 进行加速非常流 行，其中一些研究对本文有很强的指导和借鉴意义。s t e v ep l i m p t o n 针对传统c p u 集群的 并行分解算法在g p u 上仍然有很强的实用价值。r o n a l ds c r o f a n o 等人虽然并没有实现很 高的性能，但是研究中对m d 模拟中的任务进行分割的思想对本文有很强的借鉴意义。 c h r i s t o p h e r 等针对某一具体任务进行细化研究和针对存储结构的优化技术有很强的实用价 值，同时由于这一技术运用在著名的分子动力学模拟软件n a m d v m d 中，其影响很大。 陈飞国等人的研究对本文也有很大的启发。 但是迄今为止，针对高速粒子碰撞模型这类变化激烈的m d 系统下g p u 加速的研究 仍然很少。这主要是因为这类模型系统一般粒子数量大，位置变化剧烈，在g p u 上模拟 的难度较大。此外，为了达到可以实用的目的，还需要采用双精度的算法。目前使用g p u 对m d 进行加速的研究正在趋于系统化，并且越来越成熟。研究群体也越来越强大。因此 本文旨在研究前人成果的基础上，提出一种优化的使用g p u 加速的m d 算法，以达到更 第5 页 国防科学技术大学研究生院硕士学位论文 快模拟的目的。 1 3 本文研究内容和创新 本文主要以高速碰撞的分子模型为研究对象，探讨在目标系统分子激烈运动的条件下 如何使用g p u 对其进行有效加速。目前，m d 在使用g p u 进行加速主要存在两大问题： 一是经典m d 算法中各计算任务相互粘合难于分离，有的研究者将整个计算过程完全 在g p u 上实现，c p u 只做一些基本控制，这样不仅浪费了c p u 的运算能力，而且有些计 算过程不适合g p u 的s p m d 的原则，会带来性能上的损失。 二是由于g p u 与传统c p u 在结构和编程模型上存在差异，经典m d 算法并行化的方 法无法应用到g p u 上来。 为了解决以上问题并使程序达到更好的性能，本文做了以下工作： 1 、提出了一种优化的区域分解算法。本文改进了传统的区域分解算法，在通用处理 器和g p u 上分两次对分子动力学模拟中的计算任务进行分解，在c p u 上每个进程对区域 的计算任务进行粗略的估量并尽量平均的分配计算区域，在g p u 上每个线程被赋予一个 区域的粒子的计算任务。这样首次划分保证负载平衡，第二次划分解决通信开销和数据复 用问题。 2 、提出了一种改进的粒子索引方法。通过在通用处理节点上对粒子进行排序，使相 邻粒子的存储地址尽量靠近。当加速节点上的线程从全局内存上读取粒子信息时，能够呈 现出数据局部性的特点，可以减少了线程从全局内存中读取数据的次数，从而节省时间。 3 、针对g p u 的存储结构对程序进行优化。针对片上共享内存的特点，实现了无冲突 的单精度共享内存访问，减少了流处理器的闲置时间。 4 、使用多g p u 对程序进行加速。采用常用的消息传递接口( m p i ) 协议实现通用处理器 之间的并行划分，从而实现了各节点间g p u 的并行计算，满足了更快速的分子动力学模 拟的要求。 实验证明，g p u 对m d 算法的加速有明显效果。经a m dh d 4 8 7 0 加速后，m d 程序 的性能提高了4 8 倍，而经t e s l ac 1 0 6 0 加速后，m d 程序性能提高6 5 倍。在使用多g p u 对程序进行加速后，m d 程序的性能提高了1 1 2 倍。同时，经g p u 加速的m d 程序保证 了结果的正确性。 1 4 论文结构 本文作为工作的一个总结，全文共分为六章。 第一章，首先说明课题的研究背景及意义，介绍国内外的相关研究现状，阐释m d 算 法移植到g p u 上的主要问题，然后概括本文的主要工作内容和创新，最后给出文章的组 第6 页 国防科学技术大学研究生院硕士学位论文 织结构。 第二章，研究g p u 现有的软硬件环境，分析了经典m d 算法的流程。 第三章，研究使用g p u 加速m d 算法的关键技术。主要探讨m d 中任务分离和计算 任务二次划分的技术，并对作用力在g p u 上的分解的方法进行了讨论。最后针对具体g p u 和编程模型，实现了g p u 对m d 算法的加速。 第四章，在第三章实现基础之上，研究改进的粒子索引技术，设计一种基于排序的粒 子索引方法，有效的提高线程访问粒子信息的效率；研究g p u 的存储结构，使用共享内 存对程序进行优化；使用多g p u 对程序进行优化。 第五章，使用j a s m i n 框架对实验结果的正确性进行分析，使用h d 4 8 7 0 和c 1 0 6 0 对算 法的性能进行测试。 第六章，概括全文，总结课题所做工作和研究成果，并对下一步研究进行展望。 第7 页 国防科学技术大学研究生院硕士学位论文 第二章背景知识 本章第一节介绍了通用g p u 编程需要解决的一些问题和目前流行的编程模型，第二 节分析了经典m d 算法的一些特点，并提出了一种通用的基于g p u c p u 协作环境的m d 算法。 2 1g p u 系统结构特点和编程模型 g p u 用于通用科学计算的主要有两大难点，一个是存储问题，另一个是软件编程模型 的问题【4 2 1 。g p u 可编程功能一直以来都在不断发展，从顶点级别可编程到像素级别可编程， 特别是近年来一些通用编程模型的出现，都大大降低了通用g p u 编程的难度。尽管这些 编程模型都在一定程度上屏蔽了硬件实现的细节，但是了解g p u 系统结构对通用g p u 编 程仍然很有帮助。因此，本节首先分析了g p u 的系统结构，然后对编程模型进行了介绍。 2 1 1g p u 系统结构特点 传统g p u 性能发展主要是靠提升频率和增加每个周期可以执行的指令数( i p c ) ，因为 从根本上说，提高g p u 性能的主要途径就是进行并行的执行数据【2 0 】。g p u 任何其他资源 的变化，比如更多的流水管线，更多的运行线程，更大的附加缓存，都是为增加i p c 服务 的。从n v i d i a 的g t 2 0 0 到a m d 的r v 6 7 0 ，无不如是。因此，为了在工艺制程允许的范 围内提高i p c ，g p u 的a l u 都引入了单指令流多数据流( s i m d ) 的概念。但是，这样的设 计在通用计算的应用中会碰到不少效率问题。本节将分别介绍n v i d i a 公司和a m d 公司 是如何采用最新一代g p u 的系统结构来解决这些效率问题。 2 1 1 1n v i d i ag p u 硬件结构 g p u 的编译器即使经过大量优化，编译出来的指令也不能够统一长度，这些指令的操 作数有1 d 、2 d 、3 d 和4 d 。例如，像求指运算这样的复杂算术指令需要多个周期才能完 成。对于通常执行能力为一个向量的s i m da l u 来说，如果执行操作数为1 d 或2 d 这样 的指令，由于s i m d 天生的单发射端口限制，每个指令周期内处理的数据量将会很少，从 而导致s i m d 指令的并行性问题。 为了解决上诉问题，n v i d i a 公司推出了c u d a 编程模型，它包含了完整的硬件规格 说明和语言模型说明。例如，c u d a 模型中的g 8 0 内核拥有1 2 8 个最基本的1