基于雙向位圖的CSR大規(guī)模圖存儲優(yōu)化

甘新標 譚 雯 劉 杰

(國防科技大學(xué)計算機學(xué)院 長沙 430017)

(xinbiaogan@nudt.edu.cn)

大數(shù)據(jù)時代，超級計算機系統(tǒng)結(jié)構(gòu)面臨著巨大的機遇和全新的挑戰(zhàn).圖搜索處理對計算機系統(tǒng)存儲和帶寬要求甚高，傳統(tǒng)的超級計算機系統(tǒng)處理大規(guī)模圖數(shù)據(jù)的效率低下.Graph500作為數(shù)據(jù)密集型計算機系統(tǒng)的評測基準，能夠準確反映E級計算機系統(tǒng)的大數(shù)據(jù)處理能力和指導(dǎo)E級計算機系統(tǒng)設(shè)計.

Graph500以每秒遍歷的邊數(shù)(traversed edges per second， TEPS)為性能指標來衡量超級計算機處理數(shù)據(jù)密集型應(yīng)用的能力.Graph500測試性能主要受限于圖測試規(guī)模和訪存帶寬，尤其是內(nèi)存空間大小直接決定了圖的測試規(guī)模.因此，本文提出了基于雙向位圖的大規(guī)模圖數(shù)據(jù)壓縮存儲方法(bidirectional-bitmap based compressed sparse row， Bi-CSR)以增加Graph500圖測試規(guī)模，并提升Graph500圖測試性能.

本文的主要貢獻有2個方面:

1) 提出了基于雙向位圖的稀疏矩陣壓縮存儲方法Bi-CSR，大幅減少了大規(guī)模圖存儲空間.

2) 將Bi-CSR應(yīng)用于天河E級驗證的Graph500測試，達到了良好的測試性能.

1 相關(guān)工作

很多現(xiàn)實問題可以抽象為圖形結(jié)構(gòu)，因此，圖形理論在眾多學(xué)科中應(yīng)用廣泛[1-3].從現(xiàn)實問題中抽象出來的圖形結(jié)構(gòu)通常具有2個特點：小世界性(small-world)[4]和無尺度性(scale-free)[5].

圖遍歷是大數(shù)據(jù)時代背景下的一種典型的數(shù)據(jù)密集型應(yīng)用，Graph500測試基準是典型的數(shù)據(jù)密集型程序.其核心搜索程序能夠適用于數(shù)據(jù)密集型應(yīng)用，能夠解決真實世界中的實際搜索問題，測試數(shù)據(jù)集能夠反映真實數(shù)據(jù)集的普遍特征，并且Graph500具有較差的時間和空間局部性，因此，Graph500具有一般大數(shù)據(jù)問題的主要特征.近年來，面向Graph500核心算法BFS的優(yōu)化遍歷取得了一系列重要的進展.

Bader等人[6]在Cray MTA-2多結(jié)點上實現(xiàn)了多線程的并行BFS算法，利用硬件多線程技術(shù)來隱藏訪存延遲，取得了很好的性能提升；Agarwal等人[7]提出利用位圖的數(shù)據(jù)結(jié)構(gòu)來表示算法中的visit結(jié)構(gòu)，增加了visit的局部性，減少了訪存的次數(shù)；Beamer等人[8]開創(chuàng)性地提出了一種Top-down與Bottom-up相結(jié)合的混合算法，所實現(xiàn)的混合算法能夠有效地減少搜索過程中遍歷的邊數(shù)，減小了訪存開銷，極大地提高了程序的性能；Ueno等人[9]面向極大規(guī)模并行與分布式機器提出了一種高效的BFS算法，并應(yīng)用于“京”超級計算機系統(tǒng)，達到了的良好測試性能；清華大學(xué)林恒等人[10-11]面向“神威太湖之光”實現(xiàn)了一種可擴展的BFS算法，實現(xiàn)了模塊流水映射、無競爭的數(shù)據(jù)混洗、基于組消息的批處理等關(guān)鍵技術(shù)，在神威太湖之光超級計算機全系統(tǒng)上獲得了23755.7GTEPS的測試性能[11]，上述優(yōu)化技術(shù)和方法本質(zhì)上都屬于加速圖遍歷來提升Graph500測試性能.圖遍歷速度是Graph500測試性能的重要影響因素，工程實踐表明：Graph500測試性能直接受限于圖測試規(guī)模.分析Graph500榜單可知，測試圖規(guī)模越大，Graph500性能越高.內(nèi)存空間大小直接決定了Graph500圖的測試規(guī)模，Graph500的 Kronecke生成器生成的圖形通常用鄰接矩陣表示，由于頂點的平均度數(shù)較低，其鄰接矩陣為稀疏矩陣，因此，圖形的鄰接矩陣存儲格式直接影響了Graph500圖測試規(guī)模.

