基于DFT-MARTE模型的时序分析算法

徐 嘉，周 晴，杜家昊，王一华

(1.中国科学院国家空间科学中心 复杂航天系统电子信息技术重点实验室，北京 101499；2.中国科学院大学 计算机与控制学院，北京 101408)

0 引 言

随着航天事业的迅速发展，复杂的需求提升了航天嵌入式软件(aerospace embedded software，AES)的规模[1]，其开发成本和维护难度也越来越高，在需求阶段更易于降低开发成本及风险[2]。AES与外部接口数据交互复杂[3]，两者之间的联系以及AES内部节点通讯关系均可用数据流来简化表示。传统的数据流图(data flow diagram，DFD)能描述软件节点之间的数据交互关系[4]，但无法描述AES中具有时序特性的数据流。基于传统数据流图提出的同步数据流图(synchronous data flow graph，SDFG)定义了组件间通信的周期时序特性的概念[5]，通常是用于评估DSP(digital signal processing)应用程序[6]，不适用于AES时序需求建模。为满足AES的频度需求，本文考虑在DFD中融入时序特征及事件驱动等元素。MARTE[7]是嵌入式软件领域中对时间等非功能属性定义详尽的一个UML(unified modeling language)[8]扩展文件，在建模过程中通常将MARTE与UML相结合来描述需求中的时序模式[9，10]，也有将MARTE、SysML(systems modeling language)[11]与pCCSL(p clock constraint specification language)相融合来描述实时嵌入式软件的硬件和软件的需求建模过程[12，13]，上述融合的模型大都将状态图或块图与时序特性相结合，无法在需求阶段分析并改善AES中的数据流时序偏离问题[14]。

针对DFD中不具备时序特性的问题，本文提出了一个基于MARTE的数据流时序模型，弥补了传统模型无法对AES中具有时序属性的数据流建模的问题；为检测并优化需求中时序定义不准确的问题，提出了处理点缓存计算算法、时序偏离概率检测算法和时序序列分析算法。

1 时序需求模型研究

1.1 DFD模型

DFD是一种结构化分析方法，它用图形的形式来描述数据驱动的系统中数据流动和处理的过程，包括数据源点、数据流、处理点和数据存储四大组件[15]。数据源点是与系统交互数据的单元；数据流是描述节点间数据传输的单元；处理点是在系统中对传递来的数据进行加工的单元；数据存储是系统中数据停留或者将其保存的单元。数据流图是需求分析阶段对于结构化开发描述的一种功能模型。

1.2 MARTE模型

MARTE是一个用于实时嵌入式系统建模和分析的UML概要文件，根据建模和分析实时和嵌入式系统(real time/embedded system)所需的UML扩展来定义概念，定义了基于模型的实时和嵌入式系统描述的基础。MARTE包括基础包、设计模型包、分析模型包和附加包，提供了关键资源，用于说明实时嵌入式软件的非功能性需求，例如，时间方面和约束条件等[16]。

MARTE中的时间模型描述实时嵌入式系统中的时间以及时间相关概念的机制，包含逻辑时间(logical time)和物理时间(chronometric time)两个部分，以描述实时和嵌入式系统中诸如延迟、时间段和时钟的概念。根据系统设计的精确度要求，行为时序性有3种不同程度的表示方式：因果/瞬时(causal/temporal)、时钟/同步(clocked/ synchronou s)、物理/实时(physiceal/real time)。

1.3 DFT-MARTE模型

1.3.1 DFT-MARTE模型时序定义

本文将数据流与MARTE中的4种到达模式相结合，提出了DFT-MARTE模型。其中到达模式包括突发模式、偶发模式、不规则模式和周期模式，详细参数信息见表1。突发模式属于非周期性模式，包括最小到达间隔、最大到达间隔、最小数据间隔、最大数据间隔和突发量的参数，是一种在某个时间段内突发一定数据量的时序模式，可模拟物理/实时中非周期数据的情况；偶发模式属于非周期模式，包括最小到达间隔、最大到达间隔及抖动的参数，是一种在某个时间段内产生一个数据的时序模式，可模拟因果/瞬时的情况；不规则模式属于非周期模式，是一个完全确定的到达模式，包括阶段和时间间隔的参数，是在确定的时间间隔点产生数据流的时序模式，可模拟时钟/同步的情况；周期模式包括周期、抖动、相位、数据量的参数，是一种周期性产生数据流的时序模式，可模拟物理/实时中周期数据的情况。

表1 到达模式

1.3.2 DFT-MARTE模型时序结构

