【ELT.ZIP】OpenHarmony啃論文俱樂部——資料高通量無損壓縮方案

• 本文出自

  ELT.ZIP

  團隊，ELT<=>Elite(精英)，.ZIP為壓縮格式，ELT.ZIP即壓縮精英。
• 成員：
  • 上海工程技術大學大二在校生
  • 合肥師範學院大二在校生
  • 清華大學大二在校生
  • 成都資訊工程大學大一在校生
  • 黑龍江大學大一在校生
  • 華南理工大學大一在校生
• 我們是來自

  6個地方

  的同學，我們在

  OpenHarmony成長計劃啃論文俱樂部

  裡，與

  華為、軟通動力、潤和軟體、拓維資訊、深開鴻

  等公司一起，學習和研究

  作業系統技術

  …

【往期回顧】

  ① 2月23日 《老子到此一遊系列》之 老子為什麼是老子 —— ++綜述視角解讀壓縮編碼++

 ② 3月11日 《老子到此一遊系列》之 老子帶你看懂這些風景 —— ++多元探秘通用無損壓縮++

 ③ 3月25日 《老子到此一遊系列》之 老子見證的滄海桑田 —— ++輕翻那些永垂不朽的詩篇++

 ④ 4月4日   《老子到此一遊系列》之 老子遊玩了一條河 —— ++細數生活中的壓縮點滴++

 ⑤ 4月18日 ++【ELT.ZIP】OpenHarmony啃論文俱樂部——一文穿透多媒體過往前沿++

 ⑥ 4月18日 ++【ELT.ZIP】OpenHarmony啃論文俱樂部——這些小風景你不應該錯過++

 ⑦ 4月18日 ++【ELT.ZIP】OpenHarmony啃論文俱樂部——淺析稀疏表示醫學圖像++

 ⑧ 4月29日 ++【ELT.ZIP】OpenHarmony啃論文俱樂部——計算機視覺資料壓縮應用++

 ⑨ 4月29日 ++【ELT.ZIP】OpenHarmony啃論文俱樂部——點燃主緩存壓縮技術火花++

 ⑩ 4月29日 ++【ELT.ZIP】OpenHarmony啃論文俱樂部——即刻征服3D網格壓縮編碼++

 ⑪ 5月10日 ++【ELT.ZIP】OpenHarmony啃論文俱樂部——雲計算資料壓縮方案++

 ⑫ 5月10日 ++【ELT.ZIP】OpenHarmony啃論文俱樂部——大資料架構性能優化系統++

 ⑬ 5月10日 ++【ELT.ZIP】OpenHarmony啃論文俱樂部——物聯網搖擺門趨勢算法++

 ⑭  5月22日 ++【ELT.ZIP】OpenHarmony啃論文俱樂部——電子裝置軟體更新壓縮++

 ⑮ 5月22日 ++【ELT.ZIP】OpenHarmony啃論文俱樂部——人工智能短字元串壓縮++

 ⑯  5月22日 ++【ELT.ZIP】OpenHarmony啃論文俱樂部——多層存儲分級資料壓縮++

【本期看點】

• ndzip應用場景

• ndzip相關算法

• 殘差編碼複現

• SIMD

【技術DNA】

【智慧場景】

**********	********************	********************	********************	********************	********************	********************	********************	********************	********************	********************	********************	********************	********************	********************	*****************
場景	自動駕駛 / AR	語音信号	流視訊	GPU 渲染	科學、雲計算	記憶體縮減	科學應用	醫學圖像	資料庫伺服器	人工智能圖像	文本傳輸	GAN媒體壓縮	圖像壓縮	檔案同步	資料庫系統
技術	點雲壓縮	‎稀疏快速傅裡葉變換‎	有損視訊壓縮	網格壓縮	動态選擇壓縮算法架構	無損壓縮	分層資料壓縮	醫學圖像壓縮	無損通用壓縮	人工智能圖像壓縮	短字元串壓縮	GAN 壓縮的線上多粒度蒸餾	圖像壓縮	檔案傳輸壓縮	快速随機通路字元串壓縮
開源項目	Draco / 基于深度學習算法/PCL/OctNet	SFFT	AV1 / H.266編碼 / H.266解碼/VP9	MeshOpt / Draco	Ares	LZ4	HCompress	DICOM	Brotli	RAISR	AIMCS	OMGD	OpenJPEG	rsync	FSST

NDZIP — 一個用于科學資料的高通量并行無損壓縮器

概述

場景應用

