LINPACK算法及其测试方法改进_图文

1、CN431258/TP ISSN 1007130X计算机工程与科学COMPUTER ENGINEERING&SCIENCE2008年第30卷第A1期 V01.30。No.A1,2008文章编号:1007130X(2008A1003204LINPACK LINPACK and the 算法及其测试方法Improvement of Its改进。乃st Method司照凯。濮晨Sl Zhao-kai。PU Chen(江南计算技术研究所,江苏无锡214083(Jiangnan Institute of Computing Technology.Wuxi 214083,China摘要:HPL(H

2、igh Performance LINPACK是一种用来测试计算机浮点性能的基准测试程序,通过求解稠密线性方 程组来评估计算机的浮点性能。本文分析了HPL的核心算法,并对HPL的计时系统进行改进,提出了一种新的基于计 时系统的测试方法,以达到快速完成LINPACK测试的目的,实验证明这种新的测试方法很有效。Abstract:HPL(High Performance I.INPACKis a benchmark used tO measure the computers float point perform ance,it reaches this by solving a random li

3、near system in double precision.In this paper,we introduce the HPI。S algo rithm,and improve its timing system,then put forward a LINPACK test method:Timing System based LINPACK Test Method,which can help tO accelerate the LINPACK test.Theexperiment shows that this new way is helpful.关键词:高性能;LINPACK;

4、BLAS;MPl;L,U factorizationKey words:high performance LINPACK;BLAS;MPl;LU factorization中图分类号:TP309文献标识码:A1引言LINPACK是当前评测计算机浮点性能的基准测试程 序,TOP500a是根据计算机的LINPACK性能来进行排 名。LINPACK根据矩阵规模可以分为100×100,1000×1000和N×N三种“,本文分析的High Pedormanee LIN-PACK(HPL属于N×N这一类。HPL由八Petitet,R C Whaley,J.Donga

5、rra和A Cleary开发,它通过求解一个稠密线性方程组(Random Dense Linear System of Equations来测试计算机的LIN-PACK性能。本文使用的是HPL 1.0a,2004年发布的一 个版本。2HPL理论基础HPL通过求解一个稠密线性方程组来测试计算机的 LINPACK性能2|,如(1式所示:Ax=b (1 其中,A=(粕N×N且为非奇异矩阵,b=(bl,bz,bN7,x =(x1,毪,xN7,A与b均为已知,而x是待求的N维列 向量。统计求解(1式的时间,并且利用(2式来计算浮点速 率:R:2N3/3鬲-I-3N2一/2×101GF

6、LOPS (2 HPL式(2中2N3/3+3N272是浮点运算规模,T嘲,是 HPL执行时间。得到浮点速率R后,和峰值RpDuc相除,就 是这台计算机的LINPACK执行效率呀。HPL在求解(1式的时候,先对矩阵A进行LU分解 (LU Factorization,得到一个上三角矩阵U和一个下三角 矩阵L,并且A等于这两个矩阵的乘积,以方便方程的求 解,这个过程就是LU分解。常用的因式分解方法还有QR 分解和Cholesky分解,由于HPL采用的是I。U分解,所以 我们重点分析一下HPL中LU分解的实现方式。LU分解的形式有三种:Right-looking LU Faetoriza tion、L

7、eft-looking LU Faetorization和Crout-looking LU Factorization,它们之间的区别主要体现在panel内LU分 解以及尾矩阵更新的执行顺序不同HPI。中的I。U分解采用分块的形式实现,将数据分块 映射到处理器网格中,以达到均衡负载的目的。分块的大 小为NBX NB,同一列上的块组成一个panel。HPL实现收稿日期:2008-04-13;修订日期:200807一10Address:Jiangnan Institute of Computing Technology,Wu】(i,Jiangsu 214083,P.R China32的时候先对pa

8、nel内的数据进行LU分解,然后对尾矩阵进 行更新,也就是update操作。得到L矩阵和U矩阵之后, 再求出方程的解x,并且计算误差。对panel内的数据进行 LU分解是通过Panel Factorization(PFACT和Recursive Panel Factorization(RPFACT协作完成4,PFACT和RP FACT均有Rightlooking LU Factorization、Left-looking LU Factorization和Crout-looking LU Factorization三种实 现形式。在后面的实验中我们发现,这些参数对LIN PACK性能的影响不大

9、。HPL的运行还需要Message Passing Interface(MPI 和Basic Linear Algebra Subroutines(131,AS或者Vector Signal Image Processing Library(VSIPL的配合。MPI主 要用来进行各个处理器之间的通信,BLAS和VSIPL为 UJ分解提供各种矩阵或者向量运算函数。3LINPACK测试方法HPL执行的时间比较长,特别是当矩阵规模比较大的 时候,而且I,INPACK性能受各种软硬件因素以及HPL执 行参数的影响很大,所以想取得一个较佳的结果,需要有一 套合理的测试方法,不能盲目进行。3.1影响LIN

10、PACK性能的因素LINPACK性能主要受三个因素的影响。分别是硬件 因素、软件因素和HPL执行参数。I硬件因素硬件因素主要包括cache大小和存储系统结构、访存 速度、处理器性能、计算机系统的结构以及互连网络的性能 等,这些因素都会影响机器的LINPACK性能。软件因素软件因素主要指的是MPI和BLAS对HPL性能的影 响。MPI常用的有LAMMPI、MPICH和OpenMPI,这三 种MPI的性能不一样,有些针对一些特殊的结构(如 SNIP会进行优化。BLAS也有Automatically Tuned Linear Algebra Soft ware(ATLAS、GotoBLAS、Engi

11、neering and Scientific Sub-routine Library(ESSL、Intel Math Kernel Library(MKL 和AMD CoreMath Library(ACML,其中ESSL、MKL和 ACML分别由IBM、Intel和AMD开发,并且对各自的处 理器支持比较好。选择哪种BLAS,不仅要参考计算机硬 件类型,还要通过实验分析3。编译器的选择也有很大关系,文献分析了两个版本的 gee编译器对LINPACK性能的影响。HPL执行参数HPL执行参数很多,在文件“HPL.dat”中进行设置, 其中对LINPACK性能影响比较大的是P×Q、N和心

12、51 (PXQ是处理器网格的排列形式,N是矩阵规模,NB是矩 阵分块的大小,测试时需要不断的进行调整。由于硬件一般比较固定,所以我们在做LINPACK测 试时主要调整的是软件以及HPL执行参数。3.2LINPACK测试方法为了提高测试速度,有几种比较有效的测试方法,文献5和文献Ca分析了几种加快测试的方法。文献sJ根据各参数对LINPACK性能影响的大小,将 其分为A类参数和B类参数。A类参数包括P×Q、N和 NB,其他参数都是B类参数。A类参数对LINPACK性能 影响很大,B类参数影响较小。所以测试的时候先找到最 佳的P×Q,再确定最佳的N,然后是NB,当三个A类参数

13、定下来之后,再确定B类参数。文献6根据定义为矩阵运算时间与其运算量之比的效 率因子很大程度上相关于矩阵分块大小,而与矩阵规模本 身关系微乎其微这一规律,通过扫描小规模矩阵运算效率, 来确定大规模并行测试中分块大小NB,以达到缩短测试 时间的目的。上面两种测试方法都比较有效,但是它们都只把IAN-PACK的浮点速率作为唯一的评判基准。而忽略了很多细 节,比如通信时间的比重,矩阵运算时间的比重等等。为了 更好的进行LINPACK测试,需要提取更为丰富的信息。 本文提出了一种新的基于计时系统的测试方法。对原 有的HPL计时系统进行改进,提取更加丰富的关键时间 参数。通过计时系统,可以快速定位最佳测试

14、平台软硬件 配置和HPL执行参数,以达到快速完成LINPACK测试的 目的。4HPL计时系统从(2式中可以看出,HPL执行时间THPL越短,浮点执 行速率就越高。所以我们对THPL进行深入分析,并且从中 找出影响LINPACK效率的因素。4.1HPL执行时间分析假设内存空间足够,不发生交换,不考虑cache缺失, HPL的执行时间可以粗略的表示为7:=卷+紫+巡盟端P(3 -其中,口表示处理器之间进行一次通信的启动时间,口表示 通信速率,7表示处理器的矩阵一矩阵浮点运算速率。 式(3中。TI帆主要由Tc,舢a和TBCAST_两部分组 成,TG嗍表示Level 3BLAS函数的执行时间,也就是

15、HPL源码里的GEMM函数。T阢sr L册指的是广播通信 的时间。一2N3 1删2丽 047 k一一=紫+巡盟瑞攀 (5 主要受BI。AS函数库和cache缺失率的影响,所 以可以根据这个时间参数来选取合适的BLAS库和NB大 小。TBcmr_taswP主要受互联网路结构、P×Q、广播算法和 MPI的影响,所以可以根据这个时间参数来选取较优的互 联网络、MPI库、P×Q和广播算法等。本文提出的基于计 时系统的测试方法正是基于以上理论基础,通过计时系统 来尽快确定影响LINPACK性能的关键因素。4.2原有HPL计时系统HPL本身已经提供了一套计时系统,对6个时间参数 33进

16、行了统计,每个处理器都有自己对6个时问参数的统计 信息,HPI,还会把各个处理器中6个参数的最大值提取出 来。虽然计时系统最后只得到6个最大值,但是由于算法 的均衡性较好,所以不同处理器各项时间参数的取值相差 不大。这6个时I日】参数分别是:HPL_TIMING RPFACT:表示panel内LU分解的执 行时问总和。HII._TIMING_PFACT:表示PFACT的执行时间,这 个时间参数被HPL_TIMING_RPFACT所包含,是它的一 个子集。HPI.TIMINGMXSWP:表示panel内LU分解时, panel内行交换的执行时间。HPL_TIMINGUPDATE:表示update

17、函数(update 函数用来对尾矩阵进行更新的执行时间。HPI._TIMING_I。ASWP:表示update操作时行交换的 执行时间。HPL_TIMING_PTRSV:表示上三角方程求解的执行 时间。这个计时系统存在很多不足之处。首先,它没有反映 出广播通信的时间,但是当P×Q选取不同,广播算法、互 联网络和MPI函数选取不一样的时候,广播通信时间所占 的比重差异很大;其次,HPLTIMINGUPDATE时间参 数是update的执行时间,但是在update函数内也有很多广 播通信的发生,所以这个时间不能准确对应Tt;咖a。为r使提取的时间参数更好的和h、k柳一一 对应.我们对HP

18、I?进行了修改,改进了它的计时系统,以 便于uNPACK测试。4.3改进后的HPL计时系统为了更好统计和TBCASr枷,我们对 系统进行了改进。L:I洲主要是由update操作中的GEMM函数执行时间组成,PFACT和RPFACT中也有 GEMM函数,但是比重il/d,可以忽略。T脚l脚由两部分组成,一部分是panel的LU分解之后,update之前的 广播通信时间,另一部分是update时行交换时间。为此,我们增加了2个时间参数:HPL_TIMING_BCAST:表示广播通信的耗时。HPL-TIMINGGEMM:表示update函数内GEMM 函数的执行时间。在HPI。源码中找到时间参数对应

19、的具体函数,在函 数执行的开始和结束都进行计时,这样就可以统计相应操 作的执行时间。新的计时系统一共提取了8个时间参数。 T(j日州对应着HPL_TIMING_GEMM,Trcssr_t.黼由HPI。 TIMING BcAST和HPI。一TIMINGLASWP组成。基于 计时系统的IJNPACK测试方法主要依据的就是这3个时 问参数。为了验证这套计时系统是否会占用过多的时间,从而 影响HPI。的执行效率,我们做了一个实验。如表1所示。分别取N=20000、N=16000和N= 10000,其它参数和配置不变,统计HPI,执行的总时间,单 位为“秒”。最后得出结论,加上计时系统对HPI。的执行效

20、 率影响甚微。34表I计时系统对HPI.的影响N 郁:蓼手统确:茹雾统平勰差5基于计时系统的LINPACK测试通过计时系统可以深入的分析I.INPACK测试的特 性。并且提供一个很好的指导。本部分讲述了基于计时系 统的LINPACK测试的一般方法,并且在一个两处理器 SMP系统的x86服务器中运用这种方法进行测试。5.1测试一般步骤第三部分总结了两种比较常用的LINPACK测试方 法,接下来将在这些方法的基础卜引入计时系统,讲述一种 新的测试方法一一基于计时系统的LINPACK测试方法。 这种方法重点关注三个时间参数,涵盖LINPACK的矩阵 运算和广播通信,通过这些时间参数来引导测试者调整软

21、 硬件配置和HPI。执行参数。基于计时系统的IJNPACK测试方法的一般步骤如 下:第一步:确定互联网络。在不同的互联网络中运行同样的HPl。程序,通过比较时间参数HPI。一TIMINGBCAST和HPL TIMING一1,ASWP确定选择哪种曩联网络。第二步:确定BI,AS,并儿提取各个BI.AS对应的性能较好的 NB值。在单处理器、N值较小、NB取值范较大的情况F进行测 试和比较,确定最佳的BI,AS函数库.时间参数HPI。一TIMING GEMM反应出BI,AS的优劣。第i步:确定MPI。P×Q取一个适中的值。通过提取时间参数 HPI。11N t-K:赴汀和HPL_TWaNG_

22、L煳VP.确定MPI库。第四步:确定P×Q。第五步:确定N。NB。第六步:确定广播算法、DEPTH以及其他HPI。的执行参数。 这就是计时系统的I。lNPACK测试方法的一般步骤, 在实际中可能根据不同的情况会稍有变化。5.2测试举例下面将运用计时系统在一个x86服务器的测试平台上 做LINPACK测试,测试平台包括软件和硬件两个方面,所 用平台的软硬件情况如表2:表2测试平台软硬件配置Proces!;0r 2×Intd(RXeon(TMCPU 2.80GHZ Level 1Cache 8KB IC,ache,8KB D娥Level 2Cache 512陆12CacheMe

23、mory 3-8GBR呲 11.2GFUPSOperating System Lintm2.4SVIPCompiler go:2.96心L HPI,1.oa删吐f台比鞍简单,11×qn肯】×2自2×1两种选 择.接r束将讲连如何n:这个平青T进行堆f计时系统的 I,INIACK测K。在我们的测试平台F,I.NIA【K的步骤如下所“; 第步:确定InAS自十试甲骨足个2址月器的SMP系垃井十处m器 2I_IJ的埔廿业4山仃进行恃昕H水需要时联阁络进 行选群。圈1q啪数据NooP×q1×1NB的取值帆3131n分别使用ATI AS和(;otoBI

24、As洲试。!i皆墅 iE=三三并H(mloBAS在NB等十128和2。6E边附蛞的点浮点建幸较快一所m埴终确定使川饰toBl,AS,第二班:确定P×Q定义为矩陴运算时俐与苴运算量之比的效率圈子租大 程度±褶差j阵分块大小.mq矩阵规模奉身关系徽乎 其礅这一规律在图2中得到骑。闰2中的数据N219300.P×Qlx 2/2×1/1×1NB的取值从31310。“oW目2#姐从田2WH看出.P×Q在种RE形式F的曲线具 有相似性.并目pxQ一1×2时比PXQ=z×1浮速率 快所m最终确定设置PXQI×2。图2的

25、实验中NB的取值范围推大,这是为T明自线的相似性.实际只要对小范周的NB进行测试就可H确定最佳P×q值,如用3Mi.R时几个NB值进行测试就町“看出P×Q一1×2时性能最佳。horiiiiiiin一!:巨!三!二=!i:E二二二二二二二二。者嵩茄苗苗薷嵛端崩苗蔷、H目3JL十NB*RTLINPACK&罔#幽5是j个参数HPLTIMING GEMM、HPI,TIMINGH:盯和HPI,TIMINGI.swP的值。在圉川tP×Q2×】时HPLTIMINGjcAST=o遗是因为panel的I.U分解之后不需要广播。从例4中可“看出P×

26、;Q1×2时的tlPI.TIMING tV:AErHPITIMNGlASWP之和与P×Q=2×】时的HPI.TIMINGI.A,SWP#异大。从固5中“看出PXQ=1×2时的 HPI。FIMIN(;GEMMP×Q2×1时的HPL TIMI、GGEMM差异也不太。在N一128的拐点处卅I一一TIMING GEMM跳跃很大,这说%这个差异主要是自BIAS导致的,与广播通信盖系凡。【2_=10巫二三二二二41b!二塑堕!笪苎目4fP×qCaRT HPL TIMINGt￥cAsr 目TIPIHMING一1ASWP:巨亘二“L一、80

27、l-,rr-,-一75:一i_ir_ilr一70L!L:一H 5日P×QtT HPI。TIMING GEMM值第i步确定MPI袁_l中的数据N=16000,P×Q=1×2.分别选用 (peraMPI、MPICH和LAMMPI进行实验,从表中可“看 出OIMnMPI的性能最佳,尤其在NB值比较小的时僻,所H最终确定使用OI*nMPI。玉互j四里堕庄盟也型L卫望咝垡塑LHPL TIMINGBCAST(#(k“MPIMPICH I.A:VfMPI 11087111931619114g40145182l11891z 119917141885L121770I 271059L

28、260195Z 12R10B L L;84L750130LO7016311774NB240131 1847209424815B41715zO 8l 25614671951210426015111803%413687225279937519312202Z77439022%z8313039堕墼些业L生盟上卫第口步确定N,NB眦及其他参数提高N值,并且对第一步得到的几十较优NB进行测试.调节其他参救,得到最终的鞋佳值。通过多趺宴验,如 表4所示.最佳的浮点速率是8608Gflops。墨L丑土垫量鲍曼蓝堕墨一T/VNNBP×0Gflops WROCK:2R8192001201x 28601W

29、ROOC2R891281×28608WRgaC2R8202241281×28542WR眦2R8192001121×2&17B WR0X2R81g 2001041×2R445T#*44i至换。本文借助这些转换函数解决C中浮点数向VHDL中 标准位stdlogic vector的转换。在具体实现时,首先分别 将有效数字和小数点后的有效数字位数转换成整数,然后 调用conv_stdlogicvector(ARGinteger转换函数,将整 数转换为标准逻辑向餐。对应设置stdlogicvector中的每 一位,注意第七位设置为l。当两个浮点数在进行运算

30、 时,首先判断两个浮点数向龟的后七位是否相同,如果相 同,直接对有效数进行预算即叮,否则就要调整两个浮点数 的后七位,以两者的后七位中最大者为基准进行调整,然后 两者再进行运算。4结束语HTTM虽然能够初步实现软件任务到硬件任务的转 换。但日前仍存在一些n】题。首先它对输入的ANSI C源 语言还有所限制.即不支持指针、嵌套调用、case-switch控 制语句。然后就是HTTM在生成硬件任务通信接口时效 率不是很高。最后就是HTTM中用到的并行分析方法目 前还只适用于特定的一类问题,即list homomorphism问 题,目前还不具有通用性。本文设计了一个软硬件混合任务转换模型,并研究了

31、 相应的转换算法。论文研究初步实现了软件任务和硬件任 务之间的转换。考虑到该模型的具体应用,项目组正在进 行基于可重构计算的实时操作系统平台的研究工作.该模 型的具体研究和关键技术将被应用到该平台,HTTM将对 降低混合系统的设计周期和提高系统的运行效率方面会起 到积极的促进作用。参考文献:1-13G De,Micheli and D-Ku.A System for High-level Synthe sisI-C/Proe of 25th ACM/IEEE Design Automation Conf, 1988:483-488.2Hallberg J,Peng乙Synthesis unde

32、r Local Timing Con straints in the CAMAD High-Level Synthesis SystemiC/ Proc of IEEE EUR(MICRO95,1995:150-166.IsG E Marchioro,J.M Daveau,T.K Trandommional Patti tioning Or Codesi噼x IEE Proceedings on Comlmlters and Digital Techniques。VoL 145Na 3,May 1998。181195.4Saul J肌Programming Research Group.Har

33、dware/Soft ware Codesign for FPGA-Based Systems.IEEE Proceedings of the 32nd Hawaii International Conference on System Sci ences,2000。3040-3046.5Sobha Sankaran,Dr.Roger L Haggard.A Convenient Methodology for Efficient Translation of C tO VHDL IEEE, 2001,203-207.(上接第35页这样就完成了2处理器SMP系统的LINPACK测试, 浮点效率

34、为:刁:彳8.r60了87686.刁2币万一44这个实验中处理器只有两个,PxQ配置方式只有两 种,广播方式能够选择的配置方式少,不存在跨越网卡的通 信。所有的这些都限制了计时系统作用的发挥,使得某些 数据不够直观,甚至一些功能得不到表现。比如计时系统 可以用于选择广播算法;当处理器数目较多的时候,计时系 统对PXQ的确定也会有更好的指导作用;计时系统在确 定互连网络结构的时候也很有用途。所以在大机群系统 中,计时系统有着很大的潜力。6结束语本文通过对计时系统进行改进,提出了一种基于计时 系统的IJNPACK测试方法。这种测试方法可以提取详细 的时间参数,更好地引导LINPACK的快速测试。文中分 析了这种测