神威·太湖之光上排列熵算法異構并行加速

周 倩，梁建國，傅 游

(山東科技大學 計算機科學與工程學院，山東 青島 266590)

0 引 言

PE[1]可以用相對簡單的形式描述難以量化的復雜系統。與常用的突變檢測方法如短時傅里葉變換[2]、奇異值分解[3]、小波分析[4]、希爾伯特變換[5]等相比，對突變信息的識別有較好的效果。目前，PE已被廣泛應用于包括設備故障診斷[6]、檢測信號異常[7]、腦電圖檢測[8]、識別生物基因序列[9]、測量氣候復雜性[10]和紋理圖像分析[11]等領域。

隨著應用問題的規模不斷擴展，時間序列數據的規模呈指數級增長，對PE計算的時效性要求也越來越高。傳統的PE算法應用于單機環境，難以滿足海量數據處理的需要，多種基于云平臺或超算平臺的并行PE算法被先后推出。Yang Peng等[12]結合云計算平臺和大數據處理技術，設計了時間序列數據的排列熵特征提取算法，驗證了并行排列熵算法的正確性。Cao Jian等[13]提出了一種基于云計算平臺MaxCompute的并行排列熵算法，但該方法僅適用于云計算環境。張浩等[14]使用MPI+OpenACC將PE算法移植到“神威·太湖之光”的異構眾核處理器SW26010上，并取得了一定的效果，但主從核間存在大量通信，且數據規模小，沒有考慮負載均衡的問題。因此，如何對PE算法進行優化以最大程度發揮SW26010性能是一個重要的問題。

本文針對神威·太湖之光特有的眾核體系結構，提出一種粗粒度和細粒度下的混合排列熵并行計算方法，在核組間通過MPI實現粗粒度的進程級并行，核組內部利用Athread實現細粒度的從核加速，不僅縮短PE算法的計算耗時，還有效解決其數據規模過大的問題。

1 背 景

1.1 PE算法的概述

PE算法是一種檢測震動信號突變的方法，可以描述為：給定一個標量時間序列X，有

X=[x(1),x(2),…,x(n)]

(1)

其中，n為數據點總數。PE算法流程為：輸入一維序列X，嵌入維數m和時間延遲τ，通過相空間重構，重構矩陣編碼，計算PE值來檢測突變信號。

1.1.1 相空間重構

先把標量時間序列X嵌入到m維空間中，重構向量Xi的值如式(2)所示

Xi=[x(i),x(i+τ),…,x(i+(m-1)τ)]

(2)

式中：m為嵌入維數，τ為延遲時間。則標量時間序列X的相空間矩陣Mat可由式(3)表示

(3)

其中，K=n-(m-1)τ。

1.1.2 相空間矩陣編碼

對于給定向量Xi,m個實數Xi升序重新排列： [x(i+(j1-1)τ)≤x(i+(j2-1)τ)≤…≤x(i+(jm-1)τ)]。 當等式出現時，如x(i+(jk1-1)t)=x(i+(j2-1)t)， 根據它們對應的j值確定值大小：若jk1

因此，任意向量Xi在相空間矩陣Mat中，都被唯一地映射到一系列符號S(i) 上

S(i)=(j1,j2,…,jm)

(4)

其中，i=1,2,…,K，K≤m!。S(i) 是m!個不同符號 (1,2,…,m) 的排列?？梢越y計時間序列X各種排列出現的次數。

1.1.3 PE計算

假設不同符號的概率分布是P1，P2，…，PK，K≤m!， 然后將時間序列X的PE定義為K個不同符號的香農熵

(5)

當Pj=1/m!， 則Hp(m) 在ln(m!) 時達到最大值。因此，PE值可以判別時間序列信號的隨機性。PE值越大，序列信號的隨機性越高。排列熵算法的過程如圖1所示。

圖1 排列熵算法過程

1.2 SW26010多核處理器

