肖 健, 于 策, 孫濟(jì)洲, 李健增, 孟祥飛

(1. 天津大學(xué) 軟件學(xué)院, 天津 300350； 2. 天津大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 天津 300350； 3. 國(guó)家超級(jí)計(jì)算天津中心, 天津 300457)

我國(guó)高性能計(jì)算技術(shù)的發(fā)展日新月異。在基礎(chǔ)軟硬件層面,自主研發(fā)的超級(jí)計(jì)算機(jī)正在向Exascale(百萬(wàn)兆) 級(jí)邁進(jìn),處于國(guó)際領(lǐng)跑地位,但在大規(guī)模高性能應(yīng)用軟件的數(shù)量和質(zhì)量方面,與國(guó)際領(lǐng)先水平尚有一定差距[1-2]。作為大規(guī)模科學(xué)與工程計(jì)算、數(shù)據(jù)分析的基礎(chǔ)工具,并行計(jì)算是一門(mén)綜合性和實(shí)踐性都很強(qiáng)的前沿應(yīng)用類(lèi)課程。要保證并行計(jì)算課程的應(yīng)用性和前沿性,必須將理論、實(shí)驗(yàn)以及實(shí)際問(wèn)題有機(jī)地結(jié)合起來(lái),其中實(shí)驗(yàn)實(shí)踐環(huán)節(jié)是連接理論與實(shí)際的橋梁[3]。常規(guī)的實(shí)驗(yàn)?zāi)Ｊ蕉嘁愿拍詈椭R(shí)點(diǎn)為導(dǎo)向,將已有的串行代碼并行化,較少涉及科學(xué)計(jì)算、數(shù)值模擬等實(shí)際問(wèn)題的求解和性能優(yōu)化。為此,參考國(guó)外高校有針對(duì)性地應(yīng)用教學(xué)代碼庫(kù)的做法,嘗試構(gòu)建了一個(gè)并行計(jì)算教學(xué)用代碼框架,本文主要圍繞該套框架的設(shè)計(jì)與應(yīng)用范例方面展開(kāi),并探討如何在實(shí)驗(yàn)教學(xué)中促進(jìn)學(xué)生實(shí)現(xiàn)并行計(jì)算、數(shù)值分析、軟件工程等相關(guān)專(zhuān)業(yè)知識(shí)的融會(huì)貫通。

1 框架的設(shè)計(jì)原則

作為教學(xué)范例和課程實(shí)踐的代碼框架,除了涵蓋知識(shí)點(diǎn)要全面,還要突出重點(diǎn),可以適應(yīng)不同層次的教學(xué)要求。所以在開(kāi)發(fā)這套代碼時(shí),從兼顧通用性和實(shí)用性的角度出發(fā)，確定了3個(gè)主要設(shè)計(jì)原則。

首先,根據(jù)分布式計(jì)算和并行計(jì)算技術(shù)的發(fā)展趨勢(shì),在鞏固必修理論知識(shí)的基礎(chǔ)上采用模塊化設(shè)計(jì),學(xué)生可以從不同的層次和角度看待問(wèn)題,從而加速對(duì)各類(lèi)知識(shí)的融會(huì)貫通。近年來(lái),隨著大數(shù)據(jù)和云計(jì)算技術(shù)的發(fā)展,出現(xiàn)了新型的大規(guī)模分布式計(jì)算框架,比如Hadoop、Spark等[4],此類(lèi)框架提供了完整的任務(wù)調(diào)度和容錯(cuò)機(jī)制,允許開(kāi)發(fā)人員在更高的抽象層次上對(duì)實(shí)際問(wèn)題進(jìn)行建模,極大地簡(jiǎn)化了開(kāi)發(fā)和運(yùn)維。相比之下,以MPI為代表的傳統(tǒng)并行計(jì)算技術(shù),幾乎只提供了通信層的接口,程序開(kāi)發(fā)過(guò)程不得不在問(wèn)題模型與實(shí)現(xiàn)細(xì)節(jié)之間來(lái)回切換,這種較低的抽象層次極大地影響了工作效率。但MPI、OpenMP等作為大規(guī)?？茖W(xué)計(jì)算軟件或程序的底層工具庫(kù),仍需要學(xué)生熟練掌握,才能勝任實(shí)際問(wèn)題中程序調(diào)試、性能優(yōu)化,尤其是專(zhuān)用代碼開(kāi)發(fā)工作。為彌補(bǔ)傳統(tǒng)并行計(jì)算技術(shù)在實(shí)際問(wèn)題快速建模方面的不足,框架要能夠貫穿整個(gè)并行程序設(shè)計(jì)方法學(xué),使學(xué)生既能快速理解整體上的解決方案,又可以有針對(duì)性地練習(xí)具體技術(shù)。

