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

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

0 引 言

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

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

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

1 WEDM CNC系統(tǒng)硬件結(jié)構(gòu)

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

圖1 WEDM CNC系統(tǒng)硬件結(jié)構(gòu)

2 WEDM CNC系統(tǒng)任務(wù)分析

根據(jù)圖1所示W(wǎng)EDM CNC系統(tǒng)的硬件結(jié)構(gòu),走絲控制任務(wù)和脈沖電源控制任務(wù)將運行于下位機；CNC系統(tǒng)運行于上位機嵌入式Linux中,其主要任務(wù)及編號如表1所示。

表1 CNC系統(tǒng)軟件任務(wù)分析

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

圖2 WEDM CNC系統(tǒng)任務(wù)分類

本文WEDM CNC系統(tǒng)軟件采用多進程架構(gòu)實現(xiàn),每個任務(wù)對應(yīng)一個進程。Linux2.6以上版本的內(nèi)核是搶占式的[11]。本文中,為保證實時任務(wù)高速穩(wěn)定的運行,將5個實時任務(wù)進程的調(diào)度策略設(shè)置為SCHED_FIFO；其余3個非實時任務(wù)則采用默認的調(diào)度策略SCHED_Normal。

3 多核任務(wù)分配模型

3.1 問題描述

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

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

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

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

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

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

圖3 WEDM CNC系統(tǒng)任務(wù)無向交互

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

同時,需要設(shè)計一個目標函數(shù)cost作為優(yōu)化目標,該cost函數(shù)應(yīng)反映出，在給定的任務(wù)分配方案下,整個系統(tǒng)的總開銷。在該線切割CNC系統(tǒng)中,定義系統(tǒng)總開銷為任務(wù)執(zhí)行開銷costv與任務(wù)間通信開銷coste之和

cost=ωcostv+coste

(1)

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

3.2 開銷矩陣的數(shù)值化

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

vi=ci×qi

(2)

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

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

表2 WEDM CNC系統(tǒng)任務(wù)執(zhí)行開銷

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

costv=max(V·X)

(3)

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

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

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

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

dij=lij×fij

(4)

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

eij=A·Rij·F

(5)

經(jīng)過整理與歸一化,可得到WEDM CNC系統(tǒng)的任務(wù)通信開銷矩陣E,對于任意的任務(wù)分配矩陣X,其對應(yīng)的系統(tǒng)通信開銷coste可表示為

(6)

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

3.3 引入處理器負載約束的模擬退火尋優(yōu)

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

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

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

1)設(shè)定初始溫度H0,結(jié)束溫度He,降溫速率r以及連續(xù)拒絕次數(shù)K。

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

(7)

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

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

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

(8)

圖4 損失函數(shù)值、溫度與尋優(yōu)次數(shù)變化關(guān)系

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

為WEDM CNC系統(tǒng)各任務(wù)設(shè)置調(diào)度參數(shù),利用sched_setscheduler()系統(tǒng)調(diào)用設(shè)置任務(wù)的調(diào)度策略與優(yōu)先級,利用sched_setaffinity()系統(tǒng)調(diào)用設(shè)置各任務(wù)的CPU親和度,將任務(wù)固定在對應(yīng)的CPU核心任務(wù)隊列中。

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

4 結(jié) 論

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