面向申威眾核處理器的LZMA并行算法設計與優(yōu)化*

李秉政，黃高陽，許瑾晨

1.數學工程與先進計算國家重點實驗室，鄭州 450000

2.江南計算技術研究所，江蘇無錫 214125

1 引言

隨著高性能計算機性能的提升，其規(guī)模不斷擴大。大規(guī)模的高性能計算集群系統(tǒng)必須保持長期穩(wěn)定的不間斷運行，其傳輸、存儲和處理的數據量不斷增長，隨之產生的系統(tǒng)日志數據量也呈現(xiàn)出爆炸式增長。當前以及今后一段時期，可以預見的是，社會計算數據和科學計算數據規(guī)模也將隨著信息化程度的提高而不斷增長，這都給高性能計算數據處理帶來了新的挑戰(zhàn)。必須進行有效的壓縮，才能夠減少數據存儲所需空間，最大限度利用有限的通信帶寬，使高性能計算集群系統(tǒng)發(fā)揮最大的效能。

無損壓縮算法開源實現(xiàn)種類繁多，算法思想成熟。國產異構眾核高性能計算機系統(tǒng)中，現(xiàn)有的數據壓縮算法包括zlib-Deflate、xz、lz4等，在移植應用過程中并沒有對壓縮算法進行并行優(yōu)化，僅使用單核對數據進行壓縮解壓處理，其處理效率沒有太大的提升空間。在壓縮算法中，普遍存在著壓縮速率與存儲空間使用的矛盾、數據局部性差等特性，要想獲得有效的性能提升，必須針對特定的多核異構處理器進行深度的算法重構與優(yōu)化。

目前為止，已有多項研究采用多核處理器架構進行壓縮算法的并行化。BWT（Burrows-Wheeler transform）壓縮算法并行化研究較早出現(xiàn)，由Pankratius等在文獻[1]中提出，獲得線性的加速比，并應用于bzip軟件。Pigz是一個并行版本的gzip壓縮算法，由Gristwood等在文獻[2]中提出，并獲得廣泛應用，但該并行算法壓縮率較低。Patel等采用GPU對BWT無損壓縮算法二叉樹搜索過程進行并行化[3]，加速效果顯著。Wu等研究了基于CUDA（compute unified device architecture）的壓縮算法[4]，并采用分塊并行的策略在GPU上優(yōu)化LZ77壓縮算法。Gilchrist使用MPI（message passing interface）編程實現(xiàn)分布式的MPIBZIP[5]壓縮算法，適用于分布式內存計算。Wright則在分布式內存結構和共享內存結構中分別使用MPI和Pthreads編程實現(xiàn)bzip2并行算法[6]。基于BWT的壓縮算法雖然易于并行化，但在壓縮率上不如LZMA（Lempel Ziv-Markov chain algorithm）等壓縮算法。而xz、7zip等開源壓縮軟件多線程并行化過程中，僅對LZMA算法中的字符匹配核心函數并行化，加速效果不理想且受到處理器數量的限制[7-8]。Leavline等在文獻[9-10]中使用FPGA（field programmable gate array）專用集成電路加速LZMA算法，可以獲得較高的加速比，但應用成本較高，不具有普遍的適用性。

神威太湖之光異構眾核計算系統(tǒng)[11]中，基本單元為一個申威異構眾核處理器和32 GB內存與其他控制器組成的計算節(jié)點，其處理器體系結構如圖1所示。256個計算節(jié)點構成一個超節(jié)點，總計160個超節(jié)點提供93PFLOPS的實測性能。其中，從核采用輕量級的核心設計，其指令集功能非常精簡，不支持中斷等操作，僅在用戶態(tài)下運行。每個從核包含16 KB指令L1級cache和64 KB LDM（local directive memory，片上局部數據空間），支持256位向量操作。從核可與主核共享內存，采用DMA（direct memory access）方式進行內存與LDM的數據交換。從核陣列中，處于同一行或列的從核可通過寄存器通信方式進行數據交換，每次傳輸數據量最大為256 bit，延遲較低。

Fig.1 General architecture of SW26010 processor圖1 申威26010處理器結構圖