其次,注重引入并行計(jì)算領(lǐng)域的前沿研究成果,實(shí)現(xiàn)簡(jiǎn)化的教學(xué)版本,引導(dǎo)學(xué)生在實(shí)際問(wèn)題中使用,激發(fā)學(xué)生的探索熱情。目前,傳統(tǒng)的空間并行技術(shù)已經(jīng)接近性能極限,導(dǎo)致實(shí)際應(yīng)用的并行加速比趨于飽和,難以高效地利用持續(xù)增加的硬件資源。近10年來(lái),國(guó)際上對(duì)時(shí)間并行理論和技術(shù)的研究一直在持續(xù)增長(zhǎng),國(guó)內(nèi)雖有少量關(guān)注,但尚沒(méi)有真正的大型應(yīng)用出現(xiàn)[5-7]。美國(guó)能源部和橡樹(shù)嶺國(guó)家實(shí)驗(yàn)室明確指出了時(shí)間并行技術(shù)在未來(lái)超級(jí)計(jì)算中的必要性[8],并開(kāi)發(fā)了相對(duì)通用的時(shí)空間混合計(jì)算框架[9]。為此,選取了相對(duì)易于理解和應(yīng)用的Parareal算法[5],在傳統(tǒng)的空間并行維度中,增加了時(shí)間并行維度,旨在通過(guò)這個(gè)方興未艾的研究分支拋磚引玉,激發(fā)學(xué)生的創(chuàng)新思路。

最后,教學(xué)代碼還需要具有一定的實(shí)用性和良好的擴(kuò)展性。實(shí)用性體現(xiàn)在能夠與實(shí)際問(wèn)題緊密結(jié)合,并為解決實(shí)際問(wèn)題提供參考,快速地達(dá)到學(xué)以致用的目的。擴(kuò)展性體現(xiàn)在能夠方便集成學(xué)生的優(yōu)秀代碼,不斷豐富教學(xué)實(shí)驗(yàn)案例,有效地實(shí)現(xiàn)教學(xué)相長(zhǎng)。這種模式在國(guó)外高校已經(jīng)屢見(jiàn)不鮮,許多成熟的開(kāi)源代碼庫(kù),甚至是Linux操作系統(tǒng)也是以類(lèi)似的方式成長(zhǎng)起來(lái)的,希望這個(gè)框架能夠引發(fā)學(xué)生對(duì)并行計(jì)算應(yīng)用開(kāi)發(fā)的興趣,孵化出實(shí)用性成果。

2 時(shí)空間混合并行框架

本文的并行計(jì)算教學(xué)代碼的核心是一個(gè)提供時(shí)空間混合并行功能的框架。圖1顯示了空間并行和時(shí)間并行的概念,菱形方塊代表計(jì)算資源(MPI進(jìn)程等)。傳統(tǒng)的空間并行技術(shù),除了空間維度外,根據(jù)具體問(wèn)題,還可以有頻域、能級(jí)等方向上的并行,理論上,此類(lèi)并行劃分中計(jì)算依賴僅限于相鄰分區(qū)之間,計(jì)算按照時(shí)間順序串行推進(jìn),在概念上易于理解和實(shí)現(xiàn)。時(shí)間并行可以在不同的時(shí)間點(diǎn)上同時(shí)開(kāi)始計(jì)算,而物理上這些時(shí)間點(diǎn)上的數(shù)值是有嚴(yán)格的前后順序依賴關(guān)系的,這在形式上不太符合直觀認(rèn)識(shí),需要掌握其背后的數(shù)學(xué)原理才能更好地應(yīng)用。

圖1 時(shí)空間混合并行示意圖

2.1 時(shí)間并行技術(shù)概述