为描述AES中数据流的时序特性，本文扩展了数据流图的元模型。数据流图包括数据源点(data source point)、数据流(data flow)、处理点(processing point)和数据存储(data storage)这4个组件，其元模型如图1所示。数据流图是一种重要的结构设计方法，可以清晰描述系统整体的数据交互关系。但在描述AES的数据交互过程中，由于其中大多数据包含时序信息，简单的数据交互图已然无法描述AES中数据的特点，并且不利于需求中时序属性的相关检查，故提出一种基于MARTE的数据流时序模型，即DFT-MARTE模型。

图1 传统数据流图的元模型

DFT-MARTE模型的元模型是基于MARTE中的到达模式重新定义数据流图，在传统数据流图的元模型基础上添加了时序元素(time element)、缓存窗口(cache window)和随机数据发射器(random data transmitter)模块，其元模型如图2所示。其中时序元素依据MARTE中的到达模式和数据流图特点改写并添加部分定义；缓存窗口是为了保证当处理速率与输入流总体流速不匹配时，能根据预设阈值进行调节：当缓存窗口中的数据大于最大阈值时，暂停所有输入流，保证两次握手期间所有的数据均可在缓存窗口内存储，即不溢出；为保证模型的完整性，考虑到嵌入式软件中存在随机事件触发输入数据流的场景，故而在本模型中加入随机数据发射器模块，该模块可定义随机事件。该模块会按照定义的时序特征随机发射数据流，保证模型正常运行，利于后续分析时序问题。

图2 DFT-MARTE模型的元模型

DFT-MARTE模型中的缓存窗口模块是由优先队列构成，数据模块包括数据流基本信息和数据优先级。缓存窗口模块为处理点模块的关联模块，其中优先队列是用来处理带有优先级的数据，即优先级数据。数据模块会对数据流的优先级进行定义。

通常在航天嵌入式软件需求中，会根据实时性要求不同数据包选择不同优先级。针对数据流可以设定不同的优先级，在分析过程中优先级不能改变。因此，本文按照通用需求对数据优先级进行设计。

针对航天嵌入式软件需求，设计如表2所示的4种优先级。图中优先级随着序号增大而降低，如：高精度时间广播数据的优先级最高，能够打断其它优先级较低的数据处理过程。缓存窗口模块中按照数据优先级设计了4个优先队列，与4种数据优先级一一对应。当数据到达处理点时，将其放入对应的优先队列中。在处理数据时，优先弹出高优先级对应的队列中的数据。

表2 数据优先级设计

DFT-MARTE模型可用图形化的形式，清晰准确地描述AES需求中有时序特性的数据流之间的关系。DFT-MARTE模型融合了DFD和MARTE，不仅解决了DFD无法展现数据时序性的问题，而且覆盖了行为时序中的因果/瞬时的情况，可模拟事件驱动的数据流，有利于进行后续的时序相关检查。DFT-MARTE模型与其它相关模型的比较见表3。

表3 相关模型对比

2 DFT-MARTE模型的时序分析算法研究

本节介绍基于DFT-MARTE模型提出的3个算法，其一是针对处理节点存在数据溢出导致时序检测无法正常执行的问题[17]，提出了一种处理点缓存计算算法，该算法动态改变处理点缓存容量来辅助后续算法的正常执行。其二是为引导用户改进需求中的时序属性，提出一种时序偏离概率检测算法可计算输出流针对定义时序的偏移概率，在需求阶段可检测出时序问题。其三是针对时序偏离概率检测算法无法直观地帮助需求人员改进需求的问题，提出一种基于梯度下降算法[18]的时序序列分析算法，最终可给出建议的周期模式参数。

2.1 处理点缓存计算算法

处理点缓存计算算法是在处理具有时序特性的处理点时，根据处理点对应输入流的时序特性和设定的最大、最小阈值来推算所需缓存窗口容量。本算法是辅助时序检测与分析算法，使其正常执行。算法1为处理点缓存计算算法的代码。

算法1：处理点缓存计算算法

输入：Inputflows输入流数组，n数组容量，maxThres-hold最大阈值

minThreshold最小阈值，dealSpeed处理速率

输出：capacity缓存窗口容量

描述：用于计算处理点缓存容量

(1)functioncacheWindowCapacity(Inputflows, n, thres-hold)

(2) capacity, capacity1, capacity2←0 //初始化缓存容量

(3) minlength←Inputflows[0].length

(4)fori=0→n-1do//遍历所有输入流数组

(5) //按式(1)先进行累加

(6) capacity1←capacity1+Inputflows[i].length

*getMaxDataFlowSpeed(Inputflows[i])

(7) //求出最短数据流长度, 为计算式(2) 作准备

