近紅外光譜多核并行譜區(qū)選擇任務(wù)調(diào)度策略研究

黃 華 朱 潔 劉廣昊 吳習(xí)宇 祝詩平

(1.西南大學(xué)工程技術(shù)學(xué)院， 重慶 400716； 2.西南大學(xué)食品科學(xué)學(xué)院， 重慶 400716)

0 引言

近紅外光譜(Near infrared spectroscopy, NIRS)廣泛應(yīng)用于稻谷、小麥和玉米等農(nóng)產(chǎn)品的含水率無損檢測中[1-3]。在近紅外光譜定量分析模型中偏最小二乘法(Partial least squares, PLS)[4]應(yīng)用最為廣泛。從原始光譜數(shù)據(jù)中選擇特征譜區(qū)用于PLS建模有利于提高預(yù)測模型的精度。常用的譜區(qū)選擇算法[5-6]有4種：分段間隔偏最小二乘法(Interval partial least squares, iPLS)[7-9]、組合分段偏最小二乘法(Synergy interval partial least squares, siPLS)[10]、反向分段偏最小二乘法(Backward interval partial least squares, biPLS)[11]、滑動窗口偏最小二乘法(Moving window partial least squares, mwPLS)[12-14]。黃華等[9]研究表明這4種特征譜區(qū)選擇算法中mwPLS和biPLS算法預(yù)測精度較高，但其程序運行的時間都較長。如果從提高單核芯片的速度來縮短譜區(qū)選擇程序運行時間，存在兩方面問題[15]：①熱量問題，會使芯片產(chǎn)生的熱量超過處理器所能承受的極限。②性價比問題，速度快的處理器，其價格都很高、導(dǎo)致單核處理器的性價比很低。因此目前主要采用多核芯片并行執(zhí)行來縮短程序運行時間。

本文以近紅外光譜法定量分析稻谷含水率為例，在16核的云計算平臺下，首先分析順序分配法、等間距法和排序法等3種任務(wù)調(diào)度策略對并行iPLS算法性能的影響；然后將并行性能最好的任務(wù)調(diào)度策略應(yīng)用到siPLS、biPLS和mwPLS等并行算法中，分析它們的相對加速比、并行算法的效率和負載均衡等性能指標。

1 實驗材料

1.1 光譜數(shù)據(jù)

利用Bruker MPA型近紅外光譜儀采集364份稻谷樣品光譜。工作波數(shù)范圍為3 598.71～12 493.30 cm-1，掃描次數(shù)32次，分辨率為3.85 cm-1，共2 307個波數(shù)點。隨機選取其中的210個樣品作為校正集；154個樣品作為預(yù)測集。

1.2 云平臺配置及并行性能參數(shù)

云計算服務(wù)器配置如下：處理器Intel Xeon E5-2650 v3，主頻2.30 GHz、CPU核數(shù)16核、內(nèi)存16 GB，操作系統(tǒng)Microsoft Windows Server 2012 R2 Datacenter Version 6.3 (Build 9600)，所用軟件為Matlab 8.5 (R2015a)。

為了衡量并行算法性能，通常使用相對加速比、并行算法的效率和負載平衡等性能指標[15-16]。

相對加速比為

(1)

式中t1(n)——單核運行時間

tP(n)——多核運行時間

一般情況下，t1(n)>tP(n)。

并行算法的效率為

(2)

式中p——處理器核數(shù)

SP(n)≤p，所以有0

并行算法的負載均衡百分比為

(3)

式中Ti——第i個進程執(zhí)行時間

2 單核串行iPLS算法效率分析

2.1 單核串行iPLS算法計算復(fù)雜度分析

分段間隔偏最小二乘法(iPLS)首先將原始光譜波數(shù)分成2～N段，取每一小段分別用于最小二乘法(PLS)建模，并計算其預(yù)測集的均方根誤差(Root mean square error of prediction, RMSEP)，然后根據(jù)RMSEP最小的原則統(tǒng)計計算結(jié)果，從分段中選取具有最佳預(yù)測性能的光譜區(qū)域。iPLS算法計算復(fù)雜度參照文獻[9]。iPLS譜區(qū)選擇示意圖如圖1所示。