神威·太湖之光由10 240個SW26010異構多核處理器組成，每個處理器中有4個核組(CGs)，每個CG由一個管理處理單元(MPE)、一個計算處理單元(CPE)集群、一個DDR3內存控制器(MC)和一個協議處理單元(PPU)組成。每個CPE集群中有64個按8×8網格組織的CPE。SW26010處理器共有260個核，其架構如圖2所示。

圖2 SW26010處理器架構

根據2020年11月的TOP500[15]數據，“神威·太湖之光”以125 PFlop/s的理論峰值性能位列第4位，與排名前三的超級計算機的性能指標比較如表1。從表1可以看出，“神威·太湖之光”的HPL性能為93 Pflop/s，與Sierra接近；總內存容量與其它超級計算機系統接近；但HPCG僅為480.9 TFlop/s，這是由SW26010的低內存帶寬(136.51 GB/s)決定的，也導致每字節浮點數比高達22.42 Flops/byte[16]。以上數據說明，“神威·太湖之光”具有強大的計算能力，但內存帶寬相對較低，這對并行應用的移植和優化帶來困難和靈活性。

表1 TOP500排名前四的超級計算機系統簡要性能對比

1.3 神威Athread加速線程庫

Athread加速線程庫是針對SW26010所設計的主從加速編程模型，通過對核組內線程的控制與調度來提升多從核的加速性能。Athread庫包含主核上用于管理從核線程的庫和從核上支持數據傳輸和同步的庫。通過系統調用將從核初始化，此后從核交由Athread庫管理，通過庫接口將任務的入口函數和參數寫入LDM的指定位置，從核從LDM讀取任務入口和參數并開始執行。使用單函數多啟動的方式來利用從核，常見的從核調用形式如算法1所示。

算法1：在CPE上Athread框架

輸入：CPE需要執行的任務集T；劃分給每個CPE所需處理的任務TPEC=part(T,thread_id)

輸出：每個CPE的計算結果ResultCPE

(1)thread_id←ATHREAD-GET-ID；

(2)CPE接收任務GET(TPEC)；

(3)fori∈TPEC

DO(i)

endfor

(4)向MPE發送計算結果PUT(ResultCPE)；

(5)MPE調用CPE函數ATHREAD-APAWN；

(6)在等待期間穿插任務；

(7)MPE等待CPE任務結束ATHREAD-JOIN。

由算法1可見，所有從核啟動相同的函數，根據從核號從任務集中挑選出各自需要執行的部分，并通過主從核通信接口來進行相應的數據傳輸。在等待數據傳輸時，主核也可以執行其它任務。

2 PE算法并行設計與優化

本節基于SW26010處理器架構，在分析PE程序特征的基礎上，提出了PE移植和優化算法。具體工作分為兩個層次：在核組間，按文件數量劃分任務，采用對等模式，合理調度MPI進程，實現了多文件負載均衡；在核組內，使用Athread庫按塊劃分相空間重構矩陣，對其分量進行排序并記錄排序后的索引，使用雙緩沖技術減少數據在主從核之間傳輸的時間，通過重新組織傳輸數據減少了主從通信次數。采用本節所設計的MPI+athread并行優化方法，解決了PE程序中兩級負載不均衡的問題。

2.1 PE算法特征分析

2.1.1 數據規模大

本文所使用的數據集是由西安交通大學現代設計及轉子軸承系統教育部重點實驗室所發布的數據[17]，該數據集是以LDK UER204軸承為處理對象，以1 min為間隔，頻率為25.6 kHz，分別對3種工況下15個滾動軸承的全壽命周期進行采樣。將每次采樣獲取的32 768個震動信號數據存儲在一個獨立文件中，所有的滾動軸承全壽命周期采樣文件數量和達到9216個，總數據量達到3 T以上。

2.1.2 兩級負載不均衡

由于文本數量龐大，負載均衡是需要解決的一個難題。分析數據集可知，每個數據文件相互獨立且不存在數據依賴。