時(shí)間并行的概念早在50年前就已經(jīng)提出,但直至2001年才有實(shí)用性算法出現(xiàn),近10年來(lái)獲得持續(xù)關(guān)注,并開(kāi)始應(yīng)用于實(shí)際問(wèn)題。本文中使用的Parareal算法的基本邏輯并不復(fù)雜,可以分別從牛頓法、多重網(wǎng)格法等經(jīng)典算法中推導(dǎo)出來(lái),此處只給出基本思路,詳細(xì)內(nèi)容可參考文獻(xiàn)[5]。簡(jiǎn)而言之,Parareal算法由粗細(xì)2種粒度的時(shí)間積分器構(gòu)成,可以看作是時(shí)間維度上的兩重網(wǎng)格,亦可以看作是時(shí)間維度上的外推法[6]。細(xì)粒度求解器用于得到精度較高的近似解,粗粒度求解器用于得到修正項(xiàng),隨著時(shí)間演化反復(fù)進(jìn)行修正迭代,根據(jù)殘差判斷是否收斂。Parareal的修正迭代公式如下：

圖2形象地描述了Parareal算法的求解過(guò)程,物理模型的演化時(shí)間被劃分為了5個(gè)并行的時(shí)間片,時(shí)間軸上不同間隔的刻度分別代表粗細(xì)粒度的積分步長(zhǎng),綠色實(shí)線表示光滑的解析解或能與其很好重合的近似解,藍(lán)色三角形代表粗粒度的近似解,紅色四邊形代表細(xì)粒度的近似解,黃色五邊形代表修正后的更精確的近似解,經(jīng)過(guò)反復(fù)迭代,逐漸逼近時(shí)間終點(diǎn)的符合收斂條件的近似解(紅色實(shí)心圓)。

圖2 Parareal時(shí)間并行算法的基本原理

從算法的描述中可以看出,與空間并行不同,物理上時(shí)間并行中的時(shí)間依賴并不能完全消除。粗粒度求解器的作用就在為每個(gè)時(shí)間片的起點(diǎn)或終點(diǎn)提供一個(gè)估計(jì)值,這個(gè)過(guò)程是串行的,必須依賴前一個(gè)時(shí)間片的計(jì)算結(jié)果。有了這個(gè)估計(jì)值,細(xì)粒度求解器才能并行執(zhí)行,起到整體加速的目的。因此,時(shí)間并行算法的加速效果主要取決于粗細(xì)求解器的相對(duì)計(jì)算量和整體的收斂速率,這些又進(jìn)一步與實(shí)際的物理模型和采用的具體數(shù)值算法有關(guān)。

2.2 框架的體系結(jié)構(gòu)

框架的設(shè)計(jì)遵循了第1節(jié)的3個(gè)基本原則,同時(shí)參考了Flash code等成熟的大型數(shù)值模擬框架[10],采用了插件式和模塊化的結(jié)構(gòu)。如圖3所示,正交的空間并行和時(shí)間并行分別作為底層基礎(chǔ)和驅(qū)動(dòng)器,負(fù)責(zé)數(shù)據(jù)管理和流程控制；線性求解器、時(shí)間積分算法、輸入輸出、性能監(jiān)控等均作為單獨(dú)的模塊,以插件形式集成進(jìn)來(lái)。

圖3 時(shí)空間混合并行框架的體系結(jié)構(gòu)

在抽象層次上,借鑒了Chapel[11]等新型并行語(yǔ)言的應(yīng)用接口模式,除了傳統(tǒng)的MPI通信層接口,還提供了基于網(wǎng)格的上層抽象。這樣可以鍛煉學(xué)生從不同的層次和角度去解決問(wèn)題,在初期建模和任務(wù)定義階段,專(zhuān)心于業(yè)務(wù)邏輯和流程；在后期大規(guī)模計(jì)算和性能優(yōu)化階段,可以深入挖掘MPI在消息通信方面的潛力。

在并行功能上,可以支持單一進(jìn)程的串行模式、基于OpenMP的多線程、基于MPI的多進(jìn)程空間并行、時(shí)間并行等,各類(lèi)并行功能可以單獨(dú)使用、也可以混合使用,比如：OpenMP-MPI的兩級(jí)并行、MPI時(shí)空間混合并行、OpenMP-MPI時(shí)空間混合并行等。豐富的功能組合可以讓學(xué)生通過(guò)對(duì)比掌握各類(lèi)并行方法的特點(diǎn)和適用性。

在實(shí)用性上,支持多核的普通臺(tái)式機(jī)、工作站、多節(jié)點(diǎn)的集群環(huán)境、以及超級(jí)計(jì)算機(jī)系統(tǒng)?？蚣芴峁┝艘恍┩ㄓ玫木€性求解器以及時(shí)間積分模版,包括超松弛法(SOR)、雙共軛梯度穩(wěn)定法(BiCGStab)、牛頓拉夫遜法等,所有運(yùn)行參數(shù)可通過(guò)配置文件指定,方便調(diào)試和快速構(gòu)建原型。各個(gè)層次(空間網(wǎng)格、各類(lèi)求解器、時(shí)間并行算法)均可單獨(dú)擴(kuò)展,支持HDF5格式的大文件輸出、自動(dòng)完成計(jì)算和通信性能的統(tǒng)計(jì)分析,為算法優(yōu)化提供依據(jù)。

