一种具有时间语义的实时处理器模型

2021-06-17陈香兰周学海

计算机研究与发展 2021年6期

汪超陈香兰章博李曦王超周学海

(中国科学技术大学计算机科学与技术学院合肥 230027)

(wcwxy＠mail.ustc.edu.cn)

实时嵌入式系统(real-time embedded system,RTES)是航空航天、汽车和医用仪器等安全关键设备的计算与控制核心,需要实时地与被控物理环境进行交互,其功能的正确性不仅取决于计算结果的逻辑正确性,还取决于与外界交互的时间正确性.

为了保证RTES系统的时间行为正确,要求其软硬件系统具有时序确定性和可预测性[1].然而,现代计算机系统的体系结构、运行时环境、编程语言等各个抽象层次均缺乏精确的时间语义和表达时序属性的显式结构,使得系统设计者只能采用编程抽象之外的手段(如定时中断)进行时序控制,导致控制和验证程序的时序属性或处理时序冲突十分困难,并且任何软硬件改动都将对系统时序造成不可预测的影响,甚至不得不重新进行系统设计.尤为重要的是,由于上述机制内在的异步不确定性,难以建立系统的确定性抽象模型,并据此进行严谨的形式化时间行为分析,无法满足硬实时安全性设计要求.

本文重点讨论指令集体系结构(instruction set architecture,ISA)层次缺乏时间语义的问题.现代处理器的数字电路能够以纳秒级细粒度执行,但常规ISA屏蔽了这一宝贵资源,未提供具有时间语义的指令集,程序员只能依赖操作系统的时间服务进行粗粒度时序控制,其可预测时序粒度比硬件高几个数量级.常规ISA所定义的处理器行为的正确性与其时序无关,时序仅仅是计算性能指标,而不是正确性判据.

ISA层的基础设施缺乏时间语义已经成为安全关键实时系统设计方法学的一个基础性问题,需要重新考虑实时处理器的ISA和微体系结构组织.

在先前的工作[2]中,我们尝试提出一种具有时间语义的实时计算机体系结构模型实时机(realtime machine,RTM),设计了一版具有时间语义的指令集TTI(time-triggered instruction set),分析了其硬件实现的可行性.本文进一步完善RTM的定义,抽象出独立的标准时钟部件,明确中央处理器(central processing unit,CPU)时钟和标准时钟协同控制的模式.接着,本文以RTM为基础,结合时间触发自动机(time-triggered automata,TTA)理论,重新定义TTI,为其增加执行时间约束指令和任务并发管理指令,并探讨了TTI指令集的时间语义完备性问题.最后,本文通过一款实时处理器——实时处理单元(real-time processing unit,RPU)的设计实现和应用示例,验证了TTI的时间语义表达能力.

加州大学伯克利分校(University of California,Berkeley,UCB)的PRET机[3]研究动机与我们相近.PRET小组提出了限定代码段执行时间的Deadline指令[4]和MTFD指令[5],并设计了Flex PRET处理器[6].但是,他们重点关注程序时序行为的可重复性,以辅助最坏执行时间(worst-case execution time,WCET)分析,而我们以建立具有时间语义的计算机体系结构为目标,为程序员提供表达和控制程序时序行为的时间语义指令集,作为实现时序确定性系统的基础设施.

本文的主要贡献包括3个方面:

1)提出支持时间语义的实时计算机体系结构模型RTM.RTM以冯·诺依曼机为参照,通过添加标准时钟stdClk,建立ISA层次的时间模型.stdClk作为定义系统时间语义的基础,允许程序员以实时间(real time)控制RTM机I/O操作的时间属性.同时,stdClk与控制处理器执行的CPU时钟cpuClk协作,既最小化程序执行时间和I/O时序抖动,又实现了程序的I/O时序行为物理平台无关性.

2)提出作为RTM模型软硬件接口的时间语义指令集TTI.TTI以TTA理论为基础定义最小时间语义指令集,为程序员提供直接表达和控制程序时序行为的时间语义指令.

3)设计和实现实时处理器RPU.RPU基于RTM模型,为RISC-V指令集添加了TTI扩展,保证指令集时间语义.同时,它采用硬件粗粒度多线程技术(coarse-grain multithreading,CMT),以时间触发(time-triggered,TT)机制进行线程调度,保证任务级时间语义.

逻辑执行时间(logical execution time,LET)编程模型[7]是一种硬实时软件模型.本文通过LET任务集的设计示例,验证了上述工作的有效性.

1 相关工作

本节对当前实时计算设计方法、时间属性和行为建模、实时处理器设计3个方面的研究工作进行梳理.

1.1 实时计算设计方法

传统的实时嵌入式系统设计方法关注计算过程的时序可预测性,通过设计阶段进行时序分析来满足系统的时间约束.可调度性分析(schedulability analysis)[8]和端到端分析(end-to-end analysis)[9]都以任务作为最小分析单位,以任务的WCET作为输入.然而,现代计算机系统通过引入计算并行化和访存缓存化等优化机制来提升平均性能,导致系统出现严重的时序不确定性问题,任务的WCET难以紧致确定[10].本质上,保证任务的WCET不是实时系统的目标,现有方法必须要在系统设计的同时进行WCET分析以保证系统的时序正确性,这使系统开发变得复杂.另一方面,将任务作为最小单位的设计分析方法也无法保证任务内/指令级操作的时间语义,即只能表达指令在一段时间内执行的语义,不能直接表达指令在某个时刻执行的语义.