圖1 iPLS譜區(qū)選擇示意圖Fig.1 Diagram of iPLS wavelength selection

2.2 單核串行iPLS算法運行結(jié)果分析

在云計算平臺下采用傳統(tǒng)的單核串行程序運行iPLS算法。程序連續(xù)運行10次，計算每種分段情況下iPLS算法的平均程序運行時間，如圖2所示。

圖2 單核串行iPLS算法程序運行時間Fig.2 Runtime of iPLS serial algorithms on signal core

由圖2可以看出，iPLS程序的運行時間與分段數(shù)和光譜數(shù)據(jù)量有關(guān)。當分段數(shù)為2和3時程序的運行時間較長，這主要是因為這兩種分段情況下用于單次PLS建模的數(shù)據(jù)量較大。如分段數(shù)為2時，將2 307個波數(shù)點分成兩段，每一段有1 153個波數(shù)點用于PLS建模。隨著分段數(shù)的增加程序運行時間呈上升趨勢，這主要是由于分段數(shù)越多程序運行PLS算法的次數(shù)越多。在單核下iPLS串行算法程序平均運行總的時間為26.80 s。

3 云計算平臺下多核并行iPLS算法任務(wù)調(diào)度策略

3.1 基于parfor關(guān)鍵字的多核任務(wù)調(diào)度策略

在多核處理器下實現(xiàn)特征譜區(qū)選擇的并行算法流程如圖3所示。

圖3 近紅外光譜譜區(qū)選擇算法并行化流程Fig.3 Flow chart for parallel wavelength selection

由于iPLS算法具有分離性，即可以根據(jù)各分段數(shù)單獨調(diào)用PLS算法，因此可以將串行的iPLS譜區(qū)選擇算法轉(zhuǎn)換成并行算法在多核計算機中運行。在圖3中，將串行的算法分配到各個處理器上并行執(zhí)行，關(guān)鍵的問題是如何對各個處理器進行合理的任務(wù)分配，使各個處理器的負載平衡，減少各處理器的開銷時間和處理器間的通信時間，從而提高并行效率。

在單核串行算法中，運行iPLS程序會根據(jù)分段數(shù)調(diào)用各自的iPLS算法，即

fori=2:N分段數(shù)為2～N段

iPLS(i) 根據(jù)分段數(shù)調(diào)用iPLS算法

end

在Matlab中提供了parfor關(guān)鍵字實現(xiàn)將串行的for循環(huán)轉(zhuǎn)換為并行執(zhí)行[17-18]，for關(guān)鍵字改為parfor即可實現(xiàn)并行算法。

Matlab中parfor采用client和worker模式，如圖4所示。

圖4 Matlab并行計算資源池Fig.4 Matlab parallel computing resource pool

在多核處理中，其中一個核為client端，其余的多個核為worker端。在client端編寫和啟動并行代碼，Matlab的串行部分程序代碼在client端運行，在程序的執(zhí)行過程中client端根據(jù)并行代碼的關(guān)鍵字parfor尋找需要并行執(zhí)行的代碼，并將這部分代碼分配到各個worker端，然后各個worker端并行執(zhí)行，并將計算結(jié)果返回給client端。若計算機的核數(shù)為p(即有p個worker端)，循環(huán)次數(shù)為n，若n/p為整數(shù)，則循環(huán)將會被均勻分配；如果n/p不為整數(shù)，則各個worker端的任務(wù)分配將會不均勻。本文分析比較了3種任務(wù)調(diào)度策略對并行性能的影響。

(1) 順序分配法任務(wù)調(diào)度策略

