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

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

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

【本期看點(diǎn)】

• ndzip應(yīng)用場(chǎng)景
• ndzip相關(guān)算法
• 殘差編碼復(fù)現(xiàn)
• SIMD

【技術(shù)DNA】

【智慧場(chǎng)景】

NDZIP — 一個(gè)用于科學(xué)數(shù)據(jù)的高通量并行無(wú)損壓縮器

概述

場(chǎng)景應(yīng)用

• 分布式計(jì)算以及高性能計(jì)算在機(jī)器學(xué)習(xí)、大數(shù)據(jù)學(xué)習(xí)與高級(jí)建模與模擬等新興技術(shù)上都有使用。在航天航空、制造業(yè)、金融、醫(yī)療等多個(gè)領(lǐng)域也有著非常重要的作用。
• ndzip，是一種新的高吞吐量無(wú)損壓縮算法，專(zhuān)門(mén)為浮點(diǎn)數(shù)據(jù)的n維網(wǎng)格而設(shè)計(jì)，為HPC互連帶寬的的限制因素提供了一種有效的解決方案。

本文貢獻(xiàn)

1. 本文提出了一種新的壓縮算法-ndzip，它基于一個(gè)快速，且并行整數(shù)近似的的知名預(yù)測(cè)器，并結(jié)合了對(duì)硬件友好的塊細(xì)分方案；
2. ndzip 的高性能多級(jí)并行實(shí)現(xiàn)，利用SIMD? 和線程級(jí)并行；
3. 對(duì)大量具有代表性的HPC 數(shù)據(jù)進(jìn)行深入的性能評(píng)估，并與最新水平的專(zhuān)業(yè)浮點(diǎn)壓縮器和通用壓縮方案進(jìn)行比較。

技術(shù)背景

相關(guān)算法

FPZIP

• FPZIP? 使用洛倫茲預(yù)測(cè)器利用標(biāo)量 n 維網(wǎng)格內(nèi)點(diǎn)的直接鄰域的平滑性，使用范圍編碼器壓縮小的殘值。該方案具有很高的壓縮效率，特別是對(duì)于單精度值。

FPC

• FPC? 使用一對(duì)基于哈希表?的值預(yù)測(cè)器來(lái)壓縮非結(jié)構(gòu)化雙精度數(shù)據(jù)流。它提供了一個(gè)可調(diào)參數(shù)，利用壓縮效率提高速度。線程并行的pFPC 變體允許通過(guò)以塊的形式處理輸入數(shù)據(jù)來(lái)進(jìn)一步確定壓縮吞吐量的優(yōu)先級(jí)。

SPDP

• SPDP? 結(jié)合了一維預(yù)測(cè)和LZ77變體，可以壓縮單精度和雙精度數(shù)據(jù)，而不需要對(duì)任何一種格式進(jìn)行專(zhuān)門(mén)處理。

MPC

• MPC? 是一種用于GPU 的快速壓縮方案。將一個(gè)簡(jiǎn)單的一維值預(yù)測(cè)器與一個(gè)位重組方案相結(jié)合，可以很好地映射到目標(biāo)硬件的殘差中去零位。

APE 和 ACE

• APE? 和ACE ?壓縮器自適應(yīng)地從多個(gè)值預(yù)測(cè)器中選擇，將 n 維網(wǎng)格中的數(shù)據(jù)點(diǎn)與其已處理過(guò)的鄰居解相關(guān)。殘差使用一種變體的Golomb 編碼進(jìn)行壓縮。

數(shù)值預(yù)測(cè)

數(shù)值預(yù)測(cè)科學(xué)浮點(diǎn)數(shù)據(jù)中的單個(gè)數(shù)值通常在低階尾數(shù)位表現(xiàn)出較高的熵，尾數(shù)也很少出現(xiàn)精確到重復(fù)，這降低了傳統(tǒng)字典編碼器的效率。相反，我們可以使用專(zhuān)門(mén)的方法對(duì)已經(jīng)處理過(guò)的數(shù)據(jù)進(jìn)行預(yù)測(cè)，只對(duì)殘差進(jìn)行編碼。

