基于Linux的多核并行可伸縮函數(shù)式編程研究

仇 賓，崔素麗，孫曼曼，田 亮

(1. 河北師范大學(xué)附屬民族學(xué)院，河北 石家莊 050000；2. 河北師范大學(xué)計(jì)算機(jī)與網(wǎng)絡(luò)空間安全學(xué)院，河北 石家莊 050024)

1 引言

在傳統(tǒng)的Liunx平臺(tái)編程中，采用較多的是馮諾依曼模型。隨著人工智能技術(shù)在嵌入式Liunx平臺(tái)上的普及，大量數(shù)據(jù)和復(fù)雜業(yè)務(wù)促使多核并行計(jì)算能力的提升，基于這種模型實(shí)現(xiàn)的編程語(yǔ)言，由于存在IO和指令的阻塞[1-2]，造成了很多資源浪費(fèi)。此外，在實(shí)現(xiàn)多線程編程時(shí)多采用互斥鎖[3]，造成了大量數(shù)據(jù)傳輸資源的消耗。由于計(jì)算規(guī)模的增加，多核并行是當(dāng)前最有效的解決方式[4]。如何更好的實(shí)現(xiàn)多核并行計(jì)算成為關(guān)鍵，于是，很多專家針對(duì)多核并行編程展開優(yōu)化研究。Leslie在BSP分析基礎(chǔ)上提出了Multi-BSP編程模型；C-K Chui在LogP分析基礎(chǔ)上提出了mLog編程模型。這些模型雖然能夠完成多核并行計(jì)算，但是對(duì)不同的體系結(jié)構(gòu)通用性較差。此外，也有以多級(jí)并行為重點(diǎn)，加上粒度因素的編程模型，如MPI和OpenMP[5]。MPI和OpenMP的粒子不同，MPI是一種相對(duì)粗粒度的模型[6]；OpenMP是一種相對(duì)細(xì)粒度的模型[7-8]。

隨著多核并行計(jì)算應(yīng)用的越來(lái)越多，對(duì)多核并行編程模型也提出了越來(lái)越高的要求，而函數(shù)式編程具有高階性與無(wú)狀態(tài)性，能夠增強(qiáng)編程的模塊化與多態(tài)性，無(wú)需原語(yǔ)即可確保多核并行處理過程中的數(shù)據(jù)安全性。于是，本文設(shè)計(jì)了一種基于函數(shù)式的編程模型。該模型可以擺脫對(duì)互斥鎖與狀態(tài)信息的依賴。模型引入了乘法級(jí)數(shù)增長(zhǎng)的任務(wù)竊取策略，能夠有效改善任務(wù)的負(fù)載均衡。同時(shí)，模型設(shè)計(jì)了一種64bits定長(zhǎng)哈希并行計(jì)算，用來(lái)保證數(shù)據(jù)和通信的完整安全。

2 編程模型構(gòu)建

采用函數(shù)式編程，其最為關(guān)鍵的構(gòu)件就是函數(shù)。利用函數(shù)的復(fù)合和嵌套，能夠使編程過程擺脫狀態(tài)信息。為了提高函數(shù)的描述性，將一些子函數(shù)做復(fù)合或者嵌套處理。一般可以采取順序、分支和循環(huán)等手段來(lái)實(shí)現(xiàn)復(fù)雜關(guān)系的表達(dá)[9]。定義如下函數(shù)表達(dá)式

y(x)=f(u(x)，v(x))

(1)

式中，x代表函數(shù)y、u、v的輸入；同時(shí)u與v的輸出又是函數(shù)f的輸入。從該函數(shù)可以看出，函數(shù)f無(wú)需中間狀態(tài)量就能夠取出u(x)與v(x)。另外，函數(shù)y的求解涵蓋了函數(shù)的復(fù)合嵌套關(guān)系。其中，復(fù)合有利于改善編程中的數(shù)據(jù)傳遞，主要用于優(yōu)化內(nèi)存。而嵌套有利于對(duì)復(fù)雜問題的拆分，主要用于優(yōu)化并行處理。

