基于RPU 的TTI 程序设计和分析方法

高银康 陈香兰 龚小航 蒋滨泽 李 曦 周学海

（中国科学技术大学计算机科学与技术学院 合肥 230027）

（中国科学技术大学苏州高等研究院 江苏苏州 215004）

（gaoyinkang@mail.ustc.edu.cn）

实时嵌入式系统（real-time embedded system，RTES）通常应用于安全关键领域，此类系统需要实时和外界环境交互，因此不仅要保证计算结果的逻辑正确性，还要确保与外界交互的时序正确性.

实时领域的程序设计中，高层的编程模型含有时间语义，如逻辑执行时间（logical execution time，LET）编程模型[1]，而在底层的指令集架构（instruction set architecture，ISA）层面缺乏时间语义，导致编程人员无法直接控制底层程序的时序行为. 现阶段实时系统设计和分析的主要方法是，计算底层程序的执行时间，并以此作为程序时序控制的依据，但是由于程序中不确定的分支跳转指令，以及硬件体系结构（流水线、Cache、分支预测等）影响，传统程序的执行时间分析，总是悲观地分析程序在最坏情况下的执行时间（worse case execution time，WCET），而为了保证程序时序行为的正确，就必须依据WCET 进行资源的过度分配，使高层的编程模型不能精确且自然地映射至底层程序.

造成这一问题的原因是通用体系结构的ISA 没有可以表达时间语义的指令，所以和LET 等实时编程模型的表达能力存在差距. 针对该问题，最有效的方法是规定程序中每一条指令的执行时间，但是这样会限制底层硬件体系结构的发展[2]. 为平衡时间语义表达能力和执行性能的问题，Lee 等人[3]提出PRET（precision timed）概念，并提出了限定代码段执行时间的指令，一定程度上提升了底层指令集的表达能力.文献[4]提出了TTI 指令集（time-triggered instruction set），与Lee 小组工作相比，增加了时间和操作相结合的定时指令，使指令集的表达能力进一步提升，本文的分析和验证都依据TTI 指令集进行，并且将使用了TTI 指令集的程序称为TTI 程序.

Lee 等人[3]和文献[4]中对于指令集扩展的工作，仅给出了时间语义指令集的定义和实现方案，并没有说明指令集可以表达的时间语义和相应的时间语义程序设计范式，导致实时系统设计者在进行上层模型至底层程序的映射时缺乏理论依据. TTI 指令集通过不同指令组合可以表达丰富的时间语义，为了映射上层设计，需要给出TTI 程序的设计范式，明确TTI 程序可以表达的语义类型.

TTI 程序运行时，时间语义指令的执行会受到前驱代码段执行时间的影响，为了保证指令的时间语义在执行时能够得到正确表达，需要对TTI 程序进行时间行为分析. 例如，对于TTI 指令集中定时输出指令ttoat，指令语义要求在预设时间点完成输出操作，而ttoat 指令会在前驱代码段执行完成后开始执行，所以需要计算ttoat 指令前驱代码段的WCET，保证该WCET 小于ttoat 指令预设的时间点，以此保证定时语义的正确表达. 并且传统程序的时间行为分析，会以整个程序（任务）为单位，给出程序（任务）的WCET，而TTI 程序需要计算时间语义指令间程序段的WCET，并结合时间语义指令的语义要求进行时间安全性检查，验证指令运行时的正确性，所以需要改进传统程序的WCET 分析方法，提出针对时间语义程序的时间行为分析方法.

本文依据文献[4]所述工作，首先提出了TTI 程序的设计范式，说明了TTI 指令集的表达能力，明确TTI 程序可以表达的4 种语义. 同时，对Timed C[5]系列工作中提出的程序时间行为的表示TFG[6]进行扩展，提出了TTI 程序的表示TFG+，描述了TTI 程序的控制流信息、用户规定的时间行为和平台相关的时间属性. 最后，根据TFG+，基于实时处理单元（realtime processing unit，RPU），采用基于执行图[7]的低级分析方法，分析了TTI 程序的时间行为，并且对TTI程序的时间语义指令进行时间安全性检查，验证其语义在执行时能够得到正确表达. 本文提出的TFG+构建方法、时间行为分析方法以及时间安全性检查方法适用于RPU 和其他可以运行TTI 指令集的处理器架构，若采用除RPU 外的其他架构，只需要修改执行图的构建方法和执行图节点属性的计算方法即可.

本文的主要贡献有3 个方面：

1） 提出TTI 程序的设计范式，明确TTI 程序可以表达的4 种时间语义，使编程人员能够精确自然地表达上层的设计.

2） 提出TFG+，以表示TTI 程序，TFG+可以表达TTI 程序的控制流信息、用户规定的时间行为以及平台相关的时间属性，为TTI 程序的分析和时间安全性检查提供了依据.

3） 提出了TTI 程序的时间行为分析方法和时间安全性检查方法，保证TTI 程序运行时指令的语义能够正确表达.

1 相关工作

相关工作分为时间语义指令集、程序抽象表示和程序时间行为分析3 个方面进行介绍.

1.1 时间语义指令集

Lee 在文献[8]中从“实时”概念出发，总结了多种对于实时性的定义. Lee[8]认为根据不同的需求和角度，“实时”概念有6 种定义：快速计算、优先调度、对数据流的计算、有界执行、程序的时间语义和网络的时间语义. 其中，在对程序的时间语义的阐述中，Lee[8]认为实时系统设计和部署时，由于现在的通用计算ISA 中不存在时间语义，需要在更高层次重新引入时间语义，但是通用计算ISA 和高层次模型关于时间语义表达能力上存在的差距，会导致实际系统设计时的诸多问题，所以需要在实时系统设计的各个抽象层次引入时间语义.

根据上述观点，Lee 等人[2]认为通用计算机指令集隐藏了底层体系结构中精确的数字电路时钟，为了控制程序的时间行为，计算机要向高层次模型提供这一精确时间. 对于时序的控制，Lee 等人[2]定义了ISA 层需要具备的4 种能力：1）限定程序块执行时间下界；2）程序块执行超过限定时间，程序块完成后分支跳转；3）程序块执行超过限定时间，立即分支跳转；4）限定程序块执行时间的上界. 文献[2]较早地提出了ISA 层在时序控制方法需要具有的时间语义，但是没有说明上层模型到底层指令的映射关系，没有给出相应的设计范式，同时，Lee 等人[2]认为时间语义指令集只需要“限定代码段执行时间”，没有关于点时间语义的论述.

Lee 等人[2]对通用计算指令集进行扩展，增加指令DU（delay until）保证代码执行时间下界，指令MTFD（meet the final deadline）保证代码执行时间上界. 并且依据此设计了处理器PTARM[9]和FlexPRET[10]. 此方法可以限定代码的执行时间，但是无法直接表达操作发生在某个时刻的语义，所以该指令集的表达能力依旧有限.

文献[4]从实时理论出发，类比通用计算中图灵机为通用计算系统的理论基础[11]，冯·诺依曼机是通用计算机系统统一的实现模型[12]，提出了具有时间语义的实时计算机体系结构模型实时机（real-time machine，RTM），RTM 在冯·诺依曼机5 大部件的基础上扩展了标准时钟（stdClk）部件，至此处理器时钟（cpuClk）负责实时处理器的值域控制，标准时钟负责实时处理器的时域控制. 基于RTM 的理论指导，文献[4]结合时间触发自动机（time-triggered automata，TTA）理论[13]，定义了时间语义指令集TTI. 相比于Lee等人[2]提出的限定代码执行时间的时间语义指令集，TTI 指令集不仅具有限定代码执行时间上下界的delay，mtfd 指令，还增加了时间和操作相结合的定时指令ttiat，ttoat，以及任务并发管理指令，进一步扩展了指令集的表达能力. 下面详细介绍TTI 指令集的定义和实现.