• SPDP? 和MPC 使用簡(jiǎn)單的固定步長(zhǎng)值預(yù)測(cè)器，通過(guò)存儲(chǔ) k 個(gè)值，并用最近編碼的第 k 個(gè)值預(yù)測(cè)每個(gè)點(diǎn)。
• FPC? 和pFPC 使用一對(duì)基于哈希表的預(yù)測(cè)器來(lái)維護(hù)一個(gè)較大的內(nèi)部狀態(tài)，以利用值和值增量中的重復(fù)模式。
• fpzip? 使用浮點(diǎn)洛倫茲預(yù)測(cè)器來(lái)估計(jì) n 維空間中長(zhǎng)度為 2 的超立方體的一個(gè)角的值。fpzip通過(guò)奇數(shù)條邊可到達(dá)的所有其他角加起來(lái)，然后減去通過(guò)偶數(shù)條邊可到達(dá)的角。當(dāng)超立方體可用n - 1次隱式多項(xiàng)式表達(dá)時(shí)，預(yù)測(cè)精度是精確的。
• APE 和 ACE 擴(kuò)展了fpzip預(yù)測(cè)器的思想，通過(guò)在每個(gè)維度上使用高維多項(xiàng)式，以更大的計(jì)算成本為代價(jià)提高了預(yù)測(cè)精度。

差分運(yùn)算

在無(wú)損壓縮環(huán)境中，浮點(diǎn)減法不適合用來(lái)計(jì)算預(yù)測(cè)殘差。小幅度的浮點(diǎn)值通常不會(huì)以簡(jiǎn)短的、可壓縮的位的形式出現(xiàn)，而且浮點(diǎn)數(shù)的有限精度使浮點(diǎn)減法成為一種非雙射的運(yùn)算。因此，所有研究的算法都明確地計(jì)算位表示的殘差。

• FPC和pFPC 使用逐位異或差?，而SPDP和MPC 將操作數(shù)位重新解釋為整數(shù)，并對(duì)整數(shù)減法的結(jié)果進(jìn)行編碼。
• APE和ACE 提供了兩種變體。
• fpzip 也使用整數(shù)減法，但是它根據(jù)符號(hào)位對(duì)操作數(shù)進(jìn)行反運(yùn)算，以提高映射的連續(xù)性。

殘差編碼

精確的預(yù)測(cè)會(huì)產(chǎn)生具有許多相同前導(dǎo)位的小幅度殘差，即異或運(yùn)算符為零以及二進(jìn)制補(bǔ)碼的整數(shù)減法的冗余符號(hào)位。對(duì)這些前導(dǎo)位進(jìn)行有效編碼是大多數(shù)研究方案中所采用的數(shù)據(jù)簡(jiǎn)化機(jī)制。

• fpzip 使用一個(gè)范圍編碼器?來(lái)壓縮前導(dǎo)冗余位的數(shù)量，緊接著復(fù)制剩余位。距離編碼器能夠產(chǎn)生的接近最佳的位串使得其非常節(jié)省空間。然而，所需的位粒度尋址難的問(wèn)題難以有效解決。
• APE? 和ACE? 使用與fpzip?類(lèi)似的方法，但使用符號(hào)排序的Golomb 代碼來(lái)編碼冗余位的數(shù)量。
• FPC 和 pFPC 通過(guò)計(jì)算雙精度殘差中前導(dǎo)零字節(jié)的數(shù)量，使用固定映射對(duì)運(yùn)行長(zhǎng)度和4 bit中的預(yù)測(cè)部分進(jìn)行編碼。剩余部分將從第一個(gè)非零字節(jié)開(kāi)始逐字輸出。這種方法是無(wú)狀態(tài)的，在不可壓縮的情況下有可接受的1/16開(kāi)銷(xiāo)，代價(jià)是由于粒度較低而浪費(fèi)比特。
• MPC 將剩余流分成 32 個(gè)單精度（或 64 個(gè)雙精度）值的塊，發(fā)出 32（64）個(gè)最高有效位，然后是 32（64）個(gè)第二最高有效位，依此類(lèi)推。零字將從輸出流中刪除，并在每個(gè)編碼所有非零字位置的塊上替換為32或64位掩碼。這種方法在不可壓縮的情況下有非常低的開(kāi)銷(xiāo)，僅僅為1/32（1/64），由于字符粒度尋址，該方法在 GPU 上得到了有效的實(shí)現(xiàn)，但需要塊內(nèi)所有的殘差具有相似的位寬才能實(shí)現(xiàn)。
• SPDP 從一個(gè)類(lèi)似于 MPC 的重組策略開(kāi)始，但是SPDP是在字節(jié)級(jí)別上的重組策略。SPDP接著使用字節(jié)粒度整數(shù)減差運(yùn)算，并使用 lz77 系列編碼器對(duì)結(jié)果流進(jìn)行編碼。這可以消除除前導(dǎo)零之外的重復(fù)模式，并使 SPDP 也能處理非浮點(diǎn)數(shù)據(jù)。