20世纪90年代以来,研究者逐步认识到实时系统诸多问题的根源:实时计算难以依托在通用计算之上,实时系统领域需要重新定义计算机系统的各个层次[11-12].研究表明:采用构件化软件体系结构、时间触发执行机制[13]和LET编程模型[7]构建时序关键系统是实现实时系统时序隔离(temporal isolation)、可预测(predictability)、可组合(composability)和可扩展(extensibility)的可行技术路线.DCW[14]在现代处理器上实现了反应式可预测的LET编程框架,但受通用计算机体系结构和任务执行机制的限制,LET模型系统执行效率低下,需要具有时间语义的ISA和时序行为确定的体系结构支持.

1.2 时间属性和行为建模

20世纪50年代,逻辑学家在数理逻辑(logic)框架中添加时间语义,建立了时态逻辑(temporal logic)框架,以表达和推理用时间修饰的谓词.Pnuel将时态逻辑引入计算机科学领域[15].时态逻辑作为描述型的语义表达体系,适合系统建模和验证,但是难以应用于定义操作型语义的计算过程.

1991年Henzinger为符号变迁系统(labeled transition system,LTS)添加时间语义,提出时间迁移系统(timed transition system,TTS)模型[16],用于建模复杂的并发实时系统.TTS采用一个全局的虚拟时钟,时间域是实数集,时间随着事件的发生隐式地不等间距地步进.在全局时钟的度量下,TTS约束了转移(transitions)发生时间的上下界,并用时间状态序列(timed state sequences)刻画系统的状态变化.TTS作为LTS,重点关注系统所处状态及其变迁,对状态变迁时发生的计算说明较少.

1991—1994年,Alur和Dill为自动机模型添加时间语义,提出和完善了时间自动机(timed automata,TA)[17],用以建模实时系统随着时间的发展而不断变化的行为.时间自动机采用离散时间模型(discrete-time model),该时间模型要求时间序列是单调递增的整数值,即时间域是正整数域.而它接受的时间词(timed words)则采用稠密时间模型(dense-time model).时间词是指一个由关联实数时间值的符号组成的无穷序列.时间自动机采用多时钟模型来表达系统的时间需求,通过系统时间与特定时刻的大于、小于和等于关系分别表达“在……之后”“在……之前”和“在……时刻”的时间语义.时间自动机可以用来形式化地建模和验证实时系统的时间属性.相比于TTS,TA直接通过描述系统的计算过程来刻画系统的行为.另一方面,TTS只能约束转移发生时间的上下界,而TA则可以直接表达操作发生于特定时刻的语义.

时间自动机基于多时钟模型和事件触发.2004年Král和Mokrushin等人提出时间触发自动机(TTA)[18].TTA基于单时钟模型,使用“[n]”和“(n)”表达“在n时刻”和“每n时刻”的时间语义.另外,时间触发自动机接收数字化(digitalized)的时间词.究其含义,时间自动机认为计算系统从外界接收连续的信息,而时间触发自动机认为计算系统从外部设备接收处理后得到的数字信号.

时间自动机理论和时间触发自动机理论对时间语义指令集的设计具有重要的指导意义,是研究时间语义完备性理论的重要参考.

1.3 实时处理器设计

Schoeberl小组进行了一系列优化硬件最坏执行时间分析的研究.通用处理器的设计中,体系结构层次的新技术如流水线、高速缓存、分支预测和乱序执行等提升了系统的平均性能,但这些技术使程序的WCET分析越来越复杂,甚至难以进行.JOP[19]是Java虚拟机的硬件实现.JOP采用简单的三段流水使Java程序的WCET分析更准确.Patmos处理器[20]同样以优化WCET分析为目标,它采用为该目标定制的类RISC指令集.同时,Patmos使用Method Cache作为指令Cache,使用Split Cache作为数据Cache,能够提前预知指令延迟和执行时间.Hahn和Reineke关注2种时序异常,设计具有严格访存顺序的SIC(strictly in-order core)[21].SIC具有单调性,消除了时序异常并简化了WCET分析.

Roop小组对支持同步语义的反应式处理器[22]进行研究,希望通过在指令集中增加同步语义来直接支持执行同步语言程序.同步编程语言[23]基于同步假设,通过信号管理,如轮询(polling)、发射(emission)和抢占(preemption)等进行程序的同步,保证了并发行为的确定性,易于程序验证.HiDRA[24]是一个实时系统的软硬件协同设计方案,使用多个反应式核REMIC[25]构造全局异步局部同步(globally asynchronous locally synchronous,GALS)的体系结构,提供类Esterel语言的同步语义.STARPro[26]与HiDRA思想一致,但HiDRA支持类Esterel的同步语义,而STARPro旨在直接支持Esterel程序执行.另外,Roop团队提出基于C语言扩展的PRET-C同步语言,并提出支持PRET-C同步语义的微体系结构ARPRET[27].ARPRET分为2部分:1)GPP实现通用计算;2)PFU负责调度和保证功能的时间属性正确.

Lee小组提出PRET(precision timed)概念[3].他们认为硬件体系结构中的数字电路时钟是精确的,但是通用计算指令集抽象掉了这个精确的时间,所以为了程序的时序行为可重复,PRET机要向上层提供这一精确的时间.该小组研制了多款PRET处理器[4,6,28].Flex PRET处理器[6]从流水线、线程调度、时间指令、存储系统4个方面对处理器的时间属性进行规范,并用时间指令DU(delay until)保证代码的执行时间下界,时间指令EE(exception on expire)保证代码的执行时间上界.此方案可以约束指令序列执行时间的上下界,无法直接表达操作发生在某个时刻的语义.Wan和Li等人在文献[29]中提出构建时间语义指令集的思想,拟添加时间语义和操作语义绑定的指令,但该想法处于比较早期的阶段.