TTI 指令集包含时间语义寄存器和时间语义指令2 部分. 表1 给出了时间语义寄存器. 时间粒度寄存器（time granularity register），用来设置TTI 程序的时间粒度，以满足不同系统或不同工作模式的时间粒度要求；时间寄存器（current time register），用来表示系统时间，根据时间粒度寄存器生成，即标准时钟的上升沿累计值等于时间粒度寄存器时系统时间寄存器的值加1；时间戳寄存器（time stamp register），用来保存上一次时间触发操作的系统时间. 如表2 所示，TTI 指令集中共有10 条时间语义指令，按照功能分为4 部分. 文献[4]中对于指令的语义进行了详细说明.

Table 1 Time Semantic Registers表1 时间语义寄存器

Table 2 Time Semantic Instructions表2 时间语义指令

目前时间语义指令集的相关工作仅说明了每条指令的语义和对应的硬件实现方案，缺乏时间语义指令集表达能力的说明，同时，没有给出时间语义程序的设计范式，导致无法直接自然地定义上层模型中时间语义与底层时间语义程序的映射关系.

文献[4]基于TTI 指令集的定义，扩展RISC-V 指令集[14]，实现了可以执行TTI 指令集的RPU. RPU 基于经典5 段流水[15]实现，即流水线分为取指段、译码段、执行段、访存段和写回段5 个阶段. 下面给出TTI 指令集的实现.

1）系统时间管理指令. 此类指令的功能是对标准时钟进行管理，生成系统时间. 执行段，settg 指令设置tgr，setti 指令设置ctr. 写回段，getti 指令读取ctr中保存的当前系统时间到目的寄存器，getts 指令读取tsr 保存的上一时间触发操作发生时间到目的寄存器.

2）时间触发操作指令. 此类指令的特点是操作和时间绑定，规定操作在指定系统时间触发执行. 执行段，比较ctr 的值和指令预设时间，若ctr 小于指令预设时间，产生stall 信号停顿流水线，直到ctr 等于指令预设时间，执行时间触发操作指令. 后续指令ttiat/ttoat 在访存段和写回段的操作和普通load/store指令相同.

3）执行时间约束指令. 此类指令的功能是保证代码段执行时间的上下界. delay 指令用于约束代码执行时间的下界；mtfd 指令用于约束代码执行时间的上界. 执行段，delay 指令会比较ctr 的值和指令预设时间，若ctr 小于指令预设时间，表示未到延时时间，产生stall 信号停顿流水线，直到ctr 等于指令预设时间，才继续指令的执行. 对于mtfd 指令，RPU 没有相关实现，mtfd 指令只作为代码中的检查点，用于时间安全性检查.

4）任务并发管理指令. 此类指令的功能是摒弃传统的使用中断的软件任务并发管理，提供确定的硬件线程管理任务并发的能力. 本文不考虑多线程TTI 程序，所以省略任务并发管理指令的实现.

1.2 程序的表示

传统程序进行WCET 分析时，可以将程序表示为控制流图（control flow graph，CFG），在CFG 中程序以基本块（basic block）为单位进行划分，基本块间的依赖关系通过CFG 中基本块间的边进行表达. 后续许多程序表示都是对CFG 的扩充.

文献[16]中提出了CKAG（concurrent kep assembler graph），用来表示使用了处理器KEP（kiel Esterel processor）指令集的程序，KEP 是可以运行同步语言Esterel[17]的专用处理器，而CKAG 的提出是为了计算同步语言程序最坏情况反应时间（worst case reaction time，WCRT）. 同步语言PRET-C[18]为了计算WCRT 也提出了PRET-C 程序的表示TCCFG（timed concurrent control flow graph）[19].

文献[6]中提出TFG 的概念，用来表示Timed C[5]程序，进行Timed C 编译器正确性检查，Timed C程序的TFG 在CFG 的基础上，添加了表达段时间语义的时间点（timing point，TP）. 另外，FG 定义了图中每个节点的时间属性，至此TFG 不仅可以表达程序的控制流信息，还可以表达用户规定的时间行为，以及平台相关的时间属性，但是Timed C 程序的TFG受限于Timed C 语言，只是表达了段时间语义. 本文结合TTI 程序提出了TFG+，是对TFG 的扩充，表达了更为丰富的时间语义，例如点时间语义.

1.3 程序时间行为分析

现有的程序WCET 分析方法分为基于测量的WCET 分析和静态WCET 分析. 静态WCET 分析，由流分析（flow analysis）、低级分析（low-level analysis）和WCET 计算（WCET computation）组成.

1）流分析. 首先通过分析程序结构，构建程序的表示，例如CFG[20]；然后由程序员手动[21]或通过自动分析[22]给出程序循环边界（loop bound）等流事实（flow fact）.

2）低级分析. 目的是结合硬件体系结构分析CFG 中每个基本块的执行时间，常用的方法有抽象解释（abstract interpretation）[23]、 基于执行图（execution graph）[5,24-25]的分析方法. 抽象解释方法的WCET 分析工具有aiT[26]，而基于执行图的WCET 分析工具有Chronos[27]，OTAWA[28].

3）WCET 计算. 目的是计算整个程序最坏情况下的执行时间，现有基于语法树的WCET 计算方法[29-30]和基于CFG 的WCET 计算方法[31]. 基于CFG，整个程序的执行时间可以表示为每个基本块执行时间的加权和，权值为每个基本块的执行次数. 通过分析CFG 节点依赖关系和流事实，给出对每个基本块执行次数的约束，采用整数线性规划（integer linear program，ILP）方法，最大化整个程序的执行时间表达式，该方法被称为隐式路径枚举技术（implicit path enumeration technique，IPET）.

2 TTI 程序设计流程

本节给出TTI 程序相关概念，以及设计TTI 程序的基本流程.

2.1 相关概念

由1.1 节TTI 指令集的实现可知，TTI 指令集中时间语义指令在RPU 流水线执行段的行为会受到指令预设系统时间和当前系统时间寄存器ctr 的值的影响，编程人员需要依据系统时间设计TTI 程序的时间行为. 下面给出TTI 程序中“系统时间”这一概念的定义.

定义1.系统时间. TTI 程序中系统时间是以系统时刻为单位的离散值，系统时刻指的是一段实时间，系统时刻的大小由实时应用需要的时间粒度决定，TTI 程序时间语义指令中的预设时间均以系统时刻为单位，根据不同需求，不同TTI 程序的系统时刻也不相同.

如果实时应用需要的时间粒度为1 ms，即1 个系统时刻为1 ms，那么系统时间20 对应的实时间为20 ms.RPU 使用标准时钟（stdClk），结合时间粒度寄存器tgr，更新系统时间寄存器ctr 的值. 对于实时应用规定的时间粒度，TTI 程序可以使用settg 指令设置时间粒度寄存器tgr，tgr 的值应该设置为tg×f，其中tg为实时应用需要的时间粒度，f为stdClk 的频率，假设stdClk的频率为 1 MHz，而实时应用需要的时间粒度为1 ms，则时间粒度寄存器tgr 应该设置为0.001 s×1 MHz，即tgr 值为1000. 假设实时应用的时间粒度需求变得更为紧致，为0.1 ms，那么tgr 应该设置为100.

除了控制TTI 程序时序行为的stdClk，RPU 存在驱动数据通路各个功能部件同步运行的cpuClk，根据文献[4]中给出的“stdClk 和cpuClk 关系定理”可知，stdClk 和cpuClk 存在同步和异步2 种关系，在本文中只考虑同步情况，即stdClk 的周期TstdClk和cpuClk的周期TcpuClk的关系为TstdClk=n×TcpuClk.