為了更好的描述函數(shù)模型，根據(jù)函數(shù)間的復(fù)合關(guān)系構(gòu)造樹。如函數(shù)表達(dá)式(1)中，函數(shù)f映射為樹y的根節(jié)點(diǎn)，函數(shù)u和v映射為樹y的葉子節(jié)點(diǎn)。根據(jù)嵌套關(guān)系，可以在發(fā)生嵌套的時(shí)候構(gòu)建嵌套子樹，利用嵌套子樹取代相應(yīng)葉子節(jié)點(diǎn)?？紤]到語(yǔ)法解析與編譯過程對(duì)模型構(gòu)建的約束，這里采用運(yùn)行時(shí)構(gòu)建的方式。每一個(gè)節(jié)點(diǎn)可以看成調(diào)度單元，從而把函數(shù)樹模型的構(gòu)建轉(zhuǎn)換為調(diào)度優(yōu)化問題。樹中的任何一個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)子函數(shù)，每一個(gè)子函數(shù)對(duì)應(yīng)一個(gè)獨(dú)立的Task，由于函數(shù)的調(diào)用是通過棧的方式實(shí)現(xiàn)，因此映射為動(dòng)態(tài)樹模型后便可以實(shí)現(xiàn)并行處理。動(dòng)態(tài)樹模型描述如圖1所示。函數(shù)能夠?qū)栴}進(jìn)行良好的抽象化處理，編程時(shí)不必考慮線程安全問題，只考慮樹結(jié)構(gòu)即可，有利于提高并行性。此外，所有節(jié)點(diǎn)的連接關(guān)系最終匯聚到一個(gè)根節(jié)點(diǎn)上，削弱了葉子節(jié)點(diǎn)間的耦合度，有利于提升編程模型的擴(kuò)展性。

圖1 動(dòng)態(tài)樹模型

采用動(dòng)態(tài)樹模型雖然可以實(shí)現(xiàn)并行計(jì)算，但是對(duì)于多核系統(tǒng)而言，其物理線程也是有限的。所以動(dòng)態(tài)樹的并行處理屬于求解NP問題，應(yīng)盡可能保證模型整體的效率。為了方便求解，將動(dòng)態(tài)樹模型描述如下

M={N，R}

(2)

集合N是動(dòng)態(tài)樹全部節(jié)點(diǎn)；集合R是動(dòng)態(tài)樹全部節(jié)點(diǎn)關(guān)系。對(duì)于任意節(jié)點(diǎn)ni∈N，可以表示為ni：{bi，di}。bi表示ni所屬父節(jié)下的全部節(jié)點(diǎn)數(shù)；di表示ni的深度。如果ni是nj的父節(jié)點(diǎn)，則節(jié)點(diǎn)ni和nj的關(guān)系可以標(biāo)記為ri，j。ri，j體現(xiàn)了父子節(jié)點(diǎn)間的約束條件，只有在全部子節(jié)點(diǎn)均完成后，父節(jié)點(diǎn)ni才會(huì)處于就緒態(tài)。根據(jù)bi和di的分布，該NP問題的優(yōu)先級(jí)表示如下

μi=-(λ1di+λ2log2bi)

(3)

式中，λ1與λ2分別代表節(jié)點(diǎn)兩種特征的權(quán)重。ui值的大小代表了節(jié)點(diǎn)ni優(yōu)先級(jí)的高低，ui值越大，意味著ni優(yōu)先級(jí)越高。整個(gè)動(dòng)態(tài)樹模型依據(jù)優(yōu)先級(jí)順序入隊(duì)?；谀Ｐ头治?，可以確定深度影響任務(wù)執(zhí)行的層次和時(shí)間，對(duì)于深度較小節(jié)點(diǎn)，應(yīng)該為其分配較高的優(yōu)先級(jí)。

