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的計時系統(tǒng)進行改進,提出了一種新的基于計 時系統(tǒng)的測試方法,以達到快速完成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是根據(jù)計算機的LINPACK性能來進行排 名。LINPACK根據(jù)矩陣規(guī)?？梢苑譃?00×100,1000×1000和N×N三種“,本文分析的High Pedormanee LIN-PACK(HPL屬于N×N這一類。HPL由八Petitet,R C Whaley,J.Donga

5、rra和A Cleary開發(fā),它通過求解一個稠密線性方程組(Random Dense Linear System of Equations來測試計算機的LIN-PACK性能。本文使用的是HPL 1.0a,2004年發(fā)布的一 個版本。2HPL理論基礎HPL通過求解一個稠密線性方程組來測試計算機的 LINPACK性能2|,如(1式所示:Ax=b (1 其中,A=(粕N×N且為非奇異矩陣,b=(bl,bz,bN7,x =(x1,毪,xN7,A與b均為已知,而x是待求的N維列 向量。統(tǒng)計求解(1式的時間,并且利用(2式來計算浮點速 率:R:2N3/3鬲-I-3N2一/2×101GF

6、LOPS (2 HPL式(2中2N3/3+3N272是浮點運算規(guī)模,T嘲,是 HPL執(zhí)行時間。得到浮點速率R后,和峰值RpDuc相除,就 是這臺計算機的LINPACK執(zhí)行效率呀。HPL在求解(1式的時候,先對矩陣A進行LU分解 (LU Factorization,得到一個上三角矩陣U和一個下三角 矩陣L,并且A等于這兩個矩陣的乘積,以方便方程的求 解,這個過程就是LU分解。常用的因式分解方法還有QR 分解和Cholesky分解,由于HPL采用的是I。U分解,所以 我們重點分析一下HPL中LU分解的實現(xiàn)方式。LU分解的形式有三種:Right-looking LU Faetoriza tion、L

7、eft-looking LU Faetorization和Crout-looking LU Factorization,它們之間的區(qū)別主要體現(xiàn)在panel內(nèi)LU分 解以及尾矩陣更新的執(zhí)行順序不同HPI。中的I。U分解采用分塊的形式實現(xiàn),將數(shù)據(jù)分塊 映射到處理器網(wǎng)格中,以達到均衡負載的目的。分塊的大 小為NBX NB,同一列上的塊組成一個panel。HPL實現(xiàn)收稿日期:2008-04-13;修訂日期:200807一10Address:Jiangnan Institute of Computing Technology,Wu】(i,Jiangsu 214083,P.R China32的時候先對pa

8、nel內(nèi)的數(shù)據(jù)進行LU分解,然后對尾矩陣進 行更新,也就是update操作。得到L矩陣和U矩陣之后, 再求出方程的解x,并且計算誤差。對panel內(nèi)的數(shù)據(jù)進行 LU分解是通過Panel Factorization(PFACT和Recursive Panel Factorization(RPFACT協(xié)作完成4,PFACT和RP FACT均有Rightlooking LU Factorization、Left-looking LU Factorization和Crout-looking LU Factorization三種實 現(xiàn)形式。在后面的實驗中我們發(fā)現(xiàn),這些參數(shù)對LIN PACK性能的影響不大

9、。HPL的運行還需要Message Passing Interface(MPI 和Basic Linear Algebra Subroutines(131,AS或者Vector Signal Image Processing Library(VSIPL的配合。MPI主 要用來進行各個處理器之間的通信,BLAS和VSIPL為 UJ分解提供各種矩陣或者向量運算函數(shù)。3LINPACK測試方法HPL執(zhí)行的時間比較長,特別是當矩陣規(guī)模比較大的 時候,而且I,INPACK性能受各種軟硬件因素以及HPL執(zhí) 行參數(shù)的影響很大,所以想取得一個較佳的結(jié)果,需要有一 套合理的測試方法,不能盲目進行。3.1影響LIN

10、PACK性能的因素LINPACK性能主要受三個因素的影響。分別是硬件 因素、軟件因素和HPL執(zhí)行參數(shù)。I硬件因素硬件因素主要包括cache大小和存儲系統(tǒng)結(jié)構(gòu)、訪存 速度、處理器性能、計算機系統(tǒng)的結(jié)構(gòu)以及互連網(wǎng)絡的性能 等,這些因素都會影響機器的LINPACK性能。軟件因素軟件因素主要指的是MPI和BLAS對HPL性能的影 響。MPI常用的有LAMMPI、MPICH和OpenMPI,這三 種MPI的性能不一樣,有些針對一些特殊的結(jié)構(gòu)(如 SNIP會進行優(yōu)化。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開發(fā),并且對各自的處 理器支持比較好。選擇哪種BLAS,不僅要參考計算機硬 件類型,還要通過實驗分析3。編譯器的選擇也有很大關系,文獻分析了兩個版本的 gee編譯器對LINPACK性能的影響。HPL執(zhí)行參數(shù)HPL執(zhí)行參數(shù)很多,在文件“HPL.dat”中進行設置, 其中對LINPACK性能影響比較大的是P×Q、N和心

12、51 (PXQ是處理器網(wǎng)格的排列形式,N是矩陣規(guī)模,NB是矩 陣分塊的大小,測試時需要不斷的進行調(diào)整。由于硬件一般比較固定,所以我們在做LINPACK測 試時主要調(diào)整的是軟件以及HPL執(zhí)行參數(shù)。3.2LINPACK測試方法為了提高測試速度,有幾種比較有效的測試方法,文獻5和文獻Ca分析了幾種加快測試的方法。文獻sJ根據(jù)各參數(shù)對LINPACK性能影響的大小,將 其分為A類參數(shù)和B類參數(shù)。A類參數(shù)包括P×Q、N和 NB,其他參數(shù)都是B類參數(shù)。A類參數(shù)對LINPACK性能 影響很大,B類參數(shù)影響較小。所以測試的時候先找到最 佳的P×Q,再確定最佳的N,然后是NB,當三個A類參數(shù)

13、定下來之后,再確定B類參數(shù)。文獻6根據(jù)定義為矩陣運算時間與其運算量之比的效 率因子很大程度上相關于矩陣分塊大小,而與矩陣規(guī)模本 身關系微乎其微這一規(guī)律,通過掃描小規(guī)模矩陣運算效率, 來確定大規(guī)模并行測試中分塊大小NB,以達到縮短測試 時間的目的。上面兩種測試方法都比較有效,但是它們都只把IAN-PACK的浮點速率作為唯一的評判基準。而忽略了很多細 節(jié),比如通信時間的比重,矩陣運算時間的比重等等。為了 更好的進行LINPACK測試,需要提取更為豐富的信息。 本文提出了一種新的基于計時系統(tǒng)的測試方法。對原 有的HPL計時系統(tǒng)進行改進,提取更加豐富的關鍵時間 參數(shù)。通過計時系統(tǒng),可以快速定位最佳測試

14、平臺軟硬件 配置和HPL執(zhí)行參數(shù),以達到快速完成LINPACK測試的 目的。4HPL計時系統(tǒng)從(2式中可以看出,HPL執(zhí)行時間THPL越短,浮點執(zhí) 行速率就越高。所以我們對THPL進行深入分析,并且從中 找出影響LINPACK效率的因素。4.1HPL執(zhí)行時間分析假設內(nèi)存空間足夠,不發(fā)生交換,不考慮cache缺失, HPL的執(zhí)行時間可以粗略的表示為7:=卷+紫+巡盟端P(3 -其中,口表示處理器之間進行一次通信的啟動時間,口表示 通信速率,7表示處理器的矩陣一矩陣浮點運算速率。 式(3中。TI帆主要由Tc,舢a(chǎn)和TBCAST_兩部分組 成,TG嗍表示Level 3BLAS函數(shù)的執(zhí)行時間,也就是

15、HPL源碼里的GEMM函數(shù)。T阢sr L冊指的是廣播通信 的時間。一2N3 1刪2麗 047 k一一=紫+巡盟瑞攀 (5 主要受BI。AS函數(shù)庫和cache缺失率的影響,所 以可以根據(jù)這個時間參數(shù)來選取合適的BLAS庫和NB大 小。TBcmr_taswP主要受互聯(lián)網(wǎng)路結(jié)構(gòu)、P×Q、廣播算法和 MPI的影響,所以可以根據(jù)這個時間參數(shù)來選取較優(yōu)的互 聯(lián)網(wǎng)絡、MPI庫、P×Q和廣播算法等。本文提出的基于計 時系統(tǒng)的測試方法正是基于以上理論基礎,通過計時系統(tǒng) 來盡快確定影響LINPACK性能的關鍵因素。4.2原有HPL計時系統(tǒng)HPL本身已經(jīng)提供了一套計時系統(tǒng),對6個時間參數(shù) 33進

16、行了統(tǒng)計,每個處理器都有自己對6個時問參數(shù)的統(tǒng)計 信息,HPI,還會把各個處理器中6個參數(shù)的最大值提取出 來。雖然計時系統(tǒng)最后只得到6個最大值,但是由于算法 的均衡性較好,所以不同處理器各項時間參數(shù)的取值相差 不大。這6個時I日】參數(shù)分別是:HPL_TIMING RPFACT:表示panel內(nèi)LU分解的執(zhí) 行時問總和。HII._TIMING_PFACT:表示PFACT的執(zhí)行時間,這 個時間參數(shù)被HPL_TIMING_RPFACT所包含,是它的一 個子集。HPI.TIMINGMXSWP:表示panel內(nèi)LU分解時, panel內(nèi)行交換的執(zhí)行時間。HPL_TIMINGUPDATE:表示update

17、函數(shù)(update 函數(shù)用來對尾矩陣進行更新的執(zhí)行時間。HPI._TIMING_I。ASWP:表示update操作時行交換的 執(zhí)行時間。HPL_TIMING_PTRSV:表示上三角方程求解的執(zhí)行 時間。這個計時系統(tǒng)存在很多不足之處。首先,它沒有反映 出廣播通信的時間,但是當P×Q選取不同,廣播算法、互 聯(lián)網(wǎng)絡和MPI函數(shù)選取不一樣的時候,廣播通信時間所占 的比重差異很大;其次,HPLTIMINGUPDATE時間參 數(shù)是update的執(zhí)行時間,但是在update函數(shù)內(nèi)也有很多廣 播通信的發(fā)生,所以這個時間不能準確對應Tt;咖a。為r使提取的時間參數(shù)更好的和h、k柳一一 對應.我們對HP

18、I?進行了修改,改進了它的計時系統(tǒng),以 便于uNPACK測試。4.3改進后的HPL計時系統(tǒng)為了更好統(tǒng)計和TBCASr枷,我們對 系統(tǒng)進行了改進。L:I洲主要是由update操作中的GEMM函數(shù)執(zhí)行時間組成,PFACT和RPFACT中也有 GEMM函數(shù),但是比重il/d,可以忽略。T腳l腳由兩部分組成,一部分是panel的LU分解之后,update之前的 廣播通信時間,另一部分是update時行交換時間。為此,我們增加了2個時間參數(shù):HPL_TIMING_BCAST:表示廣播通信的耗時。HPL-TIMINGGEMM:表示update函數(shù)內(nèi)GEMM 函數(shù)的執(zhí)行時間。在HPI。源碼中找到時間參數(shù)對應

19、的具體函數(shù),在函 數(shù)執(zhí)行的開始和結(jié)束都進行計時,這樣就可以統(tǒng)計相應操 作的執(zhí)行時間。新的計時系統(tǒng)一共提取了8個時間參數(shù)。 T(j日州對應著HPL_TIMING_GEMM,Trcssr_t.黼由HPI。 TIMING BcAST和HPI。一TIMINGLASWP組成。基于 計時系統(tǒng)的IJNPACK測試方法主要依據(jù)的就是這3個時 問參數(shù)。為了驗證這套計時系統(tǒng)是否會占用過多的時間,從而 影響HPI。的執(zhí)行效率,我們做了一個實驗。如表1所示。分別取N=20000、N=16000和N= 10000,其它參數(shù)和配置不變,統(tǒng)計HPI,執(zhí)行的總時間,單 位為“秒”。最后得出結(jié)論,加上計時系統(tǒng)對HPI。的執(zhí)行效

20、 率影響甚微。34表I計時系統(tǒng)對HPI.的影響N 郁:蓼手統(tǒng)確:茹霧統(tǒng)平勰差5基于計時系統(tǒng)的LINPACK測試通過計時系統(tǒng)可以深入的分析I.INPACK測試的特 性。并且提供一個很好的指導。本部分講述了基于計時系 統(tǒng)的LINPACK測試的一般方法,并且在一個兩處理器 SMP系統(tǒng)的x86服務器中運用這種方法進行測試。5.1測試一般步驟第三部分總結(jié)了兩種比較常用的LINPACK測試方 法,接下來將在這些方法的基礎卜引入計時系統(tǒng),講述一種 新的測試方法一一基于計時系統(tǒng)的LINPACK測試方法。 這種方法重點關注三個時間參數(shù),涵蓋LINPACK的矩陣 運算和廣播通信,通過這些時間參數(shù)來引導測試者調(diào)整軟

21、 硬件配置和HPI。執(zhí)行參數(shù)。基于計時系統(tǒng)的IJNPACK測試方法的一般步驟如 下:第一步:確定互聯(lián)網(wǎng)絡。在不同的互聯(lián)網(wǎng)絡中運行同樣的HPl。程序,通過比較時間參數(shù)HPI。一TIMINGBCAST和HPL TIMING一1,ASWP確定選擇哪種曩聯(lián)網(wǎng)絡。第二步:確定BI,AS,并兒提取各個BI.AS對應的性能較好的 NB值。在單處理器、N值較小、NB取值范較大的情況F進行測 試和比較,確定最佳的BI,AS函數(shù)庫.時間參數(shù)HPI。一TIMING GEMM反應出BI,AS的優(yōu)劣。第i步:確定MPI。P×Q取一個適中的值。通過提取時間參數(shù) HPI。11N t-K:赴汀和HPL_TWaNG_

22、L煳VP.確定MPI庫。第四步:確定P×Q。第五步:確定N。NB。第六步:確定廣播算法、DEPTH以及其他HPI。的執(zhí)行參數(shù)。 這就是計時系統(tǒng)的I。lNPACK測試方法的一般步驟, 在實際中可能根據(jù)不同的情況會稍有變化。5.2測試舉例下面將運用計時系統(tǒng)在一個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計時系統(tǒng)的 I,INIACK測K。在我們的測試平臺F,I.NIA【K的步驟如下所“; 第步:確定InAS自十試甲骨足個2址月器的SMP系垃井十處m器 2I_IJ的埔廿業(yè)4山仃進行恃昕H水需要時聯(lián)閣絡進 行選群。圈1q啪數(shù)據(jù)NooP×q1×1NB的取值帆3131n分別使用ATI AS和(;otoBI

24、As洲試。!i皆墅 iE=三三并H(mloBAS在NB等十128和2。6E邊附蛞的點浮點建幸較快一所m埴終確定使川飾toBl,AS,第二班:確定P×Q定義為矩陴運算時俐與苴運算量之比的效率圈子租大 程度±褶差j陣分塊大小.mq矩陣規(guī)模奉身關系徽乎 其礅這一規(guī)律在圖2中得到騎。閏2中的數(shù)據(jù)N219300.P×Qlx 2/2×1/1×1NB的取值從31310?！皁W目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個參數(shù)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中的數(shù)據(jù)N=16000,P×Q=1×2.分別選用 (peraMPI、MPICH和LAMMPI進行實驗,從表中可“看 出OIMnMPI的性能最佳,尤其在NB值比較小的時僻,所H最終確定使用OI*nMPI。玉互j四里墮莊盟也型L衛(wèi)望咝垡塑LHPL TIMINGBCAST(#(k“MPIMPICH I.A:VfMPI 11087111931619114g40145182l11891z 119917141885L121770I 271059L

28、260195Z 12R10B L L;84L750130LO7016311774NB240131 1847209424815B41715zO 8l 25614671951210426015111803%413687225279937519312202Z77439022%z8313039墮墼些業(yè)L生盟上衛(wèi)第口步確定N,NB眥及其他參數(shù)提高N值,并且對第一步得到的幾十較優(yōu)NB進行測試.調(diào)節(jié)其他參救,得到最終的鞋佳值。通過多趺宴驗,如 表4所示.最佳的浮點速率是8608Gflops。墨L丑土墊量鮑曼藍墮墨一T/VNNBP×0Gflops WROCK:2R8192001201x 28601W

29、ROOC2R891281×28608WRgaC2R8202241281×28542WR眥2R8192001121×2&17B WR0X2R81g 2001041×2R445T#*44i至換。本文借助這些轉(zhuǎn)換函數(shù)解決C中浮點數(shù)向VHDL中 標準位stdlogic vector的轉(zhuǎn)換。在具體實現(xiàn)時,首先分別 將有效數(shù)字和小數(shù)點后的有效數(shù)字位數(shù)轉(zhuǎn)換成整數(shù),然后 調(diào)用conv_stdlogicvector(ARGinteger轉(zhuǎn)換函數(shù),將整 數(shù)轉(zhuǎn)換為標準邏輯向餐。對應設置stdlogicvector中的每 一位,注意第七位設置為l。當兩個浮點數(shù)在進行運算

30、 時,首先判斷兩個浮點數(shù)向龜?shù)暮笃呶皇欠裣嗤?如果相 同,直接對有效數(shù)進行預算即叮,否則就要調(diào)整兩個浮點數(shù) 的后七位,以兩者的后七位中最大者為基準進行調(diào)整,然后 兩者再進行運算。4結(jié)束語HTTM雖然能夠初步實現(xiàn)軟件任務到硬件任務的轉(zhuǎn) 換。但日前仍存在一些n】題。首先它對輸入的ANSI C源 語言還有所限制.即不支持指針、嵌套調(diào)用、case-switch控 制語句。然后就是HTTM在生成硬件任務通信接口時效 率不是很高。最后就是HTTM中用到的并行分析方法目 前還只適用于特定的一類問題,即list homomorphism問 題,目前還不具有通用性。本文設計了一個軟硬件混合任務轉(zhuǎn)換模型,并研究了

31、 相應的轉(zhuǎn)換算法。論文研究初步實現(xiàn)了軟件任務和硬件任 務之間的轉(zhuǎn)換?？紤]到該模型的具體應用,項目組正在進 行基于可重構(gòu)計算的實時操作系統(tǒng)平臺的研究工作.該模 型的具體研究和關鍵技術將被應用到該平臺,HTTM將對 降低混合系統(tǒng)的設計周期和提高系統(tǒng)的運行效率方面會起 到積極的促進作用。參考文獻: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系統(tǒng)的LINPACK測試, 浮點效率

34、為:刁:彳8.r60了87686.刁2幣萬一44這個實驗中處理器只有兩個,PxQ配置方式只有兩 種,廣播方式能夠選擇的配置方式少,不存在跨越網(wǎng)卡的通 信。所有的這些都限制了計時系統(tǒng)作用的發(fā)揮,使得某些 數(shù)據(jù)不夠直觀,甚至一些功能得不到表現(xiàn)。比如計時系統(tǒng) 可以用于選擇廣播算法;當處理器數(shù)目較多的時候,計時系 統(tǒng)對PXQ的確定也會有更好的指導作用;計時系統(tǒng)在確 定互連網(wǎng)絡結(jié)構(gòu)的時候也很有用途。所以在大機群系統(tǒng) 中,計時系統(tǒng)有著很大的潛力。6結(jié)束語本文通過對計時系統(tǒng)進行改進,提出了一種基于計時 系統(tǒng)的IJNPACK測試方法。這種測試方法可以提取詳細 的時間參數(shù),更好地引導LINPACK的快速測試。文中分 析了這種測