典型的稀疏矩陣存儲格式有COO(coordinate)，DIA(diagonal)[12]，CSR(compressed sparse row)， CSB(compressed sparse block)，ELL(ELLPACK)和HYB(hybrid ELL+COO)等[13]，上述壓縮格式在天河驗證系統(tǒng)512個結(jié)點上的最大圖測試規(guī)模及性能如圖1所示，縱軸采取GTEPS為性能指標.

Fig. 1 Various format testing on available max scale with GTEPS comparison圖1 不同格式的最大測試圖規(guī)模及性能比較

由圖1可知，CSR格式在天河驗證系統(tǒng)上的最大圖測試規(guī)模為scalemax=36，穩(wěn)定測試性能為1310GTEPS.各數(shù)據(jù)壓縮方法除了壓縮效率和最大圖測試規(guī)模及性能的不同，各種數(shù)據(jù)壓縮方法操作性、靈活性、可擴展性以及適用領(lǐng)域方面也存在明顯的差異，其中，DIA和ELL格式在進行稀疏矩陣矢量乘積時效率最高，它們是應(yīng)用迭代法求解稀疏線性系統(tǒng)最快的格式[12]；CSB的優(yōu)勢是易于向量并行；ELL的優(yōu)點是快速，COO的特點是靈活，二者結(jié)合后的HYB格式是一種優(yōu)良的稀疏矩陣表示[13-14]；CSR相比COO，HYB，CSB，DIA，ELL，更加靈活，易于操作[13]；因此，Graph500參考實現(xiàn)中采用了CSR存儲Kronecker生成圖.CSR可以采用數(shù)組或位圖2種數(shù)據(jù)結(jié)構(gòu)來完成圖壓縮存儲，基于數(shù)組結(jié)構(gòu)的CSR圖存儲與基于單向位圖結(jié)構(gòu)的CSR圖存儲空間利用率十分有限[9-11]，為此，本文提出了基于雙向位圖的CSR大規(guī)模圖存儲優(yōu)化方法進一步提高Graph500圖壓縮存儲效率，最大化Graph500圖測試規(guī)模和提升Graph500測試性能.

Fig. 2 Presentation with adjacency matrix storage for graph圖2 圖的鄰接矩陣表示

2 Graph500

Graph500以每秒遍歷邊數(shù)TEPS為性能(per-formance)指標來衡量超級計算機處理數(shù)據(jù)密集型應(yīng)用的能力.TEPS要由圖的規(guī)模和圖形遍歷的時間共同決定，尤其是內(nèi)存空間大小直接決定了圖的測試規(guī)模.

2.1 基本流程

Graph500基本流程包括圖生成、圖構(gòu)造與存儲、圖遍歷以及圖驗證4個主要步驟[15-16]，Graph500圖生成采用了Kronecker生成器，生成的圖滿足小世界性與無尺度性[15].Graph 500圖形生成器有2個輸入?yún)?shù)，分別是圖形規(guī)模scale和邊因子edgefactor.

假定scale=n，edgefactor=m，則生成的圖具有2n點和m×2n條無向邊[15].

Graph500中僅包含了2個計時模塊：圖存儲變換和圖遍歷，并且圖遍歷占據(jù)其中絕大部分時間，假定Graph500的搜索時間為t，則對于scale=n，edgefactor=m的圖，Pteps為性能指標，Pteps=m×2nt.

圖存儲將生成的圖信息轉(zhuǎn)換為包含頂點、邊以及聯(lián)系的元組信息列表，通常以鄰接矩陣的形式高效存儲.Pteps由圖規(guī)模和搜索時間共同決定，并且圖的規(guī)模對Pteps的影響尤為關(guān)鍵，圖結(jié)構(gòu)的存儲和表示模式是影響Graph500圖測試規(guī)模的重要因素.

2.2 圖結(jié)構(gòu)的存儲與表示