TFG+使用不同节点表示TTI 程序中的时间语义指令和普通指令构成的基本块. 由于RPU 流水线中同时存在多条指令，TFG+中2 个连续节点对应的时间语义指令或基本块的执行会有所重叠. 如图1 所示，基本块A的执行时间为tA，基本块B的执行时间为tB，基本块A和基本块B的整体执行时间为tAB，tA+tB＞tAB. 文献[5]给出了执行开销的概念，现在结合TFG+进行说明.

Fig.1 Example of execution cost图1 执行开销示例

定义2.执行开销.vj为TFG+中节点，vi为vj的直接前驱节点，vj对应程序段的执行开销为vi最后一条指令完成时间到vj最后一条指令完成时间的间隔.例如，在图1 中，基本块B的执行开销为cB.

本文采用执行图[7]的方法进行低级分析，以计算TFG+各个节点的执行开销. 根据定义2，构建TFG+各节点执行图时需要增加前驱节点的最后一条指令的执行信息.

2.2 TTI 程序设计流程

TTI 程序的设计流程有3 步：

1）对于给出的高层编程模型，分离其时间语义和功能语义，对于上层模型的时间语义，选择合适的TTI 程序设计范式进行表达，再结合相应的功能代码，给出对应的TTI 程序.

2）构建TTI 程序的TFG+，表达TTI 程序中的控制流信息、用户规定的程序时间行为以及平台相关的时间属性.

3）基于RPU 或其他可以运行TTI 指令集的处理器，结合TFG+中控制流信息，构建TFG+每个节点的执行图，基于执行图分析TFG+中每个节点平台相关的时间属性，并根据TFG+用户规定的程序时间行为，进行时间安全性检查.

由于RPU 采用的是顺序取指、顺序执行的模式，ttiat，ttoat，delay，mtfd 指令的执行会受到前驱代码段执行时间的影响，时间安全性检查是为了保证系统运行时，这些指令的时间语义能正确表达. 时间安全性检查会分析时间语义指令前驱代码段最坏情况下的执行时间，如果前驱代码段的最坏情况下执行时间较长，执行到时间语义指令时系统时间大于预设时间，此时mtfd 指令约束代码段执行时间上界的语义被违反，且ttiat，ttoat 指令在规定系统时刻完成输入输出操作的语义也被违反；如果前驱代码段执行时间较短，执行到时间语义指令时，系统时间小于指令预设时间，显然满足mtfd 指令约束代码段执行时间上界的语义，而ttiat，ttoat，delay 指令会停滞流水线，直到RPU 的系统时间等于指令预设的时间，此时满足delay 指令约束代码段执行时间下界的语义，由于ttiat，ttoat 指令语义要求在规定系统时刻完成输入输出操作，所以还需要验证ttiat，ttoat 指令的输入输出操作会在规定的系统时刻内完成.

3 TTI 程序设计范式

TTI 指令集可以通过不同的指令组合表达丰富的时间语义，用来满足用户对于程序时间行为的控制需求. 现在给出TTI 指令集能够表达的4 种时间语义：

1）绝对点时间语义（absolute timed semantic）. 相对于系统0 时刻的点时间约束，即规定自系统启动到某一确定时间点的系统行为.

2）绝对段时间语义（absolute timing semantic）. 相对于系统0 时刻的段时间约束，即规定自系统启动，某一段时间的系统行为.

3）相对点时间语义（relative timed semantic）. 相对于某一时刻的点时间约束，即自系统某一时刻到规定时间点的系统行为.

4）相对段时间语义（relative timing semantic）. 相对于某一时刻的段时间约束，即自系统某一时刻，规定时间段内的系统行为.

相对时间语义中的“某一时刻”，分为2 种情况：

1）设计时确定的时刻. 在系统设计时，已知该时刻的系统时间. 例如，相对时刻是规定的绝对点时间，那么这里相对时间语义中的相对时刻就是系统设计时已知，此时的相对时间语义可以转化成绝对时间语义，即绝对时间等于相对的系统时间加上相对语义预设的系统时间.

2）运行时确定的时刻. 在系统设计时，不能确定该时刻的系统时间，系统时间需要根据系统实际运行情况分析. 例如，相对时刻是系统某一数据输入时刻，该数据输入对应的指令执行完成时间会受到前驱代码段的影响，数据输入的系统时间只有在系统运行时才能确定. 此时的相对时间语义，不能转化成绝对时间语义.

下面介绍TTI 指令集对上述时间语义的实现，给出TTI 程序设计范式和TTI 程序设计规则.

3.1 绝对点时间

TTI 指令集中，可以通过setti 设置ctr 寄存器来设置系统时间. 整个系统运行前的准备工作完成后，需要使用settix0 指令，将系统时间置为0，表示系统开始运行，ttiat/ttoat 指令提供了定时输入/输出语义，可以使用settix0 指令和ttiat/ttoat 指令的组合，完成绝对点时间语义的表达.

图2 给出绝对点时间的表达示例和实际运行的时序. 如图2（a）所示，init 负责初始化系统，设置时间粒度寄存器tgr 等，完成后使用settix0 将ctr 设置为0，表示系统启动. task1 中，设计时需要在系统时间为20时进行输出，所以使用ttoat 指令，并将指定触发时间的寄存器（图2（a）中寄存器a0）设置为20.

Fig.2 Example of absolute timed semantic图2 绝对点时间语义示例

如图2（b）所示，init 任务初始化系统，并通过setti 指令将ctr 寄存器设置为0，系统启动，task1 在某一时刻调度执行，且tast1 中ttoat 指令在系统时间为20 时生效，即ttoat 指令的输出操作发生在系统时间20 和21 之间. 如果将ttoat 指令替换成ttiat 指令，则表示输入操作的发生在系统时间20 和21 之间.

3.2 绝对段时间

绝对段时间和绝对点时间类似，在系统初始化完成后，通过settix0 指令将系统时间置为0，表示系统启动，然后在需要限制的代码段后使用delay/mtfd指令，表达绝对段时间约束.

图3 给出绝对段时间的表达示例和实际运行的时序. 如图3（a）所示，init 负责初始化并启动系统. task2中，设计时规定delay 指令前程序执行时间最少为20，所以将寄存器a0 设置为20，使用delay 指令，控制程序的绝对段时间行为.

Fig.3 Example of absolute timing semantic图3 绝对段时间语义示例

如图3（b）所示，task2 在某一时刻调度执行，且task2 中delay 指令需要保证前驱代码段的执行时间大于等于20. 如果将delay 指令替换成mtfd 指令，需要保证前驱代码段的执行时间小于20.

3.3 相对点时间

用户需要表达相对于系统某一时刻的点时间行为. 这里的“某一时刻”，可以是设计时确定的系统时刻，这样相对点时间语义就可以转化为绝对点时间语义，TTI 指令的实现可以转化为上述绝对点时间语义的实现方式. 所以这里主要分析的“某一时刻”，指的是系统运行前无法确定系统时间的时刻，可以使用TTI 指令集中提供的getti 指令和ttiat/ttoat 指令组合的方式表达. 图4 给出此种情况下，相对点时间的表达示例和实际运行的时序.

Fig.4 Example of relative timed semantic图4 相对点时间语义示例

如图4（a）所示，在task3 中，用户需要相对getti指令20 个时间单位执行输出操作. TTI 指令对此种语义的实现为：设置getti 指令，获取当前系统时间，存放在a0 中，再通过addi 指令加上相对时间20，作为ttoat 指令的触发时间.

如图4（b）所示，由于getti 前程序段的执行时间不确定，所以getti 获取的系统时间也需要根据实际运行情况确定，假设的getti 执行时系统时间为x，ttoat 指令也会在相对于getti 指令20 个时间单位的x+20 生效.

3.4 相对段时间