(8) minlength←MIN(minlength, Inputflows[i].length)

(9)endfor

(10) //完成式(1), 得到按照最大阈值计算所需的缓存容量

(11) capacity1←capacity1/(1-maxThreshold)

(12) //完成式(2), 得到按照最小阈值计算所需的缓存容量

(13) capacity2←2* minlength*dealSpeed / minThreshold

(14) //按照式(3),取上述两个变量最大值作为结果值

(15) capacity←MAX(capacity1, capacity2)

(16)returncapacity;

(17)endfunction

输入: Inputflow输入流

输出: speed该输入流的最大流速

描述: 用于计算输入流的最大流速

(1)functiongetMaxDataFlowSpeed(Inputflows)

(2) speed←0 //初始化速率

(3) //如果输入流时序为突发模式

(4)ifInputflow.patternType is burstthen

(5) //获取当前突发模式下数据流时序参数信息

(6) pattern←getBurstPattern(Inputflow.patter-nId)

(7) //取最小到达间隔的反比为最大速率

(8) speed←1/pattern.minInterarrival

(9)endif

(10) //如果输入流当前时序特性为偶发模式

(11)ifInputflow.patternType is sporadicthen

(12) pattern←getSporadicPattern(Inputflow.patter-nId)

(13) speed←1/pattern.minInterarrival

(14)endif

(15) //如果输入流当前时序特性为不规则模式

(16)ifInputflow.patternType is irregularthen

(17) pattern←getIrregularPattern(Inputflow.patter-nId)

(18) //不规则模式的最小到达间隔需要遍历时间间隔

(19) interarrival←Inputflow.interarrivals[1]-Inputflow.interarrivals[0]

(20)fori=2→Inputflow.interarrivals.length-1 do

(21) interarrival←MIN(speed,Inputflow.interarrivals[i]-Inputflow.interarrivals[i-1])

(22)endfor

(23) speed←1/ interarrival

(24)endif

(25) //如果输入流当前时序特性为周期模式

(26)ifInputflow.patternType is periodic then

(27) pattern←getPeriodicPattern(Inputflow.patter-nId)

(28) speed←1/(pattern.period-pattern.jitter)

(29)endif

(30)returnspeed;

(31)endfunction

算法1的核心思想是当处理点缓存中的数据量与总窗口容量之比达到最大阈值时，暂停所有输入流，需要保证剩余缓存空间仍可存储暂停过程中到达的最大数据量；当缓存窗口内数据量与总窗口容量之比低至最小阈值时，处理点需要重启输入流，需要保证缓存中剩余数据可满足重启和数据传输过程中处理点的处理速率。具体过程如图3所示。

图3 处理点缓存计算

处理点缓存容量需要满足最大、最小阈值两种情况下的约束条件，因此，得出以下3个公式。其中，式(1)是计算在已知最大阈值时所需的缓存容量，其中inputflowk.length表示数据流传输时间，maxSpeed表示数据流传输的最大速率，maxThreshold为设定的最大阈值

(1)

式(2)是计算在已知最小阈值时所需的缓存容量，其中dealSpeed是处理点的处理速率，minThreshold为最小阈值

(2)

式(3)为处理点的缓存容量需要同时大于等于式(1)、式(2)的结果，因此，最终计算结果在两者之间取最大值

(3)

由于只有外部接口向处理点的输入流具有确定的时序特性，其余输入流的时序特性是动态变化的。因此，在时序偏离检测过程中，处理点的缓存计算是按照固定周期进行，处理点缓存空间也随之动态变化。

2.2 时序偏离概率检测算法

由于AES需求中与外部实体交互的数据流具有时序特性，故本算法通过利用多线程并发模拟输入流的时序特性，模拟得到输出流的时序特性，并将计算结果与期望时序特性进行对比，得出输出数据流的时序偏移概率。由于AES需求中存在优先级抢占现象，本算法按照表2的优先级设计，给每个处理点缓存增添了4个优先队列来处理优先级数据。

若将DFT-MARTE模型简化如图4所示。节点1、2为抽象的数据源节点，节点3为处理点，节点4为外部存储节点。在DFT-MARTE模型中，每个节点均具有时序序列α， 时序序列为一个有固定大小的滑动窗口，记录数据到达时间点的序列，数据源节点和外部存储节点具有时序特点γ， 时序特点为表1中介绍的4种到达模式，数据流均有相位δ， 相位表示数据在数据流上传输消耗的时间。

图4 DFT-MARTE模型简化