2.3 框架的實(shí)現(xiàn)方法

圖4 框架的實(shí)現(xiàn)流程

代碼在組織結(jié)構(gòu)上,特別考慮了擴(kuò)展性和實(shí)驗(yàn)教學(xué)需求。通過(guò)共享基礎(chǔ)代碼的功能和算法模版,實(shí)驗(yàn)課題和物理模型均在各自的目錄內(nèi)獨(dú)立發(fā)展。希望通過(guò)不斷豐富實(shí)驗(yàn)課題和實(shí)例代碼,積累教學(xué)成果,并適時(shí)轉(zhuǎn)化成實(shí)用的解決方案。為方便學(xué)習(xí)交流、擴(kuò)展升級(jí)以及成果積累,該框架已經(jīng)采用開(kāi)源項(xiàng)目的形式發(fā)布,目前還得到了時(shí)間并行學(xué)術(shù)組織的認(rèn)可,列入了時(shí)間并行代碼資源庫(kù)。開(kāi)源的形式還有助于學(xué)生練習(xí)現(xiàn)代軟件工程的整套流程,起到綜合實(shí)驗(yàn)的效果。

3 物理模型與實(shí)驗(yàn)課題

為了讓學(xué)生深入理解并掌握并行計(jì)算的應(yīng)用方法,將物理模型經(jīng)過(guò)簡(jiǎn)化,作為實(shí)驗(yàn)課題集成到框架中。首先引入的是在物理模型和數(shù)值計(jì)算中具有普遍代表性的熱擴(kuò)散方程,之后在擴(kuò)散問(wèn)題的基礎(chǔ)上,將具有廣泛實(shí)際應(yīng)用的多相場(chǎng)(phase field)問(wèn)題作為重點(diǎn)實(shí)驗(yàn)課題。多相場(chǎng)的數(shù)值求解一直是科學(xué)計(jì)算領(lǐng)域的研究重點(diǎn),我國(guó)神威?太湖之光超級(jí)計(jì)算機(jī)獲得戈登貝爾獎(jiǎng)的應(yīng)用均涉及相場(chǎng)模擬[12]。通過(guò)將實(shí)驗(yàn)課題與實(shí)際問(wèn)題、研究前沿相結(jié)合的方式,促進(jìn)學(xué)生對(duì)各類(lèi)知識(shí)的融會(huì)貫通,學(xué)以致用。

擴(kuò)散問(wèn)題最具代表性,且數(shù)值算法簡(jiǎn)單,適合作為教學(xué)范例。在簡(jiǎn)化后的熱擴(kuò)散模型中,擴(kuò)散系數(shù)λ為常數(shù),初始值和邊界條件給定。在框架原型系統(tǒng)的開(kāi)發(fā)階段,驗(yàn)證了時(shí)空混合并行算法對(duì)熱擴(kuò)散問(wèn)題的加速效果,詳細(xì)的實(shí)驗(yàn)結(jié)果表明在問(wèn)題規(guī)模一定的情況下,空間并行的性能(13.5倍)達(dá)到極限后,再利用時(shí)空混合并行(100個(gè)并行時(shí)間片),最終取得了整體200倍以上的性能提升[13]。

λ2Φ(熱擴(kuò)散方程)

(1)

(Allen-Cahn方程)

(2)

在擴(kuò)散項(xiàng)的基礎(chǔ)上加上反應(yīng)項(xiàng),就得到了多相場(chǎng)模擬的主要方程之一的Allen-Cahn方程。該類(lèi)方程的求解過(guò)程涉及有限差分、有限元等數(shù)值計(jì)算的經(jīng)典方法,且由于計(jì)算量大、耗時(shí)長(zhǎng),一直是高性能計(jì)算領(lǐng)域的代表型應(yīng)用。雖然框架針對(duì)的是常系數(shù)的簡(jiǎn)化版,但由于增加了非線性的反應(yīng)項(xiàng),算法的性能優(yōu)化變得極有挑戰(zhàn)性。學(xué)生可以從數(shù)值算法的混合并行化、時(shí)間并行的收斂性、網(wǎng)格結(jié)構(gòu)及網(wǎng)絡(luò)傳輸優(yōu)化等多個(gè)層次開(kāi)展實(shí)驗(yàn)。初步實(shí)驗(yàn)結(jié)果表明,在一定條件下,時(shí)空間混合并行技術(shù)可加速多相場(chǎng)的計(jì)算,但需要探索和解決的問(wèn)題還很多,較適合作為開(kāi)放性實(shí)驗(yàn)課題。

