摘   要： 核外計算中，由于I/O操作速度比較慢,，所以對文件的訪問時間占的比例較大,。如果使文件操作和計算重疊則可以大幅度地提高運行效率。軟件數(shù)據(jù)預(yù)取是一種有效的隱藏存儲延遲的技術(shù),，通過預(yù)取使數(shù)據(jù)在實際使用之前從硬盤讀到緩存中,，提高了緩存(cache)的命中率，降低了讀取數(shù)據(jù)的時間,。通過設(shè)置兩個緩沖區(qū)來輪流存放本次和下一次讀入的數(shù)據(jù)塊,實現(xiàn)訪存完全命中cache的效果,，使Cholesky分解并行程序執(zhí)行核外計算的效率得到了大幅度的提高。同時,，I/O操作的時間與CPU的執(zhí)行時間的比例也是影響效率的主要因素,。
關(guān)鍵詞： 預(yù)取,； 核外,； 并行； 集群; Cholesky分解

    隨著科學(xué)技術(shù)的迅猛發(fā)展,，人們需要處理的數(shù)據(jù)量迅速增長,。大規(guī)模并行應(yīng)用涉及的數(shù)據(jù)量是非常驚人的，內(nèi)存容量常常不能滿足涉及到大數(shù)據(jù)量計算問題的存儲需求,。因待處理數(shù)據(jù)無法全部讀入內(nèi)存,，所以只能保存數(shù)據(jù)到外部磁盤系統(tǒng)。當程序運行時,，某個時刻只能將部分數(shù)據(jù)調(diào)入內(nèi)存并參加計算,，并且在適當?shù)臅r候?qū)懟赝獯妫ㄟ^某種策略實現(xiàn)內(nèi)外存數(shù)據(jù)的交換,。由于運算過程中數(shù)據(jù)并沒有全部存放在內(nèi)核存儲器中,，所以稱之為核外計算。核外計算程序中包含大量的文件操作,，因訪問磁盤數(shù)據(jù)的速度比較慢,，所以在處理大數(shù)據(jù)量問題時，I/O性能顯然要超過CPU性能而成為重要的限制因素,。因此,，如何對核外數(shù)組進行合理調(diào)度與高效訪問是解決核外計算應(yīng)用問題的關(guān)鍵,。
    利用三角分解式求解對稱正定方程組是一種有效方法。單行卷簾存儲Cholesky分解[1]使每個節(jié)點所分配的數(shù)據(jù)最多相差一行,，但是這種劃分方式的通信開銷比較大,。多行卷簾存儲Cholesky分解[2]可以減少通信開銷,充分利用節(jié)點的緩存，但是沒有充分考慮緩存的效率問題,，因為緩存可以對程序性能帶來巨大的改變,。遞歸算法[3]通過將矩陣分塊使各個子矩陣的運算能夠在高速緩存中進行，以提高運算效率,，同時遞歸算法良好的數(shù)據(jù)局部性和矩陣遞歸的分塊,，使其非常適合分層多級存儲的計算機結(jié)構(gòu)。但是在遞歸調(diào)度算法中,，非對角塊的運算不能充分利用計算機的分級存儲結(jié)構(gòu),。分塊Cholesky分解[4-5]通過精心的挑選塊的大小，使每個塊都能充分地利用一級緩存,，并且合理地劃分塊的大小還能使每個塊常駐內(nèi)存,。參考文獻文[4]充分利用了系統(tǒng)硬件的并行機制以使通信與計算重疊，減少了節(jié)點的等待時間,。同時通過矩陣元素的重排使每個塊都被連續(xù)存儲,，以充分利用計算機的多層次存儲結(jié)構(gòu)，減少數(shù)據(jù)拷貝和內(nèi)部的變化,。但是這些算法只在數(shù)據(jù)量較小的情況下適用；當數(shù)據(jù)量較大時,，數(shù)據(jù)將無法一次性讀入內(nèi)存,，因此引進了核外計算的概念。
    本文對Cholesky分解的并行算法進行了深入的研究,，給出的核外算法通過預(yù)取[6-7]的方法使得數(shù)據(jù)在實際使用之前從硬盤移到緩存中,從而進一步提高了緩存的命中率,，減少了文件讀取的時間。
1基本概念

