異構高性能計算系統(tǒng)Linpack效率受限因素分析

賈 迅，鄔貴明，謝向輝

(數(shù)學工程與先進計算國家重點實驗室，江蘇 無錫 214125)

1 引言

目前，大規(guī)?？茖W與工程應用對系統(tǒng)計算能力的需求日益增長，這推動著高性能計算HPC(High Performance Computing)的不斷發(fā)展。研制具備每秒百億億次雙精度浮點運算能力的E級計算系統(tǒng)已成為世界各國競相爭奪的科技制高點?；贗ntel Xeon、IBM Power、AMD Opteron等高性能、高功耗商用處理器和高速互連網絡構建大規(guī)模并行系統(tǒng)是提升計算性能的典型方法。然而，隨著半導體工藝發(fā)展速度的放緩，對計算性能的不斷追求使得HPC系統(tǒng)整體能耗快速增長，可靠性和可擴展性急劇下降。能耗問題已經成為E級計算面臨的一大挑戰(zhàn)[1]。

商用處理器為了支持功能通用性，指令執(zhí)行的控制邏輯占據了芯片設計的大部分面積，芯片的計算能效較低，從而導致基于商用處理器構建的HPC系統(tǒng)的規(guī)模和性能無法有效擴展。而Intel至強融核MIC(Many Integrated Core)和NVIDIA通用圖形處理單元GPGPU(General Purpose GPU)等加速器芯片中集成了大量浮點運算部件，適合高度并行的計算密集型應用。表1對比了加速器與高性能處理器在計算性能、能效和性價比等方面的差異。相同工藝下，Intel和NVIDIA加速器單芯片的計算性能、能效和性價比是通用高性能處理器的數(shù)倍。

Table 1 Comparison among accelerators and high performance processors

多路通用高性能處理器作為主芯片通過PCIe等互連接口連接多路MIC、GPGPU等加速器從芯片，主從芯片存儲空間分離的異構計算技術可以在實現(xiàn)通用計算的同時獲得良好的計算性能、功耗和成本的平衡，其結構如圖1所示。異構計算技術在業(yè)界被廣泛應用，并且已經成為目前HPC發(fā)展的重要趨勢[2]。根據Top500組織于2017年6月發(fā)布的排名數(shù)據[3]，異構計算系統(tǒng)占HPC系統(tǒng)的比例已經達到了18.4%。其中，NVIDIA Tesla K40 GPGPU應用最多，占比為20.7%。

Figure 1 Structure of heterogeneous interconnect computing圖1 異構計算結構

異構計算技術被大量應用于HPC系統(tǒng)設計的同時，異構計算系統(tǒng)Linpack效率受限的問題日益凸顯。從Top500最新發(fā)布的排名數(shù)據[3]來看，異構系統(tǒng)Linpack效率的均值為62.28%，而同構系統(tǒng)達到了67.23%。異構與同構系統(tǒng)Linpack效率的差距在系統(tǒng)規(guī)模增大時更為顯著，如Tianhe-2、Piz Daint、Titan這三臺排名前十的大規(guī)模異構計算系統(tǒng)，其Linpack效率最高僅為77.35%，而相當規(guī)模同構計算系統(tǒng)的Linpack效率最低也達到了73.12%。較低的Linpack效率意味著系統(tǒng)中大量的計算資源無法被充分利用，從而造成系統(tǒng)資源和能耗的浪費。

針對異構高性能計算系統(tǒng)Linpack效率受限的問題，現(xiàn)有研究大多從軟件實現(xiàn)層面進行性能優(yōu)化，如改進任務劃分實現(xiàn)負載均衡、采用軟件流水線隱藏通信開銷等。本文從系統(tǒng)結構設計的角度，基于真實系統(tǒng)的設計參數(shù)和性能數(shù)據，深入分析了大規(guī)模異構計算系統(tǒng)Linpack效率受限的主要因素。本文的研究成果為未來加速器從芯片的優(yōu)化設計和異構系統(tǒng)的高效組織提供了有效指導。

2 相關工作

2.1 Linpack測試程序與核心算法