• 分布式計算以及高性能計算在

  機器學習

  、

  大資料學習

  與

  進階模組化與模拟

  等新興技術上都有使用。在航天航空、制造業、金融、醫療等多個領域也有着非常重要的作用。

  

• ndzip

  ，是一種新的

  高吞吐量無損壓縮算法

  ，專門為

  浮點資料的n維網格

  而設計，為

  HPC

  互連帶寬的的限制因素提供了一種有效的解決方案。

本文貢獻

1. 本文提出了一種新的壓縮算法-

   ndzip

   ，它基于一個快速，且并行整數近似的的知名預測器，并結合了對硬體友好的塊細分方案；
2. ndzip 的高性能多級并行實作，利用

   SIMD

   和

   線程級并行

   ；
3. 對大量具有代表性的

   HPC

   資料進行深入的性能評估，并與最新水準的專業浮點壓縮器和通用壓縮方案進行比較。

技術背景

相關算法

FPZIP

• FPZIP

  使用

  洛倫茲預測器

  利用标量 n 維網格内點的直接鄰域的平滑性，使用範圍編碼器壓縮小的殘值。該方案具有很高的壓縮效率，特别是對于單精度值。

FPC

• FPC

  使用一對

  基于哈希表

  的值預測器來壓縮非結構化雙精度資料流。它提供了一個可調參數，利用壓縮效率提高速度。線程并行的

  pFPC 變體

  允許通過以塊的形式處理輸入資料來進一步确定壓縮吞吐量的優先級。

SPDP

• SPDP

  結合了一維預測和

  LZ77變體

  ，可以壓縮單精度和雙精度資料，而不需要對任何一種格式進行專門處理。

MPC

• MPC

  是一種用于

  GPU

  的快速壓縮方案。将一個簡單的一維值預測器與一個位重組方案相結合，可以很好地映射到目标硬體的殘差中去零位。

APE 和 ACE

• APE

  和

  ACE

  壓縮器自适應地從多個值預測器中選擇，将 n 維網格中的資料點與其已處理過的鄰居解相關。殘差使用一種變體的

  Golomb 編碼

  進行壓縮。

數值預測

數值預測科學浮點資料中的單個數值通常在低階尾數位表現出較高的熵，尾數也很少出現精确到重複，這降低了傳統字典編碼器的效率。相反，我們可以使用專門的方法對已經處理過的資料進行預測，隻對殘差進行編碼。

• SPDP

  和

  MPC

  使用簡單的固定步長值預測器，通過存儲 k 個值，并用最近編碼的第 k 個值預測每個點。

• FPC

  和

  pFPC

  使用一對基于哈希表的預測器來維護一個較大的内部狀态，以利用值和值增量中的重複模式。

• fpzip

  使用浮點洛倫茲預測器來估計 n 維空間中長度為 2 的超立方體的一個角的值。

  fpzip

  通過奇數條邊可到達的所有其他角加起來，然後減去通過偶數條邊可到達的角。當超立方體可用n - 1次隐式多項式表達時，預測精度是精确的。
• APE 和 ACE 擴充了

  fpzip預測器

  的思想，通過在每個次元上使用高維多項式，以更大的計算成本為代價提高了預測精度。

差分運算

在無損壓縮環境中，浮點減法不适合用來計算預測殘差。小幅度的浮點值通常不會以簡短的、可壓縮的位的形式出現，而且浮點數的有限精度使浮點減法成為一種非雙射的運算。是以，所有研究的算法都明确地計算位表示的殘差。

• FPC和pFPC 使用

  逐位異或差

  ，而

  SPDP和MPC

  将操作數位重新解釋為整數，并對整數減法的結果進行編碼。
• APE和ACE 提供了兩種變體。

• fpzip

  也使用整數減法，但是它根據符号位對操作數進行反運算，以提高映射的連續性。

殘差編碼

精确的預測會産生具有許多相同前導位的

小幅度殘差

，即異或運算符為零以及二進制補碼的整數減法的

備援符号位

。對這些前導位進行有效編碼是大多數研究方案中所采用的

資料簡化機制

。

• fpzip 使用一個

  範圍編碼器

  來壓縮前導備援位的數量，緊接着複制剩餘位。距離編碼器能夠産生的接近最佳的位串使得其非常節省空間。然而，所需的

  位粒度尋址

  難的問題難以有效解決。

• APE

  和

  ACE

  使用與

  fpzip

  類似的方法，但使用符号排序的

  Golomb

  代碼來編碼備援位的數量。
