嵌入式電火花線切割CNC系統多核任務分配研究

曹 俊, 蔣 毅, 楊書娟, 馮 飛

(江南大學 機械工程學院 江蘇省食品先進制造裝備技術重點實驗室,江蘇 無錫 214122)

0 引 言

基于嵌入式Linux的電火花線切割(wire-cut electrical discharge machining,WEDM)電腦數控(computer numerical control,CNC)系統是多任務并行的,且任務間存在頻繁的相互通信[1]。在多任務軟件中,合理地對任務進行劃分與調度能夠顯著提高整個系統的計算效率。目前,多核結構是嵌入式處理器的發展主流,多核處理器的任務分配也成為了高性能數控系統開發必須解決的問題[2～4]。

為了提高WEDM CNC系統在嵌入式多核處理器下的執行效率與實時性,需要建立多任務模型,并對任務分配方案尋優。多核處理器調度模型主要有基于任務間相互獨立的調度模型[3]、有向無環任務圖(directed acyclic graph,GAG)模型[4]、任務無向交互圖(task interaction graph,TIG)模型[5]等。但前者未考慮任務間同步通信的問題；后兩者雖然能很好反映任務間的信息交互,但沒有考慮任務周期性,即：當多個周期性任務運行于同一處理器核心時,各任>務能否在限定周期內得到運行的問題。此外,在利用傳統的模擬退火(simulated annealing,SA)法[6]、遺傳算法(gene-tic algorithm,GA)[7]對多核任務分配問題進行尋優時,主要的優化目標通常為系統吞吐率[8]、能耗[9]等,未考慮處理器負載能力限制的問題。

本文對桌面式WEDM CNC系統進行了任務分析,建立了任務無向交互圖模型；根據處理器負載限制條件,改進模擬退火法,對所生成的隨機解引入處理器負載約束進行尋優,得到最優分配方案。

1 WEDM CNC系統硬件結構

本文采用的WEDM CNC系統硬件結構如圖1所示,由上位機和下位機兩部分組成。三星Exynos4412處理器作為上位機,運行Linux操作系統,MCU(STM32F103)作為下位機,二者通過控制器局域網(controller area network,CAN)總線進行通信。上位機部分主要包括進給模塊、工作液循環模塊及人機接口模塊。下位機部分為走絲模塊和脈沖電源模塊。

圖1 WEDM CNC系統硬件結構

2 WEDM CNC系統任務分析

根據圖1所示WEDM CNC系統的硬件結構,走絲控制任務和脈沖電源控制任務將運行于下位機；CNC系統運行于上位機嵌入式Linux中,其主要任務及編號如表1所示。

表1 CNC系統軟件任務分析

根據表1可知,WEDM CNC系統共需執行8個任務,按照任務性質,可分為周期性任務和非周期性任務；按照任務執行的實時性要求,可分為實時任務和非實時任務[10]。各任務的分類如圖2所示。

圖2 WEDM CNC系統任務分類

本文WEDM CNC系統軟件采用多進程架構實現,每個任務對應一個進程。Linux2.6以上版本的內核是搶占式的[11]。本文中,為保證實時任務高速穩定的運行,將5個實時任務進程的調度策略設置為SCHED_FIFO；其余3個非實時任務則采用默認的調度策略SCHED_Normal。

3 多核任務分配模型

3.1 問題描述

CNC系統所采用的主控芯片Exynos 4412是一種4核ARM9處理器,CNC系統軟件共有8個任務。實時任務必須以一定的頻率周期性運行,才能滿足WEDM CNC系統的實時性要求。各任務運行和互相通信存在CPU開銷,任務的運行開銷是無法避免的；運行于同一CPU核心的任務間通信開銷較小,任務間跨核心通信開銷較大；而單個核心運算能力有限,無法同時執行所有任務。

因此,解決上述矛盾的關鍵是通過合理的任務分配,使系統在滿足實時性要求和滿足所有任務的運行開銷的前提下,盡可能降低任務間通信開銷,從而降低整體CPU開銷,提升系統效率[12，13]。多核處理器的任務分配是公認的NP-Hard問題,通過建立軟件的多任務模型,利用模擬退火法等啟發式算法可以求出其最優解[14]。而在建立任務分配模型前,需要先做出一些假設：

