李秉政，黃高陽(yáng)，許瑾晨

1.數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室，鄭州 450000

2.江南計(jì)算技術(shù)研究所，江蘇無(wú)錫 214125

1 引言

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

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

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

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

Fig.1 General architecture of SW26010 processor圖1 申威26010處理器結(jié)構(gòu)圖

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

Fig.2 Memory hierarchy of computing processing element圖2 從核CPE存儲(chǔ)層次結(jié)構(gòu)圖

本文主要研究是設(shè)計(jì)一個(gè)面向國(guó)產(chǎn)申威26010異構(gòu)眾核處理器的LZMA并行算法，并結(jié)合異構(gòu)眾核處理器的特點(diǎn)，對(duì)算法進(jìn)行重構(gòu)與性能優(yōu)化。

2 LZMA算法分析

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

2.1 LZMA算法流程

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

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

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

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

2.2 空間需求分析

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

基于Hash查表的字符串匹配函數(shù)中，由于字典空間較大，其Hash散列表hash_buf預(yù)留的較大的散列空間，遠(yuǎn)超從核64 KB的LDM空間，需要進(jìn)行優(yōu)化，壓縮局部空間的使用。可以在壓縮率損失允許的范圍內(nèi)盡可能減小字典搜索的范圍，從而減小Hash查表函數(shù)散列空間的大小。

Table 1 Local variable size of hotspot function表1 熱點(diǎn)函數(shù)局部變量空間大小

2.3 訪存特性分析

LZMA算法中，使用了Hash鏈表的數(shù)據(jù)結(jié)構(gòu)來(lái)快速查找匹配字符。由于其搜索緩存比較大，其Hash查表空間范圍隨之增長(zhǎng)，在幾百KB到數(shù)十MB范圍內(nèi)隨機(jī)訪存。同時(shí)，LZ77算法基于滑動(dòng)窗口的流式壓縮中，因?yàn)槲淳幋a的數(shù)據(jù)不斷輸入，已編碼的數(shù)據(jù)在達(dá)到搜索緩存空間上限后便丟棄不用，其數(shù)據(jù)局部性較差。

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

2.4 熱點(diǎn)函數(shù)分析

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

算法1基于滑動(dòng)窗口的LZ77壓縮算法

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

3 LZMA異構(gòu)眾核并行算法

3.1 任務(wù)劃分

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

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

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

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

3.2 DMA訪存雙緩沖設(shè)計(jì)

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

本章主要對(duì)LZMA異構(gòu)眾核并行算法的壓縮率和壓縮時(shí)間等性能指標(biāo)進(jìn)行測(cè)試和分析。測(cè)試的基準(zhǔn)性能為串行LZMA算法在主核上運(yùn)行的壓縮率和壓縮用時(shí)。測(cè)試的計(jì)時(shí)方法為使用Athread計(jì)時(shí)接口統(tǒng)計(jì)算法運(yùn)行所經(jīng)過(guò)的節(jié)拍數(shù)，并由此計(jì)算出運(yùn)算時(shí)間。

4.1 基準(zhǔn)測(cè)試語(yǔ)料庫(kù)和測(cè)試平臺(tái)

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

Table 2 Silesia corpus test contents表2 Silesia語(yǔ)料庫(kù)測(cè)試用例

實(shí)驗(yàn)的平臺(tái)為神威太湖之光異構(gòu)眾核系統(tǒng)，其參數(shù)如表3所示[11]。實(shí)驗(yàn)中使用的壓縮算法基準(zhǔn)測(cè)試集為Silesia語(yǔ)料庫(kù)基準(zhǔn)測(cè)試集。同時(shí)，為了測(cè)試大數(shù)據(jù)量的壓縮性能，將Silesia語(yǔ)料庫(kù)測(cè)試集文件復(fù)制并打包，組成了GB級(jí)的數(shù)據(jù)進(jìn)行壓縮測(cè)試。

Table 3 Experiment environment表3 實(shí)驗(yàn)環(huán)境

4.2 從核性能測(cè)試結(jié)果

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

Fig.7 Test performance results of Silesia corpus圖7 Silesia語(yǔ)料庫(kù)測(cè)試性能結(jié)果

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

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

Table 5 Performance test comparison between Intel x86 and Sunway 26010表5 Intel x86與申威平臺(tái)性能測(cè)試對(duì)比

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

Table 4 Large-scale data compression test results表4 大規(guī)模數(shù)據(jù)壓縮測(cè)試結(jié)果

4.3 相關(guān)工作對(duì)比

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

5 結(jié)束語(yǔ)

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

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