时序偏离概率检测算法在图4中是计算节点4的模拟得到的时序序列α4与其时序特点γ4的匹配程度。具体流程为：节点1、2按照γ1、γ2模拟时序序列产生α1、α2， 即：α1、α2分别服从γ1、γ2；α3为α1、α2、δi、δii的叠加；α4为α3、δiii的叠加；最终计算α4与其时序特点γ4的匹配程度。由于此种叠加不是数学意义上的加法，是两种时序序列均到达时产生的新的时序序列，本算法采用多线程并发模拟DFT-MARTE模型中的动态时序关系。本算法的组成部分如图5所示。

图5 时序偏离概率检测算法结构

其中，多线程包括主线程、数据源线程、数据流线程和处理点线程。主线程负责创建线程、建立管道、时钟管理和线程管理。

创建线程是将模型中外部实体、数据流、处理点和随机事件触发器模块分别进行线程创建，其中具有输出流的外部实体和随机事件触发器模块需要创建数据源线程，其余模块与各自线程一一对应；建立管道是使线程间可以通信，数据源线程至少有一个输出管道，数据流线程仅有一个输入和输出管道，处理点线程至少有一个输入管道和一个输出管道；时钟管理是管理全局时间，更新全局时间必须保证线程间的同步，可利用循环屏障，使除主线程外所有线程在单位时间内执行完各自任务后相互等待，当所有线程均到达某个屏障点时，主线程方可递增全局时间并使其它线程进行后续操作；线程管理是主线程监控全局结果集，若全局结果集覆盖所有连接外部实体的输出流，则改变全局终止变量以终止其它线程。

数据源线程是根据每个输出流的时序特性将数据写入该输出流对应的管道中，其运行流程如图6所示。其中，在每个单位时间内，无论是否满足其时序特性，至少需要向输出管道内写入结束数据，以表示线程在当前时间对某个数据流完成相关时序判断。本算法中向输出管道写入数据均以5个字节为单位。

图6 数据源线程泳道

处理点线程的具体运行流程如图7所示。处理点线程在收到全局终止信号前，在每个单位时间内，执行以下3个任务：

图7 处理点线程泳道

(1)将处理点的所有输入管道放入队列，依次弹出队首的管道。若管道内无数据，则将其放入队列尾端；有数据则以5个字节为单位循环读取管道中的数据，并按照数据优先级将其放入对应的优先队列中；

(2)按照优先队列次序和处理速率依次弹出数据，找到弹出数据关联的后置数据流集合，循环遍历后置数据流集合，将数据写入对应输出管道内。

(3)抵达屏障，等待其它线程完成任务。

数据流线程的具体运行流程如图8所示。数据流线程在收到全局终止信号前，在每个单位时间内，执行以下3个任务：

图8 数据流线程泳道

(1)循环读取输入管道内数据，直至读到结束数据时，停止读取。

(2)首先判断线程中读到的数据是否满足数据流的前置约束，若不满足，则向输出管道内写入结束数据，然后进行任务(3)；否则需判断该数据流的目标节点是否为处理点。若是，则向输出管道内写入数据流id和结束数据；否则按照预期时序特性计算时序偏离概率，当偏离概率连续5次波动小于阈值，则将其写入全局结果集。

(3)抵达屏障，等待其它线程完成任务。

当所有线程均抵达屏障时，主线程更新全局时钟，并判断当前是否满足线程终止条件，即全局结果集中覆盖所有连接外部实体的输出流，若满足，则调整全局终止变量为true；否则进入下一个单位时间，让其余线程继续循环。

2.3 时序序列分析算法

由于系统面向外部实体的数据流的时序特性多为周期性，本算法最终给出周期模式的建议参数。本算法基于梯度下降算法将模型数据流中缓存区域的数据到达时序序列作为训练数据，对其进行拟合，在使所有训练数据满足周期模式下的同时，使抖动尽可能地缩小，最终给出建议的周期和抖动参数。

本文将时序序列中的到达的次序和时间分别作为训练数据中的x和y值 (x≥0且y≥0)， 训练数据约束如图9所示。为保证所有的训练数据均落在图中点状区域内，可得到约束条件如式(4)所示

图9 训练数据约束

(4)

为满足式(4)，可推出式(5)

(y1-y)(y-y2)≥0⟹(Tx+b-y)(y-Tx+b)≥0⟹
[b-(y-Tx)][b+(y-Tx)]≥0⟹b2≥(y-Tx)2

(5)

当抖动很大时，满足约束条件的周期就会在一个范围内，则得到的周期具有不确定性。为使最终建议的周期值T更精确，需要得到最小的抖动值b。 如式(5)所示，可通过优化 (y-Tx)2从而优化抖动值b， 因此，设计损失函数如式(6)所示

(6)