总体而言,当前实时处理器设计研究缺乏ISA层理论模型支持.在通用计算中,图灵机[30]为通用计算机系统奠定坚实的理论基础,冯·诺依曼机[31]是通用计算机系统统一的实现模型.实时处理器理论基础的缺乏,导致时间语义难以表达,或表达能力边界不确定,程序的时序行为难以形式化验证.

2 背景知识

本节介绍具有时序确定性的系统构建范式时间触发范式以及按照时间触发范式构建的计算理论时间触发自动机,介绍时间模型的分类.后文定义时间模型,参考时间触发自动机理论设计了最小时间语义指令集TTI,并以时间触发范式实现了实时处理器RPU.

2.1 时间触发范式

事件触发范式和时间触发范式是2种截然不同的系统设计范式,本节参考文献[13],对2种范式进行介绍.2种系统设计范式的核心区别是:在事件触发系统(event-triggered systems,ET系统)中,重大事件的发生导致了响应活动的启动;在时间触发系统(time-triggered systems,TT系统)中,响应活动是在预定的时间点实时启动的.

ET系统使用中断机制感知外部事件的发生,2类主要的事件是P类事件(predictable events)和C类事件(chance events).对于P类事件,可以提前保留将来传输和处理它们所需的资源.而C类事件可能在短时间内集中发生,这将超出ET系统的处理能力,系统必须有对这类事件的存储能力,并适当限制事件的感知.在ET系统中,判断任务集满足时间约束和找出可行的调度算法都是NP难的问题.因此在实践中,ET系统往往采用静态优先级算法进行运行时调度,这导致ET系统的时间行为是运行时上下文相关的,且不具有单调性,无法保证系统的时间可预测性.设计者只有通过模拟负载进行广泛的系统测试才能判断ET系统的正确性.然而,C类事件的存在导致难以对ET系统进行全面的测试.

TT系统使用轮询机制获取外部实体的状态.轮询是周期性的,轮询发生的时间序列被称为观测格(observation grid);系统根据状态进行响应,响应发生的时间序列称为响应格(action grid).TT系统需要事件传感器对外部事件进行处理,形成系统需要的状态信息.在TT系统的设计阶段,设计者首先确定系统的观测格和时间关键任务的最坏执行时间,然后在编译时期通过调度策略生成确定的调度表,在运行时期执行简单的表查找来调度任务.因此,TT系统的时间行为是运行时上下文无关的,具有确定性.通过仔细的设计,TT系统的设计者可以精确地预测任务的时序行为和系统的时序行为.另一方面,观测格和响应格决定了TT系统的时基是离散的,离散时基确保每一种输入情况都可以被观察和再现,因而TT系统的测试更加可构造和系统化.

2.2 时间触发自动机

时间触发自动机[18]是基于事件的非即时可观察性,对时间自动机进行简化而形成的计算模型.TTA是在时间触发模式下运行的有限状态自动机,接受定时语言的数字化版本.本质上,TTA是数字计算机(或数字控制器)的时间表,描述了在给定时间点该计算机应执行的操作,可以转换为计算机上的可执行程序.

TTA采用一个全局参考时钟,时间域为整数集N,它采用隐式的时间模型,把状态变化的时刻作为隐式参考点.它接受的时间词是数字化后的时间词,更符合现代数字计算机的特征.TTA只能在满足时序约束的整数时间点接收时间词(消耗外部事件)和发生转移.时序约束集合Θ包含周期性的和瞬时的(也称非周期性的)2种时序约束,分别由a(n)和a[n]来表示.标有a(n)的转移表示每n个时间单位应该检查a是否已发生;标有a[n]的转移表示第n个时间单位应该检查a是否已发生.

定义1.时间触发自动机[18].时间触发自动机ATTA定义为四元组〈Σ,S,s0,T〉,其中:

1)Σ是有限字符表,字符代表事件;

2)S是有限状态集合;

3)s0∈S是初始状态;

4)T⊆S×Σ∗×Θ×S是转移边的有限集合.

注:Σ∗是离散化后的Σ.

定义2.时间触发自动机行为语义[18].初始状态为(s0,0)的时间触发自动机〈Σ,S,s0,T〉的语义由3个规则定义:表示(s1,ω,[n],s2)∈T,使用表示(s1,ω,(n),s2)∈T,使用n表

其中,使用示不超过n的最大正整数.定义2中的第3条规则确保转移的发生不会导致有整数时间点被跳过.

图1是时间触发自动机的一个示例,其中的null符号表示接收长度为0的时间词,即不消耗事件发生转移.在初始状态S0时,自动机在第1个时间单位检测开始命令b是否发生,如果b发生,自动机将接收b并迁移到运行状态S1.在运行状态S1时,自动机每1个时间单位检测停止命令e是否发生,如果e发生,自动机将接收e并迁移到终止状态S3;每3个时间单位检测正常信号r是否发生,如果r发生,自动机将接收r并仍迁移到运行状态S1;每3个时间单位检测出错信号w是否发生,如w发生,自动机将接收w并迁移到故障状态S2.在故障状态S2,系统会进行复位,并在第5个时间单位迁移到S0状态.注意,如果在S1状态未检测到正常信号r的发生,状态机也会停留在S1状态,但不会接收一个r事件.

Fig.1 An example of time-triggered automaton图1 时间触发自动机示例

2.3 时间模型