順序分配法任務(wù)調(diào)度策略將按自然數(shù)的順序為各個核平均分配任務(wù)。例如在4核處理器上運行n為1～115段的iPLS程序(n=1表示用全譜建模，為了與全譜進行比較，n的最小值取為1)，1～115段被順序平均分成4組：第1組為第1～28段；第2組為第29～56段；第3組為第57～84段；第4組為第85～115段。client端將這4組分段數(shù)據(jù)隨機分配給4個核處理器并行執(zhí)行。

(2)等間距法任務(wù)分配調(diào)度策略

等間距法任務(wù)分配調(diào)度策略以處理器核數(shù)p為間隔值為每一個核從分段數(shù)中抽取分段數(shù)索引。例如在4核處理器上運行n為1～115的iPLS程序，以4間隔將1～115段分成4組：第1組為1、5、…、113段；第2組為2、6、…、114段，第3組為3、7、…、115段，第4組為4、8、…、112段。然后將這4組隨機分配給4核處理器并行執(zhí)行。

(3)排序法分配調(diào)度策略

排序法分配策略會根據(jù)各個核任務(wù)執(zhí)行的進程來分配任務(wù)，任務(wù)先完成的核將首先獲得下一次執(zhí)行任務(wù)。任務(wù)分配按由重到輕的原則進行。同樣以在4核處理器上運行1～115共115段的iPLS程序為例。第1次分配首先將115乘以2/3除以核數(shù)4，即115×2/12=19.16，取整為20?？臻e的前一半核首先獲得20段的計算任務(wù)。以此類推繼續(xù)給空閑的核分配任務(wù)，直到所有的任務(wù)被分配完。

3.2 多核并行iPLS算法運行結(jié)果分析

在16核云計算平臺下，分別對順序分配法、等間距法、排序法等3種任務(wù)調(diào)度策略并行計算性能進行測試。在Matlab中通過parpool關(guān)鍵字設(shè)置CPU核數(shù)分別為1～16等16種情況下運行iPLS算法。這3種任務(wù)分配策略的程序運行時間、相對加速比、并行效率和負載均衡情況如圖5、6所示。

圖5 3種分配策略程序運行時間與相對加速比Fig.5 Runtime and speedup ratio for three task scheduling strategies

圖6 3種分配策略并行效率和負載均衡比較Fig.6 Parallel efficiency and load balance for three task scheduling strategies

由圖5可見，隨著并行核數(shù)的增加程序運行時間成比例減少，相對加速比呈上升趨勢。排序法分配策略的相對加速比性能最佳。由圖6可見，順序分配法負載均衡性能最差。以4核并行iPLS算法為例，由圖2可見，當N大于3以后隨著分段數(shù)的增加計算iPLS程序的運行時間增大。在4核處理器上實驗測試結(jié)果表明：在順序分配法中程序運行時間最長為9.75 s，最短時間為3.47 s，最快的核有64.50%的空閑時間用于等待最慢的核完成任務(wù)。由圖6可見，隨著并行核數(shù)的增加負載均衡性能和并行效率都呈下降趨勢。

綜上所述，在以上3種分配策略中，排序法分配策略并行性能最佳，后文將排序法分配策略應(yīng)用到組合分段偏最小二乘法、滑動窗口偏最小二乘法和反向分段偏最小二乘法等3種譜區(qū)選擇并行算法中。

4 在云計算平臺下多核并行譜區(qū)選擇算法應(yīng)用

4.1 siPLS 算法多核并行運行結(jié)果

組合分段偏最小二乘法(siPLS)[9,12]是在分段間隔法的基礎(chǔ)上，從分段中取出L段組合成一個新的光譜數(shù)據(jù)集，用于PLS建模；然后根據(jù)RMSEP最小的原則確定最佳組合光譜區(qū)域。

在16核云計算平臺下采用排序法分配策略，siPLS算法的運行結(jié)果如表1所示。

表1 在1～16核下siPLS并行算法運行結(jié)果Tab.1 Result of siPLS parallel algorithm from 1 to 16 cores

