周 倩，梁建國，傅 游

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

0 引 言

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

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

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

1 背 景

1.1 PE算法的概述

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

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

(1)

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

1.1.1 相空間重構(gòu)

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

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

(2)

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

(3)

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

1.1.2 相空間矩陣編碼

對于給定向量Xi,m個實數(shù)Xi升序重新排列： [x(i+(j1-1)τ)≤x(i+(j2-1)τ)≤…≤x(i+(jm-1)τ)]。 當?shù)仁匠霈F(xiàn)時，如x(i+(jk1-1)t)=x(i+(j2-1)t)， 根據(jù)它們對應的j值確定值大?。喝鬸k1

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

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

(4)

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

1.1.3 PE計算

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

(5)

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

圖1 排列熵算法過程

1.2 SW26010多核處理器

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

圖2 SW26010處理器架構(gòu)

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

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

1.3 神威Athread加速線程庫

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

算法1：在CPE上Athread框架

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

輸出：每個CPE的計算結(jié)果ResultCPE

(1)thread_id←ATHREAD-GET-ID；

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

(3)fori∈TPEC

DO(i)

endfor

(4)向MPE發(fā)送計算結(jié)果PUT(ResultCPE)；

(5)MPE調(diào)用CPE函數(shù)ATHREAD-APAWN；

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

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

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

2 PE算法并行設(shè)計與優(yōu)化

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

2.1 PE算法特征分析

2.1.1 數(shù)據(jù)規(guī)模大

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

2.1.2 兩級負載不均衡

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

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

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

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

2.2 基于MPI多文件負載均衡優(yōu)化算法

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

算法2：多文件負載均衡

輸入：9216個csv文件；進程數(shù)comm_sz；進程號rank

輸出：重構(gòu)矩陣ch_ti_series_1D[]

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

forfile_num←1 to 15 do

(2) 判斷當前數(shù)據(jù)文件屬于哪個工況環(huán)境

switch(file_num)

case1-5:work_condi←“35Hz12kN”

case6-10:work_condi←“37.5Hz11kN”

case11-15:work_condi←“40Hz10kN”

default:error

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

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

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

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

(6) 相空間重構(gòu)

ch_ti_series_1D[]=re_organization()

(7)endfor

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

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

算法3：矩陣重構(gòu)分量排序

輸入：待排序數(shù)組S；嵌入維數(shù)m和重構(gòu)分量標示d

輸出：整數(shù)索引_rank[]

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

athread_get(PE_MODE,

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

&get_reply,0,0,0)

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

while(get_reply!=1);

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

(4) 利用下標數(shù)組M得到重構(gòu)分量索引

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

athread_put(PE_MODE,&res,

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

2.4 基于MPI+Athread的并行PE算法優(yōu)化方法

2.3節(jié)提出的基于Athread加速線程庫的PE并行算法，由于數(shù)據(jù)規(guī)模大，通過分析程序熱點可知，主核將重構(gòu)矩陣所需數(shù)據(jù)傳輸?shù)綇暮耸亲詈臅r的部分，本小節(jié)從減少主從通信次數(shù)和采用雙緩沖方法兩個方面對CPE數(shù)據(jù)傳輸部分進行優(yōu)化。

2.4.1 減少主從通信次數(shù)

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

圖3 PE算法athread數(shù)據(jù)劃分

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

2.4.2 雙緩沖機制

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

算法4：雙緩沖機制

輸入：重構(gòu)矩陣分量ch_ti_series_1D[]；輪次d；

輸出：寫回標志write_back

(1)fork←0 to d-1 do

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

(3) 讀入首批數(shù)據(jù)

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) 設(shè)置下一輪次標記

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

(7) 重構(gòu)矩陣分量排序

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

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) 等待最后一輪數(shù)據(jù)寫回

do while(write_back=put_reply(index))

3 實驗及結(jié)果分析

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

3.1 關(guān)鍵參數(shù)確定

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

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

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

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

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

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

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

3.2 多核組性能評估

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

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

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

表3 PE算法眾核優(yōu)化測試結(jié)果

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

圖4 PE算法強可擴展性

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

3.3 PE算法分析

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

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

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

4 結(jié)束語

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