圖G(V,E) 包含頂點集合V和邊集合E.通常對圖形的頂點進行編號，使用vi表示圖中編號為i的頂點，使用頂點對(vi,vj)表示頂點vi到頂點vj的邊.對于無向圖的每條邊，可以看作2條有向邊.

Graph500生成圖形通常采用鄰接矩陣A表示，其中的每一行Ai為鄰接表，圖的鄰接矩陣表示如圖2所示.

鄰接矩陣中第i行、第j列的元素Aij表示邊(vi,vj).對于無權(quán)圖，僅需要說明邊是否存在，通常使用1 表示存在這樣的邊，0 表示不存在這樣的邊.

大部分從現(xiàn)實問題抽象出來的圖，如Kronecker圖生成器生成的圖，頂點的平均度數(shù)遠小于頂點總數(shù)，并且符合6度分離原則和小世界效應(yīng)[4-5]，其鄰接矩陣通常為稀疏矩陣[12,18-20]，因此，Graph500中采用了基于CSR的稀疏矩陣存儲方法，CSR包含2個數(shù)組：columns和rowstarts.數(shù)組columns存儲按行壓縮的列標號，數(shù)組rowstarts存儲對應(yīng)行在columns中的索引位置，如圖3(a)所示.

Fig. 3 Structureof CSR storage for graph圖3 圖的CSR存儲結(jié)構(gòu)

如圖3(b)所示，columns中的標號為鄰接矩陣A對應(yīng)非零元素的列標號，第1個數(shù)字4表示第1個非零元的列標號為4，第2個數(shù)字5表示第2個非零元的列標號為5，第3個數(shù)字3表示第3個非零元的列標號為3，第4個數(shù)字1表示第4個非零元的列標號為1.rowstarts中的索引位置對應(yīng)A中非零元的行標號相對偏移，即對應(yīng)行中非零元的個數(shù)，如：第2個數(shù)字2和第1個數(shù)字0表示A中第0行中非零元的個數(shù)為2-0=2，第3個數(shù)字2和第2個數(shù)字2表示A中第1行中非零元的個數(shù)為2-2=0，第4個數(shù)字2和第3個數(shù)字2表示A中第2行中非零元的個數(shù)為2-2=0.

Graph500生成無向圖的鄰接矩陣表示總是對稱的，采用CSR圖數(shù)據(jù)存儲.CSR作為通用的稀疏矩陣存儲方法，具有存儲模式靈活、易于操作等諸多優(yōu)勢， 但是，CSR的大規(guī)模圖存儲效率與天河E級驗證系統(tǒng)的小內(nèi)存體系結(jié)構(gòu)特征并不能完美適配，這是因為Graph500的測試性能主要受限于訪存帶寬和內(nèi)存規(guī)模，當系統(tǒng)內(nèi)存超過閾值后(即輸入圖規(guī)模達到一定規(guī)模)，訪存帶寬將激變成為性能瓶頸，基于天河E級驗證系統(tǒng)的規(guī)模和配置，訪存帶寬尚未成為性能瓶頸，天河E級驗證系統(tǒng)的Graph500測試性能主要受限于內(nèi)存大小.面向天河E級驗證系統(tǒng)的Graph500優(yōu)化設(shè)計應(yīng)當充分發(fā)揮驗證系統(tǒng)優(yōu)勢,最小化天河E級驗證系統(tǒng)小內(nèi)存的局限性，設(shè)計與驗證系統(tǒng)的規(guī)模與存儲層次相適應(yīng)的圖數(shù)據(jù)壓縮方法，準確度量天河E級驗證系統(tǒng)的大數(shù)據(jù)處理能力，因此，面向天河E級驗證系統(tǒng)提出了一種基于雙向位圖的稀疏矩陣壓縮大規(guī)模圖存儲方法Bi-CSR，以最大化Graph500圖測試規(guī)模和提升Graph500測試性能.

3 基于雙向位圖的稀疏矩陣壓縮存儲方法

針對天河E級驗證系統(tǒng)小內(nèi)存的特征，提出了與天河E級驗證系統(tǒng)的小內(nèi)存匹配的基于雙向位圖的大規(guī)模圖數(shù)據(jù)壓縮存儲方法Bi-CSR.Bi-CSR在CSR存儲結(jié)構(gòu)的基礎(chǔ)上僅保留存儲一個或者多個頂點或邊的起始位置來壓縮CSR的數(shù)據(jù)結(jié)構(gòu)，并且在行列2個方向分別引入位圖(bitmap)來輔助識別頂點和邊信息，其中行位圖中每一位存儲一個頂點信息，列位圖中每一位存儲連續(xù)列編號信息.