时间模型是实时系统的理论核心,从时间线的构成、时间步进规则和事件观测方法等3个方面刻画和定义系统的时间行为.本文参考文献[32],对描述时间模型3个方面的维度进行说明.

描述时间模型中时间线构成的维度有:

1)离散的或者是稠密的.根据采用的时间域是离散集合还是稠密集合,时间模型分为离散时间模型和稠密时间模型.按照数学上集合连续性的概念,稠密时间模型又进一步分为连续时间模型和非连续时间模型.如果系统同时采用了离散时间模型和稠密时间模型,则系统的时间模型为混合时间模型.

2)有界的或者是无穷的.按照系统生命周期内的行为是否为周期性的,可以分为有界时间模型和无穷时间模型.

3)定序的或者是定量的.只能描述序的模型,能定序地定义时间关系,称为定序时间模型;能够描述序和时刻的模型,能定量地定义时间关系,称为定量时间模型.

教师要加强对学生们优秀的传统文化的素质教育，提升学生们的精神文化素养水平。传统文化是中华民族文化最根本的积淀，传统文化包含着丰富的爱国主义精神和优秀的道德素质文化，能够不断激发学生们的爱国热情以及提升学生们的精神文化素养水平，教师要加强对学生们的爱国主义教育，让学生们认清什么是社会主义核心价值观，树立学生们的“天下兴亡，匹夫有责”的高尚责任心和远大抱负，增强学生们的民族自豪感和自信心。其次要对学生们进行伦理道德教育，积极推行儒学教育思想，倡导与人为善以及人与社会自然的和谐相处，树立正确的社会主义荣辱观，不断塑造自我，培养自我优秀的精神品质和健康的人格。

4)线性的或者是分支的.线性时间模型为线性结构,能够表示具有唯一未来行为的属性.分支时间模型为树结构,允许用户陈述具有分支未来行为的属性.已有研究表明线性时间模型和分支时间模型是可以相互转化的.

描述时间模型中时间步进规则的维度有:

1)物理的或者是逻辑的.物理时间是指物理设备提供的时间,随实时间步进;逻辑时间是指使用某种逻辑关系对事件进行排序形成的虚拟时间,随事件发生步进.

描述时间模型中事件观测方法的维度有:

1)显示的或者是隐式的.显示时间模型使用时域范围内的显示术语,显示表达时刻,有量词可以对时间进行描述;隐式时间模型无法描述时域量词,隐含当前时刻的概念,相对于当前时刻对事件进行排序,没有量词进行度量.

2)绝对的或者是相对的.绝对时间是指使用点时间(即时刻)进行描述的时间模型;相对时间则是指使用相对于当前时间的段时间进行描述的时间模型.

另外,在分布式的场景下,时间有全局的或者是局部的之分.全局时间是指所有节点统一同步后产生的时间;局部时间是指每个节点内自己使用的时间.

3 实时机模型

本文提出RTM机模型以解决当前处理器体系结构层缺乏时间语义的问题.RTM机以冯·诺依曼机为基础,引入标准时钟stdClk,并增加时间语义指令集.TTI指令集参考TTA模型定义最小时间语义指令集,允许程序员以实时间概念定义RTM机I/O操作的时间行为属性.实时程序可以在基于RTM机的硬件平台之间进行时间语义一致的移植.

3.1 实时机模型RTM

计算机科学领域的时间概念相当原始.图灵机和冯·诺依曼机模型基于顺序控制抽象,指令一条接一条执行,时间先后关系(temporal succession)是当前机器语言级唯一可用的时序关系.虽然定义冯·诺依曼机的程序逻辑行为无需显式地引用量化时间概念,但无法满足实时系统所需要的实时间约束定义.

定义3.RTM机.RTM机对冯·诺依曼机进行扩充,如图2所示:

Fig.2 RTM machine architecture图2 RTM机结构模型

1)计算机系统由运算器、控制器、存储器、标准时钟和I/O设备等功能部件构成.

2)标准时钟用于操作定时,在保持冯·诺依曼机指令的逻辑功能不变的同时,增加约束特定操作的时序和限定操作序列(动作)的执行时间等时序功能,支持构建具有时间语义的指令集.

3)RTM机的指令字由操作码、地址码和定时码构成.操作码定义操作的功能,地址码指定操作数和下一条指令的地址,定时码指定操作的时间属性和约束.

由于各个硬件平台的时钟设备不同,即使程序具有相同的时间语义,也无法得到相同的时间行为.RTM机引入标准时钟,并据此定义其指令的时间语义,使具有时间语义的程序得到同一时间模型的支持,实现了程序的I/O时序行为物理平台无关性.

定义4.RTM机时间模型.RTM机的时间模型定义为:

1)时间线的构成是离散的、定量的、线性的时间域N.

2)时间步进规则是物理的,随牛顿时间步进.3)事件观测方法是显示的、绝对的.

RTM机以支持紧致时间设计为目标,其核心思想不是简单地在CPU中增加标准时钟,而在于明确了时间行为控制抽象,并通过提供时间语义指令集,实现了时域控制的原子性和可组合性,并最小化(周期精确)定时抖动.

时间语义指令集的完备性问题是RTM机模型的一个基础性问题,限定了RTM机的时间语义表达能力边界.需要进一步基于实时逻辑和时间自动机等理论框架对其进行研究.我们给出一种支持时间触发的RTM机时间语义指令集TTI.参考TTA模型,TTI指令集至少需要支持3种操作:

1)时间管理操作.获取全局参考时间并设置时间参考点.