用户需要表达相对于系统某一时刻在一段时间内的程序行为. “某一时刻”和上述相对点时间中的一样，这里主要分析在运行时确定的系统时刻. 图5给出此类情况下，相对段时间的表达示例和实际运行的时序.

Fig.5 Example of relative timing semantic图5 相对段时间语义示例

如图5（a）所示，在task4 中，用户需要getti 指令后的代码段执行至少20 个时间单位. TTI 指令对此种语义的实现和相对点时间语义类似，只需要把ttoat指令改为delay 指令.

如图5（b）所示，可以表达getti 指令和delay 指令间的代码段至少执行20 个时间单位.

3.5 TTI 程序设计规则

考虑时间语义指令实际使用场景和TTI 程序时间安全性检查的可行性，TTI 程序需要遵守2 个规则：

1） 为保证TTI 程序的时间行为的确定性，时间语义指令集不会出现在程序的某一分支中.

2） 对于运行时确定的相对时间语义，getti 指令和对应的时间语义指令之间只有通用计算指令，不会出现其他时间语义指令.

4 TFG+定义

TTI 程序时间行为分析和时间安全性检查，需要构建整个程序的抽象表示. 本文对TFG 扩展，以TFG+表示TTI 程序，TFG+可以表达TTI 程序的控制流信息、用户规定的时间行为以及平台相关的时间属性. 如表3 所示，TFG+由3 部分组成：图结构、程序属性、平台相关属性.

Table 3 TFG+ Definition表3 TFG+定义

1）图结构. 使用不同节点表示多种时间语义和TTI 程序其他组成部分，主要分为：①绝对时间语义节点，包括绝对段时间语义节点（absolute timing point）、绝对点时间语义节点（absolute timed point）；②运行时确定的相对时间语义节点，首先是相对时间语义的相对基准点（relative base point），然后分别是相对段时间语义节点（relative timing point）、相对点时间语义节点（relative timed point）；③普通指令构成的基本块（basic block）节点；④程序的开始（start）节点. 最后，由TTI 程序中的指令执行顺序，构成TFG+中的边. ttiat，ttoat 指令根据表达的语义，对应绝对（相对）点时间语义节点；delay，mtfd 指令根据表达的语义，对应绝对（相对）段时间语义节点；getti 指令对应相对基准点.

2）程序属性. 表示TTI 程序平台无关的时间属性，TFG+程序属性中提到的时间均为系统时间. 程序属性包括时间粒度寄存器的值、TTI 程序的开始时间、绝对（相对）点（段）时间语义节点对应的预设系统时间.

3）平台相关属性. TTI 程序平台相关的时间属性，TFG+平台相关属性中提到的执行开销和时间均以cpuClk 周期为单位. 对于普通指令构成的基本块，需要计算每个基本块的执行开销. 对于时间语义节点，该节点对应的时间语义指令需要根据前驱代码段的运行时间，决定时间语义指令的执行开销，为了保证该类指令的时间语义在运行时的正确表达，现在考虑在指令前驱代码段最坏执行情况的前提下，时间语义指令需要的延迟时间和执行开销. 由于TTI 程序的时序依赖于stdClk，而逻辑控制依赖于cpuClk，且stdClk 周期TstdClk为 cpuClk 周期Tcpuclk的整数倍，所以1 个系统时刻内包含多个cpuClk 周期，所以对于绝对点时间语义节点，需要给出在该节点对应的绝对点时间语义指令前驱代码段最坏执行情况的前提下，绝对点时间指令执行完成相对于某一系统时刻的偏移时间，同理，需要给出任务开始执行相对于某一系统时刻的偏移时间. 如图6 所示的平台相关属性coff说明，假设存在绝对点时间语义节点vatdp∈ATdP，且vatdp对应的指令为iatdp，在iatdp的前驱代码段最坏执行情况的前提下，iatdp在系统时间x执行完成，而实际上iatdp会在系统时间x内的某一时间点完成，coff（vatdp）为图6 中所示vatdp对应指令执行完成相对于系统时间x的偏移.

Fig.6 Description of platform dependent property coff图6 平台相关属性coff 说明

如算法1 所示，给出TFG+构建算法.

算法1.TFG+构建算法.

输入：TTI 程序prog；

输出：时间语义节点集合ATP，ATdP，RTP，RTdP，相对基准点集合RBP，基本块节点集合F，边集合E.

① （N,E） ←fCFG（prog）；

② forN中的每个节点i

③ （ATP,ATdP,RTP,RTdP,RBP,F,E）←partition（i）；

④ end for

算法1 中，行①对应的fCFG（prog），将prog中时间语义指令当作普通指令构建CFG，输出CFG 中的节点集合N和边集合E. 行③中的partition（i），对CFG节点进一步划分，节点i中的时间语义指令（ttiat，ttoat，delay，mtfd）以及获取系统时钟指令（getti）划分为单独节点，并将划分后的节点和边加入对应集合，输出i划分后的各种时间语义节点集合、相对基准点集合、基本块节点集合以及边集合.

图7 为具有不同时间语义的TTI 程序片段和对应的部分TFG+. 图7（a）TTI 程序中使用ttoat 指令，表达绝对点时间语义，在TFG+中，ttoat 指令对应绝对点时间语义节点，使用平行四边形表示，普通代码段根据程序结构，划分成基本块，对应基本块节点，使用矩形表示. 图7（b）使用delay 指令，表达绝对段时间语义，使用圆形表示. 图7（c）使用getti 指令和ttoat指令组合，表达运行时确定的相对点时间语义，getti对应相对基准点，使用梯形表示，ttoat 指令对应相对点时间语义节点，使用三角形表示. 图7（d）使用getti指令和delay 指令组合，表达运行时确定的相对段时间语义，getti 对应相对基准点，delay 对应相对段时间语义节点，使用菱形表示.

Fig.7 Examples of TFG+图7 TFG+示例

传统程序的CFG 只能表达程序中的控制流，即指令执行的时间先后关系（temporal succession）；TFG在CFG 的基础上扩展时间点（timing point），可以表达代码段的时间行为；TFG+相比TFG 加入了点时间语义节点，可以表达时间和操作相结合的点时间行为. 所以TFG+的表达能力强于TFG 和CFG，可以表达更为丰富的时间语义.

5 时间行为分析和时间安全性检查

针对文献[4]提到的RPU 的硬件结构，使用基于执行图的低级分析方法，计算TFG+基本块节点和时间语义节点的平台相关属性，同时对时间语义节点进行时间安全性检查.

5.1 基于RPU 的执行图

RPU 为5 段流水处理器，对应的流水段的集合为S={IF,ID,EX,MM,WB}，分别对应取指段、译码段、执行段、访存段、写回段. TFG+中每个节点对应的指令集合为I={i1,i2, …，in}. 执行图的节点集合为VXG，且VXG⊆S×I，例如，对于（IF,ij） ∈VXG，表示指令ij∈I处于流水段IF∈S. 执行图的边集合为EXG，且EXG⊆VXG×VXG，表示执行图节点间的时序依赖. 执行图的边分为2 类，如图8（b）所示，为了区分这2 类边，在执行图中使用实线和虚线分别表示，且δ(v,im)→(w,in)∈{0,1}表示2 种边，对于实线边δ(v,im)→(w,in)= 1，对于虚线边δ(v,im)→(w,in)= 0.

Fig.8 Example of execution graph图8 执行图示例

现有v∈S，w∈S，im∈I，in∈I，在执行图中存在节点（v,im）∈VXG，（w,in）∈VXG，且（v,im） → （w,in） ∈EXG，基于此详细说明这2 类边.