HPLinpack(High Performance Linpack)是目前HPC領域應用最為廣泛的Linpack性能測試程序，其由美國田納西大學計算機系教授Dongarra提出的[4]。HPLinpack的核心算法是求解階為n的線性方程：Ax=b，A∈Rn×n，x,b∈Rn。算法首先使用行選主元高斯消元法對系數(shù)矩陣[A,b]進行LU分解：Pr[A,b]=[[LU],y]，Pr,L,U∈Rn×n，y∈Rn。LU分解完成后，解原方程等價于求解上三角方程Ux=y。

從上述介紹可以看出，HPLinpack測試程序的執(zhí)行分為LU分解和回代兩個過程。其中，LU分解過程的浮點操作次數(shù)為(2/3)n3-(1/2)n2；回代過程的浮點操作次數(shù)為2n2。HPLinpack將系統(tǒng)求解線性方程時單位時間內執(zhí)行的雙精度浮點操作次數(shù)作為評價系統(tǒng)實際計算性能的標準。給出程序的執(zhí)行時間t，系統(tǒng)的實測性能Rmax可表示為：

計算系統(tǒng)的峰值性能Rpeak是單位時間內系統(tǒng)最多可執(zhí)行雙精度浮點操作的次數(shù)，可表示為處理器核心數(shù)、向量運算寬度和核心工作頻率的乘積。計算系統(tǒng)的Linpack效率E定義為實測性能與峰值性能的比值，即E=Rmax/Rpeak。

科學計算軟件庫Netlib[5]針對分布式存儲同構計算系統(tǒng)，給出了HPLinpack的并行化實現(xiàn)。程序以nb×nb為單位將系數(shù)矩陣劃分為數(shù)據塊網格，同時將計算結點組織成P×Q的網格。數(shù)據塊到結點的映射采用塊循環(huán)(block-cyclic)分布方式：數(shù)據塊(i,j)映射到結點(i%P,j%Q)。程序采用right-looking式LU分解算法，完成分解共需n/nb次迭代計算。每次迭代包含Panel分解、Panel廣播、行交換和子矩陣更新。其中，前三步的計算量較少，主要為結點間通信；子矩陣更新需要大量計算，包括雙精度三角矩陣方程求解和稠密矩陣乘，程序通過調用BLAS庫DTRSM和DGEMM兩個子過程實現(xiàn)。DGEMM子過程的執(zhí)行占據了Linpack程序運行的絕大部分時間，因而是整個程序的計算核心。

2.2 異構計算系統(tǒng)上Linpack的性能優(yōu)化

主芯片負責程序執(zhí)行過程中的結點間通信和部分計算，從芯片負責DGEMM核心的計算加速是各異構高性能計算系統(tǒng)Linpack實現(xiàn)和性能優(yōu)化的主要方法。主從芯片計算任務的劃分和主從芯片的通信開銷是異構計算系統(tǒng)Linpack實現(xiàn)的兩大難點。學術界針對這兩個難點問題展開了研究，并提出了靜態(tài)和動態(tài)的任務劃分方法[6 - 8]，以實現(xiàn)主從芯片計算任務的負載均衡，同時應用雙緩沖、數(shù)據重用、數(shù)據存儲優(yōu)化等軟件流水線技術[9 - 11]，以實現(xiàn)計算和通信的重疊，從而隱藏通信開銷。這些優(yōu)化技術應用于實際的大規(guī)模異構計算系統(tǒng)時可以有效提升系統(tǒng)的Linpack性能[7]。

從上述介紹可以看出，目前針對Linpack性能優(yōu)化的研究主要通過應用軟件實現(xiàn)技術來隱藏異構計算系統(tǒng)主從計算能力和訪存性能不對稱、存儲空間分離、主從通信開銷大的結構特點。但是，現(xiàn)有研究并未考慮異構計算系統(tǒng)的結構設計對系統(tǒng)Linpack性能或效率的約束，因而這成為本文的研究重點。

3 Linpack效率受限因素分析

3.1 加速器的DGEMM效率

王申等人[12]基于單芯片多核計算結點構成的同構計算系統(tǒng)，建立了Linpack并行性能模型。模型分析結果表明，在矩陣規(guī)模和互連網絡帶寬一定的情況下，結點DGEMM的計算效率對系統(tǒng)Linpack效率的影響幾乎是線性的。異構計算系統(tǒng)中，主處理器芯片上DGEMM的性能已接近峰值計算性能[13]，而用于計算加速的從芯片提供了系統(tǒng)主要的計算能力。因此，本文首先統(tǒng)計了不同加速器從芯片DGEMM的計算效率以及采用這些加速器芯片構建的異構計算系統(tǒng)的Linpack效率，統(tǒng)計結果如表2所示。