2)定时触发输入操作.无论是[n]还是(n),都需要定时对事件进行采样.

3)(n)原语的周期性操作.

参考以上需求,本文在3.3节中给出了TTI的定义.

RTM机以“关注分离(separation of concerns)”和“构建正确(correct-by-construction)”为设计原则,区分逻辑控制与时域控制,为实现从时序可预测设计到时序确定性设计转变奠定了理论基础,利于实时程序代码自动生成和化简实时系统验证的复杂度.

3.2 标准时钟stdClk

现代计算机系统主要有2种时钟域:1)CPU时钟cpuClk.用于驱动其数据通路中各个功能部件同步运行.不同平台的cpuClk时钟频率不同,与应用程序的时序控制无关.文献[12]认为该时钟是精确的,但是通用计算机的ISA忽略了其时间精确性.2)操作系统和应用程序提供定时中断服务的时钟.该时钟与cpuClk异步,且时序粒度高几个数量级,程序员依赖该时钟进行粗粒度时序控制.因此,为了精确控制系统的时序,需要定义新的时钟.

定义5.标准时钟stdClk.RTM机的标准时钟std Clk是基于实时间域的物理时钟,用于实时程序的时间行为控制.

标准时钟的时间粒度依赖于应用场景,对时间精度要求较高的系统可采用粒度小(如100 ns)的标准时钟,对时间精度要求较为放松的系统可采用粒度较大(如50μs)的标准时钟.引入标准时钟后,现代计算机系统通过cpuClk驱动指令执行,通过stdClk提供时域控制依据.cpuClk与stdClk的协作,分离了实时计算系统中的逻辑控制和时域控制,即分离了驱动计算机运行和控制计算机时序行为的时钟,有利于支持确定的时间语义,便于形式化建模和分析.另一方面,通过标准时钟来精确定时,保证程序员以统一的实时间抽象控制程序的时序行为,使得不同平台上的定时程序具有时间行为一致性.

基于标准时钟stdClk,RTM机实时程序的逻辑执行与其时域控制具有确定性的松弛同步时序关系,如定理1,可以实现周期精确的系统时序行为.

定理1.std Clk与cpuClk的关系定理.假设std Clk的周期为Tstd,cpuClk的周期为Tcpu,并假设Tcpu＜Tstd,则它们有2种关系:

1)当cpuClk与std Clk同步时,∃n∈N,使得Tstd＝n×Tcpu.

2)当cpuClk与stdClk异步时,∃n∈N,0≤t＜Tcpu,使得Tstd＝n×Tcpu＋t.

证明.由模运算可知,∃0≤c＜b,使得a＝cmodb.即∃0≤t＜Tcpu,使得Tstd＝tmodTcpu.当cpuClk与std Clk同步时,cpuClk与std Clk上升沿重合,即t＝0,Tstd＝0 modTcpu,所以∃n∈N,使得Tstd＝n×Tcpu.当cpuClk与stdClk异步时,cpuClk与stdClk无特别关系,0≤t＜Tcpu,所以∃n∈N,0≤t＜Tcpu,使得Tstd＝n×Tcpu＋t.证毕.

由定理1我们可以得到引理1.

引理1.假设stdClk上升沿发生时间为Ustd,该时间后下一个cpuClk上升沿发生时间为U ncpu,则它们满足关系:

1)当cpuClk与std Clk同步时,U ncpu－Ustd＝Tcpu.

2)当cpuClk与stdClk异步时,0＜U ncpu－Ustd＜Tcpu.

在同步情况下,引理1显然成立.异步情况下处于边界情况,即差值为0或者Tcpu时,异步情况转换为同步情况,可见异步情况同样成立.

定理1和引理1说明,可以将stdClk与cpuClk的最小偏差控制在一个cpuClk周期以内,最小化程序时序和I/O时序抖动.定理1和引理1展示的控制时序如图3所示.图3(a)中,std Clk与cpuClk为同步关系,其控制抖动为Tcpu;图3(b)中,stdClk与cpuClk为异步关系,其控制抖动小于Tcpu.

Fig.3 Timing of using stdClk for controlling图3 标准时钟的控制时序

实时系统技术往往应用在分布式场景下.而RTM系统的时间行为基于标准时钟,与运行平台无关,故在实时分布式场景中应用RTM,只需要对标准时钟进行同步.

根据标准时钟提供的定时,设计带有时间语义的指令集作为实时处理器软硬件接口,可以提供at,delay-until和timestamp等控制时间行为的指令,支持逻辑执行时间模型和时间触发等应用模式.

3.3 时间语义指令集TTI

RTM机的TTI指令集主要包含标准时钟管理指令、时间触发操作指令、执行时间约束指令、任务并发管理指令4部分指令,以及时间粒度寄存器tg(time granularity)、时间寄存器ti和时间戳寄存器ts.其中,标准时钟管理指令对系统的标准时钟进行管理,生成系统时间,规范其应用方法;时间触发操作指令定义操作和时间绑定的指令,保证了操作在指定时间触发执行;执行时间约束指令参考PRET机[12],保证一段代码的执行时间上下界;任务并发管理指令摒弃传统的使用中断的软件任务并发管理,提供确定性的硬件线程管理任务并发的能力.由于不同系统、甚至同一系统的不同运行模式需要不同的时间粒度,时间粒度寄存器tg,用于用户自定义时间粒度;时间寄存器ti表示当前的系统时间,系统时间由系统根据标准时钟和系统时间粒度生成;分布式系统中,时间戳(timestamp)是支持定序的重要数据,时间戳寄存器ts保存系统与外界交互事件的时间戳.