1） （w,in）只可以在（v,im）完成后开始，此类边用实线表示，且δ(v,im)→(w,in)= 1. 具体来说分为4 种情况.①对于多条指令，RPU 顺序发射、顺序执行，即（IF,im-1） → （IF,im），（ID,im-1） → （ID,im），（EX,im-1） →（EX,im），（MM,im-1） → （MM,im），（WB,im-1） → （WB,im），其中im-1和im为2 条连续指令. ②对于某一条指令，RPU顺序执行，即（IF,im） → （ID,im），（ID,im） → （EX,im），（EX,im） → （MM,im），（MM,im） → （WB,im）. ③数据冒险. RPU 使用数据旁路解决大部分数据冒险，而针对只能由延迟流水线解决的数据冒险，即2 条连续指令，第1 条是访存输入指令，第2 条指令需要使用第1 条指令的访存结果，需要在执行图中对此种情况构建相应的依赖关系，即存在边（MM,im-1） → （EX,im）.④控制冒险. 采用阻塞流水线的方式解决控制冒险，对于一条分支跳转指令，下一条指令的取指需要延迟到分支指令在执行段产生结果后，即存在边（EX,im-1） → （IF,im）.

2） （w,in）可以和（v,im）同时开始，但是不能早于（v,im），此类边用虚线表示，且δ(v,im)→(w,in)= 0. 此类边分为4 类，（ID,im-1） → （IF,im），（EX,im-1） → （ID,im），（MM,im-1） → （EX,im），（WB,im-1） → （MM,im），其中im-1和im为2 条连续指令.

算法2 给出基于RPU 的执行图构建算法.

算法2.基于RPU 的执行图构建算法.

输入：程序段prog；

输出：执行图节点集合VXG，执行图边集合EXG.

①VXG←fvertex（prog）；

② forVXG中每个节点（v, im）

③ ifv=IF

④EXG←{（IF, im） → （IF, im+1）, （IF, im） →（ID, im）}∪EXG；

⑤ else

⑥EXG←{（v, im） → （v, im+1）, （v, im） →（fnextstage（v）, im）, （v, im） →（fprestage（v）, im+1）}∪EXG；

⑦ end if

⑧ ifim与im+1存在数据冒险

⑨EXG←{（MM, im） → （EX, im+1）}∪EXG；

⑩ end if

⑪ ifim和im+1存在控制冒险

⑫EXG←{（EX, im） → （IF, im+1）}∪EXG；

⑬ end if

⑭ end for

算法2 中，行①fvertex（prog）构建执行图中所有的节点，行④和行⑥中构建多条指令顺序发射、顺序执行以及一条指令顺序执行相关的边，行⑥中fnextstage（v）表示流水段v的下一流水段，fprestage（v）表示流水段v的上一流水段，并且除了（v, im）→（fprestage（v）, im+1）的δ(v,im)→(fprestage(v),im+1)= 0，其余边均为δ(v,im)→(w,in)= 1.

算法2 仅适用于RPU，对于其他支持TTI 指令集的不同硬件架构，需要根据具体的架构特点对算法2 进行修改. 例如，可以通过修改流水段集合适应不同流水线级数的处理器，对于指令间由于资源竞争而产生的结构冒险问题可以在执行图中添加相应类型的依赖边来体现等.

如图8 所示，具体的程序段和对应的执行图，假设TFG+中节点包含指令i0，i1，i2，i3，计算节点执行开销需要考虑前驱节点最后一条指令i-1，所以构建i-1，i0，i1，i2，i3的执行图.i-1和i0存在控制冒险，所以存在边（EX,i-1） → （IF,i0），i2和i3存在数据冒险，所以存在边（MM,i2） → （EX,i3）.

5.2 执行图节点属性

对于整个执行图来说，资源集合R={IF,ID,EX,MM,WB}表示和节点执行相关的所有资源的集合，A={ar|r∈R}表示对于当前执行图中所有资源的释放时间.

现在给出执行图中的每个节点的属性，以及每个属性的计算过程，各属性中提到的时间均以cpuClk周期为单位.

假设流水段v、指令im，对应执行图中节点（v,im）.

1）λ(v,im)，表示指令im在流水段v从就绪到完成需要花费的时间.

计算过程为：如表4 所示，给出RPU 各类指令在各个流水段花费的时间. 时间指令ttiat，ttoat，delay，需要在流水线的执行段判断系统时间是否到达预设的时间，如果没有到达预设时间，要进行延时操作，所以在执行段存在的延迟时间 τ需要根据前驱代码段的执行时间进行判断. 而mtfd 指令没有具体实现，所以不考虑mtfd 在每个流水段的执行时间. RPU 采用理想的存储架构，即访问指令存储器和数据存储器均为1 个cpuClk 周期，对于其他类型的存储架构，可以进行额外分析，确定指令在各流水段的执行时间，再进行后续的计算. 例如，假设需要考虑指令Cache 的命中或缺失，且指令Cache 命中时的访存时间为1 个cpuClk 周期，系统设计者可以通过指令Cache 分析，确定每条指令的Cache 命中情况，若Cache 命中，则该指令在取指段的执行时间为1 个cpuClk 周期，若Cache 缺失，则该指令在取值段的执行时间将会大于1 个cpuClk 周期，所以表4 中所示的所有指令在取指段的执行时间为1+，表示取值时间最小为1 个cpuClk 周期，而具体值需要根据分析确定，同理，访存指令和ttiat/ttoat 指令的在访存段的执行时间也为1+，具体的访存和定时输入输出的时间需要结合实际运行情况分析确定.

Table 4 Execution Time of the Instructions in Each Pipeline Stage of RPU表4 指令在RPU 各流水段的执行时间

2）E(v,im)={∈{0,1}|r∈R}，表示处在流水段v的指令im开始执行是否会受到R中某个资源的影响.

计算过程为：如果节点（v,im）本身执行依赖于资源r∈R，那么=1. 另外，如果节点（v,im）任意前驱节点（x,ij），即（x,ij） → （v,im）∈EXG，存在=1，则=1.

3）D(v,im)={|r∈R}，表示资源释放到指令在流水段就绪执行之间的延迟时间，即R中某个资源释放与处在流水段v的指令im开始执行的时间间隔.

计算过程为：对于资源r∈R，考虑（v,im）的所有前驱节点（x,ij），即（x,ij） → （v,im）∈EXG，从资源r释放到节点（v,im）就绪的延迟时间为

4）ρ(v,im)，表示指令im在流水段v的就绪时间，即指令im在流水段v可以开始执行的时间.

计算过程为：节点（v,im）的就绪时间为

5.3 平台相关属性分析和时间安全性检查

整个分析和验证流程如图9 所示，首先分析TFG+中由普通指令构成的基本块节点的平台相关属性；再结合TFG+中的控制流信息分析时间语义节点的平台相关属性；最后，根据每个时间语义节点的语义要求以及平台相关属性的分析结果，对每个时间语义节点进行时间安全性检查，验证TTI 程序运行时指令的语义能否正确表达.

Fig.9 Flow graph of temporal behavior analysis and semantic verification图9 时间行为分析和语义验证流程图

下面分别介绍基本块节点和时间语义节点的平台相关属性确定和时间安全性检查的流程.

1）基本块节点

对于基本块节点，只需要确定基本块的执行开销. 首先对TFG+中每个基本块节点构建执行图，再根据5.2 节中执行图节点属性，确定基本块的执行开销.

定理1.基本块节点执行开销定理. 基本块节点bb∈BB，基本块最后一条指令为in，基本块前一条指令为i-1，整个基本块的执行开销为

证明. 基本块最后一条指令为in，基本块前一条指令为i-1，当前基本块的执行开销为

即

假设，对于节点（WB,i-1）和（WB,in）的关键资源分别为α ∈R，β ∈R，即

由于RPU 为顺序执行的5 段流水线，对于资源集合R={IF,ID,EX,MM,WB}，（WB,i-1）会依赖于所有的5 个资源. 由此可得