Table 2 Accelerator DGEMM efficiency and system Linpack efficiency

從表2可以看出，無論是AMD還是NVIDIA，其早期GPGPU加速器的DGEMM的計算效率均較低，僅為70%左右[14,15]。NVIDIA于2012年發(fā)布的Kepler架構Tesla K20x才將DGEMM計算效率提升至93%[16]，后續(xù)發(fā)布的K40、K80、Tesla P100等GPGPU的效率均維持在93%左右[17]。Intel MIC架構的Xeon Phi加速器DGEMM計算效率只能達到80%[18]。IBM PowerXCell 8i加速器DGEMM的計算效率最高，達到了99%[19]。

對照各加速器從芯片DGEMM計算效率與采用這些加速器的異構計算系統(tǒng)的Linpack效率來看，兩者是正相關的關系：采用早期GPGPU進行加速的Tianhe-1和Tianhe-1A系統(tǒng)的Linpack效率最高僅為55%；采用Intel Xeon Phi進行加速的系統(tǒng)其Linpack效率也只有60%左右；而采用K20x、P100和PowerXCell 8i進行加速的系統(tǒng)其Linpack效率可以達到65%～75%。顯然，加速器DGEMM計算效率的提高有效提升了基于這些加速器構建的異構高性能計算系統(tǒng)的Linpack效率。

為了更為直觀地體現(xiàn)加速器從芯片DGEMM的計算效率對異構計算系統(tǒng)Linpack效率的影響，表3統(tǒng)計了Top500排名中所有使用NVIDIA Fermi架構M2050/C2050和Kepler架構K20x GPGPU作為加速器的異構高性能計算系統(tǒng)的Linpack效率。

Table 3 HPC systems based on NVIDIA GPGPU and their Linpack efficiencies

從表3中的統(tǒng)計數(shù)據可以看出，采用M2050/C2050 GPGPU作為加速器的系統(tǒng)，其效率最高僅為54.58%，而采用K20x GPGPU的計算系統(tǒng)，效率最低也達到了64.88%。整體來看，NVIDIA GPGPU上DGEMM的計算效率從70%優(yōu)化至93%后，異構計算系統(tǒng)的Linpack效率顯著增長。

目前，Intel MIC和NVIDIA GPGPU最新的加速器芯片執(zhí)行DGEMM核心的計算效率最高分別為82%和93%，這與同構系統(tǒng)中主處理器芯片執(zhí)行DGEMM的效率還存在一定差距。由于加速器從芯片的計算性能占據了異構計算系統(tǒng)總性能的主要部分，根據文獻[12]提出的Linpack性能分析模型，DGEMM計算效率的差距將直接導致系統(tǒng)Linpack效率的損失。因此，加速器從芯片DGEMM的計算效率是目前異構高性能計算系統(tǒng)Linpack效率受限的一個主要因素。

3.2 主從芯片的資源配比

文獻[20]將異構高性能計算系統(tǒng)上Linpack的實現(xiàn)總結為三個問題：(1)核心計算的位置，即Linpack程序的DGEMM計算核心由主芯片還是從芯片完成？(2)數(shù)據存儲的位置，即Linpack程序的矩陣數(shù)據存儲在主芯片內存還是從芯片內存？(3)非核心計算的位置，即Linpack程序的Panel分解、結點間通信由主芯片還是從芯片完成？表 4統(tǒng)計了多個大規(guī)模異構HPC系統(tǒng)針對上述三個問題的實現(xiàn)。TSUBAME 2.5和Roadrunner系統(tǒng)的核心計算僅由從芯片完成，其它系統(tǒng)中主從芯片共同完成核心計算。對于數(shù)據存儲，僅Roadrunner系統(tǒng)將矩陣數(shù)據存儲在從芯片內存上，其它異構系統(tǒng)的矩陣數(shù)據均存儲在主芯片內存上。另外，由于Linpack程序的非核心計算無法有效并行且與結點間通信緊密耦合，由于異構系統(tǒng)中僅主芯片具備通信能力，因此所有系統(tǒng)中非核心計算均由主芯片完成。