圖2為從核CPE（computing processing element）存儲層次結構圖。從核可通過寄存器直接訪存和寄存器LDM訪存兩種方式讀取數據。由于主核與從核之間沒有共享緩存，寄存器直接訪存的延遲達到近百個時鐘周期。解決問題的方式之一就是通過DMA方式將數據拷貝至LDM進行訪存來提高訪存速度。這增加了并行程序設計的難度，需要程序合理地設置DMA調度策略，盡可能實現(xiàn)計算通信重疊，提高并行效率。從核間數據交換，可采用寄存器通信方式進行。根據主從并行編程模型的特點，神威太湖之光提供了Athread加速線程庫，分為主核加速線程庫和從核加速線程庫兩部分。

Fig.2 Memory hierarchy of computing processing element圖2 從核CPE存儲層次結構圖

本文主要研究是設計一個面向國產申威26010異構眾核處理器的LZMA并行算法，并結合異構眾核處理器的特點，對算法進行重構與性能優(yōu)化。

2 LZMA算法分析

本章就LZMA算法中的空間需求、訪存方式、數據局部性、熱點函數等影響其算法性能的特點，結合國產異構眾核處理器關鍵技術進行分析，以便更有針對性地對算法進行重構與優(yōu)化。

2.1 LZMA算法流程

LZMA壓縮算法由Pavlov于1998年發(fā)明[12]，其核心是基于LZ77壓縮算法的改進。LZMA中使用了基于滑動窗口的動態(tài)字典壓縮算法和區(qū)間編碼算法，具有壓縮率高、解壓縮空間需求小及速度快等優(yōu)勢。圖3所示為LZMA算法流程，包含基于LZ77[13]的滑動窗口算法和區(qū)間編碼[14]（range encoding）兩級壓縮。

LZMA算法支持4 KB到上百MB的字典空間，在提升壓縮率的同時也導致其搜索緩存空間變得很大。為了減小匹配最長的字符串所需時間，快速搜索匹配字符，LZMA算法實現(xiàn)中，將多個可能的最長匹配存儲于Hash散列表中，使用Hash鏈表或二叉查找樹的數據結構來查找匹配數據。如圖4所示，Hash函數中，將搜索緩存頭兩個字節(jié)的散列值作為一個散列數組的索引，散列數組存放著對應匹配字符組的起始位置。該散列數組大小為字典大小一半的2的整次冪。LZMA編碼器針對2、3、4個相鄰字節(jié)設置了不同級別的散列函數，用以實現(xiàn)對應不同字典大小的高效定位。

Fig.3 Flow diagram of LZMA圖3 LZMA算法流程

Fig.4 LZMA sliding window algorithm based on Hash table圖4 基于Hash查表的LZMA滑動窗口算法示意圖

2.2 空間需求分析

在異構眾核系統(tǒng)中，每個從核處理器都配有64 KB的LDM。為保證從核能夠獲得較高的加速性能，需將計算數據拷貝至從核LDM空間訪存，這就要求必須精確控制從核變量空間的使用。表1是LZMA算法熱點函數局部變量的使用情況，其中主要包含了占用空間較大的局部數組大小，局部標量空間占用空間較小，忽略不計。

基于Hash查表的字符串匹配函數中，由于字典空間較大，其Hash散列表hash_buf預留的較大的散列空間，遠超從核64 KB的LDM空間，需要進行優(yōu)化，壓縮局部空間的使用?？梢栽趬嚎s率損失允許的范圍內盡可能減小字典搜索的范圍，從而減小Hash查表函數散列空間的大小。

Table 1 Local variable size of hotspot function表1 熱點函數局部變量空間大小

2.3 訪存特性分析

LZMA算法中，使用了Hash鏈表的數據結構來快速查找匹配字符。由于其搜索緩存比較大，其Hash查表空間范圍隨之增長，在幾百KB到數十MB范圍內隨機訪存。同時，LZ77算法基于滑動窗口的流式壓縮中，因為未編碼的數據不斷輸入，已編碼的數據在達到搜索緩存空間上限后便丟棄不用，其數據局部性較差。

