欢迎访问一起赢论文辅导网
博士论文
当前位置:首页 > 博士论文
开放式数控系统的低能耗和可靠性调度算法
来源:一起赢论文网     日期:2018-10-09     浏览数:1998     【 字体:

 式数控系统主要分为 NC 嵌入 PC 型、PC 嵌入 NC 型和全软件型 NC3 种类型结构[1]。采用嵌入式 PC 数控系统可使开放式数控系统随着 PC 技术的发展而升级。开放式数控系统作为一种典型的实时系统,是数控机床的核心部件。数控系统采用编程指令实时控制数控机床的运动位置,可以通过伺服系统内的位置闭环、速度环和电流环的调节,完成程序规定的加工任务[2]。数控系统不仅要求规定在截止期限内完成任务,而且要保证任务的正确执行。随着多核平台以其强大的计算能力被广泛应用在实时系统[3],例如 AMD APUIntel Haswell,龙芯 3B1500 ARM11 MPCore等处理器。尽管多核芯片系统(Multicore System-on-chipMPSOC)的多核架构已被用于开方式数控系统中,但带来的系统能耗则越来越高,高能耗带来的高温会导致系统发生故障的可能性增加,进而降低数控系统的可靠性[4]。因此,设计满足高可靠低能耗的开放式数控系统成为一个非常重要的问题。 在开放式数控系统方面,为方便快捷地开发出专用控制器,允许系统进行二次开发。文献[5]提出开放式专用数控系统的核心模型包括:功能模型、数据模型、结构模型和行为模型,该模型采用嵌入式和多CPU架构实现了专用数控系统的分布式操作。文献[6]提出面向开放式数控系统的一种基于预分配的空闲挪用算法。算法开始前,采用预分配算法为实时周期任务预留处理器时间,使得在调度周期任务时空闲时间尽可能提前。在调度非周期任务上,采用最大的可用空闲时间机制,实现以较小的计算和较低存储开销下获得最短的非周期任务响应时间。 在降低能耗方面,动态电压调节(Dynamic Voltage Scaling,DVS)和动态电源管理DPMDynamic Power ManagementDPM)应用于能耗优化。DVS降低能耗通过调整处理器的电压,DPM利用空闲时间的处理器和关闭电源,以减少静电能耗的产生[7]。多核处理器通过权衡空闲时间长短,利用DVS调整电压或者使用DPM关闭空闲处理器。同时考虑转换开销和处理器间通信能耗。在文献[8]中,提出了一种能耗感知调度技术,以最小化能耗同时满足吞吐量和响应时间的要求。在文献[9]中,提出了一种能耗管理算法,以探索在单处理器系统中使用流水线和并行处理技术。但这种基于单处理器的技术不能直接应用于多核系统。 实现对瞬态故障的容错,需要故障检测机制[10-11]。然而,常见的故障检测机制不能满足数控系统高可靠性的需要,而N模块冗余不需要额外硬件检测故障,而是使用多数投票的方法进行故障检测和容错[10]。由于所有模块不可能同时出现相同的错误结果,因此多数投票可以实现对系统故障的检测和容错[10]。但N模块冗余需要消耗更多的能耗开销来实现容错[11]。 为解决基于嵌入式数控系统的可靠性和低能耗之间的协同调度问题,本文首先对依赖任务的有向无环图(Directed Acyclic GraphDAG)进行建模,使其成为不具有依赖的任务,消除有向无环图任务的优先关系,然后执行协同优化算法以获得更好的能耗结果。该算法利用N模块冗余技术,在任务执行相同的副本,并对其结果以投票方式输出。如果多个备份执行的结果相同,则执行正确,并回收容错阶段备份任务的空闲时间。否则,执行容错阶段的剩余副本完成容错。算法充分利用多核架构优势,采用流水线并行执行任务,在任务时序约束下,实现多核处理器系统上的低能耗和高可靠的目标。 1 系统模型与能耗模型 1.1 实时任务模型 作为数控机床的控制核心,数控系统的加工任务不是独立的而是相互依赖,需要处理轨迹插补、位置控制、运动控制等周期性任务,后续任务的完成需要前一个任务的数据。因此本文研究数控系统中的实时周期性依赖任务的调度。 定义1  有向无环图(DAG)来表示一组周期性轨迹插补任务的依赖关系。DAG是数据流图(DFG)的一种特殊情况。DFGG=<V,Ed,CM>是节点加权和边加权的有向图[12],其中V是节点集,每个节点表示迭代中的任务,Ed是连接两个节点的有向边集合,  是有向边集合E映射函数,表示两个相邻节点之间的延迟,CM(u)uV)用于计算节点u的时间函数。 定义 2  DAG 的循环周期指计算无延迟有向边所组成的最长路径需要的时间。同一次循环的相关性使用无延迟边表示,不同次循环间的相关性利用延迟边表示。带延迟边Ed(uv)G(E)表示节点V的依赖第i次循环产生的数据,而节点u的依赖数据在第(i-G(Ed))次循环产生。每个节点上的数字表示任务执行需要的时间,“|”表示节点间需要1次延迟,“||”表示2次延迟。 定义3  一个任务集合,有n个可并发执行的DAG任务{G1G2G3,…,Gn},系统中存在M个可用的并行处理器。每个DAG任务都包含若干个子任务集   ={J1J2J3,…,Jk}Ji=(  ,Ti),i =1,2,,k,同一任务的多个子任务具有一定的时序依赖关系,执行存在先后关系。 在每个执行周期内,必须在截至时限 要求下执行结束。n为周期任务的数目,Ti为任务的周期,任务的周期都等于其截至期限,  为任务在处理器最大速度下的执行时间,即最坏情况下的执行时间。表1是一个数据依赖图模型用于描述一个周期任务流包括执行时间和对应的能耗。图1是基于表1DAG模型实例,其中每个节点代表一个任务,两个节点之间的边表示任务优先级关系。 表 1 数控系统周期任务流的时间和对应能耗实例  任务高频 低频t20t EJ1 5 10 5J2 3 12 6 3J3 1 4 2 1J4 3 12 6 3J5 1 4 2 1E 1 数控系统周期任务流 DAG 模型实例 重定时技术(retiming )利用平均分配 DFG 的延迟实现最小的循环周期[13]。在 DAG 中将节点 V的每条输入边的延迟,通过 V 推向其每条输出边,通过仅改变节点初始分配值的方式,保持节点间的相关性,而初始分配可以通过装入来实现[13]。实际上,每一次的重定时等同于一次软件流水操作。 1.2  能耗模型和可靠性模型 假设处理器速度频率或速度可以连续调节。当任务 Ji在速度  下执行时,任务实际执行时间为   /  。对于整个任务集合对应的速度可以表示为 S   ,   ,   , ,   ,这里iS 是任务 Ji运行时对应的速度。本文采用文献[14]的功耗模型,系统的功耗(P)为:                         ·  。                (1) 式中:   表示系统的静态功耗,当整个系统处于关闭状态时   0;静态功耗主要包括系统的基本电路能耗和维持系统时钟以及主存和 I/O 设备在睡眠状态下的功耗;     表示与处理器频率无关的功耗;     为依赖于处理器频率的动态功耗,包括 CPU 功耗以及其他依赖于处理器速度产生的功耗;    为系统有效的负载电容;m 为动态指数( ££32 m )h 表示系统状态,当系统处于活动状态时 h=1;当系统处于睡眠状态时 h=0。当系统处于活跃状态,一个任务在  /2 个备份下的能耗可以表示如下:         ,       ,     ,           。       (2) 式中:   为处理器状态转换开销,     为处理器间通信能耗开销。 定义 4  任务的可靠性作为任务成功执行的概率。瞬时任务出错概率符合泊松分布[14]。对于支持动态电压调节的实时系统,由瞬时错误引起的任务平均出错率和处理器调整频率  (对应电压 V)之间的关系,可以表示为: λ   λ0 10 · 1   1       。                           (3J1J2J4J5J35311J1J2J4J5J353113(a) (b)开放式数控系统的低能耗和可靠性调度算法1 邓昌义12,郭锐锋2,段立明12,王  帅12,杜少华3 (1.中国科学院 沈阳计算技术研究所,辽宁 沈阳 1101682.中国科学院大学,北京 1000493.沈阳高精数控智能技术股份有限公司,辽宁 沈阳 110168) 摘要:为充分利用多核处理器的并行能力,同时在保证数控系统可靠性约束下实现系统低能耗。在任务级粗粒度软件流水线技术基础上,首先提出非依赖有向无环图算法将周期性依赖任务转换为基于重定时的一组独立任务,通过任务并发执行和动态电压调节技术降低系统能耗。其次,在保证系统可靠性方面,算法分为无错阶段和容错阶段两个阶段。在无错阶段,一个任务的多个副本同时执行,通过投票确定任务是否执行正确。当不一致时任务进入容错模式。在容错模式下,剩余副本独占处理器以最高速度完成容错。实验结果表明,所提出的算法在保证数控系统可靠性前提下,可以降低系统能耗,相比已有算法不仅具有更高的可靠性而且能耗更低。 关键词:数控数据流;多核处理器;实时操作系统;能耗;可靠性 中图分类号:TP311      文献标识码:A Cooperative optimal scheduling algorithm for low power and reliability for open CNC system DENG Changyi 12GUO Ruifeng 2DUAN Liming 12WANG Shuai12DU Shaohua3 (1.Shenyang Institute of Computing TechnologyChinese Academy of SciencesShenyang 110168China2.University of Chinese Academy of SciencesBeijing 100049China3.Shenyang Golding NC Intelligence Tech. Co.Ltd.Shenyang 110168China) Abstract:To  make  full  use  of  the  parallel  ability  of  multicore  for  ensuring  the  real-time  system reliability constraints and low power consumption.Firstlya novel non-dependent directed acyclic graph algorithmisgiven  based  on  the  coarse-grained  software  pipelining,which  can  transform  a  periodic dependency  task  graph  into  a  set  of  independent  tasks  with  the  retiming  technique.The  system  energy consumption  can  bereduced  by  the  task  parallel  execution  and  dynamic  voltage  scaling.Secondlyin terms  of  guaranteeing  system  reliability the  algorithm  isdivided  into  two  phases:fault-free  and fault-tolerant.  In  the  fault-free  phasemultiple  versions  of  thetask  areexecuted  at  the  same  timeand results  of  multiple  versions  areused  for  the  majority  voting  to  determine  whether  the  task  has  been executed  successfully.If  notthe  task  will  enter  thefault-tolerant  mode.In  the  fault-tolerant  modethe remaining  copies  performed  the  fault  tolerance  at  the  highest  speed  in  an  exclusive processor.Experimental  results  show  that  the  proposed  algorithm  can  reduce  the  system  energy consumption under the premise of guaranteeing the reliability of the systemwhich yields high-reliability and lower energy consumption than the existing algorithms. Keywordsdata  flow  in  computer  numerical  controlmulticore  processorreal-time  operating systemenergy consumptionreliability                                                    收稿日期:2017-02-07;修订日期:2017-03-30ReceivedRevisedAccepted. 基金项目:国家科技重大专项项目(2014ZX04014-021)Projectsupported by the National Science and Technology Major Project of the Ministry of Science and TechnologyChina(No.2014ZX04014-021). r vmax r v , r u 1 ,               如果 v u 的父节点 0,                                                  如果 v 是叶子节点                  (10) DPDAGA 算法中将每个节点的初始重定时值初始化为 0,找出所有叶节点并将它们放入队列 Q中。Q 的当前尾部元素存储在名为 e_value 的变量中。计算以广度优先的方式进行。当判断节点 u的父节点 v 是当前队列 Q 的尾部元素时,不需要将节点 v 放入 Q,因为它会产生不必要的冗余计算,故 e_value 变量是非常有用的。在获得每个节点的重定时值后,生成仅具有独立任务关系的重定时任务图 Gr。算法的时间复杂度为 O(n),主要来自对节点的出队入队操作。 步骤 1  DPDAGA 算法以周期性依赖任务图 G 为输入,对 G 的各个节点进行遍历,并赋值 r(u)0。 步骤 2  遍历 G 的所有节点,如果其中一个节点 u 是叶子节点则将 u 加入队列 Q,如果 u 是尾部元素则 e_valueu。 步骤 3  如果每个 u 的父节点 v 存在,则根据式(10)计算:r(v)max{r(v)r(u) + 1};如果 e_value v,则将 u 加入队列 Q,e_valuev。 步骤 4  重复以上遍历,直到 G 遍历完。输出每个任务重定时值 r 和它的任务图 Gr2.2 低能耗与可靠性协同优化调度算法 为了保证数控系统的可靠性,在多核平台上结合 DVS 技术采用具有低能耗的 N 模块冗余技术实现系统的可靠性和低能耗。为此,提出了低能耗与可靠性协同优化调度算法(Co-optimal Scheduling Algorithm for Low Power and Reliability on MulticoreCSALPRM)。所提出的 N模块冗余算法分为两个阶段: (1)无错阶段:系统运行在无错阶段,每个任务的  /2 个备份并行执行。对于每个任务,将比较 N/2 任务副本的结果。如果投票结果相同,则没有故障发生,任务成功执行。当结果不相同时,系统临时切换到容错阶段。 2)容错阶段:系统执行剩余备份任务部分,剩余的副本以独占模式执行完成投票。由于任务的 N/2 副本已经在无错阶段中被执行,因此在容错阶段中,执行相同任务的剩余 N/2 副本,执行完整的多数投票(至少大于等于 2 个任务备份)来容错故障。  图2  容错模式下任务独占处理器过程 任务容错模式下,如图3a每个处理器最多可以和其他处理上的一个任务并行执行。图2b中的第一步,J2在处理器执P1执行期间和处理器P2上的J3J5J2发生了重叠并行,当任务在容错模式执行完BJ1J2BJ2J3J4J5(a)(1)P3P2P1J3BJ1J2 J3J1 BJ2J3J4J5J1 BJ2J3J4J5J1 BJ2J3J4J5J1(2) (3)(4)(b)     最大情况下的任务平均出错率,这里      1 。低频率或者低电压将导致由瞬时错误引起的任务错误率增加。由于       ,得   1 (>0)是一个常量,表示任务出错对 DVS 的敏感量。即当处理器处于最低的频率工作时,具有最高的失效率λ   λ · 10 。 定义 5  系统的可靠性为所有任务成功正确执行的概率。一个任务按最坏时间  执行,在处理器频率 f 下的正确执行的概率为[15]:          ·      。                             (4) 定理 1      , ,   表示系统的可靠性,即每一个任务成功执行的可能性。如果任务出错,则使用空闲时间恢复第 j 个出错的任务。规定   表示系统要保证的稳定性。当整个系统存在 j 个出错任务时,其可靠性为:     , ,      ·  ·   , ,  1     ·      ·    ·   , ,   。        (5) 证明  当整个系统不存在任务时,可靠性为    , ,  ∏         。相反,实例任务 Ji的的任务出错率   为:1    。当系统中出现一个任务需要容错时其可靠性为:                , ,      ·  ·   , ,  1     ·      ·  ·   , ,  。   (6) 推广到一般模型,当有 j 个任务需要容错,此时系统的可靠性为式(5)。式中加号前半部分表示任务 J1 成功执行,余下的 j 个备份任务可以给后续任务使用;加号的后半部分表示 J1执行失败,后续任务需要 j-1 个备份任务容错。 问题描述    保证系统可靠性前提下找到最优的处理器频率使得总能耗 E 最小: 最小化:        ,       ,     ,            。      (7) 同时满足约束条件:                , ,     ;                         (8) ∑       /    。                          (9) 式中:      ,    为容错任务所需总空闲时间,D 为最坏截止期限。 2 低能耗与可靠性协同优化调度算法 2.1 非依赖有向无环图算法 非依赖有向无环图算法(Non-dependent Directed Acyclic Graph AlgorithmDPDAGA)用于将周期性 DAG 变换成仅具有数据交互的非依赖性任务。根据重定时的定义,为了将周期性相关 DAG变换为一组独立任务,DPDAGA 在原始 DAG 的每个边上添加至少一个延迟。同时,避免在每个边上的不必要的冗余延迟,任务非依赖算法必须保证每个节点的最小重定时值。基于该规则,可用式(10)计算每个节点的重定时值: 模式下执行,多核任务重叠会将引起多处理器间的任务不能同步。因此,需要对容错阶段的任务并行执行做出调整。如图2b所示,J2和任务J3在空间上发生重叠,移动J3以及它的后续任务,直到J2J3之间没有重叠,移动的时间量为 ∆ ,也即是J2任务的完成时间和J3任务的开始执行时间之差。基于这个规则,在容错模式下实现出错任务独占处理器,同时空间上和其他处理器最多实现一个任务并行执行,经过四步实现容错模式下独占处理器。 当任务成功执行,容错模式将会把备份任务丢弃,释放空闲时间用于降低能耗。如图3所示,容错阶段可以被回收的空闲时间有三种情形: 1)情况I(如图3a):如果除Ji之外没有任务,则从调度表中丢弃Ji时,释放的空闲是       ,其中  是Ji的最坏情况下的执行时间,     是比较结果(多数投票)或保存结果所需的能耗开销。 2)情况II(如图3b):如果Ji是执行时间最长的任务,释放的空闲时间:  max   ,则从调度中丢弃Ji之后,被回收空闲时间为:  max        3)情况III(如图3c):如果存在大于Ji的一个任务Jn,则在从调度中移除Ji之后,将无空闲时间。因此空闲时间计算公式表示为:         ,仅当   存在  max   ,  max   0,                                                  (11)  3 回收容错阶段空闲时间 算法的时间复杂度是O(N×M),主要来自函数Tolerance_task(Ji)对调度序列任务中出错任务的查找,以及出错任务Ji独占处理器移动其他处理器重叠任务所需要的操作。其中N是调度序列SQ的任务数,M是处理器数目。CSALPRM算法如下: 输入: 独立重定向图GrD(任务截止期限)M(处理器个数);每个任务设置 N/2 个任务备份数 输出: 调度序列和系统能耗 1.初始化调度序列SQ= ∅和当前调度时间长度L0. 2. 每个任务分配初始电压,按照任务处理时间降序排列. 3.每个任务分配N个并行拷贝 4.根据初始任务序列,将 N/2 个并行拷贝分配给不同的处理器上,获得一个新的执行序列和执行时间长度 5. If (LD )6.      则新的SQ序列是可调度的,breakBJi(a)PnP1 BJiBJnBJiBJn(b) (c)任务时间最长的任务JL,计算通信开销,增加该任务的电压,获得新调度序列和当前调度时间长度L 13. Else 14. 选择调度序列中执行任务时间最短的任务Js,计算通信开销,降低执行该任务的电压,增加任务执行时间∆t 14. If (L+<= D ) 16. 更新调度序列SQ和当前调度时间长度L=L+∆  17. Else 18. 获得新调度序列SQbreak 19. End If 20. End If 21.End While 22.任务执行阶段,在不同处理器上同时得到一个任务JiN个不同备份任务的执行结果 23.If(RT(Ji)==RT(Ji)) 24. Ji执行正确,break 25.根据式(11)回收容错阶段BJi备份任务的空闲时间 26else 27.无错模式中断,标记中断位置IR 28.启动容错模式,出错任务独占处理器,调用Tolerance_task(Ji) 29.   If SQ=&Slack_time>to 30.处理器进入睡眠模式 31. Else 32.保持当前处理器速度运行 33.End IF 34. End IF  Function Tolerance_task(Ji) 1.  For (Jiin SQ) 2.  Fori=0i<Mi++3.  If 处理器上的备份任务 BJi,有其他处理器上多个任务与其并行重叠执行例如 Ji+1Ji+2 4.  Then 5.  =BJi的完成时间-Ji+2的开始执行时间(Ji+2是其中最长执行时间任务) 6.  Ji+2以及其处理器上的后续任务向右移动∆  7.  Endif 8.  Endfor 9.  Endfor 10.  处理器以最大速度独占处理器执行备份任务 BJi,得到执行结果 RT(BJi) 11.  Return RT(BJi)and IR 3 能耗与可靠性实例分析 3.1 能耗实例分析 下面考虑调度一个有依赖关系的应用程序流,对其进行能耗优化。采用表1的任务实例,假设有4个处理器,每个处理器都支持动态电压调节。功耗为:      ·  [14],不失一般性,假设    = 1 NF,电压和频率对应关系为(2V1 GHz)(1V0.5 GHz)。每个任务的执行时间和对应的高电压低电压能耗如表1,这里时间单位是ms,能耗单位是m J。为了更好地阐明问题。假设处理器睡眠模式下能耗为0.1 W,通过总线的读写通信能耗为0.5 W,每个任务之间的通信时间是1 ms。所有任务完成续的无错阶段没有发生错误,在容错阶段的预先执行可能变得无用,但是它对平均能耗的影响可忽略不计。这是因为仅当在无错阶段中发生故障时才预先执行。 从可靠性的角度来看,这种机制增强了系统的可靠性。从平均能耗的角度分析,考虑图5中的J2J4。假设任务执行出现故障的概率为10-4J2J4的能耗为12m J12m J。当发生故障时,系统只在无错阶段执行J2,消耗2×12 = 24 m J。如果在无错阶段中执行J2期间发生故障,系统将在容错阶段执行BJ2BJ4,消耗(12+12= 24 m J。因此,执行J2J4的平均能耗是(1-10-424+10-424+24= 24.0028 m J,这和没有故障发生(24m J)时的能耗非常接近,平均能耗与无故障能耗相差小于0.01%。因此预先执行对能耗影响极小,可忽略不计。 3.3 任务集的可调度性分析 定理2  如果  是在某一个处理机故障的情况下处理机Pk上的任务集。   最大执行时间∆ max由式(12)计算,  的容错截止期FD由式(14)计算。如果  满足∆ maxFD,则任务集  可调度;否则   不可调度。 ∆ max     =∑ ∆ max/Ti Ji ×Ci+∑   ∆ maxJi ×Di (12) 此时,  Ti,           且t BJi    BJ Ti1, 且t  BJi 13 FD     Tmax, 无错阶段BJmax,容错阶段                (14) 证明  由于任务的优先级是由高到低进行分配的,    是当前分配的任务,且   -{    }已经是可调度的,只需保证    的iC 小于其截止期即可,    的是   中执行最长的任务且其iC 应该等于在时间∆ max      内   所需要的计算量。在出现处理机故障时,  上的任务仅有容错阶段任务:   (1).任务在无错阶段每个周期Ti内都执行一次,故在时间t内共需执行 t/Ti ,当任务在处理机Pk上,所需的计算时间量为 t/Ti ×Ci,这部分时间为式(12)等号后的第一部分;   (2).在容错阶段,第一个请求必须在恢复时间BJi内完成,而后续请求的周期都为Ti,因此如果tBJi,则仅第一个请求在时间[0,t]被执行,= t/Ti ,否则在时间[0,BJi]内请求执行一次,在[BJi,t]内请求执行  t  BJ  /Ti ,此时 =  t BJ  /Ti +1。      综合(1)(2),可由式(12)计算得到    的iC 。对于    的容错截止期,    为在无错阶段任务时,FD(    )为    的周期Tmax。当     为容错阶段时,由于Tmax>BJmax,只需保证      的第一个任务的iC 小于BJmax,则       在以后的周期中均可调度,故此时FD(    )BJmax。显然如果∆ maxFD (    ),则任务集   可调度。证毕. 4. 实验结果与分析 实验采用沈阳蓝天数控GJ400,系统处理器采用支持动态电压调节的低功耗64位龙芯3B-1 500处理器,该处理允许调整的电压范围为1.01.3 V,对应可变的处理器频率1.0 GHz1.5 GHz[17]。蓝的结果进行多数投票以容错故障。在容错阶段,BJ2独占处理器阶段时不执行J3,因为在检测J2中的故障之前它已经成功完成,因此不需要执行。当在容错阶段执行BJ2时,J4并行执行,其结果保存在内存中,以便它可以用于以后的投票。在执行块BJ2之后,系统切换回无错阶段,并从其被中断的点继续执行调度。在切换无错阶段之后,考虑关于任务J4的两种可能的执行情况: (1)如果在无错阶段图5b执行J4期间一个备份发生故障,当对其进行投票时,系统不需要切换到容错阶段,因为作为3个副本,一个副本的结果在无错阶段中被获得,另一个副本的结果已经存在于内部存储器中。 (2)如果在无错阶段图5a中执行J4期间没有发生故障,则不再需要在先前的容错阶段中预先执行J4的备份。  图5 在容错模式下调度任务 如果BJ4的预先执行出现故障。在这种情况下,当系统在无错阶段中执行J4时,如果没有故障发生(如图5c),则将BJ4的预先执行的结果丢弃,因此不影响最后的结果。然而,如果在无错阶段中J4的执行也出现故障(如图5d),由于预先执行的存储值也有故障,3个备份全部出错,此时系统不能容错该故障,调度失败。事实上,系统可以容错能力和备份任务数成正比,在3个备份中可以容错任何一个任务出错,在4个任务中可以实现任意二个错误容错。一般来说,系统可以容错每个任务的  /2 个故障[16]。在容错阶段中任务的预先执行(例如,图5中的BJ4)不仅可以提高可靠性而且不会对系统能耗产生显著影响,因为: (1)在容错阶段并行执行,预先执行不会施加任何时间开销。例如,在图5中可以看出。当系统必须在容错阶段中执行BJ2时,与其并行的BJ4预先执行。由于BJ2在独占处理器期间相对其他处理器在同一时间具有最长的执行时间,这意味着BJ4的预先执行会延长JB2。事实上,如果没有使用预先执行,在容错阶段期间将浪费处理器资源,因此使用事先执行有助于为容错阶段保留相对较少的空闲时间,从而更多的空闲可用于能耗管理。 J1 J2J1J2J3 J5J3J5BJ2BJ4 J5J5J4J4J1J2J1J2J3 J5J3J5BJ2BJ4 J5J5J4J1 J2J1J2J3 J5J3J5BJ2BJ4 J5J5J4J4J4J1 J2J1J2J3 J5J3J5BJ2BJ4 J5J5J4J4(a) (b)(c)(d)容错模式 瞬时故障 结果不一致 无错模式P4P3P2P1P4P3P2P17 ms,如图4a所示,该调度过程采用每个任务2个备份策略,所有处理器执行任务使用高电压。执行完毕后,对比结果,如果相同则该任务正确执行。没有任务执行时处理器进入休眠状态,这里先考虑所有任务都成功执行。此时执行图4c的任务,总能耗E=2×20×5+2×12×3+2×12×3+2×4×1+2×0.5×4×1+2×0.5×1+2×0.5×1+2×4×1+2×0.1×7+2×0.1×5= 368.4 m J。 图 4b 是利用 DVS DPM 算法以及软件并行技术。首先根据非依赖算法将图 1a 转化为图 1b。之后使用 CSALPRM 算法重新调度任务,调度结果如图 4b 所示。该算法为了尽可能降低系统能耗,使用软件并行技术,则数据依赖迭代产生的空闲时间可以被回收,用于降低处理器速度。但是需要考虑处理器内部通信开销,例如 J1J2J3J5之间的通信开销。基于此 DVS DPM 回收空闲时间降低系统能耗。所有任务在 15 ms 调度后,在处理器 P3P4剩下空闲时间,由于空闲时间不足够长,不能以补偿关闭或转换处理器状态开销,本文所提出的算法将分配与任务 J3相同的电压。整个能耗消耗 E=2×6×3+2×6×2+2×2×1+2×5×10+2×1×2+2×1×3+2×0.5×3+2×0.5×1+2×0.5×2= 180 m J。通过 CSALPRM 算法调度任务相比按正常顺序调度任务能耗节约 51.14%。可见经过并行优化的算法能够大幅度降低系统能耗。以上实例只考虑任务不出错情形下的能耗,而真实的执行过程任务会出现错误,此时调度实例见下节。  图4 使用软件流水并行技术和DVS技术调度DAG任务 3.2 可靠性实例分析 图5是所提出的N模块冗余技术在任务出错时如何工作。当没有发生故障时,系统执行无错阶段的调度如图5a所示,其中每个任务Ji1个副本被执行并且比较它们的结果。如果结果相同,则将其用作系统的结果。当任务Ji的结果不相同时,切换到容错阶段以独占处理器模式容错任务。在容错阶段中执行Ji的第3个副本,对3个结果进行多数投票以容错故障。然后再次切换至无错阶段,从它上次中断点继续执行,从而实现系统的可靠性。 图5a给出了当任务发生某些故障时所提出算法如何进行容错。假设任务J2出现故障,当比较J2的结果时,它们不匹配,因此系统暂时切换到容错阶段。在容错阶段中,J2的备份任务BJ2调度执行。(1) (2)P1Bus P2Bus P3Bus P41J1 J123456 Voting7J2 J2J1- J38 J3 J39 Voting10 Voting J5-J311J41213 Voting14 J5 J515 Voting1617J4P1Bus P2Bus P3Bus P41J1 J1234567 Voting8J4 J491011 Voting12 J2 -J1J3 J31314 Voting Voting15 J5 J5J31617 VotingJ2J2J5 -相对较少的节能(平均10.13),但CSALPRM可靠性更好。这是因为CSALPRM算法采用并行流水线技术,充分利用多核处理器的优势,而且在保证可靠性上采用N模块冗余,相对+HFT-LFT的错误检测机制更具优势,不仅能够最大限度保证系统可靠性,而且在系统无错时回收多余的空闲时间降低能耗。 表 2 不同任务下三种算法的出错率对比   图7 不同任务下3种算法的能耗对比 表2和图7分别显示了在八核处理器上执行每种类型任务的实验结果。从图中可以得到:CSALPRM不仅比+HFT提供更多的节能(平均15.18),而且具有更少的任务出错率,即CSALPRM更可靠。与-LFT相比,CSALPRM提供相对较少的节能(平均10.13),但CSALPRM可靠性更好。这是因为CSALPRM算法采用并行流水线技术,充分利用多核处理器的优势,而且在保证可靠性上采用N模块冗余,相对+HFT-LFT的错误检测机制更具优势,不仅能够最大限度保证系统可靠性,而且在系统无错时回收多余的空闲时间降低能耗。 4.2 处理器个数对能耗和可靠性的影响 从图中 8 可以看出,在任务数不变的情况下,随着处理器个数的增加,三个算法的能耗都降低,这是因为处理器个数多,处理器处于空闲的机率增大,用于 DVS 调节处理器速度的空闲时间就多,因而消耗的能耗少,但 CSALPRM 算法的能耗始终最小,这是因为 CSALPRM 算法将周期性依赖任务转化为独立任务,可以实现更高层级的任务并行。充分利用处理器的空闲时间用于降低能耗,同时对于长时间处于空闲的处理器采用 DPM 技术将其进入睡眠模式,进一步降低能耗。从图 9可以看出,随着处理器个数的增加,任务出错率降低,系统可靠性增加,这是因为处理器个数越任务出错率POF+HFT -LFT CSALPRM插补任务 10-4.35 10-2.35 10-8.65加减速任务 10-4.69 10-2.4 10-8.52运动控制任务 10-4.15 10-2.65 10-8.41任务实例00.10.20.30.40.50.60.7插补任务 加减速任务 运动控制任务归一化能耗+HFT LFT CSALPRM阶段的时间就越多,从而增强系统的可靠性。但所提出的 CSALPRM 算法,始终保持较低的出错率,说明所提出的算法使用 N 模块冗余的优越性。  图8 不同处理器数对能耗的影响  图9 不同处理器数对可靠性的影响 5 结束语 本文面向开放式数控系统研究基于国产 CPU 数控系统的低能耗和可靠性,提出了一种两阶段调度算法来解决数控系统在多处理器上调度具有严格时序约束的周期性依赖任务,同时考虑转换开销和通信开销。实现国产处理器下数控系统的高可靠性与低能耗的协同优化。提出基于粗粒度任务级软件流水线技术的 DPDAGA 算法,可用于将定期依赖任务转换为基于重新定时技术的一组独立任务,该算法能够充分利用多核处理器的优势,将任务调度并行化,增强系统调度效率。 考虑数控系统中任务加工过程可能出现的错误,在DPDAGA算法的基础上提出了低能耗与可靠性协同优化调度算法CSALPRM。在CSALPRM中首先采用N模块冗余技术,实现系统的高可靠性,同一任务执行不同副本,并将执行结果进行多数投票,决定任务是否需要容错。其次使用DVSDPM技术管理  容错阶段所产生的空闲时间,并且在运行时为任务分配动态空闲。该算法实现了数控系统的低能耗和可靠性之间的协同,增强了数控系统的整体可靠性。并且可以在支持DVS的多核处理器上使用,而不需要增加额外的硬件。 参考文献: [1]ZHOU  Zude LONG  Yihong LIU  Quan.Embedded  based  network  numerical  control  technology  and system[J].Chinese Journal of Mechanical Engineering200743(5)1-7(in Chinese).[周祖德,龙毅宏,刘泉.嵌入式网络数控技术与系统[J].机械工程学报,200743(5)1-7.] [2]  ZHOU  Gang WU  Yijie PAN  Xiaohong.Software  modules  real  time  scheduling  framework  in  CNC system[J].Journal of Mechanical Engineering200945(1)162-166(in Chinese).[周 刚,邬义杰,潘晓弘.数控系统软件模块实时调度方法[J].机械工程学报,200945(1)162-166.] [3]ANDERSON  J  H BARUAH  S  K.Energy-Efficient  Synthesis  of  Periodic  Task  Systems  upon  Identical Multiprocessor Platforms[C]//Proceedings of International Conference on Distributed Computing Systems.WashingtonD.C.USA:IEEE2004:428-435. [4] Zhu DMelhem RMossé D.The effects of energy management on reliability in real-time embedded systems[C]// //Proceedings of IEEE/ACM International Conference on Computer Aided Design.WashingtonD.C.USA:IEEE2004:35-40. [5] LIU NingWANG Gao.Development of open architecture special NC system based on embedded multi-CPUs structure[J].Computer Integrated Manufacturing Systems201218 (8):1854-1860(in Chinese).[柳 宁,王 高.嵌人式多CPU架构的开放式专用数控系统的研发[J].计算机集成制造系统,201218(8):1854-1860.] [6] LIU XianGUO Ruifeng.Preallocation-based hybrid task scheduling algorithm in numerical control system[J].Computer Integrated Manufacturing Systems201521(6):1529-1535(in Chinese).[刘 娴,郭锐锋.数控系统中基于预分配的混合任务调度算法[J].计算机集成制造系统,201521(6):1529-1535.] [7] XU RMELHEM RMOSS D.Energy-Aware Scheduling for Streaming Applications on Chip Multiprocessors[J]. 2007:25-38. [8] KIM N SKGIL TBOWMAN Ket al.Total power-optimal pipelining and parallel processing under process variations  in  nanometer  technology[C]//Proceedings  of  Ieee/acm  International  Conference  on Computer-Aided Design. WashingtonD.C.USA:IEEE2005:535-540.  [9] SHAO ZWANG MCHEN Yet al.Real-Time Dynamic Voltage Loop Scheduling for Multi-Core Embedded Systems[J].IEEE Transactions on Circuits & Systems II Express Briefs200754(5):445-449. [10] Aviziens A.Fault-Tolerant Systems[M].Morgan Kaufmann Publishers Inc.2007. [11] MILLER TSURAPANENI NTEODORESCU R.Flexible Error Protection for Energy Efficient Reliable Architectures[C]//Proceedings  of  International  Symposium  on  Computer  Architecture  and  High PERFORMANCE ComputingSbac-Pad 2010PetropolisBrazilOctober.DBLP2010:1-8. [12]XU RongbinLIU XinYANG Zzhuangzhuang ZHUANGet al.Directed acyclic graph real-time scheduling method based on deadline of task execution[J].Computer Integrated Manufacturing Systems201622 (2):455-464(in Chinese).[许荣斌,刘 鑫,杨壮壮,等.基于任务执行截止期限的有向无环图实时调度方法[J].计算机集成制造系统,201622(2):455-464.] [13] DICK R PRHODES D LWOLF W.TGFF Task Graphs for Free[J].199815(4):97-101. [14] EJLALI AAL-HASHIMI B MELES P.Low-Energy Standby-Sparing for Hard Real-Time Systems[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems201231(3):329-342. 功能模块如图5所示,其中运动控制器和PLC控制器负责进给驱动控制、主轴驱动控制及开关量控制,实现任务严格的实时性要求。任务管理器作为整个系统的管理中心,可以实现用户界面的操作信息,并为运动控制器与PLC控制器传递处理后的任务信息。在实验中,修改操作系统内核,以便在创建线程之前,使用系统调用将获得的任务相关信息发送到内核和调度程序。当任务 调 用 Pthread_create() 创 建 线 程 时 , 它 会 依 次 调 用 一 系 列 系 统 调 用 函 数 包 括 :Sys_clone(),Do_fork() Copy_process() 函 数 。 要 调 度 新 创 建 的 线 程 , 系 统 调 度 程 序 使 用Sched_fork()函数。 修改后,Copy_process()Sched_fork()函数将收集到的任务执行信息反馈到本文的能耗模型和可靠性模型,用于分析所提出的算法的能耗和可靠性。  图6 基于龙芯CPU的蓝天数控系统功能模块图 数控系统每执行一次轨迹插补任务周期 6ms,每次插补计算的结果通过命令寄存器分若干次传送到伺服控制单元以控制机床各个坐标轴的位移,位置控制任务的周期为 3 ms;每执行一次运动控制处理任务为 15 ms[6]。为了比较 CSALPRM 算法的效果,实验使用合成应用任务图。为此,使用任务图生成器 TGFF[17]TGFF 基准套件包含合成任务图,每个任务的周期按照数控系统的实际周期产生,任务类型包括插补任务,加减速任务和运动控制任务。当处理器长时间没有任务调度时,它进入睡眠模式并且仅消耗空闲能耗。数控系统可靠性试验,其中可靠性通过式(6)计算任务出错率    (1 R  )。使用式(3)的参数0l =10-6故障/s d=3 对故障率进行建模[14]。因此,对应于最大和最小电压,故障率在 10-6个故障/s 10-3个故障/秒之间变化。为了考虑故障检测机制对能耗和可靠性的影响,使用文献中实现的两种类型的软件故障检测机制: 1)重度故障检测机制(称为+HFT):具有高故障检测开销但相对高的故障覆盖。对于这种情况,假设系统使用基于代码和数据冗余,一致性检查和控制流检查的多种故障检测机制[10-11]为不同故障类型实现高故障覆盖。 2)轻故障检测机制(称为-LFT):具有相对低的故障检测开销以及低故障覆盖。对于这种情况假设系统使用较少的机制来减少检测覆盖,以降低故障检测开销的成本[19]4.1 能耗和可靠性分析 表2和图7分别显示了在八核处理器上执行每种类型任务的实验结果。从图中可以得到:CSALPRM不仅比+HFT提供更多的节能(平均15.18),而且具有更少的任务出错率,即CSALPRM更可靠。与-LFT图形用户界面(HMU)文件管理参数设置加工仿真PLC编程运动控制器……进给轴驱动控制主轴驱动控制任务管理器PLC控制器开关量控制任务加工信息用户操作信息信息反馈控制命令任务数据

[返回]
上一篇:考虑信息安全因素的多目标云工作流调度
下一篇:面向二进制程序的空指针解引用错误的检测方法