本文經(jīng)自動(dòng)駕駛之心公眾號(hào)授權(quán)轉(zhuǎn)載，轉(zhuǎn)載請(qǐng)聯(lián)系出處。

原標(biāo)題：Minuet: Accelerating 3D Sparse Convolutions on GPUs

論文鏈接：https://arxiv.org/pdf/2401.06145.pdf

代碼鏈接：https://github.com/UofT-EcoSystem/Minuet

作者單位：多倫多大學(xué) Vector Institute Amazon Meta Samsung AI Centre Toronto CentML

會(huì)議：EuroSys'24

論文思路：

稀疏卷積(Sparse Convolution) (SC) 廣泛用于處理本質(zhì)上稀疏的 3D 點(diǎn)云。與密集卷積不同，SC 通過(guò)僅允許輸出到特定位置來(lái)保留輸入點(diǎn)云的稀疏性。為了有效地計(jì)算 SC，現(xiàn)有的 SC 引擎(engines)首先使用哈希表來(lái)構(gòu)建內(nèi)核映射(kernel map)，該映射存儲(chǔ)要執(zhí)行的必要的通用矩陣乘法（GEMM）操作 (Map 步驟)，然后使用 Gather-GEMM-Scatter 過(guò)程來(lái)執(zhí)行這些 GEMM 操作 (GMaS 步驟)。在這項(xiàng)工作中，本文分析了現(xiàn)有最先進(jìn)的 SC 引擎的缺點(diǎn)，并提出了 Minuet，一種專為現(xiàn)代 GPU 量身定制的新型內(nèi)存高效 SC 引擎。Minuet 提出 (i) 用一種新穎的分段排序雙遍歷二分搜索算法(segmented sorting double-traversed binary search algorithm) 替換 Map 步驟中使用的哈希表，該算法高度利用 GPU 的 on-chip 內(nèi)存層次結(jié)構(gòu)，(ii) 使用輕量級(jí)方案在 GMaS 步驟的 Gather 和 Scatter 操作中自動(dòng)調(diào)整 tile 大小，以便使執(zhí)行適應(yīng)每個(gè) SC 層、數(shù)據(jù)集和 GPU 架構(gòu)的特定特征，以及 (iii) 采用填充高效的 GEMM 聚合方法(grouping approach)，減少內(nèi)存填充和內(nèi)核啟動(dòng)開(kāi)銷。本文的評(píng)估表明，對(duì)于端到端點(diǎn)云網(wǎng)絡(luò)執(zhí)行，Minuet 的性能明顯優(yōu)于之前的 SC 引擎，平均性能提高 1.74 倍（最大 2.22 倍）。本文新穎的分段排序雙遍歷二分搜索算法在 Map 步驟中比之前的 SC 引擎平均實(shí)現(xiàn)了 15.8 倍（最大 26.8 倍）的卓越加速。

主要貢獻(xiàn)：

本文研究了現(xiàn)有 SC 引擎的缺點(diǎn)，并提出了 Minuet，這是一種內(nèi)存高效的引擎，可以加速現(xiàn)代 GPU 架構(gòu)上的 SC 執(zhí)行。

本文提出了一種新穎的分段排序雙遍歷二分搜索算法來(lái)在 SC 中構(gòu)建內(nèi)核映射。本文提出的算法高度利用了 GPU 的 on-chip 內(nèi)存層次結(jié)構(gòu)。本文還在 Gather 和 Scatter 操作中動(dòng)態(tài)選擇性能最佳的 tile 大小，并在對(duì) GEMM 操作進(jìn)行聚合(group)之前重新排序，以最大程度地減少不必要的數(shù)據(jù)訪問(wèn)和計(jì)算。

本文使用廣泛的真實(shí)數(shù)據(jù)集、稀疏 3D 網(wǎng)絡(luò)和 GPU 架構(gòu)來(lái)評(píng)估 Minuet，并表明它在分層和端到端執(zhí)行方面都顯著優(yōu)于先前的工作。Minuet 還在 SC 的 Map 步驟中提供了卓越的加速。

論文方法：

