[發明專利]稀疏矩陣向量乘并行任務粒度參數自動調優方法和裝置

有效

• 申請號: 202010880655.8
• 申請日: 2020-08-27
• 公開（公告）號: CN111984418B
• 公開（公告）日: 2022-09-02
• 發明（設計）人: 方建濱;黃春;唐滔;彭林;張鵬;范小康;崔英博
• 申請（專利權）人: 中國人民解放軍國防科技大學
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F9/48;G06F17/16;G06N20/00;G06N20/10
• 代理公司: 北京豐浩知識產權代理事務所(普通合伙) 11781
• 代理人: 董超

本發明屬于并行計算領域，公開了一種稀疏矩陣向量乘并行任務粒度參數的自動調優方法和裝置，其方法包括預測模型構建步驟，使用機器學習的方法構建預測模型；統計特征取值獲取步驟，對矩陣原始數據文件進行分析，獲取矩陣的統計特征取值；最佳任務粒度參數預測步驟，將獲取的統計特征取值輸入預測模型，預測使用該矩陣特征值作為輸入時SpMV程序的最佳并行任務粒度參數取值；配置步驟，根據預測結果，調整并行運行時系統任務粒度。本發明裝置包括預測模型構建模塊、統計特征取值獲取模塊、最佳任務粒度參數預測模塊和配置模塊。本發明通過自適應選擇SpMV在不同輸入矩陣時的并行任務粒度，實現提高并行程序負載平衡和整體計算性能的目的。

技術領域

本發明涉及并行程序任務分配技術，尤其涉及一種稀疏矩陣向量乘并行程序的任務粒度參數自動調優方法和裝置。

背景技術

在科學計算和人工智能領域，稀疏矩陣向量乘運算(Sparse Matrix-VectorMultiplication,SpMV)作為基本算子，已得到了廣泛的應用，其對應的運算模塊也是該領域軟件中最耗時的模塊之一。不同于稠密矩陣，稀疏矩陣僅有少量的非零元素，其多數元素是零元。這些零元對運算結果不會產生影響，而存取零元并對其進行運算會有額外的開銷，導致運算效率低下。

為此，研究人員通過利用矩陣的稀疏特性，以壓縮存儲格式的方式只存儲稀疏矩陣中的非零元，從而避免對零元的處理、減少了矩陣的存儲與訪問開銷。常見的稀疏矩陣存儲格式包括Coordinate List(COO)、Compressed Sparse Row(CSR)、ELLPACK(ELL)、HybridELL+COO(HYB)等。矩陣的稀疏結構和所采用的存儲格式都會對稀疏矩陣運算性能產生影響。

實際應用中產生的稀疏矩陣的非零元分布具有不規則性，同時計算機系統存儲層次結構較為復雜，給稀疏矩陣的運算性能優化工作帶來了巨大的挑戰。目前的優化工作主要從兩方面展開：一方面，通過引入新的稀疏矩陣存儲格式和對應的SpMV實現算法，重新組織非零元的布局，以充分利用處理器的高速緩存和寬向量功能部件，從而兼顧上層稀疏矩陣特性和底層硬件體系結構特征；另一方面，通過使用并行化方法，將稀疏矩陣運算任務劃分并分派到并行計算機系統上并發執行。這些方法會引入大量的配置參數，并產生一個巨大的優化變量空間。在這個優化變量空間中，以窮舉的方式找尋最優配置參數顯然是不可行的。因此，面向稀疏矩陣向量乘運算，研究自動化的性能優化方法以獲取最優配置參數，具有十分重要的意義。

具體來說，由于計算SpMV相鄰兩行結果之間沒有依賴關系，每行的累積計算可看作一個獨立的子任務，故SpMV具有易擴展的特點。假設處理器有t個線程，在默認情況下會將稀疏矩陣的m行劃分成t個子任務，每個線程負責一個子任務，其大小為g＝m/t(任務粒度)。當任務粒度g＝m/(2·t)時，每個線程負責2個任務；當任務粒度g＝m/(4·t)，每個線程負責4個任務，以此類推……，當任務粒度g＝m/(K·t)，每個線程負責K個任務。使用不同的任務粒度將會產生不同的任務到線程的分配方式，并影響線程間的負載均衡。特別地，隨著處理器線程數量和矩陣規模的變大，任務到線程的分配方式和任務粒度呈現急劇地增長，導致了一個巨大的優化空間。因此，對于給定的稀疏矩陣數據集和多核處理器平臺，有必要構建相應的最佳任務粒度預測模型，以平衡多個線程間的計算與訪存負載，使得稀疏矩陣數據集、SpMV并行計算任務及硬件平臺間形成最佳匹配，從而最大程度地挖掘多核處理器的計算潛能，提升SpMV并行任務計算效率。

發明內容

本發明的目的在于：通過構建模型自動地調整并行運行時系統的任務粒度參數，提高稀疏矩陣向量乘(SpMV)并行程序在多核處理器上的負載平衡和整體運算性能。

本發明是這樣實現的：一種基于機器學習的稀疏矩陣向量乘并行任務粒度參數自動調優方法，包括：