由于事先無法判斷未編碼數據中重復字符串的長度和位置，也無法預測其匹配字符串的距離，因此LZMA算法中難以對數據進行預取。壓縮過程中，其字典規(guī)模隨著匹配字符串的增多而逐漸增長，壓縮當前數據塊，依賴于先前壓縮過程所獲得的字典。LZMA算法具有隨機訪存和數據依賴特性，屬于訪存密集型算法，其性能優(yōu)化的關鍵就在于結合國產異構眾核系統(tǒng)的存儲結構，對算法的數據結構和訪存進行重構，以減小訪存開銷，最大限度地發(fā)揮從核的加速性能。

2.4 熱點函數分析

LZMA壓縮算法主要的耗時函數集中于LZ77字符串匹配核心函數中。核心函數模式匹配過程如算法1所示。其中，耗時的操作主要為Hash查表和字符匹配，以及Hash散列表的更新。

算法1基于滑動窗口的LZ77壓縮算法

熱點函數中，字符匹配過程訪存具有一定的連續(xù)性，即由當前字節(jié)位置開始，匹配搜索緩存中連續(xù)相同的最長字符串。而每一次匹配的字符，則由輸入數據給出，可能出現(xiàn)最長匹配字符的位置在Hash表中散列存放，其查表訪存具有一定的隨機性。針對熱點函數的特點，主要有兩點優(yōu)化思路：一是在空間使用上精細劃分，最大程度將訪存密集的操作集中于LDM；二是對算法進行適當重構，使用兩字節(jié)Hash函數替換三字節(jié)Hash函數，進一步壓縮LDM空間的使用，減小訪存延遲。同時也要注意LDM緩存空間大小與數據傳輸的負載均衡，實現(xiàn)最大限度的計算通信隱藏。

3 LZMA異構眾核并行算法

3.1 任務劃分

將待壓縮數據均勻地分配給64個從核，從核直接訪問主存讀取待壓縮數據，并將壓縮后的數據添加首部信息后，直接輸出至主存，最后再由主核將數據塊按照順序寫入文件。在本文中，采用了主從異步并行，將LZMA算法中LZ77壓縮算法和區(qū)間編碼的核心計算任務交給從核陣列，主核只負責數據劃分和I/O操作。線程并行算法的步驟如下。

步驟1數據分塊。根據從核的數量，將待壓縮數據劃分成若干子數據塊。劃分時，按照內存頁大小的整數倍進行劃分。由于壓縮算法中計算量和輸入數據量近似呈正比關系，只需滿足所劃分的數據塊大小均等，即可實現(xiàn)并行任務負載均衡。

步驟2兩級壓縮。各個數據塊由從核獨立進行壓縮，包含兩步壓縮。在LZ77算法中，首先初始化壓縮字典。隨著滑動窗口的推進，待壓縮數據持續(xù)輸入，字典大小隨之增長。隨后，經LZ77算法壓縮的數據結構作為區(qū)間編碼的輸入數據進一步進行壓縮并輸出。

步驟3數據合并。從核完成壓縮后，主核負責將壓縮數據合并。首先寫入5 Byte header，其內容為字典大小、最大比配長度等壓縮參數信息。然后將各壓縮塊按照排列順序，添加4 Byte的首部信息block_size之后輸出。block_size內容為壓縮后數據塊的大小。

3.2 DMA訪存雙緩沖設計

通過3.1節(jié)分塊并行方式，串行LZMA壓縮算法的核心計算部分可移植至從核陣列。然而，從核直接訪問主存時，其訪存開銷將使得并行算法的性能嚴重下降，其加速效果不足以彌補訪存延遲帶來的性能損耗。另外，在串行版本LZMA壓縮算法中，待壓縮數據存儲于動態(tài)分配的一塊內存空間中，由指針指向的地址來確定其當前壓縮的滑動窗口。由于壓縮數據規(guī)模較大，從核LDM空間有限，即使按照線程任務進行分塊，其大小也遠超LDM的64 KB最大容量，待壓縮數據塊無法一次性裝入。因此需要對算法進行重構優(yōu)化，壓縮LDM空間的使用。

