（计算机科学与技术专业论文）gpu加速pqmrcgstab算法研究.pdf

国防科学技术大学研究生院硕士学位论文 摘要 近几年来，通用图形处理单元( g p g p u ) 发展迅速，可编程性不断提高，g p u 的峰 值性能已经从几个g f l o p s 增长到几个t f l o p s 。g p u 的主要应用也从图像处理转向了通用计 算中，并且越来越多的应用到加速科学计算程序的研究当中。在科学计算领域中，迭代法 求解大型稀疏线性系统在计算流体力学、数值天气预报、石油地震数据处理、材料模拟与 设计等实际应用中具有重要的意义。雅克比预条件准最小残差共轭梯度稳定算法 ( i a c o b i p r e c o n d i t i o n e dq u a s i m i n i m a lr e s i d u a lb i c o n j u g a t eg r a d i e n ts t a b l e ，缩写为 p q m r c g s t a b ) 属于克雷洛夫子空间方法，是求解大规模稀疏线性系统的有效算法，具 有短迭代步数和快速收敛等优点。然而在c p u 上利用该算法求解稀疏线性系统时会耗费大 量的时间，如何加速其求解具有重要意义。利用g p u 加速迭代法求解大型稀疏线性系统 可以降低计算周期，提高计算效率，有利于加速多种实际问题的解决。 本文通过对g p u 体系结构和编程模型的分析，研究了p q m r c g s t a b 算法在a m d g p u 和n v i d i ag p u 上移植的技术难点，包括稀疏矩阵中零元素对存储空间的浪费、计 算核心开销对性能的降低、n v i d i ag p u 上没有提供归约操作、不同的g p u 需要采用针 对性的优化方法以及多g p u 上实现算法需要数据共享等问题。通过c p u 和g p u 协作的方 式在单g p u 平台和多g p u 平台上对算法进行了加速，取得了如下的成果： 设计并实现了面向g p u 的数据处理方法。利用d i a 存储格式把带状稀疏矩阵转换成 向量，同时在迭代开始前把全部数据传递给g p u ，迭代过程中尽量避免与c p u 的数据通 信。数据在g p u 上占用的存储空间得到了压缩，并且减少了c p u 和g p u 之间的数据通信 开销。 提出了调整核心组织顺序的策略。把有数据相关且不存在与c p u 通信的核心合并起 来。该方法减少了核心启动开销，增加了数据重用，减少了c p u 向g p u 上传递的数据量。 测试表明，采用本文的计算核心划分方法使性能提高了2 9 1 1 。 设计并实现了c p u + g p u 混合归约的方法。该方法有效利用n v i d i ag p u 实现块内数 据的归约操作，利用c p u 实现块间数据的归约操作。测试表明，c p u + g p u 混合归约方法 与全在c p u 上实现的归约方法相比性能提高了3 0 4 9 ，与全在g p u 上实现的归约方法相 比提高了1 5 2 3 。 提出了针对不同g p u 平台的优化方法。优化方法包括不同g p u 平台上高速存储部件 的使用和数据结构的优化。测试表明，与平台相关的优化方法可以使算法在两种平台上的 性能得到较大幅度的提高。 分析了当前的多g p u 加速技术，提出了在多核c p u 和多g p u 上分配任务和数据通信 的方法。每个c p u 核控制一个g p u 进行计算，c p u 核负责分配任务和向g p u 发出计算 指令，g p u 负责数据的计算。我们选择了一维分割方法在不同g p u 之间分配数据，该方 第i 页 国防科学技术大学研究生院硕士学位论文 法使得数据通信开销与二维分割方法的开销卡日比减少了3 0 2 8 。 测试表明，在双精度条件下，算法在a m dr a d e o nh d4 8 7 0x 2 平台上与a m dr a d e o n h d4 8 7 0 甲台性能相比提高了7 0 ，是在四核c p u 上并行执行算法性能的1 0 倍；算法在 n v i d i at e s l as 1 0 7 0 平台上与n v i d i at e s l ac 1 0 6 0 平台性能相比提高了2 6 倍，是算法在 四核c p u 上并行执行算法性能的3 2 倍。 主题词：g p u ，p q m r c g s t a b ，迭代法，稀疏线性系统，优化 第i i 页 国防科学技术大学研究生院硕士学伊论文 a b s t r a c t i nr e c e n ty e a r s ，t h ea r c h i t e c t u r e ，p r o g r a m m i n gm o d e la n dr e l a t e da s p e c t so fg e n e r a lp u r p o s e g r a p h i c sp r o c e s s i n gu n i t ( g p g p u ) h a v eb e e nd e v e l o p e dr a p i d l y ，t h ep r o g r a m m a b i l i t yo fg p u h a v eb e e ni m p r o v i n ga l lt h et i m e ，a n dt h ep e a kp e r f o r m a n c eo fg p u g r o w sf r o ms e v e r a lg f l o p s t os e v e r a lt f l o p s t h em a i na p p l i c a t i o no fg p uh a ss h i f t e df r o mi m a g ep r o c e s s i n gt og e n - e r a l - p u r p o s ec o m p u t i n g ，a n dm o r ea n dm o r er e s e a r c h sa r ef o c u s i n go na c c e l e r a t i n gs c i e n t i f i c p r o b l e m sw i t hg p u i ns c i e n t i f i cp r o b l e m s ，u t i l i z i n gi t e r a t i v em e t h o dt os o l v et h el a r g es p a r s e l i n e a rs y s t e m si st h ek e yi nm a n yf i e l d si n c l u d i n gt h ef l u i dd y n a m i c s ，n u m e r i c a lw e a t h e rp r e d i c t i o n ，o i la n ds e i s m i cd a t ep r o c e s s i n g ，m a t e r i a l ss i m u l a t i o na n dd e s i g n mp q m r c g s t a b ( j a c o b i - p r e c o n d i t i o n e d q u a s i m i n i m a l r e s i d u a l b i c o n j u g a t e g r a d i e n t s t a b l e ， p q m r c g s t a bf o rs h o r t ) a l g o r i t h mb e l o n g st oo n ek i n do fk r y l o vs u b s p a c em e t h o d sa n di ti s a ne f f i c i e n ta l g o r i t h ms o l v i n gt h el a r g es p a r s es y s t e m ，w h i c hb o t hh a ss h o r ti t e r a t i v es t e p sa n d s t a b l ec o n v e r g e n c e h o w e v e r s o l v i n gt h e s ep r o b l e m so nc p uc o n s u m e sl o t so ft i m ew h i c h c a n n o tm e e tt h ep r a c t i c a lr e q u i r e m e n t s a c c e l e r a t i n gi t e r a t i v em e t h o dt h a ts o l v i n gl a r g es p a r s e l i n e a rs y s t e mw i t hg p uc a nn o to n l yr e d u c et h et i m eb u ta l s oi m p r o v et h ec o m p u t i n ge f f i c i e n c y ， w h i c hc a nb eg e n e r a l i z e dt os p e e du pal o to fp r a c t i c a lp r o b l e m s a f t e ra n a l y z i n gt h ea r c h i t e c t u r ea n dp r o g r a m m i n gm o d e lo fg p u ，w ed i s c u s s e dt h ed i f f i c u l t i e si na d a p t i n gp q m r c g s t a ba l g o r i t h mt oa m dg p ua n dn v i d i ag p u ，i n c l u d i n gt h e w a s t i n go ft h es t o r a g es p a c ei n t r o d u c e db ys p a r s em a t r i x ；t h ed e c r e a s i n go ft h ep e r f o r m a n c e b r i n g e db yk e r n e lo v e r h e a d ；t h el a c ko fr e d u c t i o no p e r a t i o no nn v i d i ag p u ；t h en e e do fs p e - c i a lo p t i m i z a t i o nm e t h o d so nd i f f e r e n tg p u sa n dt h en e e do fd a t as h a r i n go ns y s t e mw i t hm u l t i - p i eg p u s t h r o u g ht h ec o o p e r a t i o no fc p ua n dg p u ，w ep r o p o s e ds o m en o v e lm e t h o d s t or e a l i z et h ea l g o r i t h m t h em a i nc o n t r i b u t i o n si nt h i sp a p e ra r ea sf o l l o w s ： w ed e s i g n e da n di m p l e m e n t e dam e t h o dt od e a lw i t ht h es p e c i a ld a t as e n tt og p u b yu s i n g t h ed i as t o r a g ef o r m a tt oc o n v e r tt h eb a n ds p a r s em a t r i xt ov e c t o r s ，w ed e l i v e r e da l lt h ed a t at o g p ub e f o r es t a r to ft h ei t e r a t i o na n do n l yc o m m u n i c a t e dal i t t l ed a t aw i t hc p u c o n s e q u e n t l y ， s p a c eo ft h ed a t ad e l i v e r e dt ot h eg p u i sc o m p r e s s e d ；m o r e o v e r ，t h i sm e t h o dr e d u c e st h ec o r n m u n i c a t i o no v e r h e a db e t w e e nc p ua n dg p u w ep r o p o s e das t r a t e g yo fa d j u s t i n gt h eo r g a n i z a t i o no fk e r n e lb ym e r g i n gt h ek e m e l s a m o n gw h i c ht h e r ea r ed a t ad e p e n d e n c i e sa n dn oc o m m u n i c a t i o n sw i t hc p u 1 1 1 i sm e t h o dr e d u c e st h eo v e r h e a do fk e r n e ll a u n c h ，i n c r e a s e st h ep r o p o t i t i o no fr e u s e dd a t aa n dr e d u c e st h e a m o u n to fd a t ad e l i v e r e dt og p u t e s t ss h o wt h a tt h i sa p p r o a c hi m p r o v e st h ep e r f o r m a n c eb y 2 9 1 1 w ed e s i g n e da n di m p l e m e n t e dac p u + g p uh y b r i dr e d u c t i o na p p r o a c h i nt h i sm e t h o d ， n v i d i ag p u c h a r g e sf o rt h er e d u c t i o nb e t w e e nt h r e a d si nt h eb l o c ka n dc p uc h a r g e sf o rt h e r e d u c t i o nb e t w e e nd i f f e r e n tb l o c k s t h i sm e t h o de f f e c t i v e l yu t i l i z e st h ea d v a n t a g e so fd i f f e r e n t p l a t f o r m s ，a n dr e d u c e st h eo v e r h e a do fr e d u c t i o n t e s t ss h o wt h a t ，c p u + g p uh y b r i dr e d u c t i o n 第i i i 页 国防科学技术大学研究牛院硕士学位论文 m e t h o da c h i e v e sp e r f o r l i l a n c ei m p r o v e m e n to f3 0 4 9 c o m p a r e dt ot h ec p uo n l yr e d u c t i o n m e t h o da n di m p r o v e m e n to f15 2 3 c o m p a r e dt ot h eg p u o n l yr e d u c t i o nm e t h o d w ep r o p o s e ds e v e r a lo p t i m i z a t i o nm e t h o d sf o rd i f f e r e n tg p u p l a t f o r m s i n c l u d i n gt h eu s a g eo fh i g h s p e e dm e m o r yc o m p o n e n t sa n dd a t as t r u c t u r e s t e s t ss h o wt h a tw i t ht h ep l a t f o r m - d e p e n d e n to p t i m i z a t i o n s ，p e r f o r m a n c eo ft h ea l g o r i t h mc a nb eg r e a t l ye n h a n c e do nt w o g p u p l a t f o r n l s w ea n a l y z e dt h ec u r r e n tm u l t i g p ua c c e l e r a t i o nt e c h n o l o g y a n dp r e s e n t e dat a s ka l l o c a - t i o nm e t h o da n dd a t ac o m m u n i c a t i o nm e t h o di nt h em u l t i c o r ec p ua n dm u l t i g p up l a t f o r m e a c hc o r eo fc p uc o n t r o l so n eg p ua n de v e n l yd i s t r i b u t e st a s k st og p u t h eg p um a i n l y c h a r g e sc o m p u t a t i o n s w ec h o o s et h eo n e d i m e n s i o n a ld i v i d i n gm e t h o dt od e a lw i t ht h ed a t a c o m m u n i c a t i o n s t h i sm e t h o dr e d u c e st h ed a t ac o m m u n i c a t i o no v e r h c a da n dc o n s u m e s3 0 2 8 l e s st i m et h a nt h ec o s to ft w o d i m e n s i o n a ld i v i n gm e t h o d t e s t ss h o wt h a tp e r f o r m a n c eo ft h ea l g o r i t h mi nt h ea m dr a d e o nh d4 8 7 0x 2p l a t f o r m i n c r e a s e s7 0 c o m p a r e dw i t ht h ea m dr a d e o nh d4 8 7 0p l a t f o r i d 10t i m e sc o m p a r e d 丽m p e r f o r m a n c eo ft h ep a r a l l e la l g o r i t h mo naq u a d - c o r ec p u ；p e r f o r m a n c eo ft h ea l g o r i t h mi nt h e n v i d i at e s l as10 7 0p l a t f o r mi n c r e a s e s2 6t i m e sc o m p a r e dw i t ht h en v i d i at e s l ac10 6 0 p l a t f o r m , a n d3 2t i m e sc o m p a r e d 、i t hp e r f o r m a n c eo ft h ep a r a l l e la l g o r i t h mo naq u a d - c o r e c p u k e yw o r d s ：g p u ，p q m r c g s t a b ，i t e r a t i v em e t h o d ，s p a r s el i n e a rs y s t e m ，o p t i m i z a t i o n 第i v 页 国防科学技术大学研究生院硕上学位论文 表目录 表2 1c u d a 存储模型。1 0 表2 2 核心合并前每次迭代中核心的划分和开销统计2 1 表2 3 核心合并后每次迭代中核心的划分和开销统计2 2 表2 4 核心合并前后调用核心的总次数和开销统计2 2 第l i i 页 国防科学技术大学研究生院硕上学位论文 图1 1 图1 2 图1 3 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图3 8 图3 9 图3 1 0 图3 1 1 图3 1 2 图3 1 3 图3 1 4 图3 1 5 图3 1 6 图3 1 7 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图目录 g e f o r c e6 8 0 0 的体系结构2 n v i d i ag p u 与i n t e lc p u 性能对比图2 矩阵乘运算在g p u 和c p u 上的性能对比图4 g t 2 0 0 体系结构8 c u d a 中计算核心9 a t i 流处理器体系结构1 1 b r o o k + 中计算核心1 2 a m dg p u 编程环境。1 2 p q m r c g s t a b 算法描述1 4 2 5 * 2 5 的d i a 格式稀疏矩阵1 6 e l l 格式处理稀疏矩阵方法1 7 c s r 格式处理稀疏矩阵方法1 7 带状稀疏矩阵结构1 8 处理带状稀疏矩阵过程1 8 迭代法中计算过程分析。1 9 迭代法在g p u 上的任务分配方法1 9 全在c p u 上的归约方法2 3 无锁同步归约方法2 4 有锁同步归约方法2 5 传统二叉树归约方法2 6 传统二叉树归约方法下的数据访问2 6 带跨度的二叉树归约方法2 7 带跨度的二叉树归约方法下的数据访问2 7 使用纹理内存前后对比图2 8 a m dg p u 上申请缓存过程2 9 修补矩阵和采用d o u b l e 2 类型数据前后对比图2 9 a m dc r o s s f i r e 技术工作原理图3 2 矩阵乘在多g p u 上的加速性能图3 3 纳维叶一斯托克斯方程在多g p u 上的加速性能图3 3 算法在多g p u 平台上的任务分配图3 4 一维数据分割方法3 5 n v i d i ag p u 上对边界的处理过程3 5 第1 v 页 国防科学技术大学研究生院硕士学何论文 图4 7 二维数据分割方法3 6 图5 1 算法在t e s l ac 1 0 6 0 上与a m d 四核c p u 性能对比图3 9 图5 2 算法在t e s l ac 1 0 6 0 上相对于a m d 四核c p u 的加速比3 9 图5 3 算法在r a d e o nh d4 8 7 0 上与a m d 四核c p u 性能对比图4 0 图5 4 算法在r a d e o nh d4 8 7 0 上相对于a m d 四核c p u 的加速比4 0 图5 5 算法在不同n v i d i ag p u 数目下与a m d 四核c p u 的性能对比图4 l 图5 6 算法在不同n v i d i ag p u 数目下相对于a m d 四核c p u 的加速比4 1 图5 7 算法在不同a m dg p u 数目下与a m d 四核c p u 的性能对比图4 2 图5 8 算法在不同a m dg p u 数目下相对于a m d 四核c p u 的加速比4 2 图5 9n v i d i as 1 0 7 0 上m p i 通信开销占总执行时间比例图4 2 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文作者签名：蕉拯 日期：伊j 彳年肛月易7 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 昼瞍拉速里她垦盟墨! 些篡洼狃究 学位论文作者签名：登重坠 日期： 钞7 年la - ) 目研日 作者指导教师签名：丑墨垒丝鱼日期：叫年v 月、扫 国防科学技术大学研究生院硕士学位论文 第一章引言 稀疏线性系统的求解对于计算流体力学、数值天气预报、石油地震数据处理、材料模 拟与设计等复杂实际问题的解决具有重要的意义。然而在主流多核c p u 上求解稀疏线性系 统时，一般运行周期很长，不能满足实际应用的需求，如何有效的提高性能成为一个亟需 解决的问题。g p u 自产生以来发展十分迅速，在体系结构和编程模型方面取得了很多的进 步，其惊人的计算能力促使g p u 不断从传统的图像处理转向通用计算领域。很多研究人 员开始利用g p u 加速求解稀疏线性系统，并且取得了较好的效果。本文分析了g p u 上求 解稀疏线性系统遇到的挑战，对g p u 加速p q m r c g s t a b 算法求解稀疏线性系统的关键 技术进行了研究，并在两种主流g p u 平台上实现了该算法。本章对以上内容进行了概括 性的阐述。 第一节介绍了g p u 在体系结构和编程模型方面取得的进步，以及g p u 加速求解稀疏 线性系统的必要性和可行性；第二节介绍了目前在g p u 上加速线性系统求解的相关工作； 第三节重点分析了g p u 加速求解稀疏线性系统所面临的挑战；第四节概括了在g p u 上加 速求解稀疏线性系统的研究内容和创新；第五节给出了全文的组织结构。 1 1 课题背景 g p u 的体系结构和编程模型发展迅速，强大的计算能力促使其越来越多的应用到科学 计算当中，研究如何在g p u 上加速求解稀疏线性系统具有必要性和可行性。本节将对以 上内容予以简要介绍。 1 1 。1g p d 计算 2 0 0 4 年以来，处理器( c p u ) 频率的增长变得缓慢起来，超大规模集成电路( v l s i ) 技术发展的局限性使得更多的设计转向了多核领域，人们希望根据摩尔定律所揭示的：卷片 规模增长趋势来设计更多的多核处理器以及硬件加速器。近些年出现了很多硬件加速器， 包括图形处理器( g p u ) ，元件可编程逻辑阵列( f p g a s ) 以及c e l lb e 。很多研究人员 利用这些硬件加速器取得了较好的效果【l 】。g p u 作为一种重要的硬件加速器发展迅速， 从产生以来取得了很多进步。 第一块g p i 卜g e f o r c e2 5 6 产生于1 9 9 9 年，它的部件全部由固定的图形处理器构成， 不具有可编程性。2 0 0 1 年随着g e f o r c e3 的推出，第一块可编程的顶点处理器开始进入市 场。g p u 的编程模型在过去的几年里发展十分迅速，灵活性随着曰益完善的体系结构而不 断提高。图1 1 描述了g e f o r c e6 8 0 0 的体系结构【9 】，传统g p u 的体系结构包含了顶点处理 器和象素片段处理器，两者功能互相独立，顶点处理器执行顶点绘制程序，象素片段处理 第1 页 国防科学技术大学研究生院硕上学位论文 器处理象素绘制程序。在传统的g p u 应用中，程序员通过专门的图形接口调用g p u 进行 计算。由于只有顶点处理器和象索片段处理器两个部件是可编程的，为了调用这些部件， 图形处理的大部分过程都需要程序员指定这就要求程序员熟悉底层复杂的硬件机制。随 着g p u 的发展，传统g p u 的计算方式很快被更高层的编程模型所取代，例如b r o o k + i l ， c u d a “l ，o p e n c l “肄都是新一代g p u 编程模型的代表。这些新的编程模型封装了底层的 硬件机制，在高级语言中扩展了一些接口，这些接口指定了在c p u 和g p u 上运行的程序。 熟悉高级语言的编程人员只需通过调用这些接口就可以方便的开发g p u 程序。 图】i g e f o r c e6 8 0 0 的体系结构 ”1 葛：兰之挚争 u a p tj m j i “ 图l2n v i d i a g p u 与i n t e l c p u 性能对比图 与c p u 相比，g p u 中没有一致性的处理器缓存和复杂的分支预测机制，它通过启动 成千上万的线程来最大化并行程序的执行，同时隐藏延迟。如图l2 所示为c p u 和g p u 的性能变化趋势图。从图”中可以看出，现代g p u 的单精度性能已经能够达到i t f l o p s 并且已经能够完全支持i e e e 双精度浮点数据格式的计算；同时g p u 的性能正在以超过摩 尔定律的速度增长，多g p u 的产品也纷纷出现，a m d 以及n v i d i a 等公司都酝酿着推出 新的更加高效的架构，例如f e r m i i “哗。由于一些科学计算程序在摹于c p u 平台上的计算 第2 页 lol： 国防科学技术大学研究生院硕士学位论文 周期十分漫长，消耗资源巨大，已经小能满足实际的应川需求，如果能够利用g p u 进行 加速具有重要意义。这些特点使得g p u 越来越多的应用于通用计算中，包括线性代数1 7 岱j ， 密码学1 5 】，分子动力学【1 6 】，统计学等【1 7 1 8 1 领域。算法经g p u 加速后的性能与主流c p u 相 比达到了1 0 1 0 0 倍的加速比，同时，很多异构系统通过p c i e x p r e s s ( p c i e ) 接1 ：3 连接多 g p u 平台达到了更高的加速性能。 1 1 2g p u 上加速稀疏线性系统 很多复杂的科学计算程序的求解一般都转化为对某一个线性系统的求解。在求解线性 系统a x = b 时，应当根据不同类型的系数矩阵选择不同的求解算法。当系数矩阵为小规模 稠密矩阵时，一般采取q r 分解，l u 分解等直接求解方法求解，此时计算量较小，运算周 期较短；当系数矩阵为大规模稀疏矩阵时，一般采取迭代法求解，此时计算量较大，运算 周期较长。在稀疏线性系统达到一定规模时，在c p u 上进行迭代法求解时一般运算周期很 长，短则数个小时，长则数天乃至数月【l 纠。 在计算数学中，当求解方程或者方程组时，迭代法是一组从初值出发通过不断的循环 变换来寻找满足精度条件的新值的过程。在求解线性系统时，具有代表性的迭代法有雅可 比迭代法( j a c o b i ) ，高斯赛德尔迭代法( g a u s s - s e i d e l ) ，共轭梯度法( c o n j u g a t eg r a d i e n t s ) ， 准最小残差法( q u a s i m i n i m a lr e s i d u a l ) ，双共轭梯度法( b i c o n j u g a t eg r a d i e n tm e t h o d ) 等。在求解大规模稀疏线性系统时，这些迭代法包含的计算量很大，分支转移等操作相对 较少，同时迭代过程中需要的额外数据存储空间相对较小，比较适合在g p u 上进行运算。 1 2 相关工作 目前，研究人员在g p u 加速线性系统求解方面做了大量的工作，其中很多工作取得 了较好的效果。根据求解的线性系统类型可以把这些工作分为两个方面，一个方面是加速 直接法求解线性系统，另一个方面是加速迭代法求解线性系统。 在加速直接法求解线性系统方面，s t a n i m i r et o m o v 和j a c kd o n g a r r a l 2 0 】在文章中对混合 的多核c p u + g p u 结构进行了讨论，并在基于两个4 核c p u 和一个g p u 的混合多核+ g p u 系统上实现了l u 分解。文中在c p u 的8 个核与g p u 上进行协同计算，根据不同平台的 特点合理分配数据。l u 分解在单精度浮点条件下的性能达到3 8 8 g f l o p s ，双精度浮点条件 下的性能达到9 9 4 g f l o p s 。 v a s i l yv o l k o v 和j a m e sw d e m m e l 8 1 利用n v i d i ag p u 对稠密线性系统进行了加速。 文中实现的矩阵乘运算( g e m m ) 与n v i d i ac u b l a s2 0 中g e m m 性能相比提高了6 0 ， 文中在g p u 上实现了l u ，q r 和c h o l e s k y 分解。文中在两个g p u 上实现了l u 分解，其 单精度条件下的性能达到5 4 0 g f l o p s 。如图1 3 所示为文中在c p u 和g p u 平台上矩阵乘运 算( 单精度条件下) 取得的性能，以及性能占平台峰值性能的比例。 第3 页 国防科学技术大学研究生院硕士学位论文 枷 枷 3 0 0 捌 著枷 甚 m 口 0“胥“ 图13 矩阵乘运算在g p u 和c p u 上的性能对比图 加速迭代法求解线性系统方面，l u cb u a t o i s 2 1 j 在文章中讨论了g p u 编程技术和如何高 效使用g p u 上a p i 的方法。他们把行压缩存储格式( c s r ) o 应用在一般形式的稀疏矩 阵中，在a m d - a t ix 1 9 0 0 x t xg p u 上对共轭梯度( c o ) 迭代算法进行了加速，在单精 度条件下取得了7 g f l o p s 的性能，与c p u 上性能相比取得了6 倍的加速比。文章中没有实 现双精度的算法也没有涉发算法存多g p u 平台的实现方法。 n a t h a nb e l l 和m i c h a e lg 州a n d 在文章中对包括结构化和非结构化的多种稀疏矩阵与 向量乘运算在g p u 上的加速进行了讨论，文中采用特定的格式和计算方法来提高性能。 他们所处理的对角线格式( d i a g o n a lf o r m a t ) 稀疏矩阵与本文算法处理的稀疏矩阵比较相 似，他们在n v i d i a g e f o r c e g t x2 8 0 g p u 上的性能( 双精度) 达到1 1 g f l o p s 。由于稀疏 矩阵和向量乘是迭代法求解中的部分计算过程，文章投有详细论述如何在迭代法等算法中 有效实现该过程。 国内中科院、国防科技大学等科研院所也对g p u 加速科学计算开展了探索研究，在 很多不同领域取得了成果。中国科学院计算机刚络信息中心超级计算中心研究了流体力学 中b e n c h m a r k 问题的二维扩散方程在g p u 上的加速口”，他们有效利用了全局存储和纹理 存储，在单精度条件下与c p u 相比取得了3 4 倍的加速比。国防科技大学近期举办了2 0 0 9 年全国高性能计算学术年会会中专门对g p u 技术进行丁讨论。其中中国t o p l 0 0 2 5 1 的第 一名，由国防科技大学研制的“灭河一号”就是采用的c p u + g p u 异构体系结构。 1 3 面临的挑战 当前在稀疏线性系统求解方面的研究中，一般处理的迭代法比较简单，选代周期较长， 在双精度条件下g p u 的性能与c p u 相比优势不明显。同时存在很少工作研究多种g p u 平 台以及在包括多个g p u 的平台上加速选代法。在实际应用中，很多在c p u 上高度并行的 程序可以直接移植到g p u 上，这些程序处理的数据比较规整，处理的算法比较简单，一 般适合于g p u 上的s i m d 结构。然而，求解大型稀疏线性系统时需要解决一些复杂的问 第4 页 国防科学技术大学研究生院硕士学位论文 题。本文通过分析认为g p u 加速迭代法求解稀疏线性系统具有以卜挑战： l 、稀疏矩阵的处理及数据传递方式 稀疏线性系统中的数据( 稀疏矩阵) 包含了大量冗余的数据，不经过处理会浪费大量 的存储资源，数据需要进行预处理才能高效计算，这就需要根据稀疏矩阵的特点选择合适 的处理方法。其次是迭代过程中会产生大量无用的中间数据，这些数据在c p u 和g p u 之 间来回传递造成大量的通信开销，所以需要根据算法特点设计合适的数据传递方式。 2 、计算核心的划分方法 加速迭代法首先需要把算法的公式实现为g p u 上的计算核心，不恰当的划分计算核 心会造成大量的启动开销和数据重用性的降低。需要分析计算核心的组织方式对启动开销 和数据重用性的影响，从而设计高效的计算核心划分方法。 3 、n v i d i ag p u 上归约操作的实现 归约操作在算法中具有重要的作用，需要用来计算向量乘、矩阵向量乘以及误差，对 于算法的性能具有重要的影响。由于n v i d i ag p u 平台上没有提供归约操作的函数，需要 研究归约操作的实现方法。 4 、针对不同g p u 平台的优化 当前的两种主流g p u ，n v i d i ag p u 和a m dg p u 具有不同的体系结构和编程模型， 不同的优化方法在两种g p u 平台上会产生不同的效果。所以需要对两种g p u 平台进行深 入的分析，确定针对不同g p u 平台的优化方法。 5 、算法在多核c p u + 多g p u 平台上的实现 在多核c p u + 多g p u 平台上实现本文算法首先要把计算任务平均的分配到各个计算单 元中，这需要设计多g p u 平台上的任务分配方法。其次要处理多g p u 之间的数据通信， 数据通信的开销影响着整个系统的性能。由于很少研究涉及多g p u 平台中的数据通信问 题，如何减少数据通信开销成为本文的又一个挑战。 1 4 本文研究内容和创新 本文主要以在g p u 上加速p q m r c g s t a b 迭代算法求解稀疏线性系统为研究对象， 分析了算法在移植过程中遇到的问题，探讨了提高算法性能的多种方法，在两种不同的 g p u 平台上实现了p q m r c g s t a b 算法。 本文的主要研究内容为： l 、研究带状稀疏矩阵的特点，找到适合在g p u 上处理稀疏矩阵的方法。分析c p u 与 g p u 之间的数据通信，研究减少数据传递开销的方法。 2 、分析计算核心的组织方式对启动开销和数据重用性的影响，研究减少启动开销和 增加数据重用性的有效方法，确定计算核心的划分方案。 3 、研究n v i d i ag p u 体系结构和编程模型的特点，分析归约操作的特点，在n v i d i a 第5 页 国防科学技术大学研究牛院硕上学位论文 g p ui f 台上实现岛效的归约操作。 4 、针对n v i d i ag p u 和a m dg p u 体系结构和编程模型的特点，研究与g p u 平台相 关的优化方法。 5 、研究在