甘新標(biāo) 譚 雯 劉 杰

(國(guó)防科技大學(xué)計(jì)算機(jī)學(xué)院 長(zhǎng)沙 430017)

(xinbiaogan@nudt.edu.cn)

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

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

本文的主要貢獻(xiàn)有2個(gè)方面:

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

2 Graph500

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

2.1 基本流程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)與性能分析

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

4.1 天河E級(jí)驗(yàn)證系統(tǒng)

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

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

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

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

4.2 實(shí)驗(yàn)配置

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

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

Table 1 Configuration for Testing Graph500

4.3 Bi-CSR存儲(chǔ)空間分析與性能開銷驗(yàn)證

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

理論上，每個(gè)非零元減少的存儲(chǔ)空間為

(2)

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

(3)

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

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

(4)

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

Δrow=Δnon_z×φrow.

(5)

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

Δcolumns=Δnon_z×φcolumns.

(6)

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

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

(7)

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

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

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

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

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

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

4.4 Graph500性能測(cè)試與分析

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

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

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

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

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

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

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

5 總 結(jié)

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

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