1.2 預(yù)取方法
    在核外計算中數(shù)據(jù)存儲在磁盤上,，只有CPU對數(shù)據(jù)進行處理時才將其讀入內(nèi)存緩沖區(qū),，處理完成后寫回文件。這樣,，核外計算過程就可以描述成：讀入核外數(shù)組文件的一塊數(shù)據(jù)到內(nèi)存緩沖區(qū),，進行計算等處理，處理完成后將其寫回數(shù)組文件,；讀取下一塊數(shù)據(jù),，進行數(shù)據(jù)處理，處理完成后寫回文件,。如此反復(fù)執(zhí)行,，直到整個核外數(shù)組處理完成后結(jié)束,。顯而易見，這是一個順序流水線,，執(zhí)行I/O操作與CPU進行計算是順序執(zhí)行的,；由于二者在執(zhí)行前需彼此等待，所以程序的執(zhí)行效率非常低,。于是考慮到,，當I/O操作的數(shù)據(jù)與CPU執(zhí)行計算的數(shù)據(jù)無相關(guān)性時，可以把對下一個數(shù)據(jù)塊的I/O操作與對當前數(shù)據(jù)塊的計算重疊起來,，這樣就可以隱藏I/O的延遲,，達到縮短整個程序運行時間的目的。圖1所示為數(shù)據(jù)預(yù)取前后的對比,。

    本算法采用雙緩沖區(qū)的方式,，即為一個核外數(shù)組分配兩個內(nèi)存緩沖區(qū)buffer[2]，輪流存放本次和下一次讀入的數(shù)據(jù)塊,。用預(yù)取的方法對第s個子文件更新,，其偽碼如下：
    (1)主節(jié)點將第一個子文件讀入內(nèi)存數(shù)組buffer[0]中，并將其廣播出去,；
    (2)依次用已分解的子文件更新第s個子文件,，即對ka=1,2,……,s-1循環(huán)：
   若該節(jié)點是主節(jié)點,做以下工作：①讀入第ka個文件到buffer[ka%2]中；②發(fā)送第ka個文件;
　若該節(jié)點是從節(jié)點,則做以下工作：①用第ka-1個文件更新第s個文件,；②接收第ka個文件,。
　(3)若該節(jié)點是從節(jié)點，則用第s-1個文件更新第s個文件,。
2 用預(yù)取算法實現(xiàn)Cholesky分解
2.1 Cholesky分解并行算法的思想
    將大規(guī)模矩陣A連續(xù)拆分成q個子文件,，并將其儲存到主節(jié)點中。主節(jié)點一次調(diào)入內(nèi)存一個子文件,，依次對各子文件進行Cholesky分解,，直至最后一個子文件分解完畢。所以只要拆分的子文件大小不超過空閑內(nèi)存的范圍,，算法就可以運行,。其算法流程見圖2，具體步驟如下：
    (1)文件拆分過程
    由主節(jié)點機進行矩陣拆分存儲的操作,，打開存儲于硬盤中的A.txt文件,，依內(nèi)存容量的需要進行拆分，讀取相應(yīng)規(guī)模的數(shù)據(jù),，生成子文件,，并將這些子文件j.txt(j=1,2,3)存儲回硬盤。
    (2)A陣的Cholesky分解過程
    考慮到Cholesky分解過程中的依賴關(guān)系,，對其由上至下依次進行分解,。由于在三角分解中,，既需要分解后的上三角，又需要分解后的下三角,，所以可以將分解后的上三角復(fù)制到下三角,。這樣既可以減少運算量又可以減少存儲量。在分解過程中利用其并行性,，主節(jié)點打開第一個子文件1.txt后,，賦值給a6×15，再將a廣播出到各個從節(jié)點,。每個從節(jié)點經(jīng)卷簾計算出分解因子后,，廣播出去，如此地計算kb=2次,，該子文件的Cholesky分解完畢,。當1.txt計算結(jié)束后,主節(jié)點打開下一個子文件2.txt，賦值給a6×15,，再將a廣播到各個從節(jié)點,。同時主節(jié)點還要打開分解完畢的子文件1.txt,賦值給aa6×15(即buffer[0]),再將aa廣播到各個從節(jié)點。各個從節(jié)點用aa6×15卷簾去更新a6×15,，更新完畢后a6×15再像上面的操作,，每個從節(jié)點卷簾的計算出分解因子后，廣播出去,，如此的計算kb=2次后,，主節(jié)點打開下一個子文件3.txt，進行如文件2.tx的操作,。

