基于多核的進程拓撲感知映射研究

馮 慧

（山東科技大學(xué)計算機科學(xué)與工程學(xué)院，山東青島 266000）

0 引言

多核架構(gòu)目前為并行計算中較常見的計算架構(gòu)，未來幾年芯片上的核心數(shù)量仍會急劇增長，在高性能計算中，集群已從單個網(wǎng)絡(luò)互連的單處理器轉(zhuǎn)變?yōu)閺?fù)雜且高度分層的結(jié)構(gòu)，如中國超級計算機中心的超級計算機系統(tǒng)神威·太湖之光［1］由40 960 個節(jié)點組成。通常每個計算節(jié)點包含多個共享內(nèi)存的多核處理器，節(jié)點內(nèi)的內(nèi)存訪問時間取決于計算核心與內(nèi)存之間的距離。與不同芯片上的計算核相比，同一芯片上的計算核之間通信延遲要低得多，通信帶寬要高得多。因此，編程標(biāo)準(zhǔn)及其實現(xiàn)在充分發(fā)揮硬件系統(tǒng)計算潛力方面起著關(guān)鍵作用。在并行編程標(biāo)準(zhǔn)中，消息傳遞接口（Message Passing Interface，MPI）因其豐富的接口而廣受歡迎，但是MPI 是一種跨平臺的編程標(biāo)準(zhǔn)，設(shè)計成獨立于硬件、不提供拓撲感知的進程映射功能。一般的MPI 提供諸如MPI_DIST_GRAPH_CREATE［2］功能創(chuàng)建拓撲，但由于未考慮底層架構(gòu)，所以并不能提供有效的映射方法。

如何更好地利用多核體系架構(gòu)是真正的挑戰(zhàn)。為在多核環(huán)境下獲得最佳性能，必須考慮到硬件底層架構(gòu)和應(yīng)用特點。關(guān)于拓撲感知映射研究有：Hoffler［3］提出結(jié)合幾種啟發(fā)式算法的網(wǎng)格互連體系結(jié)構(gòu)的通用拓撲映射策略；Bhatele［4］針對網(wǎng)格互聯(lián)提出規(guī)則通信圖的自動映射方法；Hatazaki［5］為特殊的HP 集群實現(xiàn)MPI 拓撲映射功能；Mercier 等［6］使用圖分區(qū)工具SCOTCH［7］實現(xiàn)加權(quán)通信圖到加權(quán)節(jié)點架構(gòu)圖映射，但其沒有考慮網(wǎng)絡(luò)拓撲；Jeannot 等［8］提出TreeMatch 算法計算NUMA 集群中進程到資源的近似最優(yōu)映射；Wu 等［9］提出遞歸樹映射算法和遞歸二分映射算法，解決并行應(yīng)用程序的層次任務(wù)映射；Li 等［10］提出一種基于拓撲感知進程映射的同構(gòu)樹映射算法，該算法根據(jù)進程間的親和性將進程分區(qū)映射；Brandfass 等［11］通過重新排序MPI 的進程號建立MPI 進程到CPU 內(nèi)核的映射；Pellegrini［12］提出一種基于應(yīng)用程序進程圖和目標(biāo)體系結(jié)構(gòu)圖的遞歸雙分割映射算法進行映射。

本文針對當(dāng)前進程拓撲感知映射方法進行測試分析，重點討論硬件架構(gòu)和應(yīng)用通信特點二者在多核環(huán)境下進程拓撲感知映射中的影響，總結(jié)解決此類問題的研究思路：利用不同類型的應(yīng)用（CGKernal 和分子動力學(xué)）在兩種系統(tǒng)（天河1A 和曙光）上進行測試，依據(jù)測試結(jié)果分析不同架構(gòu)處理應(yīng)用時的不同特點，總結(jié)進程拓撲感知映射的適用范圍，以更好地發(fā)揮拓撲感知映射優(yōu)勢處理更復(fù)雜的大規(guī)模計算問題，硬件的架構(gòu)選擇和不同類型應(yīng)用的選擇在進程拓撲感知映射中同等重要。

1 拓撲感知信息獲取及分析