對表 4的進一步分析可以看出，系統(tǒng)核心計算和矩陣數(shù)據的存儲位置取決于主從芯片的計算性能占比和內存容量，即資源配比。由于TSUBAME 2.5和Roadrunner系統(tǒng)中從芯片性能占比達到了96%，主芯片無需參與加速計算；其它系統(tǒng)中主芯片的計算性能占比最低為9.7%，為了盡可能提升Linpack測試的性能，必須充分利用主芯片的計算能力，即需要主從芯片共同參與DGEMM核心的計算加速。另一方面，內存容量直接決定了Linpack測試的矩陣規(guī)模。Roadrunner系統(tǒng)中主從芯片的內存容量相當，矩陣數(shù)據可以直接存儲在從芯片內存上，減少了加速計算時主從芯片之間通過片間互連接口進行數(shù)據傳輸?shù)拈_銷；其它系統(tǒng)中從芯片的內存容量遠小于主芯片，因此測試的矩陣數(shù)據只能存儲在主芯片內存上，因而每次核心計算都需要主從芯片之間進行大量的數(shù)據傳輸，此時主從通信的開銷會影響異構系統(tǒng)Linpack性能的提升[20]。

Table 4 Linpack implementation on heterogeneous interconnected systems and host/accelerator chip resources

針對表 4中的計算系統(tǒng)，若將計算數(shù)據存儲在從芯片內存且僅由從芯片完成核心計算，此時異構計算系統(tǒng)的Linpack效率可表示為系統(tǒng)中從芯片的性能占比與從芯片DGEMM計算效率的乘積，再減去結點間通信和計算規(guī)模變化對系統(tǒng)Linpack效率的影響(大致為20%[20])。表5統(tǒng)計了各計算系統(tǒng)Linpack效率的估計值與系統(tǒng)實際Linpack效率的差值。

Table 5 Difference between the estimated and real Linpack efficiency

表5中，Roadrunner系統(tǒng)Linpack效率的估計值與系統(tǒng)實際Linpack效率的差為1.25%，這表明計算中采用的Linpack效率受結點間通信和計算規(guī)模影響的估計值是合理的。從效率差值隨從芯片性能占比和DGEMM效率的變化可以看出，在從芯片內存容量可以滿足測試程序矩陣規(guī)模的情況下，隨著系統(tǒng)中從芯片的性能占比和DGEMM效率的提高，異構系統(tǒng)中僅由從芯片進行核心計算時的Linpack效率可以達到甚至高于系統(tǒng)實際的Linpack效率。因此，主從芯片的資源配比是導致目前異構高性能計算系統(tǒng)Linpack效率受限的另一個主要因素。

3.3 對異構計算系統(tǒng)結構設計的需求

加速器從芯片DGEMM的計算效率直接影響了異構高性能計算系統(tǒng)的Linpack效率，而DGEMM效率受矩陣分塊大小、Cache性能、流水方式、訪存帶寬、計算訪存比等諸多因素的影響。其中，指令調度和存儲訪問延遲是決定NVIDIA GPGPU加速器DGEMM計算效率的兩大主要因素[23]。因此，結合從芯片計算和訪存的結構設計特點，進一步優(yōu)化從芯片DGEMM核心的計算性能對未來異構計算系統(tǒng)的性能發(fā)揮至關重要。

目前，異構系統(tǒng)的計算和數(shù)據存儲方式受主從芯片資源配比的影響，從而限制了系統(tǒng)Linpack效率的提升。不斷增加加速器從芯片的主存容量及其在異構計算系統(tǒng)中的性能占比是應對這個問題最直接而有效的手段，但其受限于當前的技術能力。2016年NVIDIA發(fā)布了GP100架構的Tesla P100[24]GPGPU，雖然芯片集成的HBM2內存容量僅為16 GB，但其支持通過NVLink接口[25]實現(xiàn)GPGPU片間高速互連，從而有效擴展從芯片的內存容量和計算能力。隨著新一代產品應用于異構HPC系統(tǒng)以及存儲技術的進步，異構高性能計算系統(tǒng)Linpack效率受限于主從芯片資源配比的問題將得到緩解。

4 基于Linpack性能模型的分析驗證