3.1 基于行方向位圖的稀疏矩陣壓縮

基于行方向位圖的稀疏矩陣壓縮主要目的是減少大規(guī)模圖存儲空間，擴大Graph500圖測試規(guī)模和減少訪存次數(shù).基于行方向位圖的CSR存儲通過引入行方向位圖數(shù)組row_bitmap，并且，將CSR存儲結(jié)構(gòu)中的數(shù)組rowstarts采用改進的行數(shù)組CSR_rowstarts′和位圖數(shù)組row_bitmap來表示，如圖4(b)所示.將數(shù)組rowstarts中零元行標號索引采用1 b來表示數(shù)組rowstarts中使用1個整型(32 b)來表示的索引信息，最大限度壓縮了數(shù)據(jù)存儲空間.位圖數(shù)組row_bitmap中的每一位對應(yīng)所在的行是否有非零元.圖規(guī)模越大，圖的稀疏特征表現(xiàn)越明顯，越多的采用整型(32 b)表示的索引信息可以使用1 b來輔助標注，最大限度節(jié)約了圖數(shù)據(jù)的存儲空間.

Fig. 4 Structure on Bi-CSR storage for graph圖4 Bi-CSR壓縮存儲結(jié)構(gòu)

3.2 基于列方向位圖的稀疏矩陣壓縮

基于列方向位圖的稀疏矩陣壓縮主要目的包括進一步減少大規(guī)模圖存儲空間，最大限度擴大Graph500圖測試規(guī)模和減少訪存次數(shù)，以及為面向天河E級系統(tǒng)的可變寬度向量化開辟優(yōu)化空間.

基于列方向位圖的CSR存儲通過引入列方向位圖數(shù)組columns_bitmap，并且，將CSR存儲結(jié)構(gòu)中的數(shù)組columns采用改進的列數(shù)組CSR_columns′和位圖數(shù)組columns_bitmap來表示，如圖4(c)所示.為了更加清晰地描述數(shù)組columns_bitmap中的含義，作定義：

定義1.列連續(xù)片段.列方向上連續(xù)出現(xiàn)非零元，連續(xù)片段的長度len≥2.

定義2.列非連續(xù)片段.列方向上未連續(xù)出現(xiàn)非零元，列非連續(xù)片段的長度len=1.

定義3.緊前位(closely front bit， CFB).位圖數(shù)組與當前位緊鄰的前一位，記為BCF.

定義4.緊前缺位(non-closely front bit， non- CFB).位圖數(shù)組中的首位沒有緊前位，即為緊前缺位，記為non_BCF.

columns_bitmap中的每一位對應(yīng)所在的列編號是否為連續(xù)列編號片段的起始列編號，準確含義：

數(shù)組columns中的每一位對應(yīng)列連續(xù)片段fragment的起始列編號column_label，或是列連續(xù)片段的長度值len≥2，或是列非連續(xù)片段non_fragment的列編號column_label，具體含義應(yīng)結(jié)合數(shù)組columns_bitmap中對應(yīng)位標識來判定；columns_bitmap中的每一位對應(yīng)數(shù)組CSR_columns′中相同偏移的元素值是否為連續(xù)列編號片段的起始列編號column_label，1表示CSR_columns′中相同偏移的元素值為列連續(xù)片段的列編號，0表示為非連續(xù)片段non_fragment的列編號或是連續(xù)片段長度的標識.若0的緊前缺位non_BCF是0則表示CSR_columns′中相同偏移的元素值為非連續(xù)片段的列編號column_label，若0的緊前位BCF是1則表示columns′中相同偏移的元素值為連續(xù)片段的長度值，若0的緊前位BCF是0，則表示columns′中相同偏移的元素值為非連續(xù)片段non_fragment，列編號column_label.例如：由于緊前缺位non_BCF，columns_bitmap第1個數(shù)字0，表示對應(yīng)columns′中第1個數(shù)字4為第1個非零元的列編號；由于緊前位BCF為0，第2個數(shù)字0表示對應(yīng)CSR_columns′中第2個數(shù)字5為第2個非零元的列編號；第4個數(shù)字1表示連續(xù)片段的起始列標號為CSR_columns′中第4個數(shù)字1，即第4個非零元的列編號為1；由于CFB第4個數(shù)字是1，第5個數(shù)字0表示連續(xù)片段的長度，其長度值為CSR_columns′中第5個數(shù)字2.