檢索有關(guān)底層硬件的內(nèi)存層次結(jié)構(gòu)、內(nèi)核編號等信息并非易事，目前一些感知工具可獲得硬件的底層結(jié)構(gòu)，最常見的工具是HardwareLocality（HWLOC）［13］。這種工具能輕松地提供有關(guān)廣泛系統(tǒng)上各種高速緩存級別信息，通過HWLOC 收集硬件的詳細內(nèi)部信息，如插槽的數(shù)量、計算核心數(shù)量以及內(nèi)存層次信息（包括NUMA 節(jié)點中的多級緩存）。使用HWLOC 將硬件結(jié)構(gòu)抽象成樹進行建模，其深度與層次結(jié)構(gòu)中硬件組件的深度（如網(wǎng)絡(luò)交換機、機柜、節(jié)點、處理器、緩存、核心）相對應(yīng)，其葉子節(jié)點是架構(gòu)的計算單元。

HWLOC 的靈活性使其允許跨操作系統(tǒng)對硬件架構(gòu)進行建模。HWLOC 實現(xiàn)了眾多功能的庫函數(shù)，可被其它軟件調(diào)用，因此可用來動態(tài)建立模型。另一種分析硬件方法是使用LINUX［14］查看CPU 信息指令，雖然可以通過進一步分析得出硬件的架構(gòu)信息，但前提是必須對硬件信息比較了解，才能準(zhǔn)確無誤地分析出硬件信息。另外，通過LINUX 自帶的命令分析出來的硬件信息并不完整，cache的層次不能得到完整構(gòu)建。相反，通過HWLOC 可以檢測到任意節(jié)點的硬件信息，通過命令行方式以PDF 或XML格式對硬件信息進行輸出，使硬件信息更加直觀，這也是使用HWLOC 的一大便利。

2 應(yīng)用通信獲取及分析

為獲得應(yīng)用的通信信息，Zhang 等［15］提出OPP 方法，根據(jù)通信庫中集合通信的實現(xiàn)，將集合通信轉(zhuǎn)換為一系列點對點通信操作；Buntinas［16］通過修改MPICH2［17］和Open MPI 堆棧中的低級通信層，在點對點和集合通信情況下詳盡跟蹤數(shù)據(jù)交換信息。由于該收集應(yīng)用通信信息的方法比較簡單，因此不會影響應(yīng)用程序的執(zhí)行。還有其他的MPI 實現(xiàn)者也采用這種方法，Chen 等［18］結(jié)合應(yīng)用程序代碼的靜態(tài)分析和對修改后的應(yīng)用程序動態(tài)執(zhí)行，使該應(yīng)用程序執(zhí)行速度更快，同時保留了與原始應(yīng)用程序相同的通信模式，目的是將確定通信模式所需的時間減少幾個數(shù)量級；Bosilca 等［19］提供了基于MPI 工具信息接口標(biāo)準(zhǔn)的MPI，在不修改應(yīng)用程序情況下進行通信信息追蹤。要注意的是，在所有方法中都必須執(zhí)行原始版本或更簡單版本的應(yīng)用程序。

應(yīng)用通信特點在拓撲感知映射過程中的作用至關(guān)重要，可從兩個方面去考慮應(yīng)用通信類型：①應(yīng)用通信是否規(guī)則；②應(yīng)用通信占比大小。較規(guī)則的通信應(yīng)用特點是每個進程和其它所有進程進行通信傳送的信息量幾乎一樣。另外不能忽略應(yīng)用通信占比，一般來講，應(yīng)用通信時間占總體運行時間較小的應(yīng)用對拓撲感知映射效果不會很好。

3 測試

3.1 測試環(huán)境及測試程序

在兩類架構(gòu)上對兩種類型應(yīng)用進行測試。

3.1.1 兩種架構(gòu)

（1）TH-1A。登陸節(jié)點由8 個CPU 插槽組成，每個CPU 由8 個計算核心組成（不考慮開啟超線程情況），登陸節(jié)點一共有64 個計算核心。每個CPU 上的8 個核心分別擁有32KB 的一級指令cache、32KB 的一級數(shù)據(jù)cache 和256KB 的二級cache，同時每個CPU 上的8 個計算核心通過片上互聯(lián)共享18MB 的三級cache；TH-1A 登陸節(jié)點的8個CPU 通過PCI 總線技術(shù)共享256GB 內(nèi)存。

（2）曙光集群單節(jié)點架構(gòu)。曙光登陸節(jié)點由2 個CPU插槽組成，每個CPU 由8 個計算核心組成（不考慮開啟超線程情況），登陸節(jié)點一共有16 個計算核心，每個CPU 上的8 個核心分別擁有32KB 的一級指令cache、32KB 的一級數(shù)據(jù)cache 和256KB 的二級cache，同時每個CPU 上的8 個計算核心通過片上互聯(lián)共享20MB 的三級cache；曙光登陸節(jié)點的2 個CPU 通過PCI 總線技術(shù)共享64GB 內(nèi)存。

