王慧锋;干玲剑
【摘 要】针对可编程逻辑控制器(Programmable Logic Controller,PLC)的编程语言不支持程序的并行编译,无法使控制程序并行执行于多核处理器的问题,根据功能块图的可拆分性,提出了用有向无环图(Directed Acyclic Graph,DAG)任务模型表示PLC控制程序的方法,并采用静态列表任务调度算法,优化DAG中的任务节点在不同CPU核上的分配调度,解决了PLC控制程序并行执行时会遇到的通信延时问题.此外,针对变量资源的竞争问题提出了使用互斥量的方法.实验结果表明,此方法能有效地将PLC控制程序并行运行在多核处理器上,大大缩短了程序的执行时间. 【期刊名称】《华东理工大学学报（自然科学版）》
【年(卷),期】2016(042)006
【总页数】8页(P820-826,850)
【关键词】多核处理器;并行执行;有向无环图;PLC控制程序;静态列表任务调度算法
【作 者】王慧锋;干玲剑
【作者单位】华东理工大学化工过程先进控制与优化教育部重点实验室,上海200237;华东理工大学化工过程先进控制与优化教育部重点实验室,上海200237
【正文语种】中 文
【中图分类】TP314
PLC是一种抗干扰能力强、可靠性高、使用灵活的基于单核处理器的控制系统,已广泛应用于钢铁、石油、化工、机械制造、汽车等各个行业[1]。缩短PLC控制程序的执行时间是提高PLC性能的主要方法,目前国内外学者研究设计了将程序移植到具有并行执行能力的FPGA上运行的方法[2-4],通过并行执行梯形图来缩短执行时间从而大幅度提高PLC的响应速度。多核处理器能够通过多个CPU核进行并行计算来减少程序的执行时间,但是目前针对控制程序在多核处理器上的并行执行的研究相对较少。在工业控制领域中,PLC控制程序的开发设计通常遵循IEC61131-3工业标准[5],而IEC61131-3标准规定的编程语言不支持程序的并行编译[6],即PLC工程师设计的控制程序只能运行于单核处理器上,无法直接在多核处
理器上并行运行。为了充分发挥多核处理器在工业控制领域的优势,设计使PLC控制程序在多核处理器上并行执行的方法具有重要现实意义。
真开心网
本文从函数层面根据功能块图可拆分的特性,考虑PLC控制程序中功能块之间的依赖关系,提出了一种基于DAG任务模型的方法。用DAG表示PLC控制程序,然后将基于静态列表的任务分配调度算法运用至PLC控制程序的在多核处理器上并行执行中,实现了控制程序的整体执行时间的缩短,同时也解决了PLC控制程序实际并行运行在多核处理器上时会遇到的通信延时问题。此外,本文还针对变量资源的竞争问题提出了采用互斥量的方法。
健忘患者逃出多核硬件平台结构对PLC控制程序的并行执行有至关重要的影响,例如处理器的CPU核数和通信机制会影响控制程序的执行时间和通信时间。多核硬件平台结构一般用拓扑图TG=(P,N),其中P表示内核节点集合,N表示连接内核的边集合。本文主要研究总线共享的同构多核处理器,它的各个CPU核处理速度相同,任意两个CPU核间的通信速率相等。如图1所示,m个CPU核挂载在共享总线上。本文设定同构多核处理器是全连通的,此时拓扑图可表示为TG=P。
2.1 概述
在自动化领域,工业控制程序通常使用IEC61133-3或IEC61499[7]标准进行建模。功能块图是IEC61133-3标准提出的一种最具发展潜力的编程语言,它能够形象地描述程序的并行性,具有功能块结构简单、有利于程序的结构化设计和满足代码重复利用的需求的优点。此外,功能块图程序具有良好的可拆分性,能够分段运行于多个CPU核上。因此,本文采用功能块图作为PLC控制程序模型。此外,控制系统提出的其他组件模型(例如FASA[8],Procom[9])也可以很容易地转换成这种模型。
2.2 功能块图模型
在模型中,控制程序被模拟为由功能块和连接线组成的一个网络。功能块主要分为复合功能块和基本功能块两种,其中复合功能块由其他复合功能块或基本功能块组成,所有的功能块都由存储信息的变量和处理信息的指令组成。功能块之间通过输入和输出变量进行连接,发送功能块的输出变量通过信号连接到一个接收功能块的输入变量,这种方式使得功能块之间具有依赖关系。在一段PLC控制程序中,在确定变量α的值之前,必须先确定变量β的值,则称α依赖于β,这种关系为依赖关系。依赖关系是分析控制程序逻辑的基础。
阀门控制是工业控制中比较经典的案例,在工业生产过程中具有广泛的应用。本文以阀门控
制为例介绍使PLC控制程序并行执行的方法,图2所示为阀门控制的一种功能块图(FBD)。
2.3 拆分PLC控制程序
为了使PLC控制程序能够并行编译,本文采用Beremiz开源软件将控制程序中的功能块图转化为C语言代码,但是,此工具得到的C代码是串行单线程的,并且只能运行在单核处理器上。为了能够使控制程序并行运行,先对功能块图的结构进行分析,然后以功能块为单位将控制程序离散化。
首先遍历生成的C代码,得到PLC控制程序中包含的所有功能块信息,包括功能块的名字、输入与输出变量以及信号连接线。根据这些信息,将功能块图中的信号连线转换成变量,并且保证每个功能块引脚上均存在变量。图3示出了拆分PLC控制程序为各个单独的功能块结构的具体流程。
在拆分PLC控制程序时,需要重点考虑的是信号连接线中的分支结构。在分支结构中,主连接线与各个分支的能流完全相同,因而需要为与分支及主干相连的所有功能块添加相同的变量。以阀门控制程序(图2)中的节点2、3、4所形成的分支结构为例,其信号连接线的替换结果如图4所示。
2.4 功能块之间的依赖关系
为了使拆分后的功能块能够有序地并行执行,还需要对PLC控制程序进行依赖关系分析。通过遍历拆分后的所有功能块的输入输出变量,到具有相同变量名称的输入变量和输出变量的不同功能块或者同一个功能块(考虑功能块有自循环的可能性),得到功能块之间的依赖关系,从而决定功能块之间的执行顺序。
此外,为了解决不同功能块在同一个核上或不同核上进行通信的问题,将多个功能块公共读写的变量设为全局变量。如果某个功能块改变了全局变量的值,它将影响到可以访问该变量的其他功能块,从而功能块之间实现了数据的传递。
3.1 DAG的基本概念
一个有向无环图G一般表示为一个二元组G=(T,V),其中T={τ1,τ2,τ3,…,τn} 表示图中任务节点τ的集合,τi表示第i个任务,τi的权值w(τi)为任务i的执行时间。V为图中所有有向边的集合,给定两个节点τi,τj∈T,vij表示从起点τi到终点τj的边,边表示任务之间的依赖关系,边上的权值c(vij)代表通信时间。前驱节点定义为pred(τi)={τx∈T:vxi∈V},后继节点定义为succ(τi)={τx∈T:vix∈V}。此外,满足pred(τi)=?的节点τi称为源点,而满足succ(τi)=?的节点称为汇点。
3.2 从功能块图到DAG
功能块图与DAG是非常相似的,功能块可以直接映射为DAG中的一个任务节点,功能块之间的依赖关系可以由DAG中的有向边来保存,功能块的执行时间也会被继承下来。由于本文主要考虑控制程序的并行执行问题,因此阀门控制程序中的各个功能块的执行时间使用文献[8]测量得出的结果,分别为:节点0为14 μs,节点1为6 μs,节点2为17 μs,节点3为9 μs,节点4为8 μs,节点5为9 μs,节点6为6 μs。为了使功能块图能够准确地转化为对应的DAG,还需要解决以下一些问题：
(1) 有向无环图中的任务节点之间是不存在循环的,而PLC控制程序中通常会存在内部循环体。事实上,由于记录功能块间关系的全局变量的值是可以向后传递的,也就是说存在内部循环的功能块之间的数据反向传递是自动完成的,不需要用有向边单独表示出来,但是为了补偿更新数据带来的附加延迟,在DAG中需要添加一个虚拟节点。
(2) DAG中的任务节点通常没有复合结构,而一个功能块可以拥有多个层级。本文的解决方案是将复合功能块作为一个任务节点,使复合功能块中的所有基本功能块分配到同一个CPU核上执行,节点的执行时间等于它所包含的基本功能块串行执行时间的总和。
全局变量一般存储在主存储器中,而访问主存储器通常会有几百个时钟周期的延迟。假设处理器的主频是1 GHz,访问主存储器的通信延迟大约为1 000个时钟周期,在不考虑缓存结构的情况下,通信的延迟时间为1 μs,因此阀门控制程序的DAG中所有边的权值都为1 μs。阀门控制程序的DAG表示如图5所示。
4.1 调度基本概念
在将一个由功能块组成的PLC控制程序转换成DAG后,需要解决的是DAG调度问题,即给DAG中每个任务节点合理地分配一个CPU核并且赋予一个开始时刻。节点τi∈T在CPU核p∈P上的开始时刻记为ts(τi,p),则结束时刻可表示为
荧光寿命测试其中w(τi,p)是τi在p上的运行时间。
在多核处理器TG=(P,N)上对有向无环图G=(T,V)的调度S一般可以描述如下:
所有节点的最晚结束时刻为S的调度长度,即程序的执行时间为radarsat
其中proc(τi)表示分配给τi的CPU核。
当一个节点的所有输入边结束通信时,该节点才可以开始在CPU核上执行,称该时刻为数据就绪时刻(Data Ready Time,DRT)。DRT是一个节点可以开始的最早时刻,可表示为
其中:tf(vij,proc(τi),p)为边vij∈V的通信结束时间;p为分配给τj的CPU核。
由于只有当边的起点和终点节点分配在不同CPU核上时,才会进行核间通信,因此DAG中边vij的结束时刻可表示为
海洋幼虫如果τi没有输入边,即τi为源点,那么对所有的p∈P,tdr(τi,p)=0。
对节点进行调度通常使用插入技术[10],使用该技术需要满足以下节点调度条件:
假定[A,B](A,B∈[0,])是CPU核p上的一个空闲时间区间,则当max{A,tdr(τi,p)}+w(τi,p)≤B时,τi可以安排在p上的[A,B]区间内。此时τi在p上的开始时刻为
4.2 静态列表调度算法
一般性的多核任务分配以及调度问题已经被验证是NP难题[11-12],因此很多文献研究启发式方法,期望得到一个近似最优的结果。静态列表调度算法[10]具有时间复杂度低、实用性
强、易于实现等特点,因此本文采用该方法来优化DAG任务节点的调度,具体步骤如下:
算法1:Static_List_Scheduling(G,TG)
如何选购家庭影院
输入:DAG G=(T,V)和拓扑图TG=P
输出:G在TG上的调度
(1) NodeList←Sort_Nodes(T);
(2) for each n∈NodeList do
(3) pbest←Select_Processor(n,P);
(4) Schedule_Node(n,pbest);
(5) end
Sort_Nodes()函数根据DAG中任务节点的依赖关系来确定所有节点的优先级,并建立调度列表。因为任务节点的优先级决定了任务的执行先后顺序,列表中节点的次序会影响调度结果。
文献[13]的实验结果表明,使用bottom level作为优先级进行节点排序的列表调度方法优于其他方法,因此本文使用的静态节点排序准则是按照节点的 bottom level 进行降序排列,如果两个节点具有相同的bottom level,那么随机排列各节点。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议