考虑基本块前驱指令为时间语义指令的情况，即i-1为ttiat，ttoat，delay，对于时间语义指令i-1在执行段产生的延迟，以τ(EX,i-1)表示，由于指令i-1在执行段本身存在1 个时钟周期的执行时间，故节点（EX,i-1）执行时间λ(EX,i-1)=1+τ(EX,i-1)，而执行图（WB,i-1），（WB,in）节点的D(WB,i-1)和D(WB,in)均会受到τ(EX,i-1)的影响，所以最后执行开销的计算不会因为延迟时间τ(EX,i-1)而产生额外的问题. 证毕.

2）时间语义节点

TFG+中时间语义节点的平台相关属性分析和时间安全性检查，沿着TFG+控制流进行，所以在下述分析中，假设当前时间语义节点的所有前驱时间语义节点均完成平台相关属性分析和时间安全性检查.

首先介绍时间语义节点分析需要的映射函数.

①next：{start}∪ATP∪ATdP∪RTP∪RTdP∪RBP→V，映射时间语义节点、开始节点、相对基准点到邻接后继节点.

②pre：ATP∪ATdP∪RTP∪RTdP∪RBP→V，映射时间语义节点、相对基准点到邻接前驱节点.

③tpre：ATP∪ATdP∪RTP∪RTdP∪RBP→ATdP∪{start}，映射时间语义节点、相对基准点到距该节点最近的一个前驱绝对点时间语义节点，如果没有这样的前驱绝对点时间语义节点，则映射到开始节点.

④tjitter：ATP∪ATdP∪RTP∪RTdP∪RBP→，映射时间语义节点到该指令延迟判断时间和前一条指令执行完成时间的差值，以及映射相对基准点到对应的getti 指令读取ctr 的时间和前一条指令执行完成时间的差值. 设计这一函数是为了提升TTI 程序时间行为分析的紧致程度，由于RPU 底层体系结构采用流水线机制，时间语义指令与获取系统时间指令的执行会和该指令的前驱指令重叠，所以在计算该类指令相应操作开始执行的系统时间时，需要考虑该类指令与其前驱指令由于重叠执行而产生的时间影响. 假设v∈ATP∪ATdP∪RTP∪RTdP∪RBP，v对应指令i0和指令i0的前驱指令i-1，构建指令i0和指令i-1的执行图，由于延迟判断、获取ctr 均在执行段进行，所以tjitter相当于计算指令i0在执行段就绪时间与前驱指令i-1在写回段完成时间的差值，即

根据上述基本块节点执行开销中式（1）的证明过程可得

⑤tWCET：V×V→ N，映射TFG+的2 个节点到这2 个节点及2 个节点间所有节点对应程序段的WCET. 假设有节点v1和v2，v1到v2所有节点的执行开销已知.TFG+给出了节点间控制流信息，而程序循环次数等流事实可以由额外的分析或用户指定的方式给出，最后，tWCET（v1,v2）可以通过IPET 得出.

现对TTI 程序中4 种时间语义进行时间行为分析并进行时间安全性检查.

1）绝对点时间语义节点. 假设绝对点时间语义节点为vatdp∈ATdP.vatdp预设系统时间和最近一个前驱绝对点时间语义节点预设系统时间的差值为

如果vatdp没有前驱的绝对点时间语义节点，那么tpre（vatdp） =start，所以

将单位转化为cpuClk 周期为

考虑vatdp对应指令和前一条指令重叠执行，程序从tpre（vatdp） 对应指令执行完成到vatdp对应指令的延迟判断阶段（执行段）消耗的CPU 时钟周期为

如图10 所示，绝对点时间语义节点2 种执行时序图中vatdp和tpre（vatdp）对应指令分别为in和in-1. 图10（a），TTI 程序执行到绝对点时间语义节点时，系统时间小于预设时间，需要延迟的执行时序图；图10（b），TTI程序执行到绝对点时间语义节点时，系统时间等于预设时间，不需要延迟的执行时序图.

平台相关属性计算分3 部分：

①节点延迟. 根据TFG+中的平台相关属性定义，tpre（vatdp）对应指令执行完成相对于系统时刻开始的偏移时间为coff（tpre（vatdp））. 如图10（a）所示，vatdp对应指令在执行段需要的延迟时间为

②执行开销. 计算前驱代码段最坏执行情况下vatdp的执行开销.vatdp对应指令i0，指令i0前一条指令i-1，构建i0和i-1的执行图. 此时，i0在执行段的延迟时间已知，所以λ(EX,i0)也已知，和基本块节点的执行开销计算过程一致，由式（1）可知：

③相对于系统时刻开始的偏移. 点时间语义节点对应指令的操作时间为to，RPU 中ttiat（ttoat）输入（输出）操作的时间为访存段1 个cpuClk 周期的访存开销，加上写回段1 个cpuClk 周期的写回开销，所以to共2 个cpuClk 周期. 另外指令在执行段除了额外的延迟时间，还存在1 个cpuClk 周期的执行时间. 如图10 所示，点时间语义节点完成执行相对于系统时刻的偏移为

时间安全性检查为：绝对点时间语义节点vatdp，要求输入输出开始和完成在tATdP（vatdp）和tATdP（vatdp） +1 之间. 由于采用延迟机制，输入输出操作的开始时间一定大于等于tATdP（vatdp），现在只需要操作的完成时间小于tATdP（vatdp） + 1 即可，所以对于TFG+中的绝对点时间语义节点需要满足要求：

2）绝对段时间语义节点. 假设绝对段时间语义节点vatp∈ATP. 和绝对点时间语义节点相同，首先计算vatp预设系统时间和最近一个前驱绝对点时间语义节点预设系统时间的差值，并转化为CPU 时钟周期，即

如果vatp对应指令mtfd，那么平台相关属性均为0，只需要验证mtfd 语义. 而通过延迟实现的指令delay，语义一定能得到满足，所以只需要计算平台相关属性.

下面讨论delay 平台相关属性计算. 如图11 所示，delay 节点2 种执行时序图，其中vatdp和tpre（vatdp）对应指令分别为in和in-1，图11（a）为delay 节点需要延迟的执行时序图，图11（b）为不需要延迟的执行时序图. 程序从tpre（vatp）执行完成到vatp的延迟判断阶段（执行段）消耗的cpuClk 周期为

Fig.11 Timing diagram of absolute timing semantic图11 绝对段时间语义时序图

平台相关属性计算分为3 部分：

①节点延迟. 和绝对点时间语义节点的分析过程相同，vatp对应指令在执行段需要的延迟时间为

② 执行开销. 计算前驱代码段最坏执行情况下vatp的执行开销.vatp对应指令i0，指令i0前一条指令i-1，构建i0和i-1的执行图，由式（1）可知：

下面讨论mtfd 指令时间安全性检查.vatp对应mtfd 指令要求指令前代码段的完成时间小于等于tATP（vatp），所以需要满足要求：

3）相对点时间语义节点. 此处的相对语义，均指运行时确定的相对点时间语义. 运行时确定的相对点时间语义通过getti 和ttiat（ttoat）指令组合的形式表达，如图12（a）所示，运行时确定的相对点时间语义的时序图，getti 指令获取系统时间处在1 个系统时刻内，在系统时刻的具体位置需要根据执行情况确定. 为保证系统运行时时间语义指令的正确性，如图12（b）所示，在时间安全性检查时，假设getti 指令在系统时刻最后读取系统时间. 而对于相对点时间语义指令的延迟时间等平台相关属性，则根据前驱代码段最坏执行情况进行分析.

Fig.12 Timing diagram of relative timed semantic图12 相对点时间语义时序图

