批量厄米矩阵特征值分解的GPU算法_黄荣锋.pdf
《批量厄米矩阵特征值分解的GPU算法_黄荣锋.pdf》由会员分享,可在线阅读,更多相关《批量厄米矩阵特征值分解的GPU算法_黄荣锋.pdf(7页珍藏版)》请在咨信网上搜索。
1、h t t p:/ww w.j s j k x.c o mD O I:1 0.1 1 8 9 6/j s j k x.2 2 0 1 0 0 2 3 21)h t t p s:/d o c s.n v i d i a.c o m/c u d a/p d f/c u b l a s _L i b r a r y.p d f2)h t t p s:/g i t h u b.c o m/R O C m S o f t w a r e P l a t f o r m/r o c B L A S3)h t t p:/i c l.c s.u t k.e d u/m a g m a/4)h t t p s:
2、/g i t h u b.c o m/e c r c/k b l a s-g p u到稿日期:2 0 2 2-0 1-2 5 返修日期:2 0 2 2-0 8-2 4基金项目:国家重点研发计划(2 0 1 7 Y F B 0 2 0 2 2 0 2);中国科学院战略性先导科技专项(X D C 0 5 0 0 0 0 0 0)T h i sw o r kw a ss u p p o r t e db yt h eN a t i o n a lK e yR e s e a r c ha n dD e v e l o p m e n tP r o g r a mo fC h i n a(2 0 1
3、7 Y F B 0 2 0 2 2 0 2)a n dS t r a t e g i cP r i o r i t yR e s e a r c hP r o g r a mo fC h i n e s eA c a d e m yo fS c i e n c e s(X D C 0 5 0 0 0 0 0 0).通信作者:赵永华(y h z h a o s c c a s.c n)批量厄米矩阵特征值分解的G P U算法黄荣锋1,2刘世芳1,2赵永华11中国科学院计算机网络信息中心 北京1 0 0 0 8 02中国科学院大学 北京1 0 0 0 8 0(h r f s c c a s.c n)
4、摘 要 批量矩阵计算问题广泛存在于科学计算与工程应用领域。随着性能的快速提升,G P U已成为解决这类问题的重要工具之一。矩阵特征值分解属于双边分解,需要使用迭代算法进行求解,不同矩阵的迭代次数可能不同,因此,在G P U上设计批量矩阵的特征值分解算法比设计L U分解等单边分解算法更具挑战性。文中针对不同规模的矩阵,基于J a c o b i算法设计了相应的批量厄米矩阵特征值分解G P U算法。对于共享内存无法存储的矩阵,采用矩阵“块”操作技术提升计算强度,从而提高G P U的资源利用率。所提算法完全在G P U上运行,避免了C P U与G P U之间的通信。在算法实现上,通过k e r n
5、e l融合减少了k e r n e l启动负载和全局内存访问。在V 1 0 0G P U上的实验结果表明,所提算法优于已有工作。R o o f l i n e性能分析模型表明,文中给出的实现已接近理论上限,达到了4.1 1 T F L O P S。关键词:厄米矩阵;特征值分解;批量计算;R o o f l i n e模型;性能分析中图法分类号 T P 3 0 1 B a t c h e dE i g e n v a l u eD e c o m p o s i t i o nA l g o r i t h m s f o rH e r m i t i a nM a t r i c e so n
6、G P UHUAN GR o n g f e n g1,2,L I US h i f a n g1,2a n dZ HA OY o n g h u a11C o m p u t e rN e t w o r kI n f o r m a t i o nC e n t e r,C h i n e s eA c a d e m yo fS c i e n c e s,B e i j i n g1 0 0 0 8 0,C h i n a2U n i v e r s i t yo fC h i n e s eA c a d e m yo fS c i e n c e s,B e i j i n g1
7、0 0 0 8 0,C h i n a A b s t r a c t B a t c h e dm a t r i xc o m p u t i n gp r o b l e m sa r ew i d e l ye x i s t e d i ns c i e n t i f i cc o m p u t i n ga n de n g i n e e r i n ga p p l i c a t i o n s.W i t hr a p i dp e r f o r m a n c e i m p r o v e m e n t s,G P Uh a sb e c o m ea n i
8、m p o r t a n t t o o l t os o l v es u c hp r o b l e m s.T h ee i g e n v a l u ed e c o m p o s i t i o nb e l o n g s t ot h et w o-s i d e dd e c o m p o s i t i o na n dm u s t b e s o l v e db y t h e i t e r a t i v e a l g o r i t h m.I t e r a t i v en u m b e r s f o r d i f f e r e n tm
9、a t r i c e s c a nb ev a r i e d.T h e r e f o r e,d e s i g n i n ge i g e n v a l u ed e c o m p o s i t i o na l g o r i t h m sf o rb a t c h e dm a t r i c e so nt h eG P Ui sm o r ec h a l l e n g i n gt h a nd e s i g n i n gb a t c h e da l g o r i t h m s f o r t h eo n e-s i d e dd e c o
10、m p o s i t i o n,s u c ha sL Ud e c o m p o s i t i o n.T h i sp a p e rp r o p o s e sb a t c h e da l g o r i t h m sb a s e do nt h eJ a c o b ia l g o r i t h m sf o re i g e n v a l u ed e c o m p o s i t i o no fH e r m i t i a n m a t r i c e s.F o rm a t r i c e st h a tc a n n o tr e s i d
11、 ei ns h a r e d m e m o r yw h o l l y,t h eb l o c kt e c h n i q u ei su s e dt oi m p r o v et h ea r i t h m e t i ci n t e n s i t y,t h u si m p r o v i n gt h eu s eo fG P Ur e s o u r c e s.A l g o r i t h m sp r e s e n t e d i nt h i sp a p e rr u nc o m p l e t e l yo nt h eG P U,a v o i
12、 d i n gt h ec o mm u n i c a t i o nb e t w e e nt h eC P Ua n dG P U.K e r n e l f u s i o ni sa d o p t e dt od e c r e a s e t h eo v e r h e a do f l a u n c h i n gk e r n e l a n dg l o b a lm e m o r ya c c e s s.E x p e r i m e n t a l r e s u l t so nV 1 0 0G P Us h o wt h a to u ra l g o
13、r i t h m sa r eb e t t e r t h a ne x i s t i n gw o r k s.P e r f o r m a n c e e v a l u a t i o nr e s u l t so f t h eR o o f l i n em o d e l i n d i c a t e t h a t o u r i m p l e m e n t a-t i o n sa r ec l o s e t ot h eu p p e rb o u n d,a p p r o a c h i n g4.1 1 T F L O P S.K e y w o r
14、d s H e r m i t i a nm a t r i x,E i g e n v a l u ed e c o m p o s i t i o n,B a t c hc o m p u t i n g,R o o f l i n em o d e l,P e r f o r m a n c ee v a l u a t i o n 1 引言批量矩阵计算问题广泛存在于机器学习、计算机视觉、天体物理学等领域1-4。对于多核C P U,这类问题的求解相对容易。例如结合O p e n MP和高度优化的L A P A C K/B L A S库(如MK L,o p e n B L A S)即可获得
15、较好的性能,因为许多计算可以在C P U的高速缓存中进行。然 而,由 于 缓 存 较 小,在G P U上求解批量矩阵计算问题十分困难。B L A S库是科学计算领域的基础函数库之一,库中的矩阵乘(G EMM)函数占据着核心地位。为此,许多G P U供应商提供批量G EMM的高效实现1),2),开源软件包MAGMA3)和K B L A S4)也提供批量G EMM在G P U上的实现。L A P A-C K库中函数的批量算法获得了广泛关注。例如,D o n g等5研究了批量C h o l e s k y分解;A b d e l f a t t a h等6研究了部分选主元的批量L U分解;文献7 对
16、批量矩阵计算问题的研究进行了较为全面的总结。与C h o l e s k y分解等单边分解不同,矩阵特征值分解属于双边分解,必须使用迭代算法进行求解。不同矩阵的迭代次数可能不同,因此进行批量计算的矩阵几乎不能同时收敛。当一些矩阵收敛后,计算量变小,剩余的矩阵难以充分利用G P U上的众多计算核心。因此,在G P U上设计批量矩阵的特征值分解算法更具挑战性。1)h t t p s:/d o c s.n v i d i a.c o m/c u d a/c u s o l v e r/i n d e x.h t m l特征值分解算法主要分为两类:三对角化方法和J a c o b i方法。三对角化方法
17、主要包括三步:第一步使用H o u s e h o l d e r正交变换将原始矩阵转化为三对角矩阵;第二步使用Q R迭代算法8-9、D&C算法1 0-1 1或MR R R算法1 2-1 3计算三对角矩阵的特征值分解;最后使用H o u s e h o l d e r正交变换将三对角矩阵的特征向量恢复成原始矩阵的特征向量。与之不同,J a-c o b i方法1 4-1 5无须将原始矩阵转化为三对角形式,而是直接对原始矩阵进行J a c o b i旋转。J a c o b i方法的计算量通常比三对角化方法更大,但并行性优于后者。对称矩阵特征值分解算法的时间复杂度为O(n3)(n为矩阵行数)1 6
18、,因此大规模矩阵的特征值分解算法属于计算密集型算法,可用G P U加速计算过程。E L P A-G P U库1 6与MA GMA库基于三对角化方法给出了G P U加速的大规模矩阵特征值分解算法。对于大规模矩阵,C P U与G P U之间的通信与G P U的计算能实现较好的重叠,从而隐藏通信代价。批量矩阵计算问题由于矩阵规模较小(通常不超过5 1 2),计算时间短,因此通信时间与计算时间难以重叠。在设计算法时,应尽量避免C P U与G P U之间的数据拷贝,甚至可以研究完全运行在G P U上的算法。当前对批量矩阵特征值分解的研究较少,c u S O L V E R1)提供了批量矩阵特征值分解的函
19、数,但当前只支持规模不超过3 23 2的矩阵。c u S O L V E R属于商业库,其实现细节并未对外发布。本文针对不同的矩阵规模,基于J a c o b i算法设计了相应的批量厄米矩阵特征值分解G P U算法。本文的主要贡献包括:(1)针对不超过3 23 2的矩阵,设计了共享内存算法,该算法优于c u S O L V E R库。(2)针对超过3 23 2的矩阵,设计了全局内存算法,填补了该领域的空白。(3)使用R o o f l i n e模型1 7分析了算法的实现性能,结果表明本文的实现已接近理论上限,达到了4.1 1 T F L O P S。本文第2节介绍了J a c o b i方法
20、,该方法是本文设计算法的基础;第3节介绍了针对不同矩阵规模的算法设计;第4节使用数值算例对算法进行实验验证;第5节分析算法的实现性能;最后总结全文并展望未来。2 J a c o b i方法本节介绍求解厄米矩阵的J a c o b i方法。厄米矩阵为复共轭对称矩阵,一个nn厄米矩阵A的特征值分解如下:A=QQC(1)其中,Q为nn的正交矩阵,Q的列称为A的特征向量;为nn的对角矩阵,其对角元素称为矩阵A的特征值,且按升序排列。J a c o b i方法每次从A中选择两列(如第p,q列)构造J a-c o b i旋转矩阵Jp q,并对矩阵A进行J a c o b i旋转,使其收敛于对角矩阵。因此,
21、J a c o b i方法的收敛条件为:o f f(A)=ij|ai j|23.使用R o u n d-R o b i n方法给出旋转列对(p,q)4.根据式(3)-式(5)计算Jp q5.更A的行,A=JCp qA6.更新A的列,A=AJp q7.更新Q的列,Q=QJp q8.e n dw h i l e9.计算:=A1 0.对的对角元素进行排序并交换Q对应的列由于算法1的 主 要 计 算(第5-7行)均 为 访 存 受 限(M e m o r yB o u n d)的B L A S1操作,因此,算法1属于访存受限型算法。3 基于G P U架构的算法设计为便于介绍G P U上的算法设计,本文
22、采用C UD A(C o m-p u t e rU n i f i e dD e v i c eA r c h i t e c t u r e)作为编程模型。本文的算法设计同样适用于其他G P U编程模型,如O p e n C L和H I P。首先简要介绍C UD A的一些基本概念。C U D A是一个典型的S I MT(S i n g l e I n s t r u c t i o nM u l t i p l eT h r e a d)架构,C UD A编程模型中常用的内存主要包括全局内存、共享内存以及寄存器。从全局内存到寄存器,访问延迟逐渐减小,访存带宽逐渐增加。寄存器的访问速度最快,只
23、能单线程独享。共享内存的访问延迟比寄存器内存大,但远小于全局内存的访问延迟。同一个b l o c k上的所有线程均可访问共享内存,因此,可通过共享内存实现线程间的数据交换。此外,同一个b l o c k上的线程可通过内置函数_s y n c t h r e a d s()进行同步。有效利用共享内存是在G P U上设计高效算法的关键,但共享内存属于稀缺资源,每个b l o c k可使用的共享内存至多为9 6 k B(计算能力为7.x的设备)。所有线程均可以访问全局内存,但访问延迟较大,应尽量减少对全局内存的访问。在访问全局内存时,相邻线程的访问地址也是连续的,十分有利于提升访存带宽。在C U D
24、 A中,一条FMA(F u s e dM u l t i p l yA d d)指令可以同时完成形如x=yz+w的加和乘两种运算。因此,在算法实现时,浮点运算应尽量使用FMA指令。厄米矩阵的计算为复数运算,可使用内置函数c u C f m a实现FMA指令的调用。3.1 共享内存算法对于规模较小的矩阵(如不超过3 23 2),共享内存可以容纳待分解矩阵及其特征向量。为了减少数据访问,将整个矩阵加载到共享内存进行计算,待计算完成后再将结果写回全局内存。在k e r n e l设计上,使用一个b l o c k计算一个矩阵。G r i d,b l o c k与矩阵的映射关系如图2所示。一维g r
25、i d和二维b l o c k的大小 分别 为b a t c h和(n,n/2),其 中b a t c h等 于矩阵数量。在计算时,使用一列线程实施一个列对的J a c o b i旋转。在开始J a c o b i旋转前,所有线程都计算Jp q。虽然存在冗余计算(同一列线程的p q相同),但所有线程都参与算法1中第5-7行的计算,可以提高线程利用率。图2 共享内存算法中g r i d,b l o c k与矩阵的映射F i g.2 M a p p i n gb e t w e e ng r i d,b l o c ka n dm a t r i x i ns h a r e dm e m o r
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 批量 矩阵 特征值 分解 GPU 算法 黄荣锋
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。