根据式(5)可知，抖动值b仅存在一个极值点。因此，基于梯度下降算法思想，将学习率设置为0.01，利用式(7)不断更新周期值T， 从而找到抖动值b的极值点

(7)

当损失函数收敛后，得到周期值T， 并按照式(8)计算出最小值b， 最终将得到的周期值T和抖动值b作为参考建议提供给需求人员

(8)

3 案例分析

为优化航天嵌入式软件需求，本文基于DFT-MARTE模型和时序偏离概率检测算法开发出一款DFT-MARTE模型构建及检测工具(TimingFlow)，TimingFlow界面包括功能区、模型元素区、画布区、数据特性区和工具区，工具界面如图10所示。

图10 TimingFlow界面

TimingFlow可构建的DFT-MARTE模型，利于需求人员描述需求中时序特性数据的交互关系。

处理点属性的处理速率为默认值时，即该处理点可以处理所有到达的数据，设定的最大阈值和最小阈值是为了计算处理点缓存，以保证偏离概率检测的正常进行；数据流属性中定义了相关时序特性和数据优先级信息；随机事件发射器属性关联了随机事件与数据流，TimingFlow对DFT-MARTE模型中模块属性具体定义如图11所示。

图11 模块特性

为验证本模型可以满足航天领域嵌入式软件需求，以某载荷控制器管理软件需求来验证本文提出的DFT-MARTE模型及时序分析算法。需求中包括5个外部接口、27个数据流和6个功能模块，提取如软件接收环绕器平台的数据注入包并向平台发送遥测参数等需求，利用TimingFlow构建DFT-MARTE模型，如图12所示。

图12 DFT-MARTE模型示例

从载荷控制器管理软件需求中提取到系统与外部接口之间的数据流的时序特性见表4和表5。表中数据流ID与图12中的数据流编号一一对应，时序模式覆盖了周期模式、突发模式、偶发模式和不规则模式，其中周期模式比较常用。表5为系统向外部接口发送的数据流的时序特性，属于需求中的预期时序特性，此部分容易出现时序定义不准确的问题，是后续实验主要检查对象。

表4 外部输入流时序特性

表5 外部输出流预期时序特性

在需求中，健康管理功能模块在处理数据时有50 ms的延迟，其余模块的处理速率均为默认值。计算处理点缓存是让处理点进行动态地改变缓存容量，后续时序检测和分析的正常执行可验证处理点缓存计算算法的作用。利用本工具进行时序偏离检测后，得到相关偏移率实验结果为表6第二列，其中有3个数据流的实验结果与预期时序特征偏移率较大，有3个数据流偏移概率均为个位数，甚至有两个数据流偏移概率为0。其中偏移概率越低表明需求中时序描述越准确。上述实验结果表明，需求中仍存在时序问题，后续时序序列分析可从除数据流1和26以外的数据流进行优化。

表6 时序偏离概率检测结果

以对数据流10的时序序列进行优化为例介绍时序序列分析过程，将流向数据处理FPGA接口的输出数据流的模拟时序序列作为训练数据，利用本文提出的基于梯度下降的时序序列分析算法进行拟合，拟合结果如图13和图14所示。

图13 时序序列拟合结果

图14 时序序列数据分布和回归结果

由图13可知最终得到建议周期T为103.052 299，抖动b为6.385 254，数据流10预期周期为100 ms，抖动为5 ms，实验结果建议周期为103 ms，抖动为6 ms。因为需求中大多数周期数据周期和抖动数值量级差别很大，所以图14中拟合的上下两条函数看似重合，图中横坐标表示当前已到达数据量，纵坐标代表数据到达的系统时间戳。

将其余数据流均按照上述示例得到推荐的周期模式的具体参数后，又利用时序偏离检测算法进行检测，具体检测结果可见表6。时序序列分析算法可有效帮助需求人员改进需求中的时序特性。改进前后对比如图15所示。

图15 时序偏离检测结果对比

4 结束语

本文提出了一个基于MARTE的数据流时序模型，它用于对AES的需求数据进行时序建模及分析验证；主要创新性工作如下：

(1)提出一个处理点缓存计算算法，避免时序冲突，辅助时序检测分析的正常执行；

(2)提出一个时序偏离概率检测算法，可以检测数据流的时序特征与预期值的差异概率，有利于需求编写人员改进需求；

(3)提出一个时序序列分析算法，可直观地向需求人员提供数据流的时序特性修改意见；

本文提出的模型可描述AES中具有时序特性的数据流关系，并通过本文提出的算法可检测出需求中的时序问题并进行优化，利于软件开发和维护。由案例分析可知，本文提出的算法可有效引导需求开发人员优化时序特性。