核組間采用對等模式構建MPI進程，每個進程獨立處理一個滾動軸承全壽命周期所有時刻的數據文件，進程與進程完全獨立，不存在通信與調度。但在數據集中不同工況下滾動軸承的全壽命周期各不相同，每個滾動軸承的震動信號數據文件數量差距巨大，最少的有42個，最多有2 538個，導致進程間負載極其不均衡，若不進行處理則會浪費大量計算資源。PE算法的熱點是針對相空間重構后的每個分量進行升序排序并計算得到的各分量索引，將熱點任務分配給從核執行。

在核組內部，每個csv文件中有32 768個振動信號數據，相空間重組矩陣規模為 [32768-(m-1)τ]×m。 由于SW26010處理器的一個核組中包含64個從核，無法將重構矩陣分量均勻地分配給每個從核，導致了從核計算任務不均勻。

因此在PE算法中存在兩級負載不均衡的問題。下面首先解決核組間負載不均衡問題。

2.2 基于MPI多文件負載均衡優化算法

為讀取3種工況15個軸承的數據文件，利用多個進程實現文件的并行讀取，且多個進程相互獨立地計算同一種工況下軸承的一個csv振動信號數據文件的熵值，使得進程輪詢讀取9216個數據文件，直至計算處理完。每個進程相互獨立，進程間不存在通信與調度，避免了進程間的通信耗時，實現了負載均衡。具體實現如算法2所示。

算法2：多文件負載均衡

輸入：9216個csv文件；進程數comm_sz；進程號rank

輸出：重構矩陣ch_ti_series_1D[]

(1) 遍歷15個滾動軸承文件數據

forfile_num←1 to 15 do

(2) 判斷當前數據文件屬于哪個工況環境

switch(file_num)

case1-5:work_condi←“35Hz12kN”

case6-10:work_condi←“37.5Hz11kN”

case11-15:work_condi←“40Hz10kN”

default:error

(3) 獲取每個進程在每種工況下分配到的csv文件數line←indir[l]/comm_sz;

(4) 計算每個進程所需處理的文件編號

file_num=(my_rank+1)+k*comm_sz;

(5) 每個進程獲取對應csv文件數data_input();

(6) 相空間重構

ch_ti_series_1D[]=re_organization()

(7)endfor

2.3 基于MPI+Athread的并行PE算法

在上述基于MPI的并行PE算法基礎上，引入神威Athread編程模型，在核組內部從核間進行數據并行，重構矩陣的相關計算由從核來實現，以充分發揮神威異構眾核的能力。主核主要負責讀取數據、初始化以及進程劃分任務、傳送數據、匯總索引概率來計算熵值；從核從主核獲取所需處理的重構矩陣分量數據后，每個CPE對重構矩陣分量進行升序排序，將所得序列索引傳送回主核。針對2.1.2節中所述的核組內負載不均衡的問題，先將重構矩陣按塊劃分，保證將任務量均勻的分配給每個從核，若不能均分，則由第一個從核處理余下的重構矩陣分量碎片。

算法3：矩陣重構分量排序

輸入：待排序數組S；嵌入維數m和重構分量標示d

輸出：整數索引_rank[]

(1) 從核獲取重構矩陣分量

athread_get(PE_MODE,

&ch_ti_series_1D[k*m],&a_slave[0],m*8,

&get_reply,0,0,0)

(2) 判斷數據是否正確傳輸完畢

while(get_reply!=1);

(3) 按升序排序重構矩陣分量

(4) 利用下標數組M得到重構分量索引

(5) 將索引rank[]傳送回主核

athread_put(PE_MODE,&res,

&_rank[k],8,&put_reply,0,0)

2.4 基于MPI+Athread的并行PE算法優化方法

2.3節提出的基于Athread加速線程庫的PE并行算法，由于數據規模大，通過分析程序熱點可知，主核將重構矩陣所需數據傳輸到從核是最耗時的部分，本小節從減少主從通信次數和采用雙緩沖方法兩個方面對CPE數據傳輸部分進行優化。

2.4.1 減少主從通信次數

