（电子科学与技术专业论文）基于gpu微体系结构的高性能计算研究.pdf

国防科技大学研究生院硕士学位论文 a bs t r a c t w i t ht h ed e v e l o p m e n to fp r o c e s s o r sa r c h i t e c t u r e m u l t i - c o r ea n dm a n y c o r e p r o c e s s o r sh a v eb e c o m et h em a i ns t r e a mo fc o m p u t i n gs y s t e m s a sg p u ( g r a p h i c s p r o c e s s i n gu n i t ) g e n e r a lp u r p o s ec o m p u t i n gb a s e do nc u d ac a nb ea b l et op r o v i d e s t r o n gc o m p u t i n ga b i l i t ya n db a n d w i d t h , i t h a sb e c o m et h em o s tr e p r e s e n t a t i v e a r c h i t e c t u r eo fm u l t i c o r ea n dm a n y c o r ea r c h i t e c t u r e g p up r o v i d e sar e f c r e n c et ot h e d i r e c t i o no ft h ef u t u r ed e v e l o p m e n to fa r c h i t e c t u r e t m st h e s i sh a sd o i n gai n d e p t hs t u d yo fn v i d i a g 8 0a r c h i t e c t u r e a n di ni t s r e l e a s eo ft h ec u d ap r o g r a m m i n gm o d e l a c c o r d i n gt ot h ec h a r a c t e r i s t i co fg p u m i c r o a r c h i t e c t u r e ，t h i st h e s i si sd e s i g n e da n do p t i m i z e dt oa c h i e v eav a r i e t yo fs o r t i n g a l g o r i t h m si nt h eg p uo nt h em a p ，g e tag o o da c c e l e r a t i o np e r f o r m a n c e ，i n c l u d i n g ：a n a r r a yo fr e v e r s e ，o d d - e v e ns o r t i n g ，b i t o n i cs o r t i n g ，s p e e d - u pr a t i o a r ea sf o l l o w s ： 4 1 ，17 ，2 5 ，a n dp a r t i a l l ya c h i e v e de n u m e r a t i o ns o r t i n g m e a n w h i l e ，t h r o u g hr e s e a r c ho f t h en u m e r i c a lc a c u l a t i o no ft h em a t r i x m u l t i p l ya n di m p l e m e n t a t i o n b a s e do nt h e t r a d i t i o n a lg p um a t r i x m u l t i p l ya l g o r i t h m ，t a k et h eu s eo ft e x t u r ec a c h e ，i n c r e a s e d c a c u l a t i o n f e t c hr a t i oa n dp r e f c t c ht oa c c e l e r a t et h ep e r f o r a m n c e ，i n c r e a s e db ya b o u t 10 6 0 a n d8 7 t h e n w ea l s op u tf o r w a r dt h ec p u g p uh e t e r o g e n e o u ss y s t e m s o nt h et a s k p a r t i t i o n i n gm o d e l e x p e r i m e n t a lr e s u l t ss h o wt h a t ，b a s e d o nt a s k p a r t i t i o n i n go fm a t r i x - m u l t i p l yc a ng e t10 p e r f o r m a n c ei n c r e a s e a tl a s t ，t h i st h e s i s m a k e su s eo fs i m u l a t o rg p g p u s i md e t a i l e da n a l y s i so ft h eb e h a v i o ro ft h ep r o g r a m ， g i v e ss o m eu s e f u lr e c o m m e n d a t i o n t oe l e v a t i o no fa r c h i t e c t u r e t h i ss u b j e c ti sp a r to ft h en a t i o n a l8 6 3p r o j e c t ”r e s e a r c ho nk e yt e c h n o l o g i e so f g e n e r a l p u r p o s e s t r e a mp r o c e s s o ra r c h i t e c t u r e ”r e s e a r c ho n r e c o n f i g u r a b l e h e t e r o g e n e o u ss t r e a m i n gp r o c e s s o ra r c h i t e c t u r et e c h n o l o g i e s ”a n dn a t i o n a ln a t u r a l s c i e n c ef o u n dp r o j e c t ”r e s e a r c ho nk e yt e c h n o l o g i e so fm u l t i s t r e a ma r c h i t e c t u r ef o r s c i e n c ec o m p u t i n g h n l er e s u l t so ft h er e s e a r c ha n dd e s i g nw i l lb ed i r e c t l ya p p l i e dt o t h o s ep r o j e c t s k e yw o r d s ：g p u ，s o r t i n ga l g o r i t h m ，c p u g p uh e t e r o g e n e o u ss y s t e m s ，c u d a ， g p g u s i m 第i i 页 国防科技大学研究生院硕士学位论文 表目录 表1 1 矩阵计算问题c p u 与g p u 性能比较5 表1 2n v i d i a 的c u d a 开发平台目前的成功应用5 表2 1主存与设备存储器数据带宽测试6 表3 1 倒序算法映射性能加速比1 8 表3 2 奇偶排序算法在c p u 与g p u 上执行效率比较2 1 表3 3 枚举排序在g p u 上实现的性能2 2 表3 4 双调排序在g p u 上性能实现2 3 表3 5c u d av i s u a lp r o f i l e r 运行双调排序得到的数据2 9 表4 1矩阵向量算法分别在c p u 与g p u 上运算时间及加速比3 2 表4 2 随矩阵维度变化对性能的影响3 4 表4 3 预取技术在块大小变化时时的性能变化3 9 表4 4c u d av i s u a lp r o f i l e r 运行多种矩阵乘算法各种参数指标4 0 表4 4 矩阵乘基于任务划分机制性能变化表4 3 第1 i i 页 国防科技大学研究生院硕士学位论文 图 图 图 图 图2 3 图2 5 图2 6 图2 7 图2 8 图3 1 图3 2 图3 4 图3 5 图3 6 图3 7 图3 8 图3 9 图3 1 0 图3 1 1 图3 1 2 图4 1 图4 2 图4 3 图4 5 图4 6 图4 7 图4 8 图4 9 图4 1 0 图4 1 1 图4 1 2 图5 1 图5 2 图目录 c p u 与g p u 峰值性能发展趋势2 c p u 与g p u 存储带宽比较2 c p u 计算模型2 传统的g p u 计算模型3 基于c u d a 的g p u 计算模型3 g 8 0 g t 2 0 0 中s m 微观体系结构。8 f e r m i 底层s m 体系结构1 l c u d a 编程模型1 3 c u d a 存储模型1 4 倒序原理图18 奇偶排序算法实现：2 0 枚举排序在g p u 上实现示意图。2 1 n = 1 6 的双调排序网络2 4 利用双调排序网络构造任意顺序数组递增排序网络2 5 g p u 线程映射结构。2 5 基于g p u 上实现多种排序算法执行时间比较。2 7 排序数组在g p u 上执行获得的加速比2 7 利用数据增补的方法消除体冲突2 8 消除体冲突前后性能比较2 8 c u d av i s u a lp r o f i l e r 运行得到的数据3 0 g p u 并行矩阵向量乘法示意图3 2 矩阵乘算法实现示意图3 3 矩阵乘分别在c p u 与g p u 上性能变化图3 4 计算量增大对性能的影响3 6 计算c 中子矩阵的4 个元素并加入纹理c a c h e 访问方式3 7 矩阵乘改进算法示意图3 8 改进后性能变化图3 8 矩阵维度为4 0 9 6 时b 预取效果3 9 c u d av i s u a lp r o f i l e r 运行2 5 6 * 2 5 6 矩阵维度的矩阵乘性能测试图4 0 任务划分示意图4 2 基于任务划分的矩阵乘数据存储模型4 3 g p g p u s i m 软件设计框架结构图4 4 p d o m 分支处理模式4 6 第1 v 页 国防科技大学研究生院硕士学位论文 图5 3 不同线程执行模式对各种程序性能的影响一4 7 图5 4 通过纹理c a c h e 对矩阵乘性能加速模拟示意图4 8 图5 5矩阵乘采用改进数据存储方式性能模拟示意图4 8 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他入已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意 学位论文题目： 基王鱼瞍邀佳鍪结捡的直性能! 土篡砑壅 学位论文作者签名迫夔 日期： 加1 年f ) 月谚日 学位论文版权使用授权书 本入完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目：基王壁鲤鱼邀丞缱垫数壶性能让篡狃塞 学位论文作者签名：遵墨 作者指导教师签名： 日期： 日期： 冷夕 月 月 n 年 年 q 力 川7 国防科技大学研究生院硕士学位论文 第一章绪论 1 1 课题背景及意义 过去的十几年中，虽然i m e l 、i b m 、a m d 、f u j i t s u 等通用计算的c p u 已经在 很大程度上提高了计算机的执行性能，但与8 0 年代末9 0 年代初的性能增长速度 相比还是相差很远【l 】。随着频率墙、功耗墙、存储墙等问题越来越突出，利用单个 核单线程来提高程序的性能已经非常困难了。近年来，图形处理器( g p u ，g r a p h i c p r o c e s s i n gu n i t ) 由于具有丰富的硬件计算资源和强大的存储带宽，吸引了研究者 们广泛关注。研究表明，通过g p u 来开发程序中的并行性，能够提高计算机在科 学计算领域应用的性能。例如：在大型科学计算中，通常含有大量的数据并行， 现代基于g p u 体系结构的线程编程平台，可以有效的将其映射到传统图形处理器 上，使g p u 成为了一个强大的c p u 协处理器来辅助运算。更进一步，为了覆盖 更为广泛的应用，传统的g p u 逐渐演变成今天的通用计算图形处理单元 ( g e n e r a l p u r p o s ec o m p u t i n go nt h eg p u ，g p g p u ) 。2 0 0 8 年6 年，n v i d 埝公司 推出的g t 2 0 0 结构的g p i 卜屯e f o r c e2 8 0g t x ( $ 4 4 9 6 9 9 ，2 0 0 8 年1 0 月) 含有2 4 0 个核，存储带宽为1 4 1 7 g b s ，单精度浮点的峰值性能达到9 3 6 g f l o p s ( 1 3 g i - i z ( 主 频) 3 ( 每周期每s p 完成3 个单精度浮点) 2 4 0 ( s p 数目) = 9 3 6 g f l o p s ) ，完善了 运行双精度计算的能力并获得了较好的效果，双精度的计算能力已达到了 7 8 g f l o p s ( 1 3 g h z ( 主频) 2 ( 每周期每s m 完成2 个双精度浮点) 3 0 ( s m 数 目) = 7 8 g f l o p s ) 。a m d a t i2 0 0 8 年推出的f i r e s t r e a m9 2 7 0 ( a t i 的f i r e s t r e a r n 系 列型号针对于高性能计算领域的应用) 的单精度计算的峰值达到了1 2 t f l o p s ，双 精度计算能力为2 4 0 g f l o p s 。就峰值性能而言，目前g p u 的峰值已经远超过当前 主流的处理器x 8 6 ( i n t e le 7 2 0 0 ，单精度计算能力为4 0 6 2 0 2 g f l o p s ，双精度计算能 力2 0 2 g f l o p s ) ，同时也超过了c e l l 高性能处理器( s p 2 2 9f l o p s ，d p11 3 g f l o p s ) 以及基于a s i c 的c l e a r s p e e d ( 9 6 g f l o p s ) 。g p u 的优点是，可以相同的面积芯片 上，g p u 将更多的晶体管用在计算单元上，而不是在实现片上存储器和复杂的控 制逻辑上，这使它具有极强的计算能力，但也使其应用领域受到了一定的限制【2 i 。 现代图形硬件随着工艺尺寸的逐渐变小，其作为通用计算处理单元的计算能 力也变得越来越强【3 】，例如：n v i d i a 于2 0 0 9 年1 1 月召开了产品发布会，表示即 将推出第三代通用计算产品f e r m i ( 采用4 0 n t o 工艺下，集成了3 0 亿晶体管) ，并 公布了第三代g p u 的相关技术细节，但由于没有公布处理器的频率，无法计算出 它的峰值性能；而a m d a t i 最新的产品r a d e o nh d5 8 7 0 ( a t i 的r a d e o n h d 系 列型号针对日常通用图形图像处理领域的应用) 的单精度浮点计算的峰值能达到 第l 页 国防科技大学研究生院硕士学位论文 2 7 2 t f l o p s ，双精度浮点计算达到了5 4 4 g f l o p s ，已经远远的超过当今最新c p u 的 处理速度( i n t e lx e o nw 5 5 9 0 ，单精度峰值性能达到1 0 6 5 6 g f l o p s ，双精度的计算 峰值5 3 2 8 g f l o p s ) 。图1 1 显示了当前主流c p u 与g p u 理论上的单精度浮点处 理能力1 9 。g p u 另外一个显著的特点就是存储器带宽逐年得到增强，g t 2 0 0 的存 储控制器由8 个g d d r 3 组成，位宽大小为5 1 2 b i t 。图1 2 所示的为c p u 与g p u 存储带宽，可以看出g p u 带宽增长速率上已明显超过了c p u 。强大的数据供应能 力和计算能力， 1 6 0 1 4 0 一、 婴。 岛o _ 鄂0 它 酉o 弋j 7 0 2 0 o 芝 l 2 台 _ ： j a nj a n a w j u n 五“rn o vm 皇yj 恤 0 3 翻嘻2 52 62 72 8 6 1 2 0 0 ；g e f 姒eg r x2 8 0 c _ 蔓j 2i g 西嗽9 张m g t x g 8 0ig e f 咕f c e 8 瞰m g t x g 7 i = g 西妇蚀7 9 0 0 g 6 7 0 霉g 时：饼铸舢g n v 蓐g e e6 8 0 0u l t r a 悻、，3 5 = g e f o r c e f x 斡s 0 u l t r a 哺，3 0 t g 计弧f s 8 图1 1c p u 与g p u 峰值性能发展趋势 2 0 0 32 0 0 4 2 0 0 52 0 0 62 0 0 72 0 0 82 0 0 9 图1 2c p u 与g p u 存储带宽比较 随着计算机的计算能力的不断提高，现代处理器已基本朝着三个主流方向发 第2 页 国防科技大学研究生院硕士学位论文 展：简单多核，以g p u 为代表；复杂多核，i n t e ll a r r a b e e 为代表；异构多核，i b m 的c e l l 为代表。由于l a r r a b e e 是i n t e l 即将推出的产品，但线程执行环境和核心频 率都没有向外公布，这里将不再讨论。 c e l l 处理器是s o n y 、t o s h i b a 、i b m 三家联合研制的一种典型的、更为灵活的 流处理器，其处理流应用时的吞吐率可达2 5 6 g f l o p s 。c e l l 片上集成了6 4 位r i s c 微处理器核心p p e 以及8 个用来加速流应用的协处理器运算阵列s p e 。s p e 内部 以s i m d 的形式开发数据级并行，而s p e 之间则以多线程的形式开发线程级并行。 虽然最初版本的c e l l 仅应用于游戏机设备，但其目标是替代通用微处理器构建超 高性能巨型机系统。2 0 0 8 年t o p 5 0 0 第一位为l o sa l a m o sn a t i o n a ll a b o r a t o r y 的 r o a d r u n n e r ，其中包括了6 5 6 2 个双核a m do p t e r o n 芯片和1 2 ，2 4 0 个c e l l 芯片， 性能达到1 0 2 6 p f l o p s ，峰值性能达到1 3 7 5 p f l o p s 。但与c e l l 配套的软件平台尚未 成熟，尤其是分布式计算结构需要软件的针对性优化，使得研究人员不能非常熟 练的在c e l l 搭建的计算平台上进行通用计算开发。 最近几年里，将g p u 用于通用计算领域的主要有a m d 和n v i d i a 两个公司。 a m d 在2 0 0 6s u p e r c o m p u t i n g 展览会上，推出了世界第一款专门针对企业高性能 运算的流处理器s t r e a mc o m p u t i n gp r o c e s s o r ，命名为a m ds t r e a mp r o c e s s o r ，并提 出了c t m ( c l o s et om e t a l ) 概念，使得开发者能够随意访问a m d 流处理器中的原 生指令集和大规模并行计算单元的内存，从而在g p u 上实现了更通用的应用。2 0 0 8 年第一季度a m d 推出的f i r e s t r e a m9 1 7 0 是业界第一款支持双精度浮点运算的 g p u ，采用5 5 n m 工艺，单精度浮点性能达到5 0 0 g f l o p s 。a m d 于2 0 0 8 年6 月 又发布了基于r v 7 7 0 核心的r a d e o n h d 4 8 5 0 和r a d e o n h d 4 8 7 0 ，其中拥有8 0 0 个 流处理器单元的r a d e o n h d 4 8 5 0 的单精度浮点性能达到了1 t f l o p s 。 同时，另一个巨头n v i d i a 也在2 0 0 8 年6 月推出了基于g t 2 0 0 体系结构的产 品：用于服务器运用系统的t e s l as 1 0 7 01 u 计算系统，其性能高达4 t f l o p s ，并 支持双精度浮点算术运算。稍早之前还推出了g e f o r c eg t x 2 8 0 和g t x 2 6 0 ，它们 都是基于第二代统一结构，其中g t x 2 8 0 包含了2 4 0 个流处理器，支持c u d a 2 0 编程环境，从而更好地实现了g p u 在通用领域中的应用。 g p u 在高性能超级计算机构建中也具有很大的潜力。o h i o 超级计算机中心的 b a l ec l u s t e r ，其中的g p g p 州i s u a l i z a t i o nc l u s t e r 包含18 个节点，每个节点由两 个a m d 双核o p t e r o n 芯片和两个n v i d i aq u a d r of x 5 6 0 0 图形卡搭建而成。b u l l 预计在2 0 0 9 年初推出由i n t e ln e h a l e m 与n v i d i at e s l a $ 9 0 0 搭建而成的超级计算 机。由我国国防科学技术大学自行研制的巨型机“天河一号”，由6 1 4 4 颗i n t e lc p u 和5 1 2 0 颗a m dg p u 搭建构成，峰值性能达到1 2 0 6 万亿次，实测性能为5 6 3 1 万亿次，在2 0 0 9 年1 1 月公布的全t o p 5 0 0 中排名第5 。 第3 页 国防科技大学研究生院硕士学位论文 n v i d i a 和a t i 公司都推出了适合通用计算的g p u 开发平台，使研究者和开发 者可以更好的在他们的平台上进行更为通用的并行程序开发。a t i 将他们推出的开 发平台称之为c a l ( c o m p u t ea b s t r a c t i o nl a y e r ) ，底层采用b r o o k + 进行编译，而 c a l 的具体应用主要分为两部分组成：一部分在c p u 上运行，采用c 或c + + 语言 语言进行编程；另一部分在g p u 上运行，被打包成内核函数，需要更高级的语言， 如a t ii l 1 1 。而n v i d i a 公司将采用的编程平台命名为c u d a ( c o m p u t eu n i f i e d d e v i c ea r c h i t e c t u r e ) ，c u d a 是采用c 语言的扩展集【l 】，在w i n d o w s 和l i n u x 操作 系统下都可以进行高性能计算开发，程序设计时也需要由两部分组成，一部分在 c p u 执行可支持c 或c + + ，另一部分也采用了c 语言，但增加相应的关键字来标 识在g p u 上执行的代码。就编程环境而言，c u d a 更易掌握和理解。 本课题是在n v i d i a 公司推出的并行编程模型- c u d a 上进行研究的， c u d a 平台上进行并行程序开发即给研究者们和开发者们带来了机遇，也带来了 相应的挑战。c u d a 的开发平台使用的是c 扩展语言，对其入门而言并不复杂， 但要做到真正的运用还需要对g p u 的体系结构、硬件的设计和g p u 的突出运算 能力有一定的了解，才能编出高效的的程序来。目前传统c p u 的每一次性能的提 升都会带来更多的复杂问题，如功耗墙、时钟墙、频率墙等。在微处理器体系结 构技术面临新的突破，研究人员正在进行大量新的尝试。所以需要更优化的体系 结构技术来促进体系结构的发展，g p u 利用简单多核用牺牲一定通用性的代价来 获取在部分领域的高性能计算，不失为一种好的体系结构尝试。本文将通过对基 于g p u 的体系结构进行大量算法映射，探讨限制性能提升的瓶颈，为g p u 体系 结构的改进提供参考。 1 2国内外研究现状及通用g p u 数据处理模型 1 2 1 研究现状 近年来，越来越多的研究人员致力于将适合在g p u 上运行的程序映射到g p u 结构上，取到了非常好的的效果。n v i d i a 公司2 0 0 6 年推出的c u d a 和a m d a t i 在2 0 0 8 年推出的c a l 可编程的平台后，极大地加速了这种趋势，研究人员将大 量数据密集型的计算任务映射到g p u 上，通过g p u 来获得性能提速。 2 0 0 7 年n v i d i a 的发布了特征值分解范例【5 】。 2 0 0 7 年b e r k e l e y 大学的v a s i l yv o l k o v 和j a m e sw d e m m e l 将l a p a c k 库中 的矩阵乘、l u 分解、q r 分解和c h o l e s k y 分解映射到g p u 上并对改进后的算法 做了进一步的优化，从图表1 1 可以看到对于矩阵这种数据密集型的算法是可以很 好的在g p u 上运行i o j 。 第4 页 国防科技大学研究生院硕士学位论文 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = _ - - w w - = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 2 0 0 7 年m i t s u b i s b i 电子研究所的f a t i hp o f i “i 和j a yt h o r n t o n 对图像监视做了 优化，比在普通c p u 上的运行速度提高了2 0 倍。 表1 1 矩阵计算问题c p u 与g p u 性能比较 q 6 8 5 0 8 8 0 0 g r x + e 6 7 0 0g t x 2 8 0 + e 6 7 0 0 g f l o p so f l o p ss p e e d u pg f l o p ss p e e d u p l u7 31 7 92 5 x3 0 94 1 x c h o l e s k y 7 01 8 32 7 x3 1 54 4 x q r 7 51 9 22 6 x3 4 04 4 x s g e m m8 82 0 82 4 x3 7 5 ，4 3 x p e a k 9 68 84 0 x6 6 76 9 x 2 0 0 7 年m i n n e s s o t a 大学的p e t e rb a i l e y 对b o l t z m a n n 流体动力学进行映射，优 化后性能提升了2 8 倍。 2 0 0 7 年s h e e t a ll a h a b a r ，p i n k ya g r a w a l ，p j n a r a y a n a n 在c u d a 上实现了了 神经网络的映射【1 7 1 。 2 0 0 7 年n v i d i a 正式发布的c u d as d k 包含c u b l a s 基本线性函数库1 4 ，可 以对向量和矩阵计算进行加速【8 j 。 2 0 0 8 年c h r i s t i a nl e s s i g 在c u d a 上实现了m r r r 算法，并准备进一步实现基 于m r r r 的奇异值分解【9 】。 2 0 0 8 年d a n i e lc e d e r m a n 和p h i l i p p a st s i g a s 在c u d a 上实现了快速排序算法， 相对于g p u 上的快速排序算法的2 5 倍【l 们。 2 0 0 8 年，g i o r g o sv a s i l i a d i s ，s p i r o sa n t o n a t o s ，m i c h a l i sp o l y c h r o n a k i s 等人在 c u d a 上实现了k m p 、b m 、a c 等模式匹配算法【1 1 1 。 表1 2 给出了当前成功利用c u d a 进行映射的实例。 表1 2n v l d i a 的c o d a 开发平台目前的成功应用 应用领域参考网站加速比 地震资料处理h t t p ：w w w h e a d w a v e c o n l 6 6 1 0 0 软件无线电 h t t p ：w w w a c c e l e w a r e c o r n 4 5 分子动力学h t t p ：w w w k s u i u c e d u r e s e a r c h v m d 2 4 0 神经细胞模拟 h t t p ：w w w e v o l v e d m a c h i n e s c o r n 1 0 0 m r j 处理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 由此可以看出，在g p u 上进行并行应用开发具有十分重要的意义，但同时也 对我们的研究带来了挑战。在每一个领域都有研究者做出了大量的工作，并取得 了较好的效果，在前人的基础上需要投入更多的精力和时间来进行算法映射及优 化。 1 2 2 通用g p u 数据处理模式 第5 页 国防科技大学研究生院硕士学位论文 现代多处理器技术中，s i m d 线程执行技术的采用极大地加速了程序的执行性 能。而数据流是s i m d 线程模型对数据进行处理的一种组织形式，在本质上利用 多个执行单元对多份数据执行相同的操作。s i m d 处理数据的模式类似于流处理模 式，流处理是一种以数据为中心的计算模型，通过暴露数据间的相关性，执行时 充分挖掘数据并行性；同时通过挖掘数据局部性，减少片外访存。而目前n v i d i a g p u 处理数据结构类似于流，在线程执行模型上是以单条指令多个线程的方式并 行访问数据，n v i d i a 将这种执行模型称之为s i m t ( s i n g l ei n s t r u c t i o nm u l t i p l y t h r e a d ) ，之后推出的体系结构中，添加了双精度的流处理能力，增强了科学计 算应用领域的应用范围。与此同时，a m d 数据的处理继续沿用s i m d 数据处理方 式，并不断改善其编程平台。c a l 编程环境的引入，减轻了程序员的负担，让其 可以花更多的精力投入到其他算法等相关的环节中，而不必对底层硬件有很深的 了解就可以进行算法映射【l2 1 。因此，学术界和工业界的研究者和开发者们不惜花 费巨大的精力去研究基于g p u 的算法，如：排序、数据库操作、图像处理、解线 性方程等。随着g p u 体系结构进一步的完善，将会有越来越多的可以在并行机器 上运行的应用被映射到g p u 上来，实现性能的提速而g p u 在某些应用领域也将 会在一定程度上的缓解c p u 的计算压力，让其做更多控制相关的操作，使整个系 统处于最优的运行状态。 1 3 课题研究内容与成果 本课题主要对基于g p u 的微体系结构高性能计算进行研究。本文首先对g p u 体系结构进行深入的研究，设计出适合在g p u 上执行的并行算法，再利用c u d a v i s u a lp r o f i l e r 硬件资源分析器分析性能瓶颈，采用多种措施来进行优化，尽可能 地挖掘计算性能；最后将改进前后的算法通过g p g p u s i m 模拟器的模拟，从微体 系结构级对比分析程序的执行行为，对g p u 微体系结构的改进进行探讨。本课题 的主要研究内容如下： 典型算法设计与实现 g p u 是由成百上千个核组成的多核处理器簇，通用的并行算法必须做出适当 的修改才能适合在g p u 上执行。由于g p u 同步通信机制的限制，算法的改进过 程具有一定的复杂性。本文将对排序算法、矩阵乘等并行算法进行研究和改进， 设计出其适合在g p u 上执行的并行程序，获得了良好的性能加速比。 模拟器模拟 基于g p g p u s i m 模拟器，本文还将现己映射的算法在不同的结构配置情况下 第6 页 国防科技大学研究生院硕士学位论文 进行了模拟和分析，对g p u 微体系结构的改进进行了探讨。 本文的贡献和创新体现在以下几点： 1 深入分析了n v i d i ag 8 0 g t 2 0 0 微体系结构及c u d a 编程平台。 2 实现多种排序算法在g p u 上的映射，获得了良好的性能加速，包括：数 组倒序、奇偶排序、双调排序，加速比分别为：4 1 、1 7 、2 5 ，并部分实现 了枚举排序。实现了局部排序中的算法优化技术，包括：体冲突消除和循 环展开技术。奇偶排序算法通过消除体冲突获得的加速比为3 ，双调排序 算法通过循环展开获得的加速比为2 。 3 实现了数值计算中的矩阵向量乘在g p u 上的映射。基于g p u 中的传统矩 阵乘算法，通过采用纹理c a c h e 、增大计算访存比和预取三种技术进行加 速，实测性能分别提高了约1 0 、6 0 和8 7 。 4 提出了g p u c p u 异构系统上的任务划分设计模式。实验表明，基于任务 划分的矩阵乘性能可以获得1 0 的提高。 5 基于g p g p u s i r e 模拟器，通过对典型算法在不同配置结构下进行了大量 的模拟分析，对g p u 微体系结构的改进进行了探讨。 1 4 本文结构 本文主要论述了基于g p u 微处理器高性能计算的研究，论文分为六章。 第一章为绪论，给出了课题背景及意义、国内外基于g p u 并行计算的相关研 究、课题研究内容与成果和本文结构。 第二章阐述了g s 0 体系结构、c u d a 编程模型介绍及进行实验的平台。 第三章阐述了多种并行排序算法在c u d a 编程编程实现及相应的优化措施。 第四章阐述了数值分析与科学计算中的矩阵乘在g p u 体系结构下的算法映射 及改进，并提出了任务划分的设计模式，为体系结构建模提供指导性建议。 第五章使用模拟器对数值分析中的矩阵乘进行模拟器模拟，改进g p u 模拟器 结构观察实验结果，总结规律。 第六章为结束语与工作展望，对本文工作做出小结，并对未来工作进行展望。 在最后，对给予我无私帮助的所有老师、同学和朋友表示感谢，并且给出本 文的参考文献。 第7 页 国防科技大学研究生院硕士学位论文 第二章g p u 体系结构及c u d a 编程平台介绍 2 1 1g p u 发展历程 2 1引言 1 9 9 9 年，n v i d i a 推出了第一款g p u g e f o r c e2 5 6 。它由两个主要模块组成， 一个是顶点转换和顶点光照处理器，由可以进行3 2 位浮点数运算的固定功能单元 组成；另一个是像素( 片元) 着色流水线，由进行定点数运算的固定功能单元组 成。g e f o r c e2 5 6 可以支持o p e n g l 和微软公司的d i r e c t x7 标准a p i 接口1 7 j 。 2 0 0 1 年，n v i d i a 推出了第款拥有可编程顶点着色器的g p u - - g e f o r c e3 。它 使用了可编程的顶点处理器和不可编程的像素( 片元) 处理器，并且两者都能完 成3 2 b k 单精度浮点运算【1 3 】。g e f o r c e3 可以支持d i r e c t x8 系列a p i 和o p e n g l a p i 。 2 0 0 2 年，a t i 推出的r a d e o n9 7 0 0 则是第一种拥有可编程像素( 片元) 着色 ( f r a g m e n ts h a d e r ) 的g p u ，但是它的可编程像素处理器基于2 4 位浮点流水线， 精度较低。r a d e o n9 7 0 0 可以支持d i m c t x9 的a p i 和o p e n g l a p i 。同年，n v i d i a 在其后推出的g p i - 七e f o r c ef x 是第一种使用3 2 位浮点流水线做为可编程的顶点 处理器的g p u t l j l 。 2 0 0 5 年，微软x b o x3 6 0 中使用的g p u 是一种早期的基于统一着色体系结构 ( u n i f i e ds h a d e ra r c h i t e c t u r e ) 的g p u ，只使用一种处理器进行顶点和像素处理。 2 0 0 6 年，n v i d i a 推出的g p i 卜g e f o r c e8 8 0 0 图形处理器是第一款基于g 8 0 体系结构的g p u 。g 8 0 体系结构使用统一着色单元取代了分离的顶点和像素着色 处理单元，引入了共享存储器和更为友好的开发环境。 2 0 0 8 年，n v i d i a 推出了基于g t 2 0 0 结构的g p u 。g t 2 0 0 体系结构在g 8 0 体系结构的基础上进行相应改进了，主要表现在加入了对共享存储器的原子操作 和双精度浮点运算的支持，放宽了对存储器的对齐访问。 2 0 0 9 年，a m d 计划推出了它的g p u - - f i r e s t r e a m9 2 7 0 ，其特点是具有更高的 主频，存储为g d d r 5 ，并且支持o p e n c l ( o p e nc o m p u t i n gl a n g u a g e ) 。但同时 功耗大幅增加，9 2 7 0 功耗指标为5 g f l o p s w ，峰值功耗为2 2 0 w ，已经接近n v l d i a g t 2 0 0 系列g p u 的功耗水平；与此同时，n v i d i a 在1 1 月份，对外发布了其第三 代统一体系结构的产品f e r m i ，加入了更多的s m 数目和寄存器器、共享存储器等 硬件资源，线程块调度机制也得到了进一步的优化。 随着g p u 作为通用计算的用途被人们广泛的应用，g p u 不再只处理图形图像 领域中的应用，而是加入了更多的计算执行单元来满足日益增长通用计算领域的 第1 页 国防科技大学研究生院硕士学位论文 市场需求。 2 1 2g p u 计算模型 传统的c p u