時空間混合并行框架及其在并行計算實驗教學中的應用

肖 健, 于 策, 孫濟洲, 李健增, 孟祥飛

(1. 天津大學 軟件學院, 天津 300350； 2. 天津大學 計算機科學與技術學院, 天津 300350； 3. 國家超級計算天津中心, 天津 300457)

我國高性能計算技術的發展日新月異。在基礎軟硬件層面,自主研發的超級計算機正在向Exascale(百萬兆) 級邁進,處于國際領跑地位,但在大規模高性能應用軟件的數量和質量方面,與國際領先水平尚有一定差距[1-2]。作為大規?？茖W與工程計算、數據分析的基礎工具,并行計算是一門綜合性和實踐性都很強的前沿應用類課程。要保證并行計算課程的應用性和前沿性,必須將理論、實驗以及實際問題有機地結合起來,其中實驗實踐環節是連接理論與實際的橋梁[3]。常規的實驗模式多以概念和知識點為導向,將已有的串行代碼并行化,較少涉及科學計算、數值模擬等實際問題的求解和性能優化。為此,參考國外高校有針對性地應用教學代碼庫的做法,嘗試構建了一個并行計算教學用代碼框架,本文主要圍繞該套框架的設計與應用范例方面展開,并探討如何在實驗教學中促進學生實現并行計算、數值分析、軟件工程等相關專業知識的融會貫通。

1 框架的設計原則

作為教學范例和課程實踐的代碼框架,除了涵蓋知識點要全面,還要突出重點,可以適應不同層次的教學要求。所以在開發這套代碼時,從兼顧通用性和實用性的角度出發，確定了3個主要設計原則。

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

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

最后,教學代碼還需要具有一定的實用性和良好的擴展性。實用性體現在能夠與實際問題緊密結合,并為解決實際問題提供參考,快速地達到學以致用的目的。擴展性體現在能夠方便集成學生的優秀代碼,不斷豐富教學實驗案例,有效地實現教學相長。這種模式在國外高校已經屢見不鮮,許多成熟的開源代碼庫,甚至是Linux操作系統也是以類似的方式成長起來的,希望這個框架能夠引發學生對并行計算應用開發的興趣,孵化出實用性成果。

2 時空間混合并行框架

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

圖1 時空間混合并行示意圖

2.1 時間并行技術概述

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

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

圖2 Parareal時間并行算法的基本原理

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

2.2 框架的體系結構

框架的設計遵循了第1節的3個基本原則,同時參考了Flash code等成熟的大型數值模擬框架[10],采用了插件式和模塊化的結構。如圖3所示,正交的空間并行和時間并行分別作為底層基礎和驅動器,負責數據管理和流程控制；線性求解器、時間積分算法、輸入輸出、性能監控等均作為單獨的模塊,以插件形式集成進來。

圖3 時空間混合并行框架的體系結構

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

在并行功能上,可以支持單一進程的串行模式、基于OpenMP的多線程、基于MPI的多進程空間并行、時間并行等,各類并行功能可以單獨使用、也可以混合使用,比如：OpenMP-MPI的兩級并行、MPI時空間混合并行、OpenMP-MPI時空間混合并行等。豐富的功能組合可以讓學生通過對比掌握各類并行方法的特點和適用性。

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

2.3 框架的實現方法

圖4 框架的實現流程

代碼在組織結構上,特別考慮了擴展性和實驗教學需求。通過共享基礎代碼的功能和算法模版,實驗課題和物理模型均在各自的目錄內獨立發展。希望通過不斷豐富實驗課題和實例代碼,積累教學成果,并適時轉化成實用的解決方案。為方便學習交流、擴展升級以及成果積累,該框架已經采用開源項目的形式發布,目前還得到了時間并行學術組織的認可,列入了時間并行代碼資源庫。開源的形式還有助于學生練習現代軟件工程的整套流程,起到綜合實驗的效果。

3 物理模型與實驗課題

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

擴散問題最具代表性,且數值算法簡單,適合作為教學范例。在簡化后的熱擴散模型中,擴散系數λ為常數,初始值和邊界條件給定。在框架原型系統的開發階段,驗證了時空混合并行算法對熱擴散問題的加速效果,詳細的實驗結果表明在問題規模一定的情況下,空間并行的性能(13.5倍)達到極限后,再利用時空混合并行(100個并行時間片),最終取得了整體200倍以上的性能提升[13]。

λ2Φ(熱擴散方程)

(1)

(Allen-Cahn方程)

(2)

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

4 在教學實驗中的應用

一直以來,我校高性能計算教學團隊都采用了案例和任務驅動型實驗教學方法[14]。除計算機專業外,還面向全校相關專業的研究生開設并行計算的高級選修課程。該框架源自團隊的內部積累,也是與國內外同行交流學習的成果[13]?；谠摽蚣?同時借鑒其他高校的經驗[15-16],針對本科生、研究生以及不同專業的學習需求,進一步加強了教學實驗課程的細分。

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

5 結語

本文提出的時空間混合并行計算框架,從原型系統開發到開源項目的發布歷時2年,并在國內外的超級計算機上完成了測試和功能驗證。高性能計算相關的實踐教學,可通過對源代碼的學習分析、改造優化、模型求解等多種方式,有效鍛煉學生綜合運用知識、解決實際問題的能力,同時開源形式有助于不斷豐富教學案例和實驗課題。除了多相場之外,將陸續精選出一些難度適中的科學計算問題,引導學生廣泛探索,并以天津超算中心為平臺依托,加快產學研結合。