3.1.2 兩類應(yīng)用

（1）分子動力學(xué)。分子動力學(xué)（Molecular Dynamics，MD）模擬指使用數(shù)值方法，利用計算機模擬原子核和電子所構(gòu)成的多體系統(tǒng)運動過程，廣泛應(yīng)用于物理、化學(xué)、生物、材料、醫(yī)學(xué)等多個領(lǐng)域，用來研究系統(tǒng)的結(jié)構(gòu)和性質(zhì)。通過對MD 應(yīng)用各部分運行時間進行分析，得知該應(yīng)用的大部分運行時間在進行計算，進程和進程間的通信時間占整個應(yīng)用運行時間極小部分，幾乎可以忽略不計。通過跟蹤MD 應(yīng)用的進程間通信信息，對應(yīng)用進程間通信的信息量進行分析，發(fā)現(xiàn)進程間的通信不規(guī)則以及進程之間信息交換總量小，所以MD 屬于通信不規(guī)則且通信量占比很小的應(yīng)用。

（2）CG Kernal。CG（Conjugate Gradient）是NAS Parallel Benchmarks（NPB）［20］中的一個核心程序，用于求解大型稀疏對稱正定矩陣最小特征值的近似值，它表征了非結(jié)構(gòu)風(fēng)格計算和非規(guī)整遠程通信計算類問題。通過跟蹤MD 應(yīng)用的進程間通信信息，對應(yīng)用進程間通信的信息量大小進行分析，發(fā)現(xiàn)進程間通信是不規(guī)則的，同時該應(yīng)用進程間通信的信息總量較大，所以CG 應(yīng)用屬于通信不規(guī)則且通信量較大的應(yīng)用。

3.2 測試結(jié)果及分析

分別對MD 和CG 兩類應(yīng)用在TH-1A 和曙光集群上進行3 種映射算法（自動調(diào)度、RR 算法、TreeMatch 算法）測試，測試結(jié)果見圖1—圖4。

Fig.1 Molecular dynamics（TH-1A）圖1 分子動力學(xué)（TH-1A）

Fig.2 Molecular dynamics（Dawn）圖2 分子動力學(xué)（曙光）

Fig.3 CG Kernal（TH-1A）圖3 CG Kernal（TH-1A）

Fig.4 CG Kernal（Dawn）圖4 CG Kernal（曙光）

在TH-1A 和曙光架構(gòu)上分別對3 種調(diào)度算法進行分子動力學(xué)映射綁定測試。3 種調(diào)度映射算法都沒有表現(xiàn)出較好的計算結(jié)果，這是因為分子動力學(xué)中進程間通信的時間占總體執(zhí)行時間比較小，所以進行拓撲感知映射不能得到好的效果，見圖1 和圖2。分別對CG Kernal 進行3 種調(diào)度測試，CG Kernal 在TH-1A 上使用匹配樹算法，和另外兩種算法相比表現(xiàn)出較好性能，相反CG Kernal 在曙光上3種調(diào)度方式結(jié)果差異性不明顯，如圖3 和圖4 的測試結(jié)果所示。使用相同應(yīng)用在不同架構(gòu)上進行的測試結(jié)果相差較大，分析原因是硬件架構(gòu)不同。在TH-1A 上使用64 個計算核心進行測試，由8 個CPU 插槽組成。由于計算核心數(shù)量較多，所以計算核心之間存在的層次關(guān)系也較多，需要描述的親和性信息也更加復(fù)雜。而在曙光上使用16 個計算核心，由兩個CPU 插槽組成，相較于TH-1A 計算核心數(shù)量較少，計算核心之間層次較單一，親和關(guān)系較簡單，由此可見硬件架構(gòu)特點在拓撲感知映射中至關(guān)重要。

4 結(jié)語

本文針對當(dāng)前的拓撲感知映射，從系統(tǒng)架構(gòu)和應(yīng)用特點兩方面分析了進行拓撲感知映射性能優(yōu)化時需要考慮的問題，并分析了目前該領(lǐng)域相關(guān)研究進展及特點。

綜合當(dāng)前存在的拓撲感知映射方法硬件架構(gòu)差異較大、應(yīng)用通信特點不同問題，從硬件的架構(gòu)層次及應(yīng)用的通信特點兩個方面考慮多核環(huán)境下進行拓撲感知映射性能提升，這也是未來研究的趨勢。