• FPC 和 pFPC 通過計算雙精度殘差中前導零位元組的數量，使用固定映射對運作長度和4 bit中的預測部分進行編碼。剩餘部分将從第一個非零位元組開始逐字輸出。這種方法是無狀态的，在不可壓縮的情況下有可接受的1/16開銷，代價是由于粒度較低而浪費比特。
• MPC 将剩餘流分成 32 個單精度（或 64 個雙精度）值的塊，發出 32（64）個最高有效位，然後是 32（64）個第二最高有效位，依此類推。零字将從輸出流中删除，并在每個編碼所有非零字位置的塊上替換為32或64位掩碼。這種方法在不可壓縮的情況下有非常低的開銷，僅僅為1/32（1/64），由于字元粒度尋址，該方法在 GPU 上得到了有效的實作，但需要塊内所有的殘差具有相似的位寬才能實作。
• SPDP 從一個類似于 MPC 的重組政策開始，但是SPDP是在位元組級别上的重組政策。SPDP接着使用位元組粒度整數減差運算，并使用 lz77 系列編碼器對結果流進行編碼。這可以消除除前導零之外的重複模式，并使 SPDP 也能處理非浮點資料。

算法分析

• ndzip 的算法主要分為塊細分、整數洛倫茲變換以及殘差編碼三個部分。
• 大體流程：下圖展示了ndzip壓縮管道的所有步驟，首先它将輸入的資料劃分為固定大小的超立方體，并使用多元變換在塊内對資料進行去相關，進而使其具有更短位表示殘差。然後通過位矩陣變換消除公共零位來壓縮剩餘流。壓縮後的資料塊存儲在報頭旁邊，報頭顯示了輸出流中壓縮資料塊的位置。

  

塊細分

• ndzip 不是一次性處理輸入資料的整個 n 維網格，而是将其細分為獨立壓縮的小的超立方體，然後依次進行傳輸。
• 由于該算法需要多次傳遞資料，是以可以更好地使用處理器緩存，但會略微損失解相關的效率。塊與塊之間存在依賴，我們想要消除塊之間的所有依賴關系，可以通過附加額外的資料來實作。
• 這裡作者選擇了4096個元素，則超立方體的大小可以表示為4096^1^、64^2^或16^3^。對于單精度，這相當于16KB的記憶體；對于雙精度，這相當于32KB的記憶體。預先确定塊的大小能夠在之後的步驟生成高度優化的機器碼。
• 當網格範圍不是塊的大小的倍數時，邊框元素将不被壓縮地附加到輸出中。

整數洛倫茲變換

浮點洛倫茲預測器（Floating-point Lorenzo Predictor） 對于多元資料的預測是非常高效的，但是單獨位模式的殘差計算需要解碼器從已經解碼的臨近值重建每個預測，進而引入限制并行計算的依賴。

是以，作者使用了整數洛倫茲變換（ Integer Lorenzo Transform） 解決了這個問題。整數洛倫茲變換是一種直接計算整數域内的洛倫茲預測殘差的近似的多道運算。下圖便說明了這個過程。

殘差編碼

• 關于殘差編碼，ndzip使用了與 MPC 相同的殘差編碼方案，使其可以在現在的CPU上高效的實作。

  大緻流程如下：

1. 殘差使用了二進制補碼進行表示，根據殘差的符号，确定了補碼第一位是1還是0。之後通過0消去對兩者進行編碼。
2. 殘差首先被轉換成符号-數值（sign-magnitude）表示，隻要殘差為負，就對除了第一個比特外的所有比特進行翻轉。

   

3. 然後将殘差流分成32個單精度或者64個雙精度的值，對每個塊進行

   32x32（64x64）

   的位矩陣變換

   

4. 将來自相同位置的比特分組成單詞，從輸出中消去可以消去的0詞

5. 在每個塊前面加上一個32位（64位）的頭，将非0字的位置編碼為位圖。

使用教程

• 上面的原理看的有點頭秃，下面講解如何快速上手ndzip。
• 點選進入 ndzip 的位址，git 下項目到本地。

環境搭建

環境需求

運作 ndzip 需要以下環境，

Catch2

可根據自己是否需要來選擇是否安裝。

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

CMake安裝

• CMake

  在

  Ubuntu軟體源

  中，安裝非常簡單，執行以下指令即可：

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
           

• 等待編譯添加完即可。

  

建構

使用 CUDA + NVCC 建構 ndzip

• 使用 cuda，安裝

  CUDA Toolkit

  ：

sudo apt-key del 7fa2af80 # 删除舊的GPG密鑰，之前裝過的要删掉

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 建構 ndzip

  （自己使用SYCL建構ndzip沒跑出來。。。）

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

• 完成建構

  