4 實驗與性能分析

為了驗證系統(tǒng)的大規(guī)模圖存儲優(yōu)化方法Bi-CSR，將Bi-CSR應(yīng)用于天河E級驗證系統(tǒng)進行Graph500工程測試.

4.1 天河E級驗證系統(tǒng)

天河E級驗證系統(tǒng)主要包括計算處理分系統(tǒng)、高速互連分系統(tǒng)、并行存儲分系統(tǒng)、服務(wù)處理分系統(tǒng)、監(jiān)控診斷分系統(tǒng)和基礎(chǔ)架構(gòu)分系統(tǒng)等，如圖5所示.面向天河E級驗證系統(tǒng)的Graph500重點關(guān)注其中的計算處理分系統(tǒng)和并行存儲分系統(tǒng).

Fig. 5 Architecture for Tianhe pre-exascale system圖5 天河E級驗證系統(tǒng)結(jié)構(gòu)圖

計算處理分系統(tǒng)由512個計算結(jié)點構(gòu)成，是系統(tǒng)主機的計算核心.每個計算結(jié)點包括3顆Matrix-2000+微處理器，運行頻率為2.0 GHz，峰值性能為6TFLOPS.

并行存儲分系統(tǒng)采用超高并發(fā)度的多層面并行存儲架構(gòu)；全局共享存儲層包含20個IO存儲結(jié)點，每個存儲結(jié)點集成64 TB磁盤陣列，提供共享存儲總?cè)萘?.28 PB.配置2個IO管理結(jié)點和1套8 TB全閃存陣列存儲管理元數(shù)據(jù)，提高元數(shù)據(jù)IO吞吐率.E級驗證系統(tǒng)并行存儲分系統(tǒng)的具體配置包括：32個IO加速結(jié)點、20個IO存儲結(jié)點、2個IO管理結(jié)點和1套全閃存陣列，總存儲容量1.28 PB.

4.2 實驗配置

為了驗證天河E級原型系統(tǒng)的數(shù)據(jù)密集型應(yīng)用處理能力，本文將Bi-CSR應(yīng)用于Graph500測試中，形成了面向天河E級驗證系統(tǒng)的Graph500測試版本THE-G500(Tianhe exascale Graph500).

為了驗證Bi-CSR的有效性，我們在天河E級驗證系統(tǒng)上分別采用標準參考版本Graph500和面向天河E級驗證系統(tǒng)的THE-G500版本進行了詳細的測試與比較分析，實驗平臺為部署于天津超算的天河E級原型系統(tǒng)，與Graph500測試密切面相關(guān)的系統(tǒng)參數(shù)如表1所示：

Table 1 Configuration for Testing Graph500

4.3 Bi-CSR存儲空間分析與性能開銷驗證

Bi-CSR圖數(shù)據(jù)進一步壓縮的基本思想為大規(guī)模圖矩陣的CSR壓縮存儲中每行或每列中出現(xiàn)多個非零元，然后利用行列雙向位圖協(xié)作行列標號和位移的計算，即將32 b標識的列標號和位移改進為1 b的位圖索引.

理論上，每個非零元減少的存儲空間為

(2)

由于Graph500的Kronecker圖生成器生成的圖符合小世界性和6度分離理論，應(yīng)用到Graph500圖的CSR存儲結(jié)構(gòu)中，可以推斷出圖的稀疏矩陣中每行出現(xiàn)至少2個非零元的概率為

(3)

其中，d為CSR圖結(jié)構(gòu)中每個頂點的平均度數(shù).

由于裝備天河E級驗證系統(tǒng)的眾核處理器支持可變寬度向量并行，因此，基于列方向位圖的CSR壓縮由出現(xiàn)非零元片段的概率可以松弛為每列出現(xiàn)多個非零元的概率：

(4)

因此，僅應(yīng)用基于行方向位圖的Bi-CSR的圖數(shù)據(jù)存儲空間減少量：

Δrow=Δnon_z×φrow.

(5)

僅應(yīng)用基于列方向位圖的Bi-CSR的圖數(shù)據(jù)存儲空間減少量：

Δcolumns=Δnon_z×φcolumns.

(6)