從表1可見，利用2核并行運行siPLS算法時相對加速比為1.91，程序運行時間由單核的20.70 min縮短至10.84 min，節(jié)省了47.83%的程序運行時間。從2～16核的并行運行結(jié)果來看，隨著核數(shù)的增加程序運行時間進一步減小。并行效率和負載均衡性能隨著并行核數(shù)的變化有一定的波動，核數(shù)為2時并行效率最高，為95.45%，負載均衡性能也最佳，達到95.31%。11核并行時并行效率最低，為77.98%，負載均衡性能也最差，百分比為80.03%。

4.2 biPLS算法多核并行運行結(jié)果

反向分段偏最小二乘法(biPLS)[9]首先將原始光譜的波數(shù)分成n段，然后去掉其中的任意一段，得到由n-1段光譜組合成的新光譜數(shù)據(jù)集，用于PLS建模；計算其在不同主成分數(shù)下的RMSEP，再對保存下來n-1段光譜數(shù)據(jù)重復(fù)上述進程，直到最后只剩下1段光譜為止。最后根據(jù)RMSEP最小的原則確定最佳組合光譜區(qū)域。

在16核云計算平臺下采用排序法分配策略，biPLS算法的運行結(jié)果如表2所示。

表2 在1～16核下biPLS并行算法運行結(jié)果Tab.2 Result of biPLS parallel algorithm from 1 to 16 cores

從表2可見，利用2核并行運行biPLS算法時相對加速比為1.85，程序運行時間由單核的9.22 h縮短至4.98 h，節(jié)省了45.99%的程序運行時間。從2～16核的并行運行結(jié)果來看，隨著核數(shù)的增加程序運行時間進一步減小。然而并行效率隨著并行核數(shù)的增加卻減少，2核并行時并行效率最高，為92.64%。2～16核的負載均衡性都能較好，百分比均介于85%～94%之間。

4.3 mwPLS 算法多核并行運行結(jié)果

滑動窗口偏最小二乘法(mwPLS)[19-20]是以某一點為中心，按一定的窗口長度從原始光譜中取出一段連續(xù)的光譜數(shù)據(jù)集，用于最小二乘法建模；然后根據(jù)RMSEP最小的原則確定最佳光譜中心點和窗口長度，從而獲得最佳特征光譜區(qū)域。

在16核云計算平臺下采用排序法分配策略，mwPLS算法的運行結(jié)果如表3所示。

表3 在1～16核下mwPLS并行算法運行結(jié)果Tab.3 Result of mwPLS parallel algorithm from 1 to 16 cores

從表3可見，利用2核并行運行mwPLS算法時相對加速比為1.91，程序運行時間由單核的55.51 h縮短至29.03 h，節(jié)省了47.70%的程序運行時間。從2～16核的并行運行結(jié)果來看，2核并行時并行效率最高，為95.62%。負載均衡百分比均大于94%。

5 結(jié)束語

在近紅外光譜分析中偏最小二乘法獲得了廣泛的應(yīng)用。從全部光譜中選擇最佳特征譜區(qū)可以提高PLS算法的預(yù)測精度，目前廣泛使用的譜區(qū)選擇算法有mwPLS、biPLS、siPLS、iPLS等4種。在單機單核下這4種算法程序的運行時間分別為55.51 h、9.22 h、20.70 min、26.80 s。在不改變算法精度的情況下，在云計算平臺下采用排序任務(wù)分配策略多核并行算法有較好的負載均衡性能，可以縮短程序的運行時間，提高近紅外光譜譜區(qū)選擇效率。如采用2核并行時，mwPLS和biPLS算法分別節(jié)省了47.70%和45.99%的程序運行時間。隨著核數(shù)的增加，程序運行時間會進一步減小，但并行效率不與核數(shù)成正比，從2～16核的并行運行結(jié)果來看，2核并行算法具有最高的并行效率。目前普通的計算機至少具有2核處理器，在考慮并行效率和計算成本條件下，利用2核并行計算具有經(jīng)濟性和實用性。