測試

• 測試指令

  

• 測試ndzip壓縮

  

評價

解耦多元資料

• ndzip-gpu 通過變換在解耦多元資料時實作了高資源使用率。提出了一種用于垂直位打包的新穎、高效的曲速協同原語，提供了高吞吐量的資料縮減和擴充步驟, 為檢查的資料提供了最佳的平均壓縮比, 同時在雙精度情況下的資料減少和吞吐量之間保持了有利的權衡。将資料集的壓縮比定義為壓縮大小除以未壓縮大小(以位元組為機關)，比率越低表示壓縮越強。在需要彙總比率的情況下，傳回資料集上壓縮比率的未權重算術平均值。

  

SIMD

• SIMD(Single Instruction Multiple Data），單指令多資料流，能夠複制多個操作數 ，并把它們打包在大型寄存器的一組指令集。
• ndzip專為在支援 SIMD 的現代多核處理器上高效實施而量身定制，能夠以接近主記憶體帶寬的速度壓縮和解壓縮資料，顯著優于現有方案。通過測量從系統記憶體壓縮和解壓縮到系統記憶體的時鐘時間來評估性能。第三方實作允許在必要時進行記憶體操作。傳回每秒未壓縮位元組的吞吐量，它轉換為壓縮輸入和解壓輸出帶寬。重複測量每個算法和資料集對，直到總運作時間超過一秒。在每次疊代之前，從 CPU 緩存中删除輸入資料。

  

• 利用多元度的好處可以通過使用等效的一維變換來轉換高維資料集來衡量。

  實驗

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

• 為了估計新型整數洛倫佐變換(ILT)的有效性，我們用其他預測方法代替了實作中的變換步驟，并比較了得到的壓縮比，通過使用等效的一維變換來轉換高維資料集來衡量。
• 如圖顯示了具有相同次元的所有資料集的平均壓縮比，相對于在各自次元中觀察到的最差壓縮比進行了縮放。

  

• 因為該次元相對最差的壓縮比(越小越好)，對于一維資料集，所有方案大緻相同。總體上看，FLP最好，最差的選擇是兩個一維預測器，這表明基于洛倫佐的元件顯著受益于更高的次元,選擇餘數運算對于逼近 FLP 的相關特征至關重要。

  算術平均未壓縮吞吐量

• 在測試資料上比較通過檢查的壓縮器實作，實作的吞吐量和壓縮比。 根據設計，同時并非所有算法都能同時處理單精度值和雙精度值。有些算法有一個或多個可調參數展現為連續的線，而ndzip，沒有可調的行為。

  

• 通用算法可以在浮點資料上實作高壓縮比，但隻能以犧牲大量計算資源為代價。比如，LZMA 在雙精度值上實作了最高的壓縮比，與最強的單精度壓縮器 fpzip 不相上下，同時花費更多壓縮我們最大的資料集。LZ4 實作了比任何其他審查過的單線程算法更高的壓縮和解壓縮吞吐量，同時還提供了最差的資料縮減。Zstandard 提供了一個非常好的權衡，在單精度資料上主導 Deflate 和專門的 SPDP。大多數專業算法能夠在至少一個次元上勝過通用方案。而Fpzip 是最強大的單精度壓縮器，而且僅以中等吞吐量為代價，但在解壓縮方面失去了吞吐量比較.
• 是以ndzip 是最快的專用壓縮器和解壓縮器，具有顯着優勢（“st”）。 對于雙精度資料集，稍差一些。與一些速度較慢的算法相比，我們的壓縮器提供了更低的壓縮比，但在吞吐量方面明顯優于它唯一的競争對手 LZ4。

  

結論

• 通過設計一種考慮到目标架構特性的專用壓縮算法，可以實作出色的資源使用以及壓縮率和吞吐量之間極具競争力的折中。基于我們新穎的小超立方體資料，利用了行整數洛倫佐變換(Integer Lorenzo Transform)和硬體友好的殘差編碼方案，ndzip 壓縮器利用 SIMD 和線程并行性在消費類硬體上實作超過 10 GB/s 的壓縮和解壓縮速度，顯著地減少資料量。

參考文獻：

Knorr F， Thoman P， Fahringer T. ndzip： A High-Throughput ParallelLess Loss Compressor for Scientific 2021 Data Compression Conference （DCC）.IEEE， 2021： 103-112

Knorr F, Thoman P, Fahringer T. ndzip-gpu: efficient lossless compression of scientific floating-point data on GPUs[C]//Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 2021: 1-14.

附件連結：https://ost.51cto.com/resource/2022