??想了解更多關(guān)于開源的內(nèi)容，請訪問：??

??51CTO 開源基礎(chǔ)軟件社區(qū)??

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

【技術(shù)DNA】

【智慧場景】

引言

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

背景

并行無損數(shù)據(jù)壓縮的挑戰(zhàn)

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

可變編碼器/解碼器狀態(tài)

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

可變長度編碼

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

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

專用浮點壓縮器

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

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

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

GPU上的數(shù)據(jù)壓縮

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

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

NDZIP

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

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

并行化方案

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

壓縮管道概述

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

圖 1 三級壓縮管道

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

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

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

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

圖 2 壓縮流布局

解壓管道概述

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

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

圖 3 單級解壓管道

共享內(nèi)存布局

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

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

并行整數(shù)洛倫佐變換

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

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

Warp合作垂直位封裝

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

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

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

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

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

圖 4 合作垂直位包裝

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

圖 5 合作垂直位解包

參數(shù)調(diào)整

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

評估

評估方法

將數(shù)據(jù)集的壓縮比定義為壓縮大小除以未壓縮大小（以字節(jié)為單位），較低的比率表示更好的壓縮。該定義允許使用未加權(quán)算術(shù)平均值從一組觀察值中對預期壓縮比進行有意義的分析。

通過測量從第一個內(nèi)核開始到最后一個內(nèi)核結(jié)束的設備執(zhí)行時間來評估壓縮器性能。緩沖區(qū)分配以及主機設備內(nèi)存?zhèn)鬏敳话ㄔ跍y量范圍內(nèi)。我們報告每秒未壓縮字節(jié)的吞吐量，它轉(zhuǎn)換為壓縮輸入和解壓縮輸出帶寬。重復測量每個算法-數(shù)據(jù)集對，直到總運行時間超過一秒，但至少五次。

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

結(jié)果

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

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

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

表 1 Tesla V100 上的每個 GPU 壓縮器實現(xiàn)的每個數(shù)據(jù)集的壓縮率和吞吐量

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

??想了解更多關(guān)于開源的內(nèi)容，請訪問：??

??51CTO 開源基礎(chǔ)軟件社區(qū)??

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