綜上所述，基于行列2個方向位圖的Bi-CSR的圖數(shù)據(jù)存儲空間減少量為

Δspace=1-(1-Δrow)×(1-Δcolumns).

(7)

實際應(yīng)用的Bi-CSR圖數(shù)據(jù)壓縮中，由于Graph500中頂點平均度數(shù)d=16，測試中不同圖規(guī)模以16×32的拓撲結(jié)構(gòu)分布于E級驗證系統(tǒng)上，每個結(jié)點存儲空間減少量如表2所示:

Table 2 Space Save Comparison Between Bi-CSR and CSR表2 基于Bi-CSR的圖數(shù)據(jù)空間節(jié)約率

由表2可知，THE-G500在天河E級驗證系統(tǒng)的測試過程中，應(yīng)用Bi-CSR方法后大規(guī)模圖數(shù)據(jù)存儲空間的節(jié)約率與式(5)～(7)表征的理論存儲空間節(jié)約率基本吻合，在scale=34時，大規(guī)模圖存儲空間節(jié)約率超過了60%，當scale=37時的空間節(jié)約效率達到最大值，接近70%.

Bi-CSR較CSR方法，存儲效率提升明顯，但是，Bi-CSR需要增加行方向位圖數(shù)組row_bitmap和列方向位圖數(shù)組columns_bitmap，增加了額外的存儲空間來獲得更高的壓縮比；并且Bi-CSR較CSR計算復(fù)雜度更高，需要引入緊前位BCF、緊前缺位non_BCF對列非零元片段是否連續(xù)進行判定與索引，增加了3%～5%的時間開銷，Bi-CSR性能開銷測試驗證如圖6所示：

Fig. 6 GTEPS comparison between CSR and Bi-CSR with the same testing scale圖6 相同圖測試規(guī)模下的CSR與Bi-CSR性能比較

由圖6可知，相同輸入圖測試規(guī)模下，CSR的測試性能是略優(yōu)于Bi-CSR的，實驗數(shù)據(jù)表明：相同圖測試規(guī)模下，Bi-CSR約有3%～5%的性能損失，但隨著圖測試規(guī)模的增大，性能損失逐漸縮小.Bi-CSR具有更高的圖稀疏矩陣的存儲壓縮比，相同內(nèi)存下能夠測試的圖規(guī)模也更大，因此能夠顯著提升Graph500測試性能.因此，Bi-CSR引入了行列位圖數(shù)組和更高的計算復(fù)雜度，但是獲得了更高的圖存儲壓縮比，相同內(nèi)存規(guī)模下能夠完成更大的圖規(guī)模測試，Graph500測試性能更優(yōu).

4.4 Graph500性能測試與分析

裝備天河E級驗證系統(tǒng)的MT-2000+為通用眾核處理器.不同稀疏圖壓縮方法的性能測試比較如圖1所示，本節(jié)的重點是關(guān)注CSR與Bi-CSR的性能比較分析，因此，對不同圖規(guī)模和運行配置下對基于CSR的Graph500和基于Bi-CSR的THE-G500性能進行了詳細的測試分析與比較，如圖7所示.

Fig. 7 TEPS comparison on different running threadscores per node圖7 不同線程并行時程序性能比較

由圖7可知，在天河E級驗證系統(tǒng)上，參考版本Graph500程序和天河E級驗證系統(tǒng)版本的THE-G500具備在實際測試過程中(scale>15)每結(jié)點開啟16線程并行時，性能整體表現(xiàn)最佳，并且圖的測試規(guī)模越大THE-G500性能加速效果越明顯.當測試規(guī)模為scale=15，開啟2個線程并行時，THE-G500性能提升最大，約19.35倍，開啟32個線程并行時，THE-G500性能提升最小，約5.49倍，該規(guī)模下THE-G500平均性能提升約12.9倍；當圖的測試規(guī)模為scale=20，僅開啟1個線程，THE-G500性能提升最大，約26.79倍，開啟32個線程并行時，THE-G500性能提升最小，約13.33倍，該規(guī)模下THE-G500平均性能提升約18.31倍；當圖的測試規(guī)模為scale=23，開啟2個線程并行時，THE-G500性能提升最大，約37.88倍，開啟32個線程并行時，THE-G500性能提升最小，約13.98倍，這是因為本地存儲單元有限，線程增加了，可利用局部存儲空間少了，數(shù)據(jù)遷移至更遠的外部存儲空間，該規(guī)模下THE-G500平均性能提升約23.99倍.