為了對上述分析結論進行驗證，本文針對Linpack測試矩陣數(shù)據存儲在從芯片內存，且僅從芯片進行DGEMM核心計算的情況構建了異構系統(tǒng)的性能分析模型。假設測試采用blonM廣播算法和long行交換算法[5]，且所有的通信均不沖突。加速器從芯片的性能占比Racc和DGEMM的計算效率E1是性能模型的兩個重要參數(shù)，其余參數(shù)的含義和取值見表6。

Table 6 Parameters used in the performance model

Linpack程序單次迭代所需的時間為結點計算時間與通信時間的最大值，程序在異構計算系統(tǒng)上執(zhí)行完成所需的總時間t可表示為所有迭代時間的總和，即：

本文采用Mathematica科學計算軟件[26]實現(xiàn)了上述性能模型，異構系統(tǒng)的Linpack效率隨加速器從芯片性能占比和DGEMM計算效率的變化情況如圖2所示。

Figure 2 Effects of accelerator performance ratio and DGEMM efficiency on Linpack圖2 系統(tǒng)Linpack效率隨加速器從芯片性能占比和DGEMM計算效率的變化

從圖2可以看出，從芯片性能占比Racc的值一定時，異構系統(tǒng)的Linpack效率隨從芯片DGEMM的計算效率線性變化；從芯片DGEMM的計算效率一定時，更高的從芯片性能占比對應著更高的Linpack效率。

基于性能模型的分析結果表明，從芯片的DGEMM計算效率和性能占比是影響異構計算系統(tǒng)Linpack效率的兩大重要因素；同時也證實了測試矩陣數(shù)據分布在從芯片內存，且僅由從芯片完成核心計算加速的情況下，加速器從芯片更高的性能占比和DGEMM計算效率可以有效提升異構高性能計算系統(tǒng)的Linpack效率。

5 結束語

與同構系統(tǒng)相比，異構高性能計算系統(tǒng)呈現(xiàn)主從計算和訪存能力不對稱、存儲空間分離、通信開銷大的結構特點，并且系統(tǒng)的Linpack效率提升困難。與現(xiàn)有研究依賴軟件實現(xiàn)技術進行Linpack性能優(yōu)化不同，本文立足于系統(tǒng)的結構設計，對現(xiàn)有大規(guī)模異構計算系統(tǒng)的設計參數(shù)和性能數(shù)據進行了細致分析，并基于Linpack性能模型對分析結論進行了驗證。結果表明，加速器從芯片DGEMM的計算效率和主從芯片的資源配比是目前異構高性能計算系統(tǒng)Linpack效率受限的主要因素。加速器從芯片DGEMM計算核心的性能優(yōu)化以及存儲技術的進步對未來異構計算系統(tǒng)的性能發(fā)揮具有重要作用。

[1] Kogge P, Bergman K, Borkar S, et al.Exascale computing study:Technology challenges in achieving exascale systems:TR-2008-13[R].[S.l.]:Defense Advanced Research Projects Agency Information Processing Techniques Office (DARPA IPTO),2008:1-278.

[2] Kindratenko V, Trancoso P.Trends in high-performance computing[J].Computing in Science & Engineering,2011,13(3):92-95.

[3] Top500 Organization.Supercomputer rank list[EB/OL].[2017-06-22].https://www.top500.org/lists/2017/06/.

[4] Dongarra J J,Luszczek P,Petitet A.The LINPACK benchmark:Past,present and future[J].Concurrency and Computation:Practice and Experience,2003,15(9):803-820.

[5] Repository N.HPL—A portable implementation of the high-performance linpack benchmark for distributed-memory computers[EB/OL].[2017-04-20].http://www.netlib.org/benchmark/hpl/.

[6] Fatica M.Accelerating linpack with CUDA on heterogenous clusters[C]∥Proc of the 2nd Workshop on General Purpose Processing on Graphics Processing Units,2009:46-51.

[7] Yang C, Wang F, Du Y,et al.Adaptive optimization for petascale heterogeneous CPU/GPU computing[C]∥Proc of 2010 IEEE International Conference on Cluster Computing (CLUSTER),2010:19-28.