2.2 Cholesky分解并行算法的描述
    將A連續(xù)拆分存儲到q個子文件中,，依次對各子文件進行Cholesky分解，直至對最后一個子文件分解后,，原大規(guī)模系數(shù)矩陣已被拆分到幾個小文件中存儲。將節(jié)點機分別標記為P0,，P1…Pnp,，np代表從節(jié)點機個數(shù)，P0代表主節(jié)點,，kb表示在一個子文件中單個節(jié)點機計算的行數(shù),，s是子文件依次分解的循環(huán)控制變量，ka表示讀取已分解子文件的循環(huán)控制變量,，在拆分后a∈R[kb×np]×n,，aa∈R[kb×np]×n。具體步驟如下：
    (1)文件拆分
    主節(jié)點機打開存于硬盤中的A.txt文件,，按內(nèi)存容量的需要進行拆分,，讀取相應(yīng)規(guī)模的數(shù)據(jù),，生成q個子文件。
    其中,，q=n/(np×kb),q×np×kb=nn/(np×kb)+1,其他
    (2)A矩陣的Cholesky分解過程
    ①1.txt(s=0)的Cholesky分解：(a)主節(jié)點打開1.txt,，讀取文件內(nèi)容，賦值到a[np*kb][n]數(shù)組中,，并將數(shù)組a廣播出去,。(b)從節(jié)點myid(myid=1,2,……,np)將數(shù)組a中的第i行(i%np=myid-1)進行Cholesky分解。(c)從節(jié)點將已分解的對角元素賦給數(shù)組d[n],。(d)從節(jié)點用數(shù)組a已分解的元素重寫其下三角,。(e)從節(jié)點將分解后的數(shù)組a寫回主節(jié)點。
    ②文件j.txt(s=1,2,……,q-1,j=s+1)的Cholesky分解：(a)主節(jié)點打開并讀取j.txt內(nèi)容,，賦值到a且將其廣播出去,。(b)用預(yù)取的方法對第j個子文件更新。即主節(jié)點依次打開已分解文件ka.txt(ka=0,1,…,s-1),，賦值給buffer[ka%2],，并將buffer[ka%2]廣播出去。在各個從節(jié)點根據(jù)buffer[ka%2]的值更新數(shù)組a值的同時,，主節(jié)點讀取下一個已分解的文件,。(c)用數(shù)組buffer[ka%2]的元素重寫數(shù)組a的下三角。(d)將數(shù)組a進行Cholesky分解,。(e）將數(shù)組a本次分解的對角線元素賦值給數(shù)組d[n],。(f)用數(shù)組a本次分解的元素重寫其下三角。(g)將分解后的數(shù)組a寫回主節(jié)點,。
2.3 算法的復(fù)雜度分析
    對于點對點的通信,，測量開銷使用乒乓法：節(jié)點0發(fā)送m個字節(jié)給節(jié)點1；節(jié)點1從節(jié)點0接收m個字節(jié)后,，立即將消息發(fā)回節(jié)點0,。總的時間除以2,，即可得到點到點通信時間,，也就是執(zhí)行單一發(fā)送或接收操作的時間。通信開銷的解析表達式是消息長度m(字節(jié))的線性函數(shù)：tcomm(m)=Ts+Tb×m;其中Ts表示通信的啟動時間,Tb表示發(fā)送每個字節(jié)所需時間(它是帶寬的倒數(shù)),。由于MPI_Bcast 函數(shù)采用樹算法,，所以一次MPI_Bcast的通信開銷為tcomm(s)×logP。Cholesky分解的執(zhí)行時間可分為子文件的更新時間和自身分解時間,。因此,，Cholesky分解時間：Tc=Tg+Tf，其中Tg是子文件更新時間,，Tf是自身的分解時間,。在文件的更新時間中,又細化為讀文件時間Td,、計算時間Tj和通信時間Tt。為了減少分解的執(zhí)行時間,，本文通過預(yù)取的方法使更新過程中的讀文件與計算重疊,，使得Cholesky分解的時間開銷：Tc<Tf+Td+Tj+Tt。當文件的讀取與計算完全重疊時,，Cholesky分解的時間可表示為Tc=Tf+Tt+max(Td,Tj),。
    子文件的大小是通過參數(shù)kb(1≤kb≤n/np)而設(shè)定的，當kb=n/np時相當于無文件劃分并行求解,；當kb=1時,，在每個子文件中每個節(jié)點機只計算一行，此時的通信量最大(按照這種分配方法劃分數(shù)據(jù)后,，每個處理器上須存儲的內(nèi)容為kb×np×n規(guī)模的矩陣A),。因此算法的并行執(zhí)行時間：Tn=T1+Tc+T2，其中,，T1為劃分子文件消耗的時間,，Tc是Cholesky分解時間，T2為冗余的控制和管理開銷,。
3 實驗測試與結(jié)果分析
    實驗環(huán)境采用由5臺主頻為2.8 GHz的Intel Xeon CPU,，內(nèi)存為ECC DDR-2 SDRAM 2 GB的Dell PowerEdge 2850構(gòu)建的集群。該集群運行Linux RH9操作系統(tǒng),，并且建立了MPI并行編程環(huán)境,。本文測試的兩個程序分別為：帶狀循環(huán)劃分的核外程序out和帶狀循環(huán)劃分的核外預(yù)取程序pre。
    表1表示當A的階數(shù)n=2 478,核外Cholesky分解各個部分的執(zhí)行時間對比,。表2表示了在節(jié)點數(shù)np分別為2,3,4,5時,，Cholesky分解中的子文件更新各個部分的時間對比(kb=10,n=2 479)。圖3為核外預(yù)取程序相對于核外程序更新時間的效率提高百分比,。

    由表1可見,，在求解過程中Cholesky分解中的更新部分占了大部分時間，所以提高更新部分的執(zhí)行率能明顯縮短總的執(zhí)行時間,。
    由表2可見,，預(yù)取方法使得子文件的更新時間平均縮短了15%左右。

    圖3表明,，核外預(yù)取分解并行算法的效率明顯好于核外分解并行算法，并且隨著節(jié)點個數(shù)的增加,，提高的效率先增大后減小,。這是因為隨著節(jié)點數(shù)目的增加，子文件容量增加,，計算量增加,，計算與文件讀取的重疊時間越多,。在節(jié)點數(shù)np=3時，效率提高幅度最大,。當節(jié)點數(shù)np>3時,，隨著節(jié)點數(shù)的增加通信時間急劇增加，而計算時間逐漸減少,，計算與文件讀取的重疊時間減少,，所以執(zhí)行效率提高的幅度降低。
    本文通過對Cholesky分解并行算法的研究,，表明預(yù)取方法是計算核外稠密線性方程組的有效方法,，非常有利于縮短I/O與CPU速度間的差距。數(shù)據(jù)預(yù)取的方法可以做到計算與I/O并行,，即在計算一塊數(shù)據(jù)的同時讀入下一塊要處理的數(shù)據(jù),。為了存放預(yù)取的數(shù)據(jù)，本文采用雙緩沖區(qū)的方式,，即為一個核外數(shù)組分配兩個內(nèi)存緩沖區(qū),，輪流存放本次和下一次讀入的數(shù)據(jù)塊。此外,，預(yù)取方法同樣適用于QR分解,、LU分解、高斯削去等其他線性代數(shù)問題,。當然采用數(shù)據(jù)預(yù)取技術(shù)時,，I/O操作時間與CPU執(zhí)行時間的比例是保證預(yù)取效果的關(guān)鍵。
    事實上,，Cholesky分解也可以采用數(shù)據(jù)重用的方法,。通過減少對子文件的讀取次數(shù)，可以進一步提高Cholesky分解算法的效率,。由于目前分布存儲計算機的處理速度都很高,，而其網(wǎng)絡(luò)通信速度較慢,所以用增加計算和通信粒度的辦法來降低通信成本。
參考文獻
[1] 遲學(xué)斌. Transputer上Cholesky分解的并行實現(xiàn)[J]. 計算數(shù)學(xué),，1993(3):289-294.
[2] 王順緒,，周樹荃.卷簾行存儲下的一種并行Cholesky分解及其在PAR95上的實現(xiàn)[J].南京航空航天大學(xué)學(xué)報，1999,，31(4)：428-432.
[3] 陳建平. Jerzy Wasniewski,，Cholesky分解遞歸算法與改進[J].計算機研究與發(fā)展，2001,，38(8):923-926.
[4] GUSTAVSON F G, KARLSSON L, KAGSTRO B M. Distributed SBP cholesky factorization algorithms with nearoptimal scheduling[J]. ACM Transactions on Mathematical Software, 2009, 36(2):1-25.
[5] ANDERSEN B S, GUNNELS J A, GUSTAVSON F G, et al. A fully portable high performance minimal storage hybrid format cholesky algorithm[J]. ACM Transactions on Mathematical Software, 2005,31(2):201-227.
[6] 丁文魁,，汪劍平，向華，等.p-HPF并行編譯系統(tǒng)核外計算的實現(xiàn)及優(yōu)化策略[J].計算機學(xué)報,，1999,，22(10):1042-1049.
[7] 姚維.Linux下一種磁盤節(jié)能的預(yù)取算法[J].計算機系統(tǒng)應(yīng)用，2010,19(7):91-94.