假设相对点时间语义节点为vrtdp∈RTdP，对应的相对基准点为vrbp∈RBP.vrbp对应的getti 指令会在EX段读取系统时间，所以从getti 读取系统时间（EX段）到vrtdp的延迟判阶段（执行段）消耗的cpuClk 周期，还需要加上getti 指令执行段、访存段、写回段的执行时间，对于RPU 来说为3 个CPU 时钟周期，结果为

平台相关属性计算分2 部分：①节点延迟. 如图13 所示，vrbp对应的getti 指令在执行段的时间相对于系统时刻开始的偏移为offset，该偏移时间受到vatp前一个绝对点时间语义节点或程序开始时间的影响，图13 中假设getti 指令的前一个绝对点时间语义指令为in-1. 首先，tpre（vrtdp）对应指令执行完成到vrbp对应getti 指令的执行段的时间为

Fig.13 Timing diagram of getti instruction execution图13 getti 指令执行时序图

vrbp对应的getti 指令执行段相对于系统时刻开始的偏移时间为

vrtdp在执行段的延迟时间为

②执行开销.vrtdp对应指令i0，指令i0前一条指令i-1，构建i0和i-1的执行图. 由式（1）可知：

下面讨论时间安全性检查.vrbp对应的getti 指令获取的系统时间，会受到前驱代码段的执行时间的影响，只考虑前驱代码段的最坏执行情况，不一定能保证后续相对点时间语义指令的正确性. 图14（a）显示前驱代码最好执行情况下，vrbp和vrtdp间程序的允许执行时间tb；图14（b）显示前驱代码最坏执行情况下，vrbp和vrtdp间程序的允许执行时间tw. 图14 中，getti 指令最好执行情况下获取到的系统时间为y，getti 指令最坏执行情况下获取到的系统时间为x，存在y＜x，显然tw＞tb.

Fig.14 Example of impact of getti instruction predecessor code fragment图14 getti 指令前驱代码段的影响示例

如图14（b）所示，验证时假设vrbp读取系统时间，发生在系统时刻最后，vrtdp对应指令的操作时间为to，所以为保证相对点时间语义的正确性，需满足3 个要求：

第1 个要求保证相关程序段的执行时间不超过限定时间；第2 个要求保证输入输出操作的时间不超过限定时间，其中加1 为vrtdp对应指令在执行段除了延迟以外的1 个cpuClk 周期；第3 个要求保证程序段执行以及输出输入操作的时间不超过限定时间.

4）相对段时间语义节点. 假设相对段时间语义节点为vrtp∈RTP，对应的相对基准点为vrbp∈RBP. 和相对点时间语义节点相同，从getti 读取系统时间（执行段）到vrtp的延迟判阶段（执行段）消耗的CPU 时钟周期为

和绝对段时间语义节点相同，如果vrtp对应指令为mtfd，tjitter（vrtp）=0，且只需验证mtfd 语义. delay 指令，只需要计算平台相关属性.

delay 指令平台相关属性计算分2 部分：

①节点延迟. 和相对点时间语义节点相同，tpre（vrtp）对应指令执行完成到vrbp对应getti 指令的执行段的时间为

vrbp对应的getti 指令执行段相对于系统时刻开始的偏移时间为

vrtp在执行段的延迟时间为

②执行开销.vrtp对应指令i0，指令i0前一条指令i-1，构建指令i0和i-1执行图，由式（1）可知：

下面讨论mtfd 指令时间安全性检查. 和相对点时间语义验证相同，考虑getti 指令执行的最坏情况.假设vrbp对应getti 指令执行段读取系统时间发生在系统时刻最后，所以为保证相对段时间语义的正确性，需满足要求：

6 TTI 程序示例

本节给出TTI 程序示例，并对TTI 程序进行时间行为分析和时间安全性检查，最后通过在RPU 上实际部署运行，验证时间行为分析和时间安全性检查的正确性. 本节主要有2 个应用示例，分别为自动驾驶示例和防抱死系统示例.

6.1 自动驾驶示例

本文采用文献[4]中给出的自动驾驶示例. 假设一个自动驾驶系统中有3 个任务：1）采集任务，传感器采集数据，进行数据预处理，周期为2 ms；2）分析任务，对预处理之后的数据进行分析和处理，得到响应数据，周期为1 ms；3）执行任务，将响应数据分发到执行器，周期为2 ms.

使用交错LET 语义对任务集进行实现，图15 显示了该任务集的任务分解和建模时序，虚线箭头体现了任务的数据依赖关系. 其中，每个任务被分解为3 个子任务，分别为I，C，O，其中O 和I 这2 个子任务被合并为一个OI 子任务组，保证了该任务集的交错LET 语义.

Fig.15 Interleaved LET implementation图15 交错LET 语义实现

任务1 对应采集任务，t1oi 对应采集任务的OI子任务组，t1c 对应采集任务的C 任务. 任务2 对应分析任务，t2oi1 对应分析任务第1 个周期的OI 子任务组，t2c1 对应分析任务第1 个周期的C 任务，同理，t2oi2，t2c2 分别对应分析任务第2 个周期的OI 子任务和C 任务. 任务3 对应执行任务，t3oi 对应执行任务的OI 子任务组，t3c 对应执行任务的C 任务. 最后自动驾驶示例的实现代码如图16 所示，RPU 提供了硬件多线程机制，所以将任务分类放置在不同的硬件线程上，其中0 号硬件线程（thread 0）用于初始化系统，1 号硬件线程（thread 1）用于执行OI 子任务，2号硬件线程（thread 2）用于执行C 任务，3 号硬件线程（thread 3）用于执行软实时任务. 可以使用TTI 指令集中的并发管理指令，控制硬件线程的调度时间，从而确定硬件线程上每个任务的调度时间. 如图16 所示，为自动驾驶系统在RPU 各硬件线程上的程序.

Fig.16 Example of autonomous driving program图16 自动驾驶程序示例

现在给出运行自动驾驶示例的RPU 参数，RPU的cpuClk 频率为25 MHz，TcpuClk为0.04 μs，stdClk 频率为1MHz，TstdClk为1 μs，stdClk 和cpuClk 同步，且时间粒度为25，即1 个系统时刻为25 μs.

如表5 所示，给出LET 实例中每个任务程序的属性. 任务1、任务2、任务3 对应的C 任务是普通程序，OI 子任务是TTI 程序，每个OI 子任务中都需要分别表达输入和输出绝对点时间语义，且对应不同的系统时间. 另外给出每个任务被调度执行的系统时间.

Table 5 Example of Tasks Properties表5 任务属性示例

现在给出自动驾驶示例中C 任务WCET 分析结果，t1c 的WCET 为0.5 ms，t2c1 和t2c2 的WCET 为0.25 ms，t3c 的WCET 为0.5 ms. 自动驾驶示例中每个任务的OI 子任务的程序结构类似，所以使用t3oi 作为例子进行说明. 如图17 所示，t3oi 任务对应TTI 程序和TFG+，图17 中省略部分分别表示t3oi 在指令ttoat 执行前的准备工作和指令ttiat 执行后的处理工作，此部分由普通指令构成，所以在TFG+中对此部分的普通基本块节点进行省略. 下面给出TFG+中程序属性和平台相关属性.

Fig.17 Task t3oi program and TFG+图17 任务t3oi 程序和TFG+

1）程序属性. 除时间粒度，TFG+此类属性的单位均为系统时刻. TFG+中时间粒度ttg= 25，任务开始系统时间tstart= 6，ttoat 指令对应绝对点时间语义节点v1∈ATdP，ttiat 指令对应绝对段时间语义节点v2∈ATdP，ttoat 指令预设系统时间为tATdP（v1） = 7，ttiat 指令的预设系统时间为tATdP（v2） = 7.