Table 1 Functionality of TTI"s Instructions表1 TTI指令功能

TTI指令的功能如表1所示,表1中r1,r2和rd为通用寄存器.TTI指令集包括:

1)标准时钟管理指令.setti/getti指令用于设置/获取时间寄存器ti,即系统时间;settg指令用于设置时间粒度寄存器tg,即系统当前时间粒度、时间向前自增的单位(time unit);getts指令用于获取时间戳寄存器ts,即系统上一条时间触发操作指令ttiat/ttoat的生效时间.

2)时间触发操作指令.ttiat/ttoat指令用于在指定时刻对I/O端口进行输入/输出;ttiat/ttoat指令的执行代表系统与外部环境的交互事件,会设置时间戳寄存器ts.

3)执行时间约束指令.delay指令用于约束代码的最短执行时间,即到该时间之前,delay指令会阻塞后续代码执行;mtfd指令用于约束代码的最坏执行时间,需要编译时期的检查配合完成,即保证执行该指令的时间不超过指定时间.

4)任务并发管理指令.tkend指令用于标志当前线程中任务的截止;addtk指令用于向硬件时间触发调度表添加表项,即通过addtk指令设置好静态的时间触发调度表.

TTI的正确执行需要保证其逻辑正确性和时间正确性.

Fig.4 Example of translating TTA to TTI program图4 TTA转换为TTI程序示例

3.4 TTI的时间语义完备性分析

为了支持实时计算,需要回答RTM机应该具有什么时间语义,或其最小时间指令集应包含哪些指令等问题.RTM机的逻辑功能指令集与冯·诺依曼机指令集等价,而TTI指令集的时间语义应至少具有与TTA相同的时间语义表达能力.

TTI能够充分支持TTA的时间语义:1)支持TTA时间模型.TTA采用一个全局的参考时钟,对应TTI中由标准时钟生成的系统时间ti.时间触发自动机以进入状态作为时间参考点,TTI可以使用getti获取当前系统时间,然后使用该时刻作为参考点.2)支持a(n)语义.支持周期语义可以使用循环结合时间触发操作指令来实现.周期对应循环,获取周期开始时的系统时间ti,使用ttiat在ti＋n时刻进行输入.如果输入的是a,则发生状态迁移;否则,进入下一个周期.3)支持a[n]语义.支持瞬时语义使用ttiat完成即可.

TTI对时间触发自动机语义的充分支持,意味着所有TTA可以转换成TTI程序,即TTI是TTA时间语义完备的.一个简单的转换示例如图4所示,图4(a)中TTA从S0开始运行,在第2个时间单位接收b事件转移到S1;对应图4(b)中S0代码段,S0代码段使用getti获取当前系统时间,将其加2作为ttiat的执行时刻,检查ttiat输入的事件是否为b,如果是,转移到S1代码段,否则永远停留在S0代码段.图4(a)在S1状态时,TTA每1个时间单位检测e事件是否发生,如果是,则接收e事件转移到S0状态;对应图4(b)中S1代码段,S1代码段使用getti获取当前系统时间,将其加1作为ttiat的执行时刻,检查ttiat输入的事件是否为e,如果是,转移到S0代码段,否则,跳转到begin代码段,等待下一个时间单位检测e事件是否发生,实现周期语义.

4 实时处理单元

实时处理器RPU是RTM机的实例.4.1节基于RISC-V指令集[33]定义TTI指令集,形成RISCV TTI功能模块.4.2节给出基于经典五段流水设计的RPU的原理图,RPU添加了粗粒度多线程和时间触发执行等确保时序属性的机制.接着,本文以开源32位RISC-V处理器CV32E40P[34]为框架对RPU进行实现,并以软核的方式部署到Xilinx Artix-7 XC7A100T FPGA上,实现时RPU采用的stdClk频率为1 MHz,cpuClk频率为25 MHz.4.3节和4.4节给出Xilinx Vivado 2019仿真和综合得到的时序结果和资源消耗结果.

4.1 RISC-V TTI

RISC-V是一个典型的三操作数、加载存储形式的RISC指令集架构,由基础指令集和扩展指令集组成.基础指令由基本整数指令构成,扩展指令分为标准扩展和非标准扩展两大类.现阶段的标准扩展有乘法和除法扩展(M)、原子指令扩展(A)、单精度(F)和双精度(D)运算扩展等.非标准扩展作为一个高度特殊化的扩展,允许用户根据需求自定义完成.

本文基于RISC-V非标准扩展对TTI指令集进行定义,采用RISC-V预留的opcode域custom-0,根据funct3区分上述四类指令,如表2、表3所示.RISC-V TTI扩展与原RISC-V指令集采用相同的寻址模式,有所不同的是,ttoat指令有3个操作数,都是读寄存器,即要从寄存器组中读出r1,r2和r3寄存器,最后在r1指定的时刻将r3写入r2表示的输出端口上.本文的实现平台,开源RISC-V核CV32E40P的通用寄存器组有3个寄存器读端口,因此扩展工作不会因为ttoat的特殊增加额外开销.

Table 2 Word Format of R-Type Extended TTI Instructions表2 R类型TTI扩展指令的指令字格式

Table 3 Word Format of Custom-Type Extended TTI Instructions表3 自定义类型TTI扩展指令的指令字格式

4.2 RPU的设计

