嵌入式电火花线切割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系统经上述建模优化后,充分利用了多核处理器的性能,达到了线切割工艺的实时性要求。