假設1 由于操作系統只運行單一CNC系統,可為各進程分配盡可能高的優先級,使得絕大多數Linux系統進程的優先級相對較低,所以在本文中忽略系統進程的影響。

假設2 為了簡化模型,忽略Linux對于非實時進程睡眠時間獎勵機制的影響。

假設3 由于同一核心內運行的進程可通過Cache通信,同核心內通信開銷記為0。

WEDM CNC系統的TIG模型如圖3所示,可以表示為一個二元組G=(V,E),其中，V為執行開銷矩陣,E為通信開銷矩陣。圖中各結點表示各任務的執行開銷,每條邊表示相應兩個任務之間的跨核心通信開銷。

圖3 WEDM CNC系統任務無向交互

因此，該多核任務分配問題的抽象化描述：4核系統要執行任務T,有四元組為：Σ=(T,V,E,X),其中,T為任務的集合,表示為{t1,t2,t3,t4,t5,t6,t7,t8}；V為執行開銷矩陣,表示為[v1v2v3v4v5v6v7v8],其中,vi為ti的執行開銷；E為通信開銷矩陣,矩陣大小為8×8,其中，元素eij表示任務ti和任務tj在不同核心間的通信開銷,eij=eji,且eii=0；X為任務分配矩陣,矩陣大小為8×4,若xik=1,表示任務ti在核心k上執行,否則，xik=0。

同時,需要設計一個目標函數cost作為優化目標,該cost函數應反映出，在給定的任務分配方案下,整個系統的總開銷。在該線切割CNC系統中,定義系統總開銷為任務執行開銷costv與任務間通信開銷coste之和

cost=ωcostv+coste

(1)

其中，ω用于調節通信開銷和執行開銷之間的差異,通過在Exynos4412上測試可知,執行開銷時間較通信延遲時間大一個數量級,可認為，前者對實時性的影響比后者要大一個數量級左右,因此，可確定ω=10。

3.2 開銷矩陣的數值化

WEDM CNC系統中大多數任務是周期性任務。綜合考慮單次執行耗時以及其執行頻率兩個因素,定義任務ti的執行開銷vi為

vi=ci×qi

(2)

式中ci為任務ti單次執行的耗時,ms;qi為任務ti要求的最低執行頻率,Hz。

對于非周期性任務(如G代碼解釋),在正常加工時不運行,不參與CPU資源的競爭,其最低執行頻率可認為是0,即執行開銷為0。WEDM CNC系統各任務執行開銷如表2所示。歸一化后,可得到執行開銷矩陣V=[0.578,0.323,0,0.303,0.856,0.641,1,0]。

表2 WEDM CNC系統任務執行開銷

根據表2可知,所有任務的執行開銷總和∑vi大于3 000,顯然至少需要4個核心同時參與運算。因此,為鼓勵算法使用更多的核心,均衡各核心負載,定義整個系統的執行開銷為各核心執行開銷的最大值,可表示為

costv=max(V·X)

(3)

計算任務間通信開銷時,主要關注耗時較高的跨核心通信,可通過模糊綜合評價法定量評價。提出通信頻率、單次通信的數據量大小(以下簡稱數據量大小)和延遲要求3個評價指標。利用層次分析法(analytic hierarchy process,AHP),得到權值向量A=[0.18 0.12 0.70]。再針對圖3中每一條邊eij,提取其在各指標的量化值：

1)通信頻率方面:對于任意eij,其對應通信頻率指標fij取任務i與任務j中執行頻率的較小值;

2)數據量指標方面:根據各通信單次傳輸數據量的大小量化；

3)延遲要求方面:考慮到周期性任務較非周期性任務對通信延遲更敏感,定義通信延遲要求dij為任務間跨核心通信的延遲lij與通信頻率fij之積

dij=lij×fij

(4)