在這項(xiàng)工作中，本文使用各種點(diǎn)云網(wǎng)絡(luò)、真實(shí)數(shù)據(jù)集和 GPU 架構(gòu)來(lái)描述現(xiàn)有 SC 引擎 [8,9,43]，并發(fā)現(xiàn)它們存在三個(gè)關(guān)鍵缺點(diǎn)。首先，他們使用哈希表（例如，cuckoo 哈希表 [1]）來(lái)構(gòu)建內(nèi)核映射，其中存儲(chǔ)必要的 GEMM 操作。然而，在哈希表中執(zhí)行大量查詢會(huì)導(dǎo)致不規(guī)則的數(shù)據(jù)訪問(wèn)，其中大部分由昂貴的GPU全局內(nèi)存來(lái)服務(wù)，從而導(dǎo)致較高的數(shù)據(jù)訪問(wèn)成本。其次，最先進(jìn)的 SC 引擎在 Gather 和 Scatter 操作中將 在 tiles 中的 SC 的多個(gè)輸入/輸出特征通道處理為一組連續(xù)的特征通道，以提高 GPU 內(nèi)存吞吐量。然而，本文觀察到他們總是采用單一的固定 tile 大小，這會(huì)導(dǎo)致性能不佳。在圖 4 中，本文證明了性能最佳的 tile 大小取決于點(diǎn)云網(wǎng)絡(luò)的每個(gè)特定 SC 層、真實(shí)數(shù)據(jù)集和 GPU 架構(gòu)的特征。第三，在 GMaS 步驟中，現(xiàn)有的SC引擎執(zhí)行與批處理方案中的多個(gè)權(quán)重偏移相對(duì)應(yīng)的GEMM操作：它們通過(guò)用零值填充GEMM操作數(shù)將多個(gè)GEMM操作聚合在一起，即，它們?cè)谒蠫EMM操作數(shù)中提供相同的大小，并且將它們作為單個(gè)批處理 GEMM 內(nèi)核執(zhí)行。通過(guò)這種方式，他們可以最大限度地減少 GPU 內(nèi)核啟動(dòng)開(kāi)銷并提高 GPU 硬件利用率 [43]。然而，本文發(fā)現(xiàn)先前的 SC 引擎在 GMaS 步驟中按照 Map 步驟產(chǎn)生的順序（即權(quán)重偏移的順序）將 GEMM 操作聚合。這種方法會(huì)導(dǎo)致高填充開(kāi)銷（第3節(jié)），即添加大量零值，從而產(chǎn)生許多冗余數(shù)據(jù)訪問(wèn)和計(jì)算。

為了解決上述問(wèn)題，本文提出了 Minuet，這是一種專為現(xiàn)代 GPU 量身定制的新型內(nèi)存高效 SC 引擎。Minuet 高度利用 GPU 的 on-chip 內(nèi)存層次結(jié)構(gòu)，使 SC 執(zhí)行適應(yīng)輸入數(shù)據(jù)集和 GPU 架構(gòu)的特點(diǎn)，減少不必要的數(shù)據(jù)訪問(wèn)和計(jì)算。在 Map 步驟中，本文挑戰(zhàn)了基于哈希表的搜索比 GPU 上的二分搜索性能優(yōu)越的普遍觀念 [1, 2]，并提出了一種基于二分搜索的創(chuàng)新算法，專門用于在現(xiàn)代 GPU 架構(gòu)上的 SC 的 Map 步驟中構(gòu)建內(nèi)核映射。本文利用在執(zhí)行排序查詢時(shí)，二分搜索實(shí)現(xiàn)高系統(tǒng)效率的關(guān)鍵觀察結(jié)果，利用連續(xù)排序查詢之間的數(shù)據(jù)局部性，并提出分段排序雙遍歷二分搜索算法(segmented sorting double-traversed binary search algorithm)。

本文提出的 SC 算法可以實(shí)現(xiàn)與基于哈希表的搜索類似的理論計(jì)算復(fù)雜度（第 5.1.3 節(jié)），并提供顯著更高的內(nèi)存效率，提高 GPU on-chip caches 的命中率（圖 16b）。在GMaS執(zhí)行步驟中，Minuet提供了兩種優(yōu)化。首先，本文在每次 Gather 和 Scatter 操作中即時(shí)調(diào)整用于處理多個(gè)輸入/輸出特征通道的 tile 大小。這項(xiàng)關(guān)鍵技術(shù)使 Minuet 能夠使 SC 執(zhí)行適應(yīng)點(diǎn)云網(wǎng)絡(luò)、真實(shí)數(shù)據(jù)集和 GPU 架構(gòu)中每個(gè) SC 層的特定特征，從而在 Gather 和 Scatter 操作中提供高系統(tǒng)性能。其次，Minuet 集成了一種填充高效的 GEMM 聚合策略，該策略首先根據(jù)輸入/輸出特征向量的大小對(duì) GEMM 操作進(jìn)行重新排序，然后將 GEMM 操作聚合到批量的 GEMM 內(nèi)核啟動(dòng)中。通過(guò)這種方式，Minuet 可以優(yōu)化 (i) 零值填充量，從而最大限度地減少對(duì) GEMM 內(nèi)核中無(wú)用數(shù)據(jù)的不必要的數(shù)據(jù)訪問(wèn)和計(jì)算，以及 (ii) GEMM 內(nèi)核啟動(dòng)(kernel launch) 開(kāi)銷。