3 任務(wù)負(fù)載均衡策略

3.1 計(jì)算資源分析

基于Linux平臺(tái)的多核系統(tǒng)是資源有限的，在節(jié)點(diǎn)任務(wù)調(diào)度時(shí)需要考慮資源約束。首先是處理器性能，它主要受CPU頻率、Cache和指令等一些因素影響。因?yàn)橛绊懸蛩剡^多，無(wú)法對(duì)單一指標(biāo)進(jìn)行量化評(píng)價(jià)，采用給定任務(wù)的方式來(lái)測(cè)試其計(jì)算性能，公式表示如下

(4)

n是測(cè)試的任務(wù)數(shù)；ti是第i個(gè)任務(wù)所需的時(shí)間。ComPower即可用于描述處理器的計(jì)算性能。

然后是系統(tǒng)的存儲(chǔ)空間，由于Linux平臺(tái)在并行任務(wù)過程中，每一個(gè)任務(wù)都應(yīng)該先檢查存儲(chǔ)條件。檢查存儲(chǔ)空間的方式為

Mu=Mall-Mhu

(5)

Mall是系統(tǒng)全部存儲(chǔ)空間；Mhu是系統(tǒng)已消耗存儲(chǔ)空間。Mu即為系統(tǒng)當(dāng)前有效存儲(chǔ)空間。內(nèi)存也是Linux平臺(tái)任務(wù)需要考慮的關(guān)鍵資源，其檢查方式與存儲(chǔ)類似，公式表示為

Ru=Rall-Rhu

(6)

Rall是系統(tǒng)全部?jī)?nèi)存；Rhu是當(dāng)前已消耗內(nèi)存。Ru即為系統(tǒng)當(dāng)前有效內(nèi)存。

3.2 任務(wù)竊取策略

由前述函數(shù)式編程模型可知，基于Linux平臺(tái)的多核并行函數(shù)式編程可以轉(zhuǎn)化為多任務(wù)并發(fā)調(diào)度。而這個(gè)過程又可看成是對(duì)資源的訪問，為了提高整體的編程性能，就需要提高對(duì)資源的訪問效率和合理性。在改善多核并行處理時(shí)，當(dāng)前一些編程機(jī)制會(huì)采用回溯與分治操作。由于這些操作一般需要通過線程實(shí)現(xiàn)，因此可能會(huì)有線程中止導(dǎo)致操作失敗的情況發(fā)生?？梢哉f(shuō)當(dāng)前任何一種編程機(jī)制都存在資源問題，尤其是在多核并行處理時(shí)任務(wù)和資源的不確定場(chǎng)合。于是，本文采用任務(wù)竊取策略，核心思想是在監(jiān)測(cè)到Linux平臺(tái)多核系統(tǒng)的某個(gè)線程存在空閑，則會(huì)去竊取其余線程任務(wù)。