為了改善數據局部性，本文根據LZ77滑動窗口算法的特點，結合LDM空間資源使用情況，采用基于非阻塞DMA的訪存雙緩沖技術。如圖5所示，從核不直接訪問主存讀取壓縮數據，而是通過DMA方式將當前壓縮窗口的數據及其前后部分數據作為一個壓縮單元傳輸到LDM緩沖區(qū)，實現(xiàn)快速訪存；與此同時，下一個壓縮單元已發(fā)起DMA傳送，進行數據預取，待當前壓縮單元任務完成后，便可直接進行壓縮計算，實現(xiàn)計算訪存重疊，這進一步減小了訪存開銷。同時，輸出數據也設置緩沖區(qū)，通過DMA方式拷貝至內存。算法2為使用Athread接口實現(xiàn)的LZMA算法多線程并行的示例。

Fig.5 DMA double buffer圖5 DMA雙緩沖示意圖

算法2基于Athread接口的LZMA并行算法

3.3 LDM空間布局優(yōu)化

LZMA算法串行版本中，使用指針直接指向待壓縮數據的內存空間，以位移的形式實現(xiàn)基于滑動窗口的字典壓縮算法。而在從核多線程并行中，需要將壓縮數據拷貝至LDM緩存區(qū)進行訪存。為了實現(xiàn)DMA雙緩沖，充分利用LDM空間，本節(jié)采用手動方式對LDM地址空間進行細粒度的管理分配，并對滑動窗口算法進行了重構。設置一個連續(xù)的雙緩沖空間，指針bufferbase指向該地址空間起始地址，即第一塊緩沖區(qū)起始位置。指針buffer_middle指向緩沖空間的中間位置，即第二塊緩沖區(qū)的起始位置。指針pos_start和pos_end分別指向當前滑動窗口的起始位置和結束位置。

算法開始時，如圖6所示，首先發(fā)起阻塞式DMA請求，讀取數據塊至緩沖區(qū)1，之后調用滑動窗口壓縮函數，同時發(fā)起非阻塞式DMA請求讀取下一個數據塊至緩沖區(qū)2。當滑動窗口指針pos_end移動至buffer_middle位置時，檢查非阻塞式DMA請求完成，便可繼續(xù)壓縮。之后，滑動窗口指針pos_start移動至buffer_middle位置時，同時發(fā)起非阻塞DMA請求讀取下一個數據塊至緩沖區(qū)1。指針pos_start和指針pos_end移動至緩沖區(qū)結束位置時，循環(huán)移動至起始位置繼續(xù)壓縮，直至全部數據壓縮完畢為止。

Fig.6 LDM address space partition of sliding window encoding based on DMA double buffer圖6 DMA雙緩沖滑動窗口壓縮的LDM空間布局

4 實驗結果與分析

本章主要對LZMA異構眾核并行算法的壓縮率和壓縮時間等性能指標進行測試和分析。測試的基準性能為串行LZMA算法在主核上運行的壓縮率和壓縮用時。測試的計時方法為使用Athread計時接口統(tǒng)計算法運行所經過的節(jié)拍數，并由此計算出運算時間。

4.1 基準測試語料庫和測試平臺

Silesia壓縮測試語料庫由Deorowicz于2003年提出[15]，提供涵蓋當前使用的典型數據類型的文件數據集，其文件大小介于6 MB和51 MB之間。該語料庫的提出主要為了解決傳統(tǒng)Canterbury語料庫缺少大型文件和文件類型單一的問題?；鶞蕼y試集的測試用例如表2所示。

Table 2 Silesia corpus test contents表2 Silesia語料庫測試用例

實驗的平臺為神威太湖之光異構眾核系統(tǒng)，其參數如表3所示[11]。實驗中使用的壓縮算法基準測試集為Silesia語料庫基準測試集。同時，為了測試大數據量的壓縮性能，將Silesia語料庫測試集文件復制并打包，組成了GB級的數據進行壓縮測試。

Table 3 Experiment environment表3 實驗環(huán)境

4.2 從核性能測試結果

為了測試LZMA并行算法在眾核處理器上的加速效果，選取主核串行版本LZMA算法作為基準，來對比不同優(yōu)化方案的性能。其在Silesia語料庫基準測試的壓縮速率和壓縮率如圖7所示。從核直接讀取主存數據的線程并行版本中，由于訪存瓶頸較大，64線程從核并行僅獲得了2倍的平均加速比，甚至在某些用例中用時超過了串行壓縮。而使用DMA雙緩沖方式進行計算通信重疊的優(yōu)化版本，壓縮速率獲得了3.7倍的平均加速比和4.1倍的最大加速比，表明使用DMA雙緩沖并行性能得到了較大提升。在壓縮率方面，并行與串行版本算法的壓縮率基本相同。