應(yīng)用Bi-CSR大規(guī)模圖空間壓縮方法、面向MT-2000+天河E級驗證系統(tǒng)版本的THE-G500全系統(tǒng)性能測試如圖8所示，圖8中表現(xiàn)的性能均為在對應(yīng)結(jié)點規(guī)模下能夠穩(wěn)定測試的最大圖規(guī)模scale值.

Fig. 8 Performance for THE-G500 testing on tianhe pre-exascale system圖8 面向天河E級驗證系統(tǒng)的THE-G500性能測試

由圖8可知，面向E級驗證系統(tǒng)版本的THE-G500性能較官方的參考Graph500測試程序性能提升顯著，單結(jié)點最小加速比接近20倍加速比，全系統(tǒng)最大加速超過100倍，受限于系統(tǒng)內(nèi)存，當圖規(guī)模測試到scale=36，參考版本Graph500不能穩(wěn)定地完成測試任務(wù)，最可能原因是內(nèi)存壓力大，對網(wǎng)絡(luò)以及系統(tǒng)穩(wěn)定性要求高.由于Bi-CSR能夠節(jié)約近70%的存儲空間，THE-G500在全系統(tǒng)下可以將圖的測試規(guī)模成功進一步擴大到scale=37，穩(wěn)定測試性能為2.131E+12TEPS，當圖規(guī)模繼續(xù)增大時，THE-G500也無法完成穩(wěn)定測試，最重要的原因是，壓縮優(yōu)化后的圖存儲空間仍然超過了E級驗證系統(tǒng)最大存儲空間.綜上所述，THE-G500較Graph500能夠應(yīng)用更大規(guī)模的圖測試，并且，在相同可用存儲空間下，THE-G500較Graph500的最大性能加速比已超過100倍，THE-G500性能加速比隨著結(jié)點規(guī)模的增加具有更好的擴展性.需要說明的是，全系統(tǒng)THE-G500測試性能包含了可變寬度向量優(yōu)化帶來的性能提升，由于可變寬度向量優(yōu)化是基于列方向位圖的稀疏矩陣壓縮方法的延伸，并且，可變寬度向量優(yōu)化加速BFS遍歷并不是本文關(guān)注的重點.因此，將可變寬度向量優(yōu)化直接歸入了基于列方向位圖的稀疏矩陣壓縮帶來的性能提升.

面向天河E級驗證系統(tǒng),應(yīng)用Bi-CSR方法設(shè)計實現(xiàn)了面向目標系統(tǒng)的Graph500測試版本THE-G500，實驗結(jié)果表明:THE-G500能夠充分發(fā)揮天河E級驗證系統(tǒng)的數(shù)據(jù)密集型應(yīng)用處理潛力，同時驗證了面向天河E級驗證系統(tǒng)的大規(guī)模圖存儲優(yōu)化方法Bi-CSR的高效性.

5 總 結(jié)

E級驗證系統(tǒng)將面向大科學(xué)工程計算，兼顧海量信息大數(shù)據(jù)智能處理平臺，大規(guī)模圖處理是評測超E級系統(tǒng)處理數(shù)據(jù)密集型應(yīng)用能力的重要手段.為此， 針對天河E級驗證系統(tǒng)小內(nèi)存，基于CSR圖結(jié)構(gòu)引入行列雙向位圖進一步壓縮稀疏矩陣存儲空間，提出了大規(guī)模圖數(shù)據(jù)壓縮存儲方法Bi-CSR，該方法將大幅減少稀疏矩陣存儲空間，最大化Graph500圖測試規(guī)模和提升Graph500測試性能，在天河E級驗證系統(tǒng)512結(jié)點系統(tǒng)上，全系統(tǒng)穩(wěn)定測試性能TEPS為2.131×1012， 面向天河E級驗證系統(tǒng)時，位列Graph500 排名第9，同等系統(tǒng)規(guī)模下THE-G500性能表現(xiàn)優(yōu)異.

貢獻聲明：作者甘新標提出了基于雙向位圖的大規(guī)模圖存儲壓縮方法，并完成算法設(shè)計；作者譚雯參與算法編碼實現(xiàn)、實驗測試和論文修改工作；作者劉杰參與實驗設(shè)計與討論，制定實驗內(nèi)容，協(xié)調(diào)實驗資源.