新型的分布式并行稠密矩陣乘算法

　　并行矩陣乘法是線性代數(shù)中最重要的基本運(yùn)算之一，同時(shí)也是許多科學(xué)應(yīng)用的基石。隨著高性能計(jì)算（HPC）向E級(jí)計(jì)算發(fā)展，并行矩陣乘法的通信開(kāi)銷所占比重越來(lái)越大。如何降低并行矩陣乘法的通信開(kāi)銷，提高并行矩陣乘的可擴(kuò)展性是當(dāng)前研究的熱點(diǎn)之一。本文提出一種新型的分布式并行稠密矩陣乘算法，即2.5D版本的PUMMA（ Parallel Universal matrix Multiplication Algorithm）算法，該算法是通過(guò)將初始的進(jìn)程分成c組，利用計(jì)算節(jié)點(diǎn)的額外內(nèi)存，在每個(gè)進(jìn)程組上同時(shí)存儲(chǔ)矩陣A、B和執(zhí)行1/c的 PUMMA算法，最后通過(guò)規(guī)約操作來(lái)得到矩陣乘的最終結(jié)果。本文基于 BLACS（ Basic Linear Algebra Communication Subprograms）通信庫(kù)實(shí)現(xiàn)了一種從2D到2.5D的新型數(shù)據(jù)重分配算法，與 PUMMA算法相結(jié)合，最終得到2.5 D PUMMA算法，可直接替換 PDGEM（ Parallel double- precision General Matrix-matrix Multiplication），具有良好的可移植性。與國(guó)際標(biāo)準(zhǔn)算法庫(kù) ScalaPACK（ Scalable Linear algebra Package）中的 PDGEMM等經(jīng)典D算法相比，本文算法縮減了通信次數(shù)，提高了數(shù)據(jù)局部性，具有更好的可擴(kuò)展性。在進(jìn)程數(shù)較多時(shí)，例如4096進(jìn)程時(shí)，系統(tǒng)測(cè)試表明相對(duì) PDGEMM的加速比可達(dá)到2.20~2.93.進(jìn)一步地，本文將2.5 D PUMMA算法應(yīng)用于加速計(jì)算對(duì)稱三對(duì)角矩陣的特征值分解，其加速比可達(dá)到1.2以上本文通過(guò)大量數(shù)值算例分析了2.5DMMA算法的性能，并給出了實(shí)用性建議和總結(jié)了未來(lái)的工作。