PE算法核心主要涉及重構矩陣Mat的計算，且矩陣Mat各行之間不存在數據依賴關系，可以直接在原數據結構上進行并行化。圖3(a)是上述2.3節中采用基于塊劃分方法的數據分割圖，在主核中將一維線性序列進行相空間重構，在主從核間傳輸重構矩陣分量，從核獲取所需處理的重構矩陣分量后，再進行排序。由于重構矩陣規模大，主從核傳輸數據產生了很大的耗時。為了減少主從通信次數，提出了將構建重構矩陣分量的任務分散到從核的優化方案，如圖3(b)所示。根據PE算法的特點可知，重構矩陣具有一定的規律性，矩陣第i行僅需要一維震動信號序列的第i～i+m號元素。

圖3 PE算法athread數據劃分

由圖3(b)可見，主核不再將重構矩陣分量發送給從核，而是發送構建重構矩陣分量所需的一維震動信號序列，每個從核接收各自所需的序列后再重構成矩陣分量，進行后面的計算工作。這一方法將主核的任務分散至從核，發送的數據量大幅減少，提高了程序性能。

2.4.2 雙緩沖機制

在CPE并行區域中，雖然DMA固有特性可以大大降低內存訪問的開銷，但在PE程序的大規模數據情況下，主從核的內存訪問限制了并行效率。為了進一步提高并行效率，采用雙緩沖機制，充分發揮DMA固有的異步性能。在主從核傳輸數據的過程中，有多輪DMA操作，CPE需要使用雙內存空間來緩沖MPE和CPE的重構矩陣分量數據，在CPE傳輸所需數據的過程中進行計算操作，從核間的通信開銷小于計算開銷，從而實現了計算與訪存的重疊，眾核加速會達到理想的并行加速效果。

算法4：雙緩沖機制

輸入：重構矩陣分量ch_ti_series_1D[]；輪次d；

輸出：寫回標志write_back

(1)fork←0 to d-1 do

(2) 設置當前輪次標記index←mod(k,2)+1

(3) 讀入首批數據

put_reply(mod(k+1,2)+1)←1

(4) athread_get(PE_MODE,ch_ti_series_1D

[k*m/2],a_slave[0,index],m*8,get_reply,0,0,0)

(5) 修改當前輪次標記

index←mod((j-jmin),2)+1

(6) 設置下一輪次標記

next←mod((j-jmin)+1,2)+1

(7) 重構矩陣分量排序

(8) 讀入下一輪次所需數據

athread_get(PE_MODE,ch_ti_series_1D[k*m/2+1],a_slave[0,next],m*8,get_reply,0,0,0)

(9)endfor

(10) 等待最后一輪數據寫回

do while(write_back=put_reply(index))

3 實驗及結果分析

本節在“神威·太湖之光”上對第2節提出的優化方法進行實驗測試。首先給出嵌入維數m和時間延遲τ這兩個參數的選取規則。為了評估本文所提出方法的有效性，在單個節點上進行測試，并與串行版本進行比較，得到其運行時間和加速比，再將并行PE算法擴展至多個節點，并進行可擴展性分析，最后通過所得15個滾動軸承全壽命周期的熵值，進行分析。

3.1 關鍵參數確定

由排列熵的定義可知，嵌入維數m和時間延遲τ的取值會影響PE值的大小。相空間重構矩陣分量具有m！種序列，若m取值過大，導致索引序列是不重復的，每種序列僅出現一次，以至于PE值固定為同一個值，不能表達震動信號的突變，也就不具有實際意義。Band等[1]在提出排列熵的概念時就建議m取3～7，τ取1。綜合其它相關文獻[18]的研究可知，在突變信號檢測中，τ對熵值的影響較小，而m取6時得到的PE值能夠較好地反映滾動軸承振動信號的突變。因此，在實驗中取嵌入維數m=6，時間延遲τ=1。

單核組性能評估表2顯示了PE串行算法和單核組并行算法的性能比較，并行算法的計算性能遠高于串行算法。相比于主核，使用64個從核進行并行計算在理論上能夠產生64倍的加速。但實際上，加速比遠遠小于理論值，僅取得了11.86倍的加速，其原因是：

