??想了解更多關于開源的內容，請訪問：??

??51CTO 開源基礎軟件社區??

??https://ost.51cto.com??

【技術DNA】

【智慧場景】

引言

• 無損數據壓縮是一種很有前途的軟件方法，可以減少加速器集群上科學應用的帶寬需求，而不會引入近似誤差。合適的壓縮器必須能夠有效壓縮浮點數據，同時使系統互連飽和以避免引入不必要的延遲。
• 在通往百億億次的道路上，能源效率正成為高性能計算(High Performance Computing, HPC) 創新的主要驅動力。節點內并行性的快速增長，包括GPU作為通用加速器的出現，大大降低了計算密集型應用程序的能源成本。
• 為了證明數據壓縮在加速節點間通信方面的可行性，論文探討了 GPU 壓縮如何提供必要的性能。在ndzip的基礎上，提出了ndzip-gpu，這是一種用于 ndzip 的高效 GPU 并行化方案，一種先進的無損浮點壓縮器。

背景

并行無損數據壓縮的挑戰

• 由于可變編碼器/解碼器狀態和可變長度輸出流編碼的必要性，傳統的無損壓縮器傾向于支持串行實現。

可變編碼器/解碼器狀態

• 在一般情況下，通過為輸入數據構建概率模型并將較短的表示分配給可能的輸入,將較長的表示分配給不太可能的輸入來實現數據量的無損減少（比如Huffman編碼）。解碼器必須知道編碼器的概率模型才能反轉此映射。由于模型通常既不是提前知道的，也不是整個數據流的靜態模型，因此對于單程壓縮器來說，顯式地交換它變得不可行。編碼器和解碼器都將從先前觀察到的未壓縮符號構建并不斷更新相同的模型。
• 一個高度并行的壓縮器必須能夠打破這個依賴鏈，以避免由同步共享狀態主導的運行時行為。具有大狀態的壓縮器（例如字典編碼器）在對它的輸入空間進行粒度細分是會明顯的降低效率。局部去相關方案在這方面更加穩健。

可變長度編碼

• 分塊數據流的壓縮是一個輸入并行問題，因為壓縮的塊長度事先不知道。并行壓縮器的線程必須同步才能確定輸出流中各個塊的位置。有兩種基本方法可以避免圍繞這種依賴進行序列化：

• 在快速暫存內存中的 k 個并行線程中壓縮 k 個塊，在屏障之后導出輸出位置，最后讓每個線程將寫入提交到輸出流。
• 將整個流壓縮到足夠大的中間緩沖區，使用前綴和計算所有塊的輸出位置，并使用單獨的壓縮步驟最終確定輸出流。

專用浮點壓縮器

• 浮點二進制表示具有比面向字節的通用壓縮器所假定的更大的字長。此外，來自實際應用程序的浮點數據有很多位相同的重復值，這些值很容易進行重復數據刪除。因此，傳統的字典編碼器方法在這類數據上并不是特別有效。
• 源自物理模擬或傳感器陣列的密集網格數據往往表現出低頻分量，這使得從相鄰值進行局部預測是可行的。網格的維數越高，由于每個值的相鄰單元數越多，預期的局部相關性就越多。因此，專門的浮點壓縮器的構建通常包括以下三個組件：

• 預測器通過字典、哈希表或相鄰值從先前編碼的點估計數據。
• 差分算子以可逆方式計算值與其預測之間的殘差，例如使用 XOR 運算或整數差。
• 殘差編碼器使用有利于小幅度值的可變長度代碼表示殘差。算法通常旨在通過諸如游程編碼(Run-length encoding, RLE)或算術編碼(Arithmetic coding)之類的表示來消除前導零位(leading-zero)。