4 在教學(xué)實(shí)驗(yàn)中的應(yīng)用

一直以來(lái),我校高性能計(jì)算教學(xué)團(tuán)隊(duì)都采用了案例和任務(wù)驅(qū)動(dòng)型實(shí)驗(yàn)教學(xué)方法[14]。除計(jì)算機(jī)專(zhuān)業(yè)外,還面向全校相關(guān)專(zhuān)業(yè)的研究生開(kāi)設(shè)并行計(jì)算的高級(jí)選修課程。該框架源自團(tuán)隊(duì)的內(nèi)部積累,也是與國(guó)內(nèi)外同行交流學(xué)習(xí)的成果[13]?；谠摽蚣?同時(shí)借鑒其他高校的經(jīng)驗(yàn)[15-16],針對(duì)本科生、研究生以及不同專(zhuān)業(yè)的學(xué)習(xí)需求,進(jìn)一步加強(qiáng)了教學(xué)實(shí)驗(yàn)課程的細(xì)分。

對(duì)于計(jì)算機(jī)專(zhuān)業(yè)側(cè)重并行技術(shù)和數(shù)值算法,實(shí)驗(yàn)涵蓋了空間網(wǎng)格劃分和管理、文件并行讀寫(xiě)、數(shù)值算法并行化等普通專(zhuān)業(yè)課題,也包括開(kāi)發(fā)自適應(yīng)網(wǎng)格的接口,實(shí)現(xiàn)其他時(shí)間并行算法等具有較高難度的課題,鼓勵(lì)學(xué)生為框架貢獻(xiàn)自己的求解器,擴(kuò)充和優(yōu)化框架的基礎(chǔ)功能。對(duì)于相關(guān)專(zhuān)業(yè)的選修課,則利用框架的高層接口,側(cè)重上層建模能力的訓(xùn)練,解決學(xué)習(xí)科研中的實(shí)際問(wèn)題。圖4(b)展示了此類(lèi)實(shí)驗(yàn)的流程,首先學(xué)生利用有限差分或有限元方法,完成模型的離散化,然后從框架提供的算法中選擇合適的組合,并編寫(xiě)問(wèn)題特有的計(jì)算代碼(stencil code),設(shè)置初值和邊界條件,最后進(jìn)行實(shí)驗(yàn)方法的可行性驗(yàn)證。此類(lèi)實(shí)驗(yàn)可以為框架增加實(shí)際的應(yīng)用課題,豐富教學(xué)案例。對(duì)于課程設(shè)計(jì),鼓勵(lì)計(jì)算機(jī)專(zhuān)業(yè)和其他專(zhuān)業(yè)的學(xué)生組隊(duì),將實(shí)際問(wèn)題建模和求解過(guò)程優(yōu)化結(jié)合起來(lái),培育實(shí)用性解決方案。目前,相場(chǎng)模擬作為第一個(gè)開(kāi)放性實(shí)驗(yàn)課題,還處于收集和優(yōu)化算法階段。

5 結(jié)語(yǔ)

本文提出的時(shí)空間混合并行計(jì)算框架,從原型系統(tǒng)開(kāi)發(fā)到開(kāi)源項(xiàng)目的發(fā)布?xì)v時(shí)2年,并在國(guó)內(nèi)外的超級(jí)計(jì)算機(jī)上完成了測(cè)試和功能驗(yàn)證。高性能計(jì)算相關(guān)的實(shí)踐教學(xué),可通過(guò)對(duì)源代碼的學(xué)習(xí)分析、改造優(yōu)化、模型求解等多種方式,有效鍛煉學(xué)生綜合運(yùn)用知識(shí)、解決實(shí)際問(wèn)題的能力,同時(shí)開(kāi)源形式有助于不斷豐富教學(xué)案例和實(shí)驗(yàn)課題。除了多相場(chǎng)之外,將陸續(xù)精選出一些難度適中的科學(xué)計(jì)算問(wèn)題,引導(dǎo)學(xué)生廣泛探索,并以天津超算中心為平臺(tái)依托,加快產(chǎn)學(xué)研結(jié)合。