Fig.7 Test performance results of Silesia corpus圖7 Silesia語料庫測試性能結果

進一步分析，本文討論了DMA雙緩沖設計中單個緩沖區(qū)大小buffer_size的選擇對消息傳遞次數及壓縮速率的影響。如圖8所示，當buffer_size小于20 KB時，因單次DMA拷貝數據量較小，計算與通信不能實現(xiàn)全部重疊，同時DMA次數增多，相應的DMA開銷增大，壓縮速率略有下降。當buffer_size大于25 KB時，壓縮速率隨緩沖區(qū)大小變換不大。理論上，緩沖區(qū)的設置應當使得DMA通信延遲與計算達到負載均衡，但由于LDM空間有限，并且需要預留給其他局部變量使用，無法繼續(xù)擴大緩沖區(qū)，故取當前性能最佳的緩沖區(qū)大小作為最優(yōu)參數，實現(xiàn)計算通信的重疊收益最大化。

Fig.8 DMA buffer size influence on speedup performance圖8 DMA雙緩沖塊大小對加速比的影響測試

Table 5 Performance test comparison between Intel x86 and Sunway 26010表5 Intel x86與申威平臺性能測試對比

絕大部分壓縮測試語料集數據規(guī)模較小，均未提供GB級的測試用例。本文基于Silesia語料庫組合生成大文件測試集，以測試LZMA并行算法在大規(guī)模數據中的壓縮性能。表4顯示了大規(guī)模數據壓縮中串行LZMA算法和并行算法的性能比較。由數據表可知，當數據量超過500 MB時，并行壓縮速率有著明顯的提升，最大能達到5.3倍的加速。該并行壓縮算法在大規(guī)模數據的壓縮方面有更好的適應性。

Table 4 Large-scale data compression test results表4 大規(guī)模數據壓縮測試結果

4.3 相關工作對比

Alakuijala和Kliuchnikov等人使用Canterbury壓縮測試語料庫對Bzip2、LZMA等壓縮算法進行了性能測試和對比分析[16]。其實驗平臺為Intel E5-1650 v2 3.5 GHz處理器。本文用申威異構處理器平臺的測試結果與之對比。由于壓縮數據集不同，故僅分析平均壓縮率和平均加速比的情況，結果如表5所示。在CPU頻率差距明顯的情況下，申威主核串行算法性能不及Intel CPU，而從核并行的加速模式較Intel CPU加速效果十分明顯，表明從核加速模式具有較好的性能優(yōu)勢。

5 結束語

超級計算機性能的快速提升，使得傳統(tǒng)科學計算應用和以大數據、人工智能為代表的社會計算應用得以不斷擴展，其應用數據和集群系統(tǒng)運維數據的規(guī)模也在不斷擴大，帶來了機遇與挑戰(zhàn)。近年來，異構多核的體系架構成為高性能計算的主流發(fā)展方向，其硬件結構和并行編程模式的復雜性使得應用性能的提升面臨一定的挑戰(zhàn)。在壓縮算法中，普遍存在著壓縮速率與存儲空間使用的矛盾、數據局部性差等特性，要想獲得有效的性能提升，必須針對特定的多核異構處理器進行深度的算法重構與優(yōu)化。

本文的主要工作是將LZMA壓縮算法移植至神威太湖之光國產異構眾核系統(tǒng)中，針對異構眾核處理器的特點對算法進行了并行化重構與優(yōu)化。使用Athread接口對LZMA算法進行多線程分塊并行，設計基于DMA的雙緩沖模式，實現(xiàn)計算通信的重疊。進一步優(yōu)化中，對LDM地址空間進行細粒度的管理和布局優(yōu)化，合理設置緩沖區(qū)大小，獲得最佳的計算通信重疊效果。測試結果表明，在Silesia語料庫基準測試集中，并行壓縮算法最大獲得了4.1倍的加速比。在大文件壓縮測試中，并行壓縮算法最大獲得了5.3倍的加速比。與主流CPU串行算法相比，并行LZMA算法在申威異構眾核處理器上加速效果明顯，大幅降低了算法執(zhí)行時間，具有較好的性能優(yōu)勢。