• 除了 ndzip 算法之外，還有幾個著名的基于 CPU 的無損浮點壓縮器。fpzip使用洛倫佐預測器來利用1維網格內點的直接鄰域的平滑度，壓縮使用范圍編碼器的殘差。該方案表現出很高的壓縮效率，特別是對于單精度值，但僅限于單線程操作。FPC使用一對基于哈希表的值預測器來壓縮非結構化雙精度數據流。線程并行 pFPC 變體允許通過處理塊中的輸入數據來進一步確定壓縮吞吐量的優先級。ZFP是一種固定速率有損壓縮器，它使用頻率變換對多維網格中的浮點值進行去相關。

GPU上的數據壓縮

適用于浮點數據的GPU的公開可用的無損數據壓縮器比較少，作者在文中列舉了幾個：

• 通用壓縮機。nvCOMP3是適用于英偉達GPU的無損數據壓縮框架。它包括眾所周知的 LZ4 壓縮器的高吞吐量實現和非常適合整數數據的可配置級聯壓縮管道。
• cudppCompress是一個通用的面向字節的GPU壓縮器。它并行化了著名的bzip2壓縮器的三個階段，與類似時代的硬件CPU實現相比，實現了可測量的加速。對應的并行化解壓器沒有實現。
• 在有些工作中，GPU已成功用作協處理器來加速Burrows-Wheeler變換。LZW和LZSS壓縮器還存在并行實現，GPU熵編碼有快速Huffman和非對稱數字系統(ANS)編碼器。
• 專門的浮點壓縮機。 MPC是一種用于單精度或雙精度浮點數據的非結構化、多變量流的 GPU 壓縮方案。兩步一維值預測與垂直位打包相結合，這是一種很好地映射到目標硬件的編碼方案。
• GFC是一種用于非結構化雙精度數據的超快 GPU 壓縮器。來自一維預測器的殘差通過游程編碼前導零位來壓縮。與所有其他評估過的壓縮器不同，GFC 會生成碎片壓縮輸出，并在傳輸回主機時進行壓縮。

NDZIP

ndzip 是先進的塊壓縮器，針對單精度或雙精度浮點數據的一維到三維網格。它使用整數洛倫佐變換逼近洛倫佐預測器，這是一種用于多維塊的局部去相關的可分離就地操作。殘差使用先前在MPC 中發現的垂直位打包方案進行編碼，消除了相鄰殘差位位置的零游程。通過完全在整數域內操作，該算法保證了壓縮操作的可逆性以及可移植性。與既定的通用壓縮器（例如 Deflate）和專用算法（例如 fpzip或FPC）相比，ndzip 已被證明可以在 CPU 上提供出色的吞吐量，其實現同時利用線程和 SIMD 并行性。而ndzip-gpu壓縮器完全再現了 ndzip 的壓縮格式。

關于ndzip更多的內容，可以看之前發布的文章OpenHarmony啃論文俱樂部—數據高通量無損壓縮方案，里面詳細的介紹了ndzip算法，并且包含算法的使用教程。

并行化方案

這部分，我們將介紹并行化方案ndzip-gpu如何能夠在多達 768 個線程之間有效地分配變換和殘差編碼，同時將分支發散和序列化保持在最低限度。我們的目標是在設備上的全局內存緩沖區之間進行壓縮和解壓縮。

壓縮管道概述

并行壓縮的輸出偏移問題可以通過每個塊中的全設備同步或多個內核啟動以及通過中間全局暫存緩沖區的往返來解決。ndzip-gpu采用第二種方法，預計全局障礙將部分否定計算繁重的殘差編碼器中短路評估的好處。

圖 1 三級壓縮管道

上圖詳細說明了三級壓縮過程。內核1將一個未壓縮的塊從全局加載到共享內存中，將浮點值轉換為其整數表示。然后n維整數洛倫佐變換計算n中的殘差在原地傳遞塊數據。殘差被分組為 32 個單精度或64個雙精度值的序列，并通過垂直位打包進行編碼，從而產生一個頭字和可變數量的非零列。

分配了一個全局暫存緩沖區，為不可壓縮的情況提供了足夠的空間。索引空間被細分為塊，每個塊為所有頭字保留一個塊，然后為每個位壓縮列序列保留一個較小的塊。從輸入網格的維度，暫存緩沖區中的所有塊偏移量都是先驗已知的。

