[發明專利]一種適應于“神威·太湖之光”上HPCG優化的數據結構及其高效實現方法

有效

• 申請號: 201710353362.2
• 申請日: 2017-05-18
• 公開（公告）號: CN107273094B
• 公開（公告）日: 2020-06-16
• 發明（設計）人: 敖玉龍;楊超;劉芳芳;尹萬旺;魏迪;袁欣輝;蔣麗娟
• 申請（專利權）人: 中國科學院軟件研究所;無錫江南計算技術研究所
• 主分類號: G06F9/30
• 分類號: G06F9/30;G06F9/32;G06F9/38;G06F17/16
• 代理公司: 北京科迪生專利代理有限責任公司 11251
• 代理人: 楊學明;顧煒

本發明公開了一種適應于“神威·太湖之光”上HPCG優化的數據結構及其高效實現方法，基于“神威·太湖之光”上的申威眾核處理器體系結構特征和HPCG算法優化的需要，使用了改進ELL格式的數據結構對原始數據結構進行替換，除了包含矩陣數據本身的數據結構，還支持分塊著色，索引轉換，進程通信，以及向量位置映射等相關的數據結構，并且中間處理過程采用了申威眾核平臺提供的Athread多線程庫進行并行，最終應用于HPCG算法的核心函數SpMV和SymGS優化過程中，相應的性能和帶寬百分比取得了一致性的加速比，最高分別為18.2和17.6。

技術領域

本發明所涉及自定義數據結構及其高效實現方法，支撐了HighPerformanceConjugate Gradients(HPCG，高性能的共軛梯度)基準測試程序在“神威·太湖之光”超計算機上的高性能實現。其中，中間處理過程使用了國產申威眾核平臺提供的Athread庫進行多線程并行。

背景技術

High Performance Conjugate Gradients(HPCG，高性能的共軛梯度)基準測試程序是一種對全世界超級計算機進行排名的新標準。該測試基準主要用于衡量超級計算機解決大規模稀疏線性系統的能力，相比于目前TOP500排名所采用的HighPerformanceLinpack(HPL)基準測試，其計算、訪存與通信模式更能代表目前基于偏微分方程求解的一類廣泛的科學與工程計算應用，也有助于更全面地反映系統的訪存帶寬和延遲以及通信能力。大規模稀疏線性系統部署在高性能計算機上進行計算時，其依賴的底層數據結構對于求解線性系統的算法至關重要。同樣地，數據結構本身的構造過程，對訪存有較高的需求，若不能根據高性能計算機的體系結構進行有效優化，將非常耗時。

HPCG源于半結構網格上的三維熱傳導應用，核心是將三維規則區域上的Poisson方程采用有限差分法進行離散，最終轉換成一個稀疏線性方程組的求解問題。在大規模并行環境中，HPCG使用三維區域分解策略，也就是按照3個維度將整個計算區域劃分成子區域，然后每個子區域被分配一個MPI進程。其中每個子區域的規模由輸入參數指定，即如果(nx×ny×nz)是由一個MPI進程處理的子區域大小，且(npx×npy×npz)是總進程數，那么所解問題的全局規模就為(npx×nx)×(npy×ny)×(npz×nz)。

由于HPCG使用的是27點stencil，在HPCG中，每個網格點的更新都依賴其周圍緊鄰的最多26個鄰居點，可選取的值為：26(內部點)、17(邊界面上的點)、11(邊界線上的點)和7(邊界頂點)。最終生成的稀疏線性系統具有下述特點：內部點對應27個非零元，邊界點對應7-18個非零元，對稱正定非奇異，已知精確解為1.0，匹配的右端項的初始值為0。參考版本采用的數據結構主要是Compressed Sparse Row(CSR)格式。具體數據結構如下：

整個結構主要包含三個部分：矩陣數據存儲，索引映射，以及進程間通信。其中，與矩陣的數據存儲相關的主要有：nonzerosInRow存儲矩陣每行非零元的個數，mtxIndG存儲矩陣的全局索引，mtxIndL存儲矩陣的進程內索引，matrixValues存儲矩陣元素的數值，matrixDiagonal存儲矩陣對角線元素的數值。與索引映射相關的主要有：globalToLocalMap用來進行全局索引到進程內索引的轉換，localToGlobalMap用來進行進程內索引到全局索引的轉換。在MPI多進程環境下，與進程間通信相關的主要有：elementsToSend存儲向鄰居矩陣發送的未知向量x的索引，neighbors存儲鄰居進程的進程ID，receiveLength存儲接收每個鄰居進程外區數據的個數，sendLength存儲向每個鄰居進程發送數據的個數，sendBuffer用于鄰居通信時存儲向鄰居進程發送的未知向量x。