??想了解更多關(guān)于開(kāi)源的內(nèi)容，請(qǐng)?jiān)L問(wèn)：??

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

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

【技術(shù)DNA】

【智慧場(chǎng)景】

引言

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

背景

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

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

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

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

可變長(zhǎng)度編碼

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

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

專用浮點(diǎn)壓縮器

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

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

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

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

適用于浮點(diǎn)數(shù)據(jù)的GPU的公開(kāi)可用的無(wú)損數(shù)據(jù)壓縮器比較少，作者在文中列舉了幾個(gè)：

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

NDZIP

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

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

并行化方案

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

壓縮管道概述

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

圖 1 三級(jí)壓縮管道

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

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

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

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

圖 2 壓縮流布局

解壓管道概述

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

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

圖 3 單級(jí)解壓管道

共享內(nèi)存布局

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

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

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

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

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

Warp合作垂直位封裝

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

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

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

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

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

圖 4 合作垂直位包裝

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

圖 5 合作垂直位解包

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

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

評(píng)估

評(píng)估方法

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

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

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

結(jié)果

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

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

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

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

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

??想了解更多關(guān)于開(kāi)源的內(nèi)容，請(qǐng)?jiān)L問(wèn)：??

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

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