本文使用各種 3D 點(diǎn)云網(wǎng)絡(luò)、真實(shí)數(shù)據(jù)集和 GPU 架構(gòu)對(duì) Minuet 進(jìn)行了廣泛評(píng)估，并證明 Minuet 顯著優(yōu)于之前的作品。與最先進(jìn)的 SC 引擎相比，Minuet 的端到端性能平均提高了 1.74 倍（最高 2.22 倍），并且在 Map 步驟比之前的 SC 引擎實(shí)現(xiàn)了平均 15.8 倍的卓越加速（最高 26.8倍），在 GMaS 步驟中平均提高 1.39倍（最高 2.38倍）。

圖 6.Minuet 的高層概述。

圖 1. 密集卷積與稀疏卷積。

圖 2. SC 執(zhí)行可以分為兩個(gè)步驟。為了簡(jiǎn)單起見(jiàn)，本文使用二維坐標(biāo)進(jìn)行說(shuō)明。

圖 5. 在 SC 中執(zhí)行 GEMM 操作的各種方法，其中一個(gè)藍(lán)色和白色方塊分別表示一個(gè)實(shí)際輸入特征向量和一個(gè)零填充特征向量。假設(shè) ?? 和?? 分別是填充特征向量和實(shí)際輸入特征向量的數(shù)量，則填充開(kāi)銷定義為（??/??）。

圖 7. 隨機(jī)遍歷查詢時(shí)執(zhí)行四個(gè)查詢的二分搜索示例（即未排序查詢（左）與排序查詢方法（右））。

圖 8. 完整查詢排序（頂部）和分段查詢排序（底部）的示例。綠色實(shí)心框代表在 GPU 全局內(nèi)存中具體化的(materialized)數(shù)組。綠色虛線框表示未在內(nèi)存中具體化的(materialized)數(shù)組，它們的值是即時(shí)計(jì)算的。

圖 9. 優(yōu)化相鄰 SC 層中權(quán)重偏移和輸出坐標(biāo)的排序開(kāi)銷。

圖 10. 當(dāng)對(duì)已排序源數(shù)組中的排序查詢段執(zhí)行二分搜索時(shí)（表示為二叉搜索樹(shù) ），使用反向二分搜索查找查詢數(shù)組段中 pivot 的下界以減少比較次數(shù)的示例。

圖 11. 雙重遍歷二分搜索執(zhí)行步驟。

實(shí)驗(yàn)結(jié)果：

總結(jié)：

Minuet 是一款高效 SC 引擎，可在 GPU 上加速 3D 點(diǎn)云網(wǎng)絡(luò)。Minuet 高度利用 GPU on-chip 內(nèi)存層次結(jié)構(gòu)，提高執(zhí)行并行性和元數(shù)據(jù)成本，并減少 SC 執(zhí)行時(shí)不必要的數(shù)據(jù)訪問(wèn)和計(jì)算。本文的評(píng)估表明，在各種稀疏點(diǎn)云網(wǎng)絡(luò)、數(shù)據(jù)集和 GPU 架構(gòu)中，Minuet 在端到端執(zhí)行時(shí)的平均加速明顯優(yōu)于之前最先進(jìn)的 SC 引擎 1.74 倍。本文的結(jié)論是 Minuet 是一種專為現(xiàn)代 GPU 量身定制的新型內(nèi)存高效 SC 引擎，并希望本文的工作能夠鼓勵(lì)對(duì)點(diǎn)云網(wǎng)絡(luò)和其他稀疏深度學(xué)習(xí)網(wǎng)絡(luò)的進(jìn)一步全面研究和優(yōu)化策略。

原文鏈接：https://mp.weixin.qq.com/s/0K-LUMnQZ8fovouJiqkflw