曹 俊, 蔣 毅, 楊書(shū)娟, 馮 飛

(江南大學(xué) 機(jī)械工程學(xué)院 江蘇省食品先進(jìn)制造裝備技術(shù)重點(diǎn)實(shí)驗(yàn)室,江蘇 無(wú)錫 214122)

0 引 言

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

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

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

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

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

圖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ù)將運(yùn)行于下位機(jī)；CNC系統(tǒng)運(yùn)行于上位機(jī)嵌入式Linux中,其主要任務(wù)及編號(hào)如表1所示。

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

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

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

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

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

3.1 問(wèn)題描述

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

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

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

假設(shè)2 為了簡(jiǎn)化模型,忽略Linux對(duì)于非實(shí)時(shí)進(jìn)程睡眠時(shí)間獎(jiǎng)勵(lì)機(jī)制的影響。

假設(shè)3 由于同一核心內(nèi)運(yùn)行的進(jìn)程可通過(guò)Cache通信,同核心內(nèi)通信開(kāi)銷(xiāo)記為0。

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

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

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

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

cost=ωcostv+coste

(1)

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

3.2 開(kāi)銷(xiāo)矩陣的數(shù)值化

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

vi=ci×qi

(2)

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

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

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

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

costv=max(V·X)

(3)

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

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

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

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

dij=lij×fij

(4)

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

eij=A·Rij·F

(5)

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

(6)

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

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

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

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

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

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

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

(7)

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

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

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

(8)

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

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

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

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

4 結(jié) 論

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