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

馮 慧

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

0 引言

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

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

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

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

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

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

2 應用通信獲取及分析

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

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

3 測試

3.1 測試環境及測試程序

在兩類架構上對兩種類型應用進行測試。

3.1.1 兩種架構

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

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

3.1.2 兩類應用

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

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

3.2 測試結果及分析

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

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

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

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

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

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

4 結語

本文針對當前的拓撲感知映射，從系統架構和應用特點兩方面分析了進行拓撲感知映射性能優化時需要考慮的問題，并分析了目前該領域相關研究進展及特點。

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