2）平台相关属性. TFG+此类属性的单位均为cpuClk周期. t3oi 在指令ttoat 前的准备工作的最坏情况下的执行开销为200 个cpuClk 周期，以及指令ttiat 后的处理工作的最坏情况下的执行开销为300 个cpuClk 周期. 首先，计算节点v1的平台相关属性，并验证节点v1对应ttoat 指令的语义. 根据式（3），计算节点v1预设时间和任务开始时间的差值并转化为cpuClk 周期：

RPU 在系统时间为6 时执行t3oi 任务，任务开始相对于系统时刻开始的偏移为0，所以coff(start)=0.计算从任务开始执行到v1的延迟判断阶段消耗的cpuClk 周期，由式（4）可得

由于t3oi 在执行ttoat 前的准备工作的WCET 为200 个cpuClk 周期，即

对于v1延迟判断时间和前一条指令执行完成时间的差值tjitter（v1），需要构建执行图，如图18 所示，其中 τ表示ttoat 指令在执行段的延迟时间. 根据式（2），执行图节点信息可得

Fig.18 Example of task t3oi execution graph图18 任务t3oi 执行图示例

由式（5），节点v1对应指令的延迟时间为τ=td(v1)，且

如图17 所示，根据节点v1的延迟时间和执行图中节点信息，由式（6），节点v1执行开销为

由式（7），相对于系统时刻的偏移为

对于RPU 来说，输入操作的时间to= 2，所以

最后，进行时间安全性检查，即

节点v1对应ttoat 指令的语义可以得到保证.

对于v2的平台相关属性的计算和v1类似，给出v2平台相关属性的计算结果. 节点v2和节点v1的预设时间相同，所以节点v2的延迟时间为td(v2)=0，执行开销为ct(v2)=1，相对于系统时刻开始的偏移为coff(v2)=4，所以v2的语义也通过验证.

至此任务t3oi 时间行为分析和语义验证完成，其他时间语义程序的分析和验证过程类似. 图19 为自动驾驶示例在RPU 上的运行时序图. 在图19 中，给出每个绝对点时间语义指令生效的实时间，将表5中每个时间语义指令预设时间转化为实时间后，和图15 进行比较可知，语义均正确表达，同时，LET 语义也得到保证.

Fig.19 Runtime time diagram of RPU threads图19 RPU 线程运行时序图

6.2 防抱死系统示例

防抱死系统（anti-lock braking system, ABS）是为了防止车轮在紧急刹车过程中车轮抱死而导致车辆失控的控制系统，ABS 最早于1950 年在文献[32]中提出，现在广泛应用在车辆的刹车控制系统中. 本文采用LET 编程模型，实现ABS 中的控制器部分，并且将LET 模型映射至TTI 程序，通过时间行为分析和时间安全性检查验证时间语义指令的正确性，最后部署到RPU 上，验证TTI 程序的功能和时序的正确性.

如图20 所示，ABS 的控制模型有5 个部分：车辆、车轮、转差、摩擦以及控制器. 车辆部分的输入为摩擦系数mu，输出为车辆速度vv，以及地面对车轮的摩擦力Ff；车轮部分的输入为来自地面的摩擦力Ff以及控制器部分施加给车轮的刹车扭矩Tb，输出为车轮的角速度ww；转差部分的输入为车辆的速度vv，以及车轮的角速度ww，输出为轮胎和地面的转差s；摩擦部分的输入为转差s，输出当前车轮相对地面的摩擦系数mu；控制器部分的输入为转差s，以及车辆的速度vv，输出为应当施加给车轮的刹车扭矩Tb. 各部分连接起来构成一个自反馈系统.

Fig.20 ABS control model图20 ABS 控制模型

ABS 模型中除控制器外的其余部分在模拟物理环境以及作为传感器输入，控制器部分通过特定算法控制整个ABS，而且控制器部分的算法具有硬实时性、周期性、I/O 特性等，适合使用LET 编程模型.图21 所示为控制器部分的具体构成，控制器部分的输入为转差s和车辆速度vv，输出为刹车扭矩Tb，其中控制器部分可以根据转差的大小调整输出的刹车扭矩，车辆速度用来判断是否需要防抱死控制，当车辆速度小于规定的最小速度vmin，不需要进行防抱死控制. 由于车辆转差在0.2 时，车轮和地面产生的摩擦力最大，刹车效果最好，所以控制器部分的目的在于通过调整刹车扭矩的大小，将车轮和地面的转差维持在0.2 左右，控制器部分会比较当前转差和0.2的差值，并将结果通过一个bang-bang 控制器输出为正负信号，液压系统（hydraulic system）通过接收该信号来调整刹车扭矩，最后控制系统将刹车扭矩输出，以实现对车轮的控制.

Fig.21 ABS controller part图21 ABS 控制器部分

如图22 所示，ABS 模型中控制器部分对应的TTI 程序，其中控制器部分算法采用交错语义的LET编程模型实现，和6.1 节自动驾驶示例不同，ABS 控制器部分代码将LET 中的OI 子任务和C 任务合并在一个TTI 程序中.

Fig.22 TTI program of controller part图22 控制器部分TTI 程序

图22 中寄存器a7 中的值表示控制算法的周期，可以根据具体的需求确定，控制算法会在周期开始，使用ttoat 指令定时输出上一轮计算得到的刹车扭矩，使用ttiat 指令定时输入本轮计算刹车扭矩需要的转差和车辆速度，然后经过图22 中所示计算过程，确定本轮需要输出的刹车扭矩.

运行图22 所示控制器部分TTI 程序的RPU 参数和6.1 节中自动驾驶示例相同. 控制算法的执行周期为2 ms. 如图23 所示，控制器部分TTI 程序对应的部分TFG+. 该TFG+是将TTI 程序中循环展开构建，对应TTI 程序中第1 轮循环和第2 轮循环，其中第1轮循环为图22 中行①～⑬内容，该轮循环中绝对点时间语义指令需要在0 ms 完成相应操作；第2 轮循环为图22 中行④～⑬内容，且第2 轮循环中的行⑤⑥的时间语义指令分别对应TFG+中的绝对点时间语义节点v1，v2，v3，这3 个节点对应指令需要在2 ms 完成相应操作. 显然如果图23 中TFG+对应的TTI 程序可以通过时间安全性检查，则图22 中TTI 程序后续循环的时序正确性也可以得到保证.

Fig.23 TFG+ of controller algorithm图23 控制器算法的TFG+

经过时间行为分析和时间安全性检查图23 所示控制器部分TTI 程序中时间语义指令均能正确执行，图24 显示控制器部分TTI 程序第1 轮和第2 轮循环在RPU 上运行的时序图. 图24 中O 表示定时输出指令，I1 和I2 分别表示2 条定时输入指令，第1轮循环的时间为0～2 ms，第2 轮循环的时间为2～4 ms. 根据图24 可知，定时输入、定时输出操作均在规定的系统时刻内完成，符合ABS 中控制器部分对于时序的要求.

Fig.24 Runtime time diagram of controller part图24 控制器部分运行时序图

7 总 结

通用计算机在指令集架构中没有提供时间语义指令，导致上层控制模型中的时间行为无法精确自然地映射至程序代码，控制精度大大降低，系统的实时性受到影响.

本文在已经提出的TTI 指令集基础上，总结了TTI 指令集可以表达的4 种时间语义，以此来描述复杂系统的时间行为. 并且提出了TTI 程序的表示TFG+，同时，基于RPU 给出了分析TTI 程序时间行为和时间安全性检查的方法.

未来，我们将进一步完善TTI 指令集相关工作，对TTI 指令集语义进行形式化说明，以及扩展TFG+对并发语义的支持.

作者贡献声明：高银康提出思想、撰写论文；陈香兰、龚小航、蒋滨泽、李曦、周学海提供论文撰写指导和修改意见.