中文題目：ScalFrag：面向GPU的高效自適應啟動與分塊MTTKPRP方法

論文題目：ScalFrag: Efficient Tiled-MTTKRP with Adaptive Launching on GPUs

錄用期刊/會議：IEEE International Conference on Cluster Computing (CCF-B類會議)

原文DOI：10.1109/CLUSTER59578.2024.00036

原文鏈接：https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=10740878

錄用/見刊時間：07 November 2024

作者列表：

1） 林文清 中國石油大學（北京）人工智能學院 計算機科學與技術 本21

2） 王赫萌 中國石油大學（北京）人工智能學院 先進科學與工程計算 博23

3） 鄧昊東 中國石油大學（北京）人工智能學院 計算機技術 碩24

4） 孫慶驍 中國石油大學（北京）人工智能學院 計算機系教師

摘要:

本文旨在加速稀疏張量的MTTKRP（矩陣化張量乘以Khatri-Rao積）計算，首先在GPU平臺上動態選擇最佳的內核啟動配置，以適應輸入張量的獨特特征；再通過共享內存減少數據訪問時間，采用流水線并行技術允許多個計算任務并行執行，從而降低整體計算時間。ScalFrag緩解了稀疏張量模式不規則造成的瓶頸和數據計算等待時間過長的問題，在處理不同特征的稀疏張量時表現優于先進庫ParTI，且在較小的張量上，性能提升更為顯著。實驗結果表明，MTTKRP的性能提高了1.2倍至2.2倍。

背景與動機: 

張量分解是從大量高維稀疏數據集中挖掘潛在模式的關鍵技術，在揭示復雜數據中的潛在結構方面發揮著至關重要的作用。在張量分解的各種方法中，張量典范分解（CPD）因其在捕捉多元線性關系方面的有效性，在眾多科學學科和實際應用中被廣泛采用。然而，CPD的計算效率由MTTKRP（矩陣化張量乘以Khatri-Rao積）所主導。由于張量數據的多樣性和復雜性，以及計算環境的多變性，幾乎不可能為MTTKRP計算找到一組通用且最優的參數配置。且現實世界的張量數據通常很大，從主機到設備傳輸數據會花費大量時間。本文旨在加速GPU平臺上的稀疏MTTKRP計算，通過自調優啟動策略和流水線并行策略，緩解稀疏張量模式不規則性相關的瓶頸。

設計與實現:

一、自調優啟動策略：

該策略的核心在于動態選擇最優的參數組合，以適應不同特征的矩陣化張量。通過分析張量的維度和分布特征，提取張量的關鍵特征參數，包括張量的全局特征和局部特征，以預測MTTKRP操作的執行情況。利用提取的特征參數，通過機器學習訓練不同的啟動參數選擇模型，輸出張量啟動參數的最優組合。在內核計算過程中，將頻繁訪問的數據和中間結果存儲在共享內存中，以減少數據訪問的延遲。

 

圖1 自調優啟動參數選擇策略

二、流水線策略：

該策略首先對COO格式的稀疏張量進行分段，每個分段包含一部分非零元素及其相應的坐標信息。然后根據GPU的性能和內存容量以及段的數量創建不同數量的CUDA流，每個流負責傳輸和處理一個或多個特定的數據段。當一個數據段從CPU傳輸到GPU時，GPU可以處理之前已經傳輸完成的數據段，從而減少等待時間，提高資源利用率。

 

圖2 用于MTTKRP計算的流水線并行策略

實驗結果及分析: 

一、MTTKRP內核性能對比

使用ScalFrag后，稀疏張量MTTKRP的平均加速比為1.2倍（最高為2.2倍）。對于較小的稀疏張量，性能加速更為明顯，因為它們在僅非零元素的數量上就存在顯著差異。實驗表明，固定參數GFlops并不總能達到最佳計算性能。ScalFrag通過為每個輸入稀疏張量選擇最佳啟動設置，有效提高了MTTKRP的計算效率。

圖3 ScalFrag和ParTi的MTTKRP內核性能對比

二、MTTKRP端到端性能對比

實驗表明，大多數張量都能通過流水線并行實現性能提升，平均加速比為1.5倍，最大加速比約為2.0倍。輸入的稀疏張量越小，流水線能覆蓋的傳輸時間就越多，性能加速就越明顯，ScalFrag緩解了前文提到的數據計算等待時間過長的問題。

 

圖4 ScalFrag和ParTi的MTTKRP端到端性能對比

結論:

本文深入探討了針對GPU平臺的MTTKRP優化方法，并設計了一種自適應啟動策略，該策略根據張量的稀疏特征動態選擇最佳的啟動參數組合，以確保充分利用GPU的計算資源。本文還引入了一種流水線并行技術，通過優化任務之間的依賴關系，使多個計算任務能夠并行執行，從而顯著減少總體計算時間。實驗結果表明，ScalFrag比先進庫ParTI表現更好，并且能夠在短時間內找到更合適的內核啟動參數配置。

通訊作者簡介:

孫慶驍，中國石油大學（北京）計算機系副教授，碩士生導師，CCF體系結構專委會執行委員，CCF高性能計算專委會執行委員。2023年博士畢業于北京航空航天大學計算機學院，入選首屆“CCF體系結構優秀博士學位論文激勵計劃”，獲得“ACM SIGHPC China優秀博士學位論文”。從事任務運行時系統、深度學習系統和性能建模調優等方面的研究，主持國家自然科學基金青年項目和國家重點研發計劃子課題各1項。以第一作者及通訊作者在SC、IPDPS、TC、TPDS等高水平國際會議和期刊上發表論文10余篇，獲得IEEE Computer亮點論文和CLUSTER’21會議最佳論文提名。擔任IEEE TC/TPDS/TCC、ACM Computing Survey、Springer SUPE/FCS、CCF THPC、計算機工程與科學等國內外期刊的審稿人。

聯系方式：qingxiao.sun@cup.edu.cn