表2 單主核版本與單主從核版本的運行時間對比

(1)排列熵算法僅將重構矩陣排序進行從核加速，沒有考慮數據讀取與熵值計算，在處理大規模數據時，讀取數據的時間開銷也很大；

(2)在主進程劃分任務時，任務的切分需要時間；

(3)從核所需要的計算數據由主核獲取，需要時間進行通信，在帶寬一定的前提下，傳輸數據將損耗大量時間；

(4)由于CPE存儲空間有限，無法同時獲取大量數據，部分數據碎片需要直接訪問MPE主存來獲取，增加了訪存時間，無法達到理論加速比。

3.2 多核組性能評估

采用與單核組實現相同的方式，用MPI實現了基于多個SW26010處理器核組的并行程序。首先將多個數據文件均勻地劃分到每個SW26010處理器核組上，然后充分利用64個從核，采用加速線程庫Athread在處理器核組內并行處理，其核組內處理過程與圖3(b)的描述一致。

在基于粗粒度與細粒度的并行排列熵算法中，成倍增加進程數，得到其對應的測試數據，測試結果以單核組串行程序的性能指標為基準，性能對比結果見表3。

由表3數據分析可得，在128進程時，最大加速比達到了123.73倍。且本文設計的PE算法并行效率穩定，其原因是此算法并不存在MPI進程間的通信與調度，各個進程相互獨立。因此，隨著進程數的增加，不會產生過多的額外開銷，并行效率不會降低。

表3 PE算法眾核優化測試結果

在分析并行PE算法的強可擴展性時，將MPI進程數成倍擴大至128個，SW26010節點數擴展至32個，其實驗結果如圖4所示。

圖4 PE算法強可擴展性

由圖4可見，PE算法的執行時間隨著節點數的增加而減少，單核組執行時間為5951.4 s，當MPI進程數達到128時，執行時間為48.1 s，此時加速比最高達到了123.73倍。但是相比于單核組并行版本，PE并行程序的可擴展性并未達到理想的加速狀態，僅為理想狀態的96.7%。其主要原因在于，雖然進程間并未存在通信與調度，但創建并行域、進程任務切分、核組內數據傳輸依然花費了時間開銷。因此，在實際應用時，需要綜合考慮數據規模、嵌入維數和時間延遲的選取規則、平臺節點資源情況、合理設置核組數，避免資源的浪費或競爭。

3.3 PE算法分析

圖5是使用本文所設計的PE算法得到的1號和2號滾動軸承的全壽命周期PE值的折線統計圖。這兩個軸承的失效位置均為外圈，在正常的工作狀態下，排列熵值穩定在9.8附近，在經過損壞臨界點處，PE值急劇下降，最后降為8.7附近。

圖5 滾動軸承全壽命周期PE值折線

滾動軸承在正常狀態下的震動信號為隨機信號，信號無規則，PE值較為平穩；故障時信號中存在周期性的沖擊信號，具有一定的規律性，因此PE值呈現下降趨勢?？梢钥闯?，本文所設計的PE算法能夠很好的反映出滾動軸承的振動信號變化，適用于檢測各種領域振動信號的突變，具有很強的通用性。

4 結束語

本文在“神威.太湖之光”平臺上提出了一種基于MPI+Athread的PE算法并行加速方法，實現了粗粒度的進程級并行和細粒度的線程級并行，解決了文件數量過多所產生的負載不均衡、數據量龐大所引起的效率低等問題，采用了雙緩沖技術減少了主從通信時間，使用DMA通信和重組傳輸數據降低了主從通信次數，將核心計算任務合理劃分到從核，提高了算法的時效性。此外，對本文所提方法進行測試，驗證不僅可以在單個節點上實現11.86倍的加速，而且在多個節點上具有良好的可擴展性和并行效率。下一步，將在“神威·太湖之光”異構平臺上，針對在大規模應用的并行化過程中普遍存在的問題，提出一種通用的并行模型。