函數(shù)式編程時(shí)，對(duì)多核處理器的隊(duì)列進(jìn)行監(jiān)控，如果發(fā)現(xiàn)隊(duì)列內(nèi)任務(wù)數(shù)量低于設(shè)定閾值，便將該隊(duì)列標(biāo)記為Filch。調(diào)度中心在發(fā)現(xiàn)Filch標(biāo)記后，對(duì)該隊(duì)列的竊取對(duì)象采取決策。包括竊取的目標(biāo)Worker執(zhí)行器和任務(wù)規(guī)模，其執(zhí)行代碼如圖2所示。核心代碼中參數(shù)performer指定了竊取目標(biāo)，返回值filchNum為竊取規(guī)模。程序?qū)Ω`取數(shù)量采用乘法級(jí)數(shù)增長(zhǎng)，至第次竊取時(shí)，任務(wù)規(guī)?？梢赃_(dá)到initFilchn，這樣可以避免反復(fù)竊取。

圖2 任務(wù)竊取核心代碼

在竊取過程中，除了考慮竊取目標(biāo)和規(guī)模外，因?yàn)樯婕暗竭w移與通信操作，還需要充分考慮竊取的時(shí)機(jī)。根據(jù)處理器的實(shí)際處理能力來(lái)確定竊取閾值。通常情況下，閾值的選取與處理能力成正比。當(dāng)某個(gè)Worker隊(duì)列內(nèi)任務(wù)規(guī)模降至閾值以下，或者Worker隊(duì)列處于空閑狀態(tài)，都將觸發(fā)竊取策略的執(zhí)行，從而有效權(quán)衡多核并行處理與竊取處理的開銷問題。基于前述分析，負(fù)載均衡的核心代碼如圖3所示。

圖3 負(fù)載均衡核心代碼

4 哈希并行計(jì)算

由于Linux平臺(tái)應(yīng)用涉及的數(shù)據(jù)和通信對(duì)完整性、安全性要求日益增加，本文設(shè)計(jì)了一種哈希并行計(jì)算。保證原始消息(Message)可靠性的同時(shí)，也盡可能避免對(duì)并行處理效率的影響。Message是任意長(zhǎng)度，且可能包含字母、數(shù)字和特殊字符。假定Message的字符長(zhǎng)度是Lc，則中所有字符對(duì)應(yīng)的ASCII二進(jìn)制串可以表示為

C=Binary(c1，c2，…cn)

(7)

式中，ci是Message內(nèi)第i個(gè)字符；n是Message內(nèi)的字符總數(shù)。為了提高不規(guī)則消息的處理效率，這里將輸出統(tǒng)一為64bits哈希值。根據(jù)消息中字符的數(shù)量，視情況采取補(bǔ)位操作，補(bǔ)位規(guī)則描述如下

(8)

利用該公式對(duì)Message的字符數(shù)量進(jìn)行檢查，只有當(dāng)n是64的整數(shù)倍時(shí)，無(wú)需采取補(bǔ)位操作。通過迭代對(duì)c4i…c4i+3進(jìn)行序列拼接，其迭代處理過程描述如下

xt+i-1=xt+i-2XOR(c4i…c4i+3)

(9)

迭代過程直至所有的Message位執(zhí)行結(jié)束，通過隨機(jī)方式從中選出64bits哈希值。

為了驗(yàn)證Message字符拼接的混沌性，通過三維球形空間中的3000個(gè)點(diǎn)分布來(lái)進(jìn)行模擬，迭代結(jié)束后的分布結(jié)果如圖4所示。從分布結(jié)果可知，雖然混沌計(jì)算在單次會(huì)表現(xiàn)出一定的隨機(jī)性，但是整個(gè)迭代過程是存在確定性的。所有點(diǎn)在球形空間中表現(xiàn)出良好的均勻分布，表明所設(shè)計(jì)的哈希生成方式不僅具有良好的隨機(jī)性，而且具有良好的分布均勻性。

圖4 混沌映射結(jié)果

5 仿真與結(jié)果分析

實(shí)驗(yàn)服務(wù)器選擇Intel Xeon E7-4820型號(hào)處理器，該處理器為八核。此外，服務(wù)器內(nèi)存是128B，操作系統(tǒng)是Ubuntu16.04。測(cè)試過程使用的應(yīng)用程序包括histogram、linear regression和word count，它們所使用的數(shù)據(jù)集大小分別為2.0GB、3.5GB和3.0GB。為了測(cè)試多核并行編程的性能，分別從執(zhí)行時(shí)間和可伸縮性進(jìn)行驗(yàn)證。

5.1 執(zhí)行時(shí)間分析

將本文所提的多核并行編程模型與MPI、OpenMP[8]進(jìn)行性能比較，首先測(cè)試三種編程模型的執(zhí)行時(shí)間。針對(duì)histogram、linear regression和word count應(yīng)用程序，采用10次求平均的方式得到三種模型的最終時(shí)間，結(jié)果如圖5所示。通過結(jié)果對(duì)比可得，三種編程模型在執(zhí)行不同應(yīng)用程序時(shí)的性能存在細(xì)微差別，這是由于不同的應(yīng)用程序?qū)θ蝿?wù)、內(nèi)存和存儲(chǔ)等資源的分配存在差異導(dǎo)致的。但是綜合來(lái)看，本文所提的函數(shù)式編程模型優(yōu)勢(shì)明顯，在histogram、linear regression和word count應(yīng)用程序的執(zhí)行時(shí)間上僅為MPI模型的7.13%、11.51%和8.02%；為OpenMP模型的17.05%、25.13%和17.50%。

圖5 不同編程模型的執(zhí)行時(shí)間比較

5.2 可伸縮性分析

在大多數(shù)并行編程模型中都存在嚴(yán)重的鎖競(jìng)爭(zhēng)，測(cè)試得到不同編程模型在histogram、linear regression和word count三種情況下的鎖競(jìng)爭(zhēng)情況。圖6為不同編程模型在Linux平臺(tái)上的鎖競(jìng)爭(zhēng)開銷。從結(jié)果分析可知，所提多核并行函數(shù)式編程能夠?qū)㈡i競(jìng)爭(zhēng)開銷穩(wěn)定的控制在0.5%以下，顯著降低了鎖競(jìng)爭(zhēng)現(xiàn)象的發(fā)生，避免由此導(dǎo)致的額外開銷。

圖6 不同編程模型的鎖競(jìng)爭(zhēng)開銷比較

由于處理器的核數(shù)量直接影響并行計(jì)算能力，核數(shù)量越多，并行計(jì)算能力越高。為了描述多核并行計(jì)算能力，采用加速比作為評(píng)價(jià)指標(biāo)。它是用于描述單核和多核情況下，某個(gè)應(yīng)用的執(zhí)行時(shí)間比，計(jì)算公式為

Sur=Tcore(1)/Tcore(n)

(10)

式中，Tcore(1)是單核情況下的執(zhí)行時(shí)間；Tcore(n)是多核情況下的執(zhí)行時(shí)間。

測(cè)試得到不同編程模型對(duì)histogram、linear regression和word count應(yīng)用程序的平均加速比，結(jié)果如圖7所示。從結(jié)果比較可知，所提函數(shù)式編程模型加速比近似于線性，能夠更好的利用多核提高應(yīng)用程序的執(zhí)行速度。結(jié)合鎖競(jìng)爭(zhēng)測(cè)試結(jié)果，表明所提函數(shù)式編程模型在提高多核利用率的情況下，明顯減少了線程訪問公共資源時(shí)的開銷，顯著提升了多核并行編程的可伸縮性。

圖7 不同編程模型的加速比

6 結(jié)束語(yǔ)

本文針對(duì)Liunx平臺(tái)編程中存在的IO和指令阻塞，以及互斥鎖等問題，提出了一種多核并行函數(shù)式編程模型。采用函數(shù)的復(fù)合和嵌套，能夠使編程過程擺脫狀態(tài)信息。同時(shí)，結(jié)合順序、分支和循環(huán)等手段能夠?qū)崿F(xiàn)復(fù)雜關(guān)系的表達(dá)。函數(shù)模型轉(zhuǎn)換成動(dòng)態(tài)樹后，可以看成是對(duì)資源訪問的優(yōu)化調(diào)度，于是設(shè)計(jì)了負(fù)載均衡策略和64bits定長(zhǎng)哈希并行計(jì)算，確保資源訪問和數(shù)據(jù)安全。通過仿真測(cè)試，得到在不同應(yīng)用程序情況下，函數(shù)式編程模型的執(zhí)行時(shí)間、鎖競(jìng)爭(zhēng)與加速比均明顯優(yōu)于MPI和OpenMP模型，表明函數(shù)式編程模型具有更高的執(zhí)行效率，可伸縮性得到顯著提高，具有更高的多核并行計(jì)算能力。