對各指標建立三個評價等級(低,中,高),根據各指標量化值的極值和均值,構造正態型隸屬度函數。計算eij各指標在各等級的隸屬度,可得評價矩陣Rij；設綜合得分向量F=[1 2 3],可得對應的通信開銷值

eij=A·Rij·F

(5)

經過整理與歸一化,可得到WEDM CNC系統的任務通信開銷矩陣E,對于任意的任務分配矩陣X,其對應的系統通信開銷coste可表示為

(6)

綜上所述,求得執行開銷矩陣V和通信開銷矩陣E后,對于給定任務分配矩陣X,可計算對應損失函數cost。以損失函數cost作為目標函數,利用模擬退火法[15]對任務分配矩陣X進行尋優,即可得到最優的任務分配方案。

3.3 引入處理器負載約束的模擬退火尋優

模擬退火法是一種經典尋優算法,實現簡單,使用靈活,不易陷入局部最優。表2中,任務的執行開銷vi即為1 s內該任務至少需要占用CPU的時間。顯然,當同一核心中各任務的vi值之和大于1 000時,該核心無法滿足所有任務的執行開銷,該分配方案是不可行的。即，通過執行開銷矩陣V,可建立起任意核心分配方案中,單一核心內vi值之和小于1 000這一重要的約束條件。

而經由執行開銷矩陣V、通信開銷矩陣E和任務分配矩陣X共同定義的損失函數cost無法表達上述約束條件。所以，需要將處理器負載約束與模擬退火法結合起來,對分配方案進行尋優。

結合處理器負載約束的模擬退火法流程如下：

1)設定初始溫度H0,結束溫度He,降溫速率r以及連續拒絕次數K。

2) 對新生成的方案利用處理器負載約束過濾。對于滿足約束條件的新方案,若其cost值更小,則立即接受該方案,若該方案導致cost值增加了,則按一定概率P接受該方案,P的取值為

(7)

式中 Δcost為新舊方案損失函數的差值,H0為當前溫度值。在尋優的初始階段,溫度較高,接受較差方案的概率較大,有利于跳出局部最優解,而隨著溫度降低,P逐漸趨近于0,算法幾乎只接受較優方案,有利于更快收斂。

3)終止條件判定。若連續K個新解都被算法拒絕,則以當前解作為最優解輸出并結束,若不滿足終止條件則降低溫度并重復上述操作。

執行上述模擬退火法對WEDM CNC系統的任務分配問題進行尋優,設定初始模擬溫度為100,退火結束溫度為0.1,降溫速率為0.98,經過多次實驗,損失函數值與溫度值隨尋優次數的變化如圖4所示。從圖中可看出,該尋優算法不僅有跳出局部最優解的能力,而且在300次迭代內即可找出基于4核處理器的WEDM CNC系統任務分配的最優解,在多次重復實驗中,所得到的最優解一致為

(8)

圖4 損失函數值、溫度與尋優次數變化關系

因此,得到的最優任務分配方案為：核心1負責t1,t2和t8；核心2負責t3,t4和t6；核心3執行t5；核心4執行t7。在Linux中,各個核心有相對獨立的任務隊列,在完成多核任務分配后,即可確定各任務在其對應任務隊列的優先級。

為WEDM CNC系統各任務設置調度參數,利用sched_setscheduler()系統調用設置任務的調度策略與優先級,利用sched_setaffinity()系統調用設置各任務的CPU親和度,將任務固定在對應的CPU核心任務隊列中。

運行CNC系統,利用top命令查看各任務的CPU資源占用情況如圖5所示,從圖中可以看出,在使用改進的模擬退火算法進行多核任務分配后,充分發揮了多核處理器的運算性能。

4 結 論

本文根據線切割工藝需求,對WEDM CNC系統進行了任務分析,建立了CNC系統的TIG任務模型。根據WEDM CNC系統特點,對問題進行抽象化描述,利用模糊綜合評價法對任務模型進行定量分析。引入處理器負載約束改進模擬退火法,使其能在考慮任務周期的同時快速收斂到最優方案,并進行實驗。結果表明：WEDM CNC系統經上述建模優化后,充分利用了多核處理器的性能,達到了線切割工藝的實時性要求。