本节基于经典五段流水线[35]给出以TTI为软硬件接口的RPU的设计.相较于经典五段流水新增/改动部分的原理图如图5所示.本文采用PLL分频的方法产生1 MHz的标准时钟std Clk,可参考其他文献采用更加精确的实现方法.分频的方法产生的std Clk与cpuClk周期是整倍数关系,且std Clk与cpuClk上升沿同步.由引理1可知,在本文的std Clk与cpuClk协同下,控制将会在std Clk生效后的Tcpu时间生效.

图5中的Decode模块增加了对RISC-V TTI指令的译码,Control模块增加了相应的控制.图5中的Time Unit模块负责管理std Clk,产生系统时间,如图6所示.时间粒度寄存器保存通过settg指令设置的时间粒度;cnt寄存器直接接收标准时钟进行自增,当cnt寄存器增长到与tg寄存器相等的时候,表示系统时间的时间寄存器ti自增;ti寄存器也可通过setti指令进行设置,通过getti指令进行读取.

Fig.5 Block diagram of RPU(Only incremental part of classic pipelines)图5 RPU原理图:经典五段流水改动部分

Fig.6 Block diagram of Time Unit图6 Time Unit原理图

时间触发操作指令按照TT机制执行.to信号生效后,RPU比较ti寄存器和r1,若ti＜r1,表示未到触发时间,RPU通过Stall＆Flush模块停顿流水线;若ti＝r1寄存器,RPU执行当前时间触发操作指令,并将当前ti寄存器值记录到时间戳寄存器ts,ts寄存器可通过getts进行读取;若ti＞r1寄存器,表示系统发生时序错误异常.对TTI中时间触发操作指令的实现,保证了RPU指令级的时间可预测属性.

RPU采用粗粒度多线程支持TTI的并发管理指令.CMT需要RPU有多套硬件上下文,体现在图5中的PC Group和Regfile Group模块.线程采用TT机制切换体现在图5中的CMT Control模块,该模块根据由标准时钟生成的ti进行硬件线程控制.addtk指令会向TT Table中增加表项,RPU根据TT表控制线程切换.TT表结构如图7所示,它使用图示结构模拟队列,图7中的Time和ID寄存器组为数组,head和tail两个寄存器为头尾指针,通过ad d信号添加表项ad d_time和ad d_id;在表头指定的时刻弹出head_time和head_id,进行线程切换控制.线程也可通过执行tkend表示当前任务执行完成,主动释放RPU控制权.CMT Control模块中的FSM负责线程切换控制,其时序如图8状态机所示.FSM正常情况下运行在S0状态,当TT表弹出表头或者线程执行tkend释放控制时,FSM跳转到S1状态;在S1状态,RPU会清空IF段、ID段和EX段,保存正在执行线程的PC,并执行WB段,这3个任务可并行完成,FSM在下个cpuClk上升沿跳转到S2;在S2状态,RPU执行MM段,执行MM段与执行WB段要串行完成,所以需要单独一个cpuClk;至此,上个线程的上下文保存完毕;在S3状态,RPU执行线程切换,更改PC Group和Regfile Group中的ID寄存器,随后进入S0运行新线程.对TTI中并发管理指令的实现,保证了RPU任务级的时间可预测属性.

Fig.7 Structure of TT table图7 TT表结构

Fig.8 FSM of thread switching图8 线程切换状态机

RPU是一款指令级时间可预测和任务级时间可预测的实时处理器.它支持标准时钟,是RTM的实例;以TTI为软硬件接口,从指令集体系结构层次为上层提供了时间语义;RPU的设计实现验证了RTM和TTI的可行性.同时,RPU的时间触发设计理念契合时间触发通信协议,如TTP和Flex Ray等.将来,在分布式场景下,可以为RPU添加时间触发通信协议接口,从而保证系统级时间可预测性.

4.3 时序结果

RPU的时间可预测性体现在其具有确定性的时序上,即TTI的指令在运行时都具有时序确定性,图9、图10和图11显示了系统时间生成的时序、时间触发操作指令执行的时序和线程切换的时序.

图9是Time Unit模块中对标准时钟管理的时序图.为了清楚表示时序,图中波浪部分隐去若干cpuClk周期.图9中系统设置的时间粒度tg＝100,即系统时间的单位是100μs.可以看出,在标为2的cpuClk,cnt与tg相等,在标为3的cpuClk,ti从原来的2变成了3,与引理1、4.1节中的分析吻合.结合ti,ti_w和ti_data信号在标为5和标为6的cpuClk的变化可知setti指令功能正确.整体来说,标准时钟产生系统时间ti的过程时序精确,抖动总是Tcpu＝40 ns.

Fig.9 Timing of Time Unit图9 Time Unit时序

图10显示的是时间触发操作指令的运行时序,to信号表示当前EX段有一条ttiat或ttoat指令;idex_r1表示该指令的触发时间,to_stall表示是否因tio指令产生了流水线阻塞.从图10可知,在标为2的cpuClk一条tio指令进入流水线,在EX段等待时间变为20时时间触发执行;在标为7的cpuClk,即ti到达20的下一个cpuClk周期开始执行.时间触发操作指令的执行时序精确,抖动也是Tcpu＝40 ns.

Fig.10 Timing of time-triggered operation图10 时间触发操作指令时序

图11则展示了线程切换时序,head_time表示TT表中下一个切换发生时间,curr_stat表示FSM的当前状态,thread_control表示FSM提供给RPU的控制信号,ID表示PC中的ID寄存器.图11和图8所示的线程切换状态机吻合,说明RPU的并发管理同样cpuClk周期精确,时间可预测.

图9、图10和图11体现了RPU的时序确定性,时序确定有利于建立RPU的确定性抽象模型,并据此进行严谨的形式化时间行为分析,满足硬实时安全性设计要求.

