【ELT.ZIP】OpenHarmony啃論文俱樂部—硬體加速的快速無損壓縮

• 本文出自

  ELT.ZIP

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

  7個地方

  的同學，我們在

  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啃論文俱樂部——多層存儲分級資料壓縮++

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

 ⑱  6月3日 ++【ELT.ZIP】OpenHarmony啃論文俱樂部——快速随機通路字元串壓縮++

【本期看點】

• LZ4回顧

• 對于資料格式的改進

• 對于哈希計算的優化

• 優化後硬體架構

【技術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

引言：

着高品質多媒體服務的增加，資料壓縮已成為使用存儲的電子裝置的必要條件。

多年來，移動通信和視訊服務的品質不斷提高，傳輸和存儲資料的需求呈爆炸式增長。對大容量存儲和傳輸的需求增長速度至少是存儲和傳輸容量增長的兩倍。本文将為大家介紹一種基于 LZ4 的改進算法和一種優化的移動裝置硬體結構。

應用場景

1.移動通信

::: hljs-center

:::

2.視訊服務

::: hljs-center

:::

移動裝置限制條件

• 近年來，随着物聯網等場景的不斷發展，一些問題也逐漸的暴露了出來，就比如嵌入式裝置上的

  CPU時鐘頻率

  ，

  電源

  等資源都是有限的；對于部分裝置來說可能換個時鐘頻率高的時鐘、換個大的電池确實可以解決問題，但對于手機這種嵌入式移動裝置來說，像是要做到便攜、輕薄等等要求，體積就被限制住了，電源也是以被限制住了。
• 是以，需要一種基于硬體的壓縮方法來解決這個問題。

本方案的解法

基于

字典

的

自适應壓縮方法

都起源于

Lempel-Ziv 算法

,

LZ4

是最快的壓縮算法之一。

但下面我們将為大家介紹一種先進的

算法

和

硬體架構

，提高了

壓縮比

和

速度

。為了獲得

更高的壓縮比

，本算法

可變長度格式

，而

LZ4 采用定長格式

。實驗結果表明，該體系結構的

壓縮吞吐量

可達 3.84Gbps，

壓縮比

可達4 。

通過這種方式，我們基于硬體的架構以低功耗提高了移動裝置的記憶體性能和電池壽命。

LZ4 分析

• LZ4 是 LZ77 的一個變種算法，是 Collet 在2011年提出的

  固定的（fixed），面向位元組（byte-oriented）

  的算法。
• LZ4 的伸縮資料如圖所示，它由

  令牌（Token） 、 字面量長度（Literal length） 、 偏移量（Offset） 和 比對長度（Match length）

  組成。
• LZ4 和 LZ77 類似，它有一個滑動視窗，由一個

  搜尋緩沖區

  和一個

  向前查找緩沖區

  組成。
• LZ4 搜尋之前沒有壓縮資料流中的重複資料，并用索引替換它。
• LZ4 通過哈希表來比對資料，進而提高了壓縮速度。

  

令牌（Token）

• 令牌（Token） 長一個位元組，其中前4個位元組為

  字面量長度（Literal Length）

  ，其後四個位元組為

  比對長度（Match Length）

  。

• Token[3:0]

  表示

  比對長度

  ，表示 0 ~ 15 的文字長度。

• Token[7:4]

  表示

  字面量長度

  ，是比較不重要的位，比對長度從0 ~ 15。

  

• Token [7:4]

  的值如果為0，則代表沒有文字。

• Token [7:4]

  的值如果為15，則表示文字長度必須有從 0~255 的額外位元組來表示字面量的完整長度。

• Token [3:0]

  的如果值為0，則表示最小比對長度為4，稱為

  min match

  。
• 是以，

  Token [3:0]

  的值從0到15意味着比對長度值從4到19。如果

  Token[3:0]

  的值為15，則比對長度中有更多位元組。

字面量長度（Literal Length）

• 當

  Token[7:4]

  值為 15 時，

  字面值長度（Literal Length）

  就是額外的位元組。
• 如果

  字面量長度

  為 0~254，則沒有更多的位元組。如果

  字面量長度

  是255，在下一個字面量長度中有産生更多的位元組。

偏移量（Offset）