編碼后，每個線程塊將它們各自的塊寫入暫存內存，并將塊長度寫入單獨的緩沖區。內核2計算長度緩沖區上的并行前綴和，以獲得緊湊輸出流中所有塊的偏移量。最后，使用偏移緩沖區，內核 3 從零內存加載塊并將它們存儲在輸出流中的最終位置。每個塊中第一個塊的輸出偏移量收集在流頭中.

圖2中可視化的流布局有意將固定大小的元信息（塊偏移和塊頭）與可變長度的壓縮列編碼分開。這允許解碼器并行計算壓縮列的絕對偏移量，而無需同步或多次通過流。

圖 2 壓縮流布局

解壓管道概述

由于可以從流標頭中檢索壓縮緩沖區中每個塊的偏移量，因此解壓縮是輸出并行的，并且不需要塊之間的同步。單個內核啟動足以解碼整個流或任意塊子集。圖3詳細說明了單個塊的解壓過程。

• 內核首先從第一個塊中加載所有的頭，對設置的位進行計數以獲得每個序列的非零列數，最后執行前綴求和以在共享內存中生成偏移表。
• 然后可以并行反轉所有塊的位打包，擴展到殘差的共享內存塊。
• 然后通過逆整數洛倫佐變換恢復未壓縮值的整數表示。
• 最后，通過反轉整數映射來恢復浮點位模式，然后將塊寫入全局輸出網格緩沖區。

圖 3 單級解壓管道

共享內存布局

必須仔細選擇多通道轉換步驟的中間結果的共享內存布局，以避免所有必需的訪問模式之間的存儲庫沖突。硬件將根據需要將沖突的加載或存儲拆分為盡可能多的無沖突訪問，這可以顯著增加受共享內存訪問限制的函數的運行時間，例如整數洛倫佐變換。這個問題沒有明顯的通用解決方案，相反，索引空間變換必須分別專門針對一維、二維和三維情況以及單精度和雙精度數據。

• 填充。為了確保沿所有軸訪問超立方體的連續索引可以映射到不重疊的銀行，插入了填充詞。由于每個內存塊都是32位寬，并且64位加載和存儲是作為兩個連續的 32 位訪問執行的，因此雙精度情況下的填充仍然必須是 32 位寬。這需要對 64 位值進行故意未對齊的訪問。
• 定向訪問順序。在變換步驟的每個維度中，對通道項目的迭代可以建模為固定步幅的循環。然而，由于每個激活的warp(SM的基本執行單元)同時處理 32 個通道，因此必須明確計算每個通道中第一項的內存偏移量。必須再次小心地對一組通道進行分區以避免存儲庫沖突。

并行整數洛倫佐變換

n維整數洛倫佐變換，包括正向和逆向，由n個通道組成。在每個定向通道中，可以并行處理L個數據；這些通道分布在線程塊的線程之間。

• 前向變換。前向變換在每條車道4096次迭代中構造殘差，用與其前任的整數差替換值表示。前驅值在寄存器中進行跟蹤，因此該方案只需要在共享內存中的每個數據點執行一次加載和一次存儲。
• 逆變換。為了重構值表示，每個逆變換通道必須將已解碼的前驅添加到每個殘差。由于這引入了一個大小與塊邊長相等的依賴鏈，因此最多可以有4096^{1-1/n}個獨立通道（1對應1維， 64對應2維，256對應3維）。
  由于每個通道的逆變換構成前綴和，因此可以通過采用并行掃描來避免串行化。在實踐中，我們通過在連續塊內存上使用快速并行前綴和來反轉一維變換，并通過對每個通道執行順序求和來接受二維和三維情況的有限占用。

Warp合作垂直位封裝

固定寬度整數序列的垂直位封裝已經在數據庫系統中看到了先前的應用。這種壓縮長度不能被處理器最小可尋址單元分割的位模式的方法在并行硬件上有效地矢量化，例如支持 SIMD 的處理器。