[8] Quintana-Ortí G,Igual F D,Quintana-Ortí E S,et al.Solving dense linear systems on platforms with multiple hardware accelerators[C]∥ACM Sigplan Notices.ACM,2009,44(4):121-130.

[9] Yang C,Chen C,Tang T,et al.An energy-efficient implementation of LU factorization on heterogeneous systems[C]∥Parallel and Distributed Systems (ICPADS),2016 IEEE 22nd International Conference on.IEEE,2016:971-979.

[10] Jo G,Nah J,Lee J,et al.Accelerating LINPACK with MPI-OpenCL on clusters of multi-GPU nodes[J].IEEE Transactions on Parallel and Distributed Systems,2015,26(7):1814-1825.

[11] Li Jia-jia, Li Xing-jian,Tan Guang-ming. DGEMM performance on CPU/ATI GPU hybrid architectures[J].Information Technology Letter,2011,9(6):12-27.(in Chinese)

[12] Wang Shen, Qi Feng-bin, Gu Hong-feng, et al.Linpack parallel performance model and its prediction[J].Computer Engineering,2012,38(16):81-84.(in Chinese)

[13] Sun N H,Xing J,Huo Z G,et al.Dawning Nebulae:A PetaFLOPS supercomputer with a heterogeneous structure[J].Journal of Computer Science and Technology,2011,26(3):352-362.

[14] AMD Corporation.Entering the golden age of heterogeneous computing[EB/OL].[2017-04-27].https://developer.amd.com/wordpress/media/2012/10/IUCAA_Pune_PEEP_2008.pdf.

[15] NVIIDA Corporation.CUDA accelerated linpack on clusters[EB/OL].[2017-04-27].http://www.nvidia.com/content/gtc-2010/pdfs/2057_gtc2010.pdf.

[16] NVIDIA Corporation.K20-K20X GPU accelerators benchmarks[EB/OL].[2017-04-27].http://www.nvidia.com/docs/IO/122874/K20-and-K20X-application-performance-technical-brief.pdf.

[17] Oak Ridge National Laboratory.IBM Power8 CPU overview and deatis[EB/OL].[2017-04-27].https://www.olcf.ornl.gov/wp-content/uploads/2017/01/SummitDev_IBM-Power8-CPUs_Walkup.pdf.

[18] Heise Online. Intel brings official Xeon Phi co-processor[EB/OL].[2017-04-27].https://www.heise.de/newsticker/meldung/SC12-Intel-bringt-Coprozessor-Xeon-Phi-offiziell-heraus-1747942.html.

[19] Kistler M,Gunnels J,Brokenshire D,et al.Petascale computing with accelerators[C]∥Proc of ACM Sigplan Symposium on Principles and Practice of Parallel Programming,2009:241-250.

[20] Endo T,Matsuoka S,Nukada A,et al.Linpack evaluation on a supercomputer with heterogeneous accelerators[C]∥Proc of 2010 IEEE International Symposium on Parallel & Distributed Processing (IPDPS),2010:1-8.

[21] Liao X,Xiao L,Yang C,et al.MilkyWay-2 supercomputer:System and application[J].Frontiers of Computer Science,2014,8(3):345-356.

[22] Wikipedia org.Titan supercomputer[EB/OL].[2017-04-27].https://en.wikipedia.org/wiki/Titan.

[23] Tan G, Li L, Triechle S, et al.Fast implementation of DGEMM on Fermi GPU[C]∥Proc of 2011 International Conference for High Performance Computing,Networking,Storage and Analysis,2011:35.

[24] NVIDIA Corporation.Tesla P100 [EB/OL].[2017-04-25].https://images.nvidia.com/content/pdf/tesla/whitepaper/pascal-architecture-whitepaper.pdf.

[25] NVIDIA Corporation.NVLink high-speed interconnect:Application performance[EB/OL].[2017-04-27].http://www.nvidia.com/object/nvlink.html.

[26] Wolfram.Wolfram Mathematica[EB/OL]. [2017-07-26].https://www.wolfram.com/.

附中文參考文獻：

[11] 李佳佳,李興建,譚光明.CPU/ATI GPU混合體系結構上DGEMM的性能研究[J].信息技術快報,2011,9(6):12-27.

[12] 王申,漆鋒濱,谷洪峰,等.Linpack并行性能模型及其預測[J].計算機工程,2012,38(16):81-84.