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

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

(1. 河北師范大學附屬民族學院，河北 石家莊 050000；2. 河北師范大學計算機與網絡空間安全學院，河北 石家莊 050024)

1 引言

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

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

2 編程模型構建

采用函數式編程，其最為關鍵的構件就是函數。利用函數的復合和嵌套，能夠使編程過程擺脫狀態信息。為了提高函數的描述性，將一些子函數做復合或者嵌套處理。一般可以采取順序、分支和循環等手段來實現復雜關系的表達[9]。定義如下函數表達式

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

(1)

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

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

圖1 動態樹模型

采用動態樹模型雖然可以實現并行計算，但是對于多核系統而言，其物理線程也是有限的。所以動態樹的并行處理屬于求解NP問題，應盡可能保證模型整體的效率。為了方便求解，將動態樹模型描述如下

M={N，R}

(2)

集合N是動態樹全部節點；集合R是動態樹全部節點關系。對于任意節點ni∈N，可以表示為ni：{bi，di}。bi表示ni所屬父節下的全部節點數；di表示ni的深度。如果ni是nj的父節點，則節點ni和nj的關系可以標記為ri，j。ri，j體現了父子節點間的約束條件，只有在全部子節點均完成后，父節點ni才會處于就緒態。根據bi和di的分布，該NP問題的優先級表示如下

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

(3)

式中，λ1與λ2分別代表節點兩種特征的權重。ui值的大小代表了節點ni優先級的高低，ui值越大，意味著ni優先級越高。整個動態樹模型依據優先級順序入隊?；谀Ｐ头治觯梢源_定深度影響任務執行的層次和時間，對于深度較小節點，應該為其分配較高的優先級。

3 任務負載均衡策略

3.1 計算資源分析

基于Linux平臺的多核系統是資源有限的，在節點任務調度時需要考慮資源約束。首先是處理器性能，它主要受CPU頻率、Cache和指令等一些因素影響。因為影響因素過多，無法對單一指標進行量化評價，采用給定任務的方式來測試其計算性能，公式表示如下

(4)

n是測試的任務數；ti是第i個任務所需的時間。ComPower即可用于描述處理器的計算性能。

然后是系統的存儲空間，由于Linux平臺在并行任務過程中，每一個任務都應該先檢查存儲條件。檢查存儲空間的方式為

Mu=Mall-Mhu

(5)

Mall是系統全部存儲空間；Mhu是系統已消耗存儲空間。Mu即為系統當前有效存儲空間。內存也是Linux平臺任務需要考慮的關鍵資源，其檢查方式與存儲類似，公式表示為

Ru=Rall-Rhu

(6)

Rall是系統全部內存；Rhu是當前已消耗內存。Ru即為系統當前有效內存。

3.2 任務竊取策略

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

函數式編程時，對多核處理器的隊列進行監控，如果發現隊列內任務數量低于設定閾值，便將該隊列標記為Filch。調度中心在發現Filch標記后，對該隊列的竊取對象采取決策。包括竊取的目標Worker執行器和任務規模，其執行代碼如圖2所示。核心代碼中參數performer指定了竊取目標，返回值filchNum為竊取規模。程序對竊取數量采用乘法級數增長，至第次竊取時，任務規?？梢赃_到initFilchn，這樣可以避免反復竊取。

圖2 任務竊取核心代碼

在竊取過程中，除了考慮竊取目標和規模外，因為涉及到遷移與通信操作，還需要充分考慮竊取的時機。根據處理器的實際處理能力來確定竊取閾值。通常情況下，閾值的選取與處理能力成正比。當某個Worker隊列內任務規模降至閾值以下，或者Worker隊列處于空閑狀態，都將觸發竊取策略的執行，從而有效權衡多核并行處理與竊取處理的開銷問題?；谇笆龇治觯撦d均衡的核心代碼如圖3所示。

圖3 負載均衡核心代碼

4 哈希并行計算

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

C=Binary(c1，c2，…cn)

(7)

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

(8)

利用該公式對Message的字符數量進行檢查，只有當n是64的整數倍時，無需采取補位操作。通過迭代對c4i…c4i+3進行序列拼接，其迭代處理過程描述如下

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

(9)

迭代過程直至所有的Message位執行結束，通過隨機方式從中選出64bits哈希值。

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

圖4 混沌映射結果

5 仿真與結果分析

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

5.1 執行時間分析

將本文所提的多核并行編程模型與MPI、OpenMP[8]進行性能比較，首先測試三種編程模型的執行時間。針對histogram、linear regression和word count應用程序，采用10次求平均的方式得到三種模型的最終時間，結果如圖5所示。通過結果對比可得，三種編程模型在執行不同應用程序時的性能存在細微差別，這是由于不同的應用程序對任務、內存和存儲等資源的分配存在差異導致的。但是綜合來看，本文所提的函數式編程模型優勢明顯，在histogram、linear regression和word count應用程序的執行時間上僅為MPI模型的7.13%、11.51%和8.02%；為OpenMP模型的17.05%、25.13%和17.50%。

圖5 不同編程模型的執行時間比較

5.2 可伸縮性分析

在大多數并行編程模型中都存在嚴重的鎖競爭，測試得到不同編程模型在histogram、linear regression和word count三種情況下的鎖競爭情況。圖6為不同編程模型在Linux平臺上的鎖競爭開銷。從結果分析可知，所提多核并行函數式編程能夠將鎖競爭開銷穩定的控制在0.5%以下，顯著降低了鎖競爭現象的發生，避免由此導致的額外開銷。

圖6 不同編程模型的鎖競爭開銷比較

由于處理器的核數量直接影響并行計算能力，核數量越多，并行計算能力越高。為了描述多核并行計算能力，采用加速比作為評價指標。它是用于描述單核和多核情況下，某個應用的執行時間比，計算公式為

Sur=Tcore(1)/Tcore(n)

(10)

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

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

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

6 結束語

本文針對Liunx平臺編程中存在的IO和指令阻塞，以及互斥鎖等問題，提出了一種多核并行函數式編程模型。采用函數的復合和嵌套，能夠使編程過程擺脫狀態信息。同時，結合順序、分支和循環等手段能夠實現復雜關系的表達。函數模型轉換成動態樹后，可以看成是對資源訪問的優化調度，于是設計了負載均衡策略和64bits定長哈希并行計算，確保資源訪問和數據安全。通過仿真測試，得到在不同應用程序情況下，函數式編程模型的執行時間、鎖競爭與加速比均明顯優于MPI和OpenMP模型，表明函數式編程模型具有更高的執行效率，可伸縮性得到顯著提高，具有更高的多核并行計算能力。