• 偏移量（Offset）

  占用2位元組，采用

  little-endian

  格式，它表示要複制的比對的位置。
• 偏移值為 1 表示目前位置為 1 byte。最大偏移量為 65535。

比對長度（Match Length）

• 比對長度（Match Length）

  類似于上面說到的

  字面量長度（Literal Length）

  。
• 當

  Token[3:0]

  達到可能的最高值 15 時，額外的位元組被添加到

  比對長度

  中。

總結

• LZ4 總是為

  偏移量（Match Length）

  配置設定 2位元組，但其實這對壓縮比的性能影響不大。
• LZ4算法最初是為了在一般處理器上進行軟體實作而提出的，是以在一些硬體上實作 LZ4 存在一定的限制。

改進的LZ4

本文作者改進了LZ4的

資料格式的序列

和

哈希計算

。

• 通過指定壓縮單元的大小，可以優化哈希表的大小。
• 将壓縮單元的大小設定為 4KB，可以為記憶體頁進行優化并節省内部記憶體。

資料格式

• 這裡作者改變了 LZ4

  的首部（Header）

  和

  偏移量（Offset）

  ，下圖分别是 改進後的 LZ4 與 LZ4 的格式。

Header	Token	Literal	Length Literals	Offset	Match Length
2 Bytes	1 Byte	0-n Bytes	0-L Bytes	1-2 Bytes	0-n Bytes
Token	Literal Length	Literals	Offset	Match Length
-	-	-	-	-
1 Byte	0-n Bytes	0-L Bytes	2 Bytes	0-n Bytes

首部（Header）

• 頭部位于每個壓縮單元的開頭，包含

  壓縮大小（Compressed Size）

  和

  原始标志（Raw Flag）

  。
• 如果

  壓縮後的資料大小

  大于

  原始資料大小

  ，則

  原始标志（Raw Flag）

  則被标記為

  1

  ，

  原始資料

  将被添加在

  首部（Header）

  之後，壓縮符号将不被添加，

  解壓器

  也不需要解壓該壓縮單元。
• 在資料根本沒有壓縮的最壞情況下，

  原始标志（Raw Flag）

  使解壓縮程式更快。
• 在最壞的情況下，壓縮單元大小被添加到原始資料的頭部大小中。

偏移量（Offset）

• 偏移量（Offset）

  由

  大小标志（Size Flag）

  和

  偏移量大小（Offset Size）

  組成。

• 大小标志（Size Flag）

  是最重要的位。如果

  大小标志

  值為 0，

  偏移量大小

  則使用 7 bit，即

  {offset [7]， offset[6:0]}

  。
• 如果

  大小标志

  值為 1，

  偏移量大小

  則使用 15 bit，即

  {offset [15]， offset[14:0]}

  。

• 偏移量大小

  表示比對的位置，最大偏移大小值為32768。

• 可變偏移位元組長度使我們的方法比LZ4有更好的壓縮比。

  哈希計算

• 哈希函數的目的是将任意大小的資料映射到固定大小的資料。對于比對檢測，使用哈希表的搜尋算法要比其他算法快得多。
• 理想的哈希表的大小是輸入資料位乘以壓縮機關位元組的大小。 但是，由于哈希表的大小是有限的，是以哈希計算計算輸入的比特數要比輸入的比特數小。
• 哈希計算的性能取決于不同的輸入得到相同結果的頻率。
• LZ4的哈希計算算法基于Fibonacci哈希原理，計算公式如下：

  

• 上述公式中的

  IN

  為32位值，LZ4的哈希計算公式在硬體上實作複雜，并且計算周期長。于是作者改進了該哈希計算公式，公式如下：

  

• 這裡壓縮單元大小為4KB，改進後的公式被 12 bit 屏蔽，僅使用位操作就可以将32位輸入映射到12位。是以，一個很小的硬體資源就足以計算改進後的哈希計算公式，并且隻需要一兩個周期。

建議的硬體架構

總子產品

• 這裡作者提出了一種建議使用的硬體架構。它主要由

  核心子產品(壓縮子產品和解壓縮子產品)和進階微控制器總線體系結構（AMBA）

  接口組成，實作應用處理器的互連。