算法分析

• ndzip 的算法主要分為塊細(xì)分、整數(shù)洛倫茲變換以及殘差編碼三個(gè)部分。
• 大體流程：下圖展示了ndzip壓縮管道的所有步驟，首先它將輸入的數(shù)據(jù)劃分為固定大小的超立方體，并使用多維變換在塊內(nèi)對(duì)數(shù)據(jù)進(jìn)行去相關(guān)，從而使其具有更短位表示殘差。然后通過(guò)位矩陣變換消除公共零位來(lái)壓縮剩余流。壓縮后的數(shù)據(jù)塊存儲(chǔ)在報(bào)頭旁邊，報(bào)頭顯示了輸出流中壓縮數(shù)據(jù)塊的位置。

塊細(xì)分

• ndzip 不是一次性處理輸入數(shù)據(jù)的整個(gè) n 維網(wǎng)格，而是將其細(xì)分為獨(dú)立壓縮的小的超立方體，然后依次進(jìn)行傳輸。
• 由于該算法需要多次傳遞數(shù)據(jù)，因此可以更好地使用處理器緩存，但會(huì)略微損失解相關(guān)的效率。塊與塊之間存在依賴(lài)，我們想要消除塊之間的所有依賴(lài)關(guān)系，可以通過(guò)附加額外的數(shù)據(jù)來(lái)實(shí)現(xiàn)。
• 這里作者選擇了4096個(gè)元素，則超立方體的大小可以表示為40961、642或163。對(duì)于單精度，這相當(dāng)于16KB的內(nèi)存；對(duì)于雙精度，這相當(dāng)于32KB的內(nèi)存。預(yù)先確定塊的大小能夠在之后的步驟生成高度優(yōu)化的機(jī)器碼。
• 當(dāng)網(wǎng)格范圍不是塊的大小的倍數(shù)時(shí)，邊框元素將不被壓縮地附加到輸出中。

整數(shù)洛倫茲變換

浮點(diǎn)洛倫茲預(yù)測(cè)器（Floating-point Lorenzo Predictor） 對(duì)于多維數(shù)據(jù)的預(yù)測(cè)是非常高效的，但是單獨(dú)位模式的殘差計(jì)算需要解碼器從已經(jīng)解碼的臨近值重建每個(gè)預(yù)測(cè)，從而引入限制并行計(jì)算的依賴(lài)。

因此，作者使用了整數(shù)洛倫茲變換（ Integer Lorenzo Transform） 解決了這個(gè)問(wèn)題。整數(shù)洛倫茲變換是一種直接計(jì)算整數(shù)域內(nèi)的洛倫茲預(yù)測(cè)殘差的近似的多道運(yùn)算。下圖便說(shuō)明了這個(gè)過(guò)程。

殘差編碼

• 關(guān)于殘差編碼，ndzip使用了與 MPC 相同的殘差編碼方案，使其可以在現(xiàn)在的CPU上高效的實(shí)現(xiàn)。大致流程如下：

殘差使用了二進(jìn)制補(bǔ)碼進(jìn)行表示，根據(jù)殘差的符號(hào)，確定了補(bǔ)碼第一位是1還是0。之后通過(guò)0消去對(duì)兩者進(jìn)行編碼。

殘差首先被轉(zhuǎn)換成符號(hào)-數(shù)值（sign-magnitude）表示，只要?dú)埐顬樨?fù)，就對(duì)除了第一個(gè)比特外的所有比特進(jìn)行翻轉(zhuǎn)。

然后將殘差流分成32個(gè)單精度或者64個(gè)雙精度的值，對(duì)每個(gè)塊進(jìn)行 32x32（64x64） 的位矩陣變換

將來(lái)自相同位置的比特分組成單詞，從輸出中消去可以消去的0詞

在每個(gè)塊前面加上一個(gè)32位（64位）的頭，將非0字的位置編碼為位圖。

使用教程

• 上面的原理看的有點(diǎn)頭禿，下面講解如何快速上手ndzip。
• 點(diǎn)擊進(jìn)入 ndzip 的地址，git 下項(xiàng)目到本地。

環(huán)境搭建

環(huán)境需求

運(yùn)行 ndzip 需要以下環(huán)境，Catch2 可根據(jù)自己是否需要來(lái)選擇是否安裝。