Fig.11 Timing of thread switching图11 线程切换时序

4.4 资源消耗

RPU基于CV32E40P实现.实现之前,本文对CV32E40P进行了裁剪,删去了如硬件循环等影响处理器时序的功能.裁剪后CV32E40P的资源消耗如表4所示.本文关注FPGA资源消耗3个重要指标:查找表(lookup table,LUT)、FF(flip-flop)和BRAM(block ram),但是CV32E40P未用到BRAM,因此没有列出BRAM数据.表5、表6测得RPU线程数为2,4,8,16,32时,TT表项大小为4,8,16,32,64时LUT和FF的消耗.

Table 4 Resource Consumption Table of Modified CV32E40P表4 裁剪后CV32E40P的资源消耗表

Table 5 LUT Consumption Table of RPU表5 RPU LUT消耗表

Table 6 FF Consumption Table of RPU表6 RPU FF消耗表

从表5和表6可以看出,RPU的实现会增加LUT和FF资源的使用,FF的额外消耗多于LUT的额外消耗,这是由于RPU会更多地使用寄存器导致的.另外,LUT和FF的资源消耗随着线程数大小的增长(表的每一列)和TT表大小的增长(表的每一行)线性增长.其中,资源消耗随线程数的增加增长迅速,随TT表大小的增加增长缓慢,符合设计时的预期.

5 LET应用示例

本节首先对LET模型和LET模型的3种实现语义进行简单介绍,进而给出根据其中的交错LET实现方案使用TTI对RPU编程的应用实例.

5.1 LET模型介绍

Henzinger和Kirsch等人借鉴ZET和BET模型各自的优点,提出LET模型[7].采用LET模型时,任务总是在其激活区间的开始处读数据和结束处写数据,使其可观察的时序行为独立于任务的物理执行.LET确定了读程序输入到写程序输出之间所需的时间,而不考虑执行程序所需的时间,具有平台可移植性.虽然实际应用时LET模型的资源(缓存、时间)利用率较低,但LET为控制工程师和软件工程师提供了清晰的时序模型接口.2017年以来,随着多核平台下可预测性成为关键问题,工业界认为LET对于解决多核混合安全关键应用和分布式实时系统的通信确定性问题极具吸引力.

LET编程模型将任务的逻辑行为“输入计算-输出”过程相分离,如图12所示,定义了严格的输入输出时刻,要求在指定时刻输入,在输出时刻之前计算出结果,并能够将输出结果保持到指定时刻输出,具有时间行为可预测、可组合和平台无关性等重要特征,利于设计时进行系统行为验证.

Fig.12 LET programming model图12 LET编程模型

LET抽象中输入和输出都是零执行时间的,然而现实中输入和输出操作需要一定的执行时间,因此,在实践中要尽量满足LET模型零执行时间的假设.在考虑系统端到端延迟的情况下,LET模型主要可以分为3种实现语义[36],如图13所示.

Fig.13 Example schedule of three semantics of LET implementation图13 LET模型3种实现语义

图13(a)和图13(b)中P任务的周期为C任务的2倍,图13(c)中P任务和C任务同周期.图13(a)显示的是LET的Giotto语义,它按照输入输出任务块的因果关系确定执行顺序.图13(b)显示的是LET的交错通信语义,在LET通信阶段,每个任务的输入输出操作被合并为一组任务,不同的任务组交错执行.基于任务链的LET语义可以在特定情况下优化不可观测事件的通信,降低通信开销,优化任务链的端到端延迟.图13(c)显示的是LET的Giotto语义和基于任务链的LET语义的对比,其上半部分是按照Giotto语义执行的结果,下半部分是按照基于任务链的LET语义执行的结果.从图13中可以看出,基于任务链的LET语义具有更低的逻辑端到端延迟.

5.2 RPU对LET的支持示例

本节通过示例RPU对逻辑执行时间模型的支持,说明RPU的应用能力,提供时间可预测的实时应用开发平台.

本节使用的示例说明在自动驾驶中,假设有:

1)采集任务,负责通过传感器采集数据,并进行数据预处理,周期为2 ms;

2)分析任务,对预处理之后的数据进行预定算法的分析和处理,得到响应数据,周期为1 ms,WCET为0.25 ms;

3)执行任务,将响应数据分发到执行器进行外部环境的控制,周期为2 ms,WCET为0.5 ms.

3个任务的数据依赖图如图14所示:

Fig.14 Data dependency graph of sample tasks图14 示例任务的数据依赖图

本文按照交错LET的语义对示例任务集进行编程,采用共享内存进行通信.图15显示了该任务集的任务分解和建模时序,图14中的数据依赖体现为图15中的虚线箭头.其中,每个LET任务被分解为I,C,O三个子任务,O和I两个子任务被合并为一个OI子任务组,保证了该任务集的交错LET语义,显示出图15所示时序.

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

图15中OI子任务组在RPU上会执行0.05 ms.图16是使用TTI在拥有4线程的RPU上实现图15所示时序的伪代码.TT表在时间触发地执行线程切换时会弹出表头项,对于图15中以2 ms为周期的运行系统,需要一个额外任务负责向调度表添加每个周期的调度表项.图16的代码中,使用0号线程管理调度表;使用1号线程执行各个任务的OI子任务组;使用2号线程执行各个任务的C子任务;使用3号线程执行软实时任务,即当硬实时任务执行完,RPU处于空闲状态时,会切换到3号线程执行.结合4.2节展现的时序可知,图16所示的代码保证了图15的交错LET语义.