• 核心子產品通過

  進階外設總線（APB）與處理器

  進行控制信号通信。輸入資料和輸出資料通過

  進階可擴充總線（AXI）

  處理。
• 下圖為總體的硬體架構：

  

• 下表描述了是各個子產品的數量，面積以及總面積。

子產品	子產品數量	面積	總面積(mm2)
Compress	1	0.01320	0.01320
Decompress	1	0.01345	0.01345
Hash Table	2	0.00515	0.01029
SRAM	8	0.00652	0.05215
AXI(DMA)	1	0.01187	0.01187
APB	1	0.00133	0.00133

壓縮子產品

• 壓縮子產品主要由

  SRAM控制元件、哈希計算元件、位元組比對元件和流生成元件

  組成，下圖為壓縮子產品的架構圖。

  

• 為了避免資料輸入的瓶頸，壓縮子產品将輸入資料寫入8個獨立的SRAM。
• 之後壓縮機從SRAM移位寄存器讀取128 bit 資料。
• 對于每個 4 byte 的輸入資料，哈希計算子產品計算哈希值，讀取哈希表來比較和更新索引。
• 如果在哈希表中搜尋計算出來的哈希值，則移動到該位置并開始比對位元組。當比對長度大于4時，因為哈希值已經從前面的文字計算出來了，此時可以跳過哈希計算。
• 壓縮單元最後一次資料處理完畢後，壓縮機檢查壓縮尺寸是否大于原始尺寸。如果大于原始尺寸，壓縮子產品将

  原始标志（Raw Flag）

  設定到

  首部（Header）

  并輸出原始資料。
• 當壓縮記憶體資料時，對于未壓縮的頁，隻将頁頭寫入輸出。在這種情況下，CPU讀取頭中的

  原始标志（Raw Flag）

  ，解壓時執行

  memcpy

解壓縮子產品

• 解壓縮子產品比壓縮子產品簡單，它主要由

  SRAM控制元件、流解析元件和緩沖區元件

  組成。

  ::: hljs-center

:::

• 解析器流 通過從SRAM讀取輸入資料來解析報頭和每個符号。
• 字面量 通過複制文字長度從輸入資料中獲得的
• 比對部分 是通過比對長度從已經解壓的資料中的偏移位置複制的。
• 如果與目前資料的偏移距離太近，後續管道可能不會寫入資料。是以便有了緩沖區來儲存沒有寫入的資料。

實驗及結果

• 在這裡，作者将提出的設計與原來的 LZ4 進行了比較，并展示了壓縮比與壓縮速度以及各種資料類型之間的關系，這些資料類型包括

  二進制資料、文本資料、Android應用程式包、字型資料、JPEG圖像以及 HTML頁面資料

  。
• 本實驗所提出設計運作在 400MHz 的處理環境下。資料的吞吐量也取決于總線條件，在考慮總線條件的情況下，要考慮整個子產品的壓縮速率。

  

• 由圖 【壓縮比與壓縮速度的關系】 可知，壓縮比與壓縮速率呈線性關系。
• 較低的壓縮比意味着大多數的輸入位元組都被處理，是以壓縮速率變慢。
• 相反地，壓縮速率很快的情況下，将會跳過部分比對的位元組，壓縮比會增大。
• 總的來說，壓縮速率取決于壓縮比，壓縮速率也與壓縮比呈正比。

  

  

• 由于在LZ4中有一個加速選項，加速值越高，壓縮越快；相應的，壓縮比會降低。這裡便有了上述兩圖與LZ4各加速方案進行了比較的實驗。

總結

本文提出了一種改進的 LZ4 算法和硬體結構。可變長的偏移量、優化的雜湊演算法以及硬體流水線都提高了壓縮速率和壓縮比。

• 該設計可實作高達3.84Gbps的壓縮吞吐量和高達4的壓縮比。
• 它的壓縮速度比 LZ4 算法快4%，壓縮比比 LZ4 算法高5%，但它的最高時鐘頻率比 LZ4 慢。
• 文中所提出的硬體架構可以針對移動裝置環境進行優化，是以它不僅可以用于壓縮移動裝置中的内部存儲，還可以用于壓縮RAM，進而有望提高記憶體性能。
• 該硬體架構還可以實作低電流驅動和低功耗驅動，進而提高電池壽命。

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