• CMake >= 3.15
• Clang >= 10.0.0
• Linux (我這里用的Ubuntu20)
• Boost >= 1.66
• Catch2 >= 2.13.3 (可選，用于單元測(cè)試和微基準(zhǔn)測(cè)試)

CMake安裝

• CMake? 在Ubuntu軟件源中，安裝非常簡(jiǎn)單，執(zhí)行以下命令即可：

sudo apt install cmake

• 版本檢查（CMake >= 3.1.5）：

cmake --version

• 看到 CMake 版本大于3.1.5?即可。

Clang 安裝

• Clang 也存在 Ubuntu軟件源中，步驟和CMake差不多，命令如下：

sudo apt install clang

• 版本檢查（Clang >= 10.0.0）：

clang --version

• 可以看到 Clang 版本為10.0.0?,符合要求

Boost 安裝

• Boostr 也存在 Ubuntu軟件源中，命令如下：

```undefi`ned
sudo apt-get install libboost-all-dev

- 版本檢查（Boost >= 1.66）：
```undefined
dpkg -S /usr/include/boost/version.hpp

Catch2 添加

• Catch2需要去github上下載編譯，命令如下：

git clone https://github.com/catchorg/Catch2.git
cd Catch2
cmake -Bbuild -H. -DBUILD_TESTING=OFF
sudo cmake --build build/ --target install

• 等待編譯添加完即可。

構(gòu)建

使用 CUDA + NVCC 構(gòu)建 ndzip

• 使用 cuda，安裝CUDA Toolkit：

sudo apt-key del 7fa2af80 # 刪除舊的GPG密鑰，之前裝過(guò)的要?jiǎng)h掉
wget https://developer.download.nvidia.com/compute/cuda/repos/wsl-ubuntu/x86_64/cuda-wsl-ubuntu.pin
sudo mv cuda-wsl-ubuntu.pin /etc/apt/preferences.d/cuda-repository-pin-600
wget https://developer.download.nvidia.com/compute/cuda/11.7.0/local_installers/cuda-repo-wsl-ubuntu-11-7-local_11.7.0-1_amd64.deb
sudo dpkg -i cuda-repo-wsl-ubuntu-11-7-local_11.7.0-1_amd64.deb
sudo apt-get update
sudo apt-get -y install cuda

• 使用CUDA + NVCC 構(gòu)建 ndzip（自己使用SYCL構(gòu)建ndzip沒(méi)跑出來(lái)。。。）

cmake -B build -DCMAKE_CUDA_ARCHITECTURES=75 -DCMAKE_BUILD_TYPE=Release -DCMAKE_CXX_FLAGS="-march=native"
cmake --build build -j

• 完成構(gòu)建

測(cè)試

• 測(cè)試命令

• 測(cè)試ndzip壓縮

評(píng)價(jià)

解耦多維數(shù)據(jù)

• ndzip-gpu 通過(guò)變換在解耦多維數(shù)據(jù)時(shí)實(shí)現(xiàn)了高資源利用率。提出了一種用于垂直位打包的新穎、高效的曲速協(xié)同原語(yǔ)，提供了高吞吐量的數(shù)據(jù)縮減和擴(kuò)展步驟, 為檢查的數(shù)據(jù)提供了最佳的平均壓縮比, 同時(shí)在雙精度情況下的數(shù)據(jù)減少和吞吐量之間保持了有利的權(quán)衡。將數(shù)據(jù)集的壓縮比定義為壓縮大小除以未壓縮大小(以字節(jié)為單位)，比率越低表示壓縮越強(qiáng)。在需要匯總比率的情況下，返回?cái)?shù)據(jù)集上壓縮比率的未加權(quán)算術(shù)平均值。

SIMD

• SIMD(Single Instruction Multiple Data），單指令多數(shù)據(jù)流，能夠復(fù)制多個(gè)操作數(shù) ，并把它們打包在大型寄存器的一組指令集。
• ndzip專(zhuān)為在支持 SIMD 的現(xiàn)代多核處理器上高效實(shí)施而量身定制，能夠以接近主內(nèi)存帶寬的速度壓縮和解壓縮數(shù)據(jù)，顯著優(yōu)于現(xiàn)有方案。通過(guò)測(cè)量從系統(tǒng)內(nèi)存壓縮和解壓縮到系統(tǒng)內(nèi)存的時(shí)鐘時(shí)間來(lái)評(píng)估性能。第三方實(shí)現(xiàn)允許在必要時(shí)進(jìn)行內(nèi)存操作。返回每秒未壓縮字節(jié)的吞吐量，它轉(zhuǎn)換為壓縮輸入和解壓輸出帶寬。重復(fù)測(cè)量每個(gè)算法和數(shù)據(jù)集對(duì)，直到總運(yùn)行時(shí)間超過(guò)一秒。在每次迭代之前，從 CPU 緩存中刪除輸入數(shù)據(jù)。

利用多維度的好處可以通過(guò)使用等效的一維變換來(lái)轉(zhuǎn)換高維數(shù)據(jù)集來(lái)衡量。

實(shí)驗(yàn)

新型整數(shù)洛倫佐變換(ILT)的有效性

• 為了估計(jì)新型整數(shù)洛倫佐變換(ILT)的有效性，我們用其他預(yù)測(cè)方法代替了實(shí)現(xiàn)中的變換步驟，并比較了得到的壓縮比，通過(guò)使用等效的一維變換來(lái)轉(zhuǎn)換高維數(shù)據(jù)集來(lái)衡量。
• 如圖顯示了具有相同維度的所有數(shù)據(jù)集的平均壓縮比，相對(duì)于在各自維度中觀察到的最差壓縮比進(jìn)行了縮放。

• 因?yàn)樵摼S度相對(duì)最差的壓縮比(越小越好)，對(duì)于一維數(shù)據(jù)集，所有方案大致相同。總體上看，F(xiàn)LP最好，最差的選擇是兩個(gè)一維預(yù)測(cè)器，這表明基于洛倫佐的組件顯著受益于更高的維度,選擇余數(shù)運(yùn)算對(duì)于逼近 FLP 的相關(guān)特征至關(guān)重要。
  算術(shù)平均未壓縮吞吐量
• 在測(cè)試數(shù)據(jù)上比較通過(guò)檢查的壓縮器實(shí)現(xiàn)，實(shí)現(xiàn)的吞吐量和壓縮比。 根據(jù)設(shè)計(jì)，同時(shí)并非所有算法都能同時(shí)處理單精度值和雙精度值。有些算法有一個(gè)或多個(gè)可調(diào)參數(shù)體現(xiàn)為連續(xù)的線，而ndzip，沒(méi)有可調(diào)的行為。

• 通用算法可以在浮點(diǎn)數(shù)據(jù)上實(shí)現(xiàn)高壓縮比，但只能以犧牲大量計(jì)算資源為代價(jià)。比如，LZMA 在雙精度值上實(shí)現(xiàn)了最高的壓縮比，與最強(qiáng)的單精度壓縮器 fpzip 不相上下，同時(shí)花費(fèi)更多壓縮我們最大的數(shù)據(jù)集。LZ4 實(shí)現(xiàn)了比任何其他審查過(guò)的單線程算法更高的壓縮和解壓縮吞吐量，同時(shí)還提供了最差的數(shù)據(jù)縮減。Zstandard 提供了一個(gè)非常好的權(quán)衡，在單精度數(shù)據(jù)上主導(dǎo) Deflate 和專(zhuān)門(mén)的 SPDP。大多數(shù)專(zhuān)業(yè)算法能夠在至少一個(gè)維度上勝過(guò)通用方案。而Fpzip 是最強(qiáng)大的單精度壓縮器，而且僅以中等吞吐量為代價(jià)，但在解壓縮方面失去了吞吐量比較.
• 所以ndzip 是最快的專(zhuān)用壓縮器和解壓縮器，具有顯著優(yōu)勢(shì)（“st”）。 對(duì)于雙精度數(shù)據(jù)集，稍差一些。與一些速度較慢的算法相比，我們的壓縮器提供了更低的壓縮比，但在吞吐量方面明顯優(yōu)于它唯一的競(jìng)爭(zhēng)對(duì)手 LZ4。

結(jié)論

• 通過(guò)設(shè)計(jì)一種考慮到目標(biāo)架構(gòu)特性的專(zhuān)用壓縮算法，可以實(shí)現(xiàn)出色的資源使用以及壓縮率和吞吐量之間極具競(jìng)爭(zhēng)力的折中。基于我們新穎的小超立方體數(shù)據(jù)，利用了行整數(shù)洛倫佐變換(Integer Lorenzo Transform)和硬件友好的殘差編碼方案，ndzip 壓縮器利用 SIMD 和線程并行性在消費(fèi)類(lèi)硬件上實(shí)現(xiàn)超過(guò) 10 GB/s 的壓縮和解壓縮速度，顯著地減少數(shù)據(jù)量。

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

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

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