它可以很容易地適應于壓縮輸入位位置的任意子集，而不是對整數中的連續位進行操作，再次允許在 SIMD 架構上高效實現。在這種形式中，它以前曾作為MPC壓縮器的一部分用于 GPU 浮點壓縮。在下文中，我們將未壓縮的單詞稱為行，將未壓縮序列中相同位置的位稱為列。

ndzip-gpu的新穎打包方案通過以下方式顯著提高了現代GPU上MPC方法之外的性能：

1. 短路評估無線程發散的全零塊的昂貴轉置步驟。
2. 通過避免塊來允許獨立的前向進展- 在打包期間完全同步。
3. 通過將壓縮塊寫入全局暫存緩沖區并在解包期間使用單獨的壓縮內核。
4. 避免圍繞輸出流位置進行序列化，通過讀取粗粒度塊偏移量來避免圍繞輸入流位置進行序列化來自流標頭并計算塊內的細粒度塊偏移作為并行前綴和。

• 包裝。在ndzip-gpu編碼器中，32 個線程協作打包 32 個 32 位或 64 個 64 位行。圖4顯示了更簡單的32位情況的機制，其中一個字對應一個線程。

圖 4 合作垂直位包裝

• 解包。解碼階段使用類似的線程分配，如圖5中所示的32位情況。首先，每個打包塊的長度被確定為其頭部的位數(popcount)。根據這些長度，使用線程塊并行前綴和計算打包流的偏移量。

圖 5 合作垂直位解包

參數調整

由于ndzip格式要求固定塊大小，最重要的可調參數是每個塊的線程數。這個數字可以獨立于實現的其余部分進行選擇，并允許用緩存局部性換取更高的占用率，從而提高隱藏指令延遲的能力。

評估

評估方法

將數據集的壓縮比定義為壓縮大小除以未壓縮大?。ㄒ宰止潪閱挝唬^低的比率表示更好的壓縮。該定義允許使用未加權算術平均值從一組觀察值中對預期壓縮比進行有意義的分析。

通過測量從第一個內核開始到最后一個內核結束的設備執行時間來評估壓縮器性能。緩沖區分配以及主機設備內存傳輸不包括在測量范圍內。我們報告每秒未壓縮字節的吞吐量，它轉換為壓縮輸入和解壓縮輸出帶寬。重復測量每個算法-數據集對，直到總運行時間超過一秒，但至少五次。

所有 CPU 算法都通過測量執行時間來進行基準測試，不包括可以提前執行的所有內存分配。

結果

圖6展示了ndzip-gpu提供的吞吐量和壓縮比之間的出色權衡。

• 在評估的測試數據上，并行化方案在單精度情況下同時提供了所有測試過的壓縮器的最佳平均壓縮比和最高吞吐量。
• 對于雙精度，GFC 和nvCOMP級聯方案超過ndzip-gpu在 RTX 2070 SUPER 和 A100 GPU 上的速度，但是壓縮比更差。
• 與GFC和MPC不同，ndzip-gpu顯示出壓縮和解壓縮速度之間的顯著差異。這可以用壓縮器的多級架構來解釋，它需要完整的全局內存往返來進行壓縮。

圖 6 與Tesla V100上的壓縮器/解壓縮器吞吐量相比的平均壓縮比

表 1 Tesla V100 上的每個 GPU 壓縮器實現的每個數據集的壓縮率和吞吐量

• 每個數據集的壓縮效率。上表列出了每個壓縮器在每個數據集上實現的壓縮率和吞吐量。雖然ndzip-gpu平均實現了最佳的數據縮減和最高的吞吐量，但某些數據集可以通過競爭對手的算法更有效或更快地壓縮。對于大多數輸入，ndzip和MPC的比率非常接近，因為這兩種算法共享相同的殘差編碼算法。

??想了解更多關于開源的內容，請訪問：??

??51CTO 開源基礎軟件社區??

??https://ost.51cto.com??。