面向Web的WCET模式自动分析系统
2017-02-27姬孟洛舒云星黄辰林
姬孟洛 舒云星 黄辰林 高 翔
1(洛阳理工学院计算机与信息工程学院 河南 洛阳 471023)2(洛阳理工学院对外合作处 河南 洛阳 471023)3(国防科技大学计算机学院 湖南 长沙 410073)
面向Web的WCET模式自动分析系统
姬孟洛1舒云星2黄辰林3高 翔1
1(洛阳理工学院计算机与信息工程学院 河南 洛阳 471023)2(洛阳理工学院对外合作处 河南 洛阳 471023)3(国防科技大学计算机学院 湖南 长沙 410073)
针对传统的WCET(Worst-Case Execution Time)分析方法面临的精度不高和用户使用繁琐问题，提出一种自动分析程序模式的方法并据此设计实现了一个面向Web的WCET分析系统。首先在对源程序进行分析的基础上，利用程序控制流程图，通过数据流框架进行切片，获得依赖于输入变量的无循环控制流程图ICFG。然后，通过对ICFG每条路径求解，获得程序的模式及其输入表达式，并计算其对应的WCET。最后，将上述分析方法设计实现为针对C语言的动态链接库(DLL)，并利用该DLL实现一个面向Web的WCET自动分析系统——WCET Mode Analyzer。WCET Mode Analyzer对基准程序的分析结果，验证了该方案的有效性和应用的简便性。
实时系统 WCET 程序模式 程序分析
0 引 言
实时系统，包括嵌入式实时系统，在进行任务调度时，需要事先知道每个任务的执行时间。这个时间，指的是最坏情况的执行时间WCET[1]。研究获取WCET值的方法是实时系统的重要研究领域，它不仅应用于可调度性检测，还应用于非实时系统性能分析和嵌入式系统的耗电量分析[2]。
获取WCET值的主要方法是静态分析。WCET静态分析根据程序的执行流和运行程序的处理器特性这两方面的信息来估算程序的WCET。而配置这些信息复杂、繁琐且易于出错。同时，静态分析要求安全，也就是给出的估值不能低于任务可能执行时间的最大值。因此，传统的WCET分析方法通常具有易于高估任务WCET值和不易使用的缺点[2-3]。
实时系统，尤其是嵌入式实时系统，通常都有模式。系统的一个模式定义了该系统以及其中相关任务的一种特殊行为。举例来说，一个系统通常有启动模式和正常模式，甚至有正常模式和紧急模式。
利用程序模式能够更精确地计算任务WCET。这体现在三个方面。其一，根据程序不同的模式，分别计算各模式的WCET，取其中最大的WCET，比不加区分计算出的WCET要精确[4-5]。其二，不同的模式，其要求的WCET往往不同。其三，类似于WCET参数化分析，每一个模式都有一个由输入参数值范围构成的表达式，因此，在任务执行时才确定模式，从而有更精确的WCET值[6-7]。
针对WCET分析的缺点，本文实现一种面向Web的WCET模式自动分析系统——WCET Mode Analyzer。该系统允许用户通过Web方式上传被分析的源程序，根据源程序，能够自动确定其模式以及模式对应的输入参数值表达式，然后通过选择专业人员配置的程序运行处理器的特征，从而能够计算每一种模式对应的WCET。
1 背景知识
实时系统程序的WCET静态分析(以下简称WCET分析)通常包括三部分：程序执行流分析、处理器特征分析以及基于二者信息的WCET计算。
程序执行流分析包括分析循环的最大迭代范围、递归调用的深度范围和不可行路径等程序流约束信息。不可行路径是指对任何输入数据都不可能执行的程序路径。
处理器特征分析就是分析程序目标代码的实际执行时间，即建立执行时间模型，此分析也称为低层分析。对于无高速缓存、无流水线的传统CISC(Complex Instruction Set Computer)指令，其每条指令的执行时间是固定的。因此，任意两条指令的执行时间，就是其所包含的每条指令的执行时间累加。此方法称为Time schema方法。
流水线的WCET的分析方法通常是利用保留表[8]。此时，两条指令的执行时间就是两条指令对应的两个保留表连接之后，从第一条指令第一个阶(stage)到最后一条指令的最后一个阶之间的指令周期(cycle)数。
高速缓存的WCET典型分析方法是把每条指令的访问进行分类，分为4类：总是丢失(always miss)、总是命中(always hit)、第一次访问丢失后续命中(first miss)和第一次访问命中后续丢失(first hit)，然后根据不同访问类型计算缓存引起WCET[2-3,8]。
WCET计算就是在已知程序执行流和执行时间模型的情况下，为程序计算WCET估值[2-3]。这里简单介绍基于树的方法和基于路径的方法。
基于树的方法根据复合、条件和循环语句所形成语法树，通过遍历程序的语法分析树，自底向上逐步计算整个程序的WCET估值。此方法也称为Time schema方法。常用于CISC指令集的计算。
基于路径的方法通过计算程序中不同路径的WCET，从中选择最大的WCET。对于循环lp，基于路径的方法可简单表示为：
WCETlp=WCETpath×n
(1)
其中，WCETpath是循环lp中执行时间最长的路径path的WCET值，n为循环lp的迭代次数。
2 WCET模式自动分析方法
基于源程序代码，本分析方法包括七个步骤，其中前六个步骤用于产生模式，最后步骤计算模式对应的WCET。
2.1 产生任务的无循环控制流图NLCFG
程序控制流图CFG(ControlFlowGraph)[9]，是对程序的图形化表示，由节点和有向边组成，它既表示了程序的控制结构信息，也表示了程序语句执行的流向。一个结构化程序由三种基本语句构成：复合语句、条件语句和循环语句，与之对应，程序CFG也由三种基本结构组成：顺序、分支、循环。
程序CFG节点分为赋值节点、分支点和汇聚点。赋值节点对应于程序的赋值语句，分支节点对应于条件或循环语句的条件判断，此条件也称为分支谓词。
程序CFG的边表示程序的执行流向，分支节点的边称作分支，对应于程序中一段要顺序执行的语句序列。
无循环控制流图NLCFG(NoLoopControlFlowGraph)是一种特殊的控制流图，其与CFG的区别在于其循环语句产生的CFG节点只包括循环体节点而不包括分支谓词节点及相应的回边。所以产生程序NLCFG是因为经过循环迭代的依赖输入变量的值变得无法确定。
按照程序的三种基本语句，分析源程序，能够产生程序的NLCFG。与程序CFG表示类似，程序NLCFG的节点可用数字标识，边可以用节点的二元组表示，比如边(m,n)表示从节点m到节点n的有向边。
获得程序NLCFG的同时，也获得NLCFG节点与源程序语句的对应关系，同时，循环体节点也得到标识。
2.2 利用NLCFG确定依赖输入变量及其对应节点
依赖输入变量可以递归定义为：由输入变量定义的变量是依赖输入变量，由输入变量和依赖输入变量定义的变量也是依赖输入变量。
针对NLCFG，从入口节点开始，利用通用单调数据流框[10]，依照深度优先策略，可以确定每个变量是否是依赖输入变量。
为了确定依赖输入变量及其对应的NLCFG节点，为每个节点设立两个状态：节点执行前状态与执行后状态。节点前状态由所有流向该节点的节点后状态确定，而节点后的状态则是该节点执行后改变的状态。对于所有流向一个节点的节点，如果这些节点的节点后状态中，该变量是依赖输入变量，那么，在此节点的节点前状态中，该变量的状态定义为依赖输入变量。
所谓深度优先策略是指，在处理一个节点后，对该节点的后续节点，按照深度优先策略进行排队处理。首先对后续节点排队。排队之后，对队列中的第一个节点同样处理，只有在第一个节点及其后续节点处理完毕或者无法处理之后，才开始处理该节点队列中的第二个节点。一个节点无法处理是指，如果该节点有一个前任节点的执行后状态是不确定的。一个节点m的前任节点是一个节点集合，满足：它们都有一条边指向节点m。同理，节点m的后续节点是一个节点集合，满足：节点m有一条边指向这些节点。
对于无法处理的节点，将该节点重新排在队列末尾。基于深度优先策略确定依赖输入变量算法可参考图1所示。
图1可以分为两部分，前半部分围绕队列Q1，根据节点对依赖输入变量的引用关系，确定每个变量的节点后状态是否为依赖输入变量，其中定义引用变量为依赖输入变量的节点为依赖输入节点。后半部分围绕队列Q2，确定该节点的后续节点的节点前状态。
图1 基于深度优先策略的依赖输入变量确定算法
对于结构化程序，由于NLCFG没有循环结构，所以NLCFG为单向有向图，因此，NLCFG中的节点是有序的。也因此，所述算法能够保证快速确定每个节点的状态。
2.3 确定依赖循环变量、非输入分支变量及其节点
一个变量如果在循环体中定义，则该变量为依赖循环变量。一个变量如果在定义中引用了依赖循环变量，则该变量同样为依赖循环变量。同样，一个变量如果在非依赖输入分支谓词的分支中定义，则该变量为依赖非输入分支变量。一个变量如果在定义中引用了依赖非输入分支变量，则该变量同样为依赖非输入分支变量。以上两类变量统称为非依赖输入变量NOINPUT。
针对一个循环体节点或非依赖输入分支节点，首先确定一个变量在节点后状态中为NOINPUT，然后，利用通用单调数据流框，可以确定所有后续的NOINPUT变量。
2.4 删除非依赖输入节点产生ICFG
针对NLCFG，删除图中非依赖输入节点。删除的方法仍然按照节点的基本结构进行，所不同的是，一个分支节点或者汇合节点可以是空节点。所谓空节点就是不执行任何操作的节点。空节点对应语句为空语句。
最终形成的无循环控制流图NLCFG为输入变量相关的NLCFG，标记为ICFG(InputdependentControlFlowGraph)。
2.5 产生ICFG的所有路径
对于ICFG，可产生其所有路径。由于ICFG是单向图，可按照深度优先策略产生所有路径。
2.6 针对每条路径产生其输入条件
针对ICFG的每一条路径，在这个路径上只有两类节点，一类是赋值节点，另一类是分支节点。对于分支节点，如果其分支谓词表达式是输入变量的线性表示，则可以构造出该分支谓词针对输入变量的线性表达式。
假定输入表示为X=
dj=(F(I0+(0,…,△ij,…,0))-F(I0))/△ij
(2)
j=1,2,…,m
其中I0=(i1,…,ij,…,im)为任一输入，△ij为任一不为0的增量。
对于ICFG上的一条路径，该路径上每个分支取向已经确定，同时，每个分支谓词对输入变量的线性表达式已知，因此，可以根据路径上的分支谓词构造输入变量的约束组。如果定义目标函数为所有输入变量累加的最小值，则构成一个典型的线性规划求解问题。
利用线性规划解析器，即可解得输入变量的值或者是范围，此即为该ICFG路径的输入条件，此条件即为该模式对应的输入条件。如果线性规划问题无解，则说明该路径为不可行路径。
2.7 模式的WCET分析
假定md是任务M的一个模式，如果M中路径P属于md中路径，则称路径P由模式md支配。如果路径P由模式md支配，则路径P上的节点/基本块也由模式md支配。即：一个节点/基本块由模式md支配，如果M中存在一条路径P，满足：md支配路径P且该节点/基本块在P上。
一个语句真值(true)/ 假值(false)控制依赖于b，如果当b为true/false时才执行该语句[9]。对于模式md的每个谓词b，有两个语句集合，它们分别真值和假值控制依赖于b。
根据模式md支配的路径P，能够确定md中每个谓词b的取值(true/false)。如果b的取值为true，则真值控制依赖于b的节点由模式md支配，而假值控制依赖于b的节点模式md不支配。反之亦成立。
对于指定模式下的WCET分析，不应当考虑模式不支配的节点，而相应的WCET分析方法保持不变。
对于指定模式md下的Timeschema计算，只需考虑md支配的分支或者基本块即可。流水线的计算按照路径的方法进行。对于指定模式md下的WCET高速缓存分析，只需考虑miss情况。一条指令被划分miss，只有当存在一个md支配的控制流中该位置的其它程序线也可能被缓存，也就是它和另一个md支配的程序线的缓存发生冲突。否则，它是hit。
对于指定模式md下的基于路径的计算，式(1)中WCETpath对应循环lp的最长路径Path有限制，Path应当是由md支配的路径。如果循环lp中最长路径Path不是由md支配的，则检查循环lp中次长路径。显然循环lp中至少有一条模式md支配的路径，因此最终能够得到由md支配的最长路径Path。
本文采用基于路径的计算方法。
3 WCET模式自动分析的实现
在基于抽象解释的WCET自动分析工具NPCA-WCET[11]的基础上，我们实现了面向C语言的WCET程序模式自动分析。该实现称为处理对象库 (DLL)，它是一个具有公共语言运行时CLR(CommonLanguageRuntime)特征的动态连接库，它还能够为C语言之外的诸如C#语言所调用。
3.1 处理过程
处理对象库 (DLL)的主要处理逻辑包括三部分：词法和语法分析(parse)、模式分析，以及指定模式的WCET分析，如图2所示。
图2 模式分析的处理过程
在图2中，首先对C源程序进行词法和语法分析，生成程序结构信息的对象表示，其中包括控制流图、输入变量表和变量表。对程序结构信息进行程序流信息分析即用于获取WCET分析的流信息。这些信息包括：函数调用关系、递归调用关系、循环的界限以及不可行路径等。程序流分析方法是基于抽象解释[12]支持的变量值范围传播[10]。
ICFG分析即包括前述第2节的前五个步骤，其结果产生输入变量相关的无循环控制流图ICFG以及其对应的所有路径。针对其每一条路径，构造对应的线性约束系统，并进行求解。求解器采用：如果有解，则该路径对应一个模式，线性约束系统就是它的输入条件；如果无解，这对应一个不可行路径。
缓存分析利用高速缓存的配置信息以及程序流信息和映射文件提供的指令序列，对每条指令和数据缓存操作进行分类，已备时间分析使用。
时间分析根据程序流信息、缓存分类信息和程序流信息对于的指令序列，根据指令系统信息，计算每个模式以及整个函数的WCET。
3.2 实现类
WCET模式分析的具体实现可以通过面向对象的方法进行设计实现，其实现类及对象关系如图3所示。
图3 WCET模式分析实现类及对象关系
WCET模式分析实现主要体现在COneFile类上。COneFile关联源文件类CSrcFile和映射文件类CMapFile。通过COneFile类函数Analyse对源文件进行词法分析，生成相应的Token对象列表。在Token对象列表的基础上，可以通过其函数GetFunItem进行语法分析从而获取源文件包含的函数对象CFunItem，然后，通过类CFunItem的函数GetModeItem获取该函数包含的模式对象CModeItem和节点CNode对象。
可以通过对CMapFile分析，将源文件对应的指令序列映射到相应的函数及其节点对象CNode上。
以上类以及相关类，生成为具有CLR特性的动态链接库。
从对象的组织关系上讲，一个COneFilet对象包含了一个源文件CSrcFile对象，一个可能的映射文件CMapFile对象和函数对象CFunItem队列。映射文件是编译器产生的源文件与机器指令的映射列表文件，一般编译器都具有生成该文件的功能，WCET模式分析器利用此文件建立源文件与其执行指令的对应关系。
函数对象CFunItem队列包含了该COneFilet对象的所有函数。每个CFunItem包含了CFG节点CNode队列和分析出来的模式，也使用CModeItem队列表示。节点CNode包括分支节点CBranchNode和赋值节点CAssignNode，每个节点对应两个变量表VariableTable，并包含了一个表达式，一个表达式用变量CVariable和操作符COperator队列表示。
4 面向Web的WCET分析系统
利用处理对象库 (DLL)提供的WCET模式分析功能，可以实现具有模式分析功能的系统。本节实现一个面向互联网的WCET模式分析器——WCETModeAnalyzer。
之所以将WCETModeAnalyzer设计成面向互联网不仅是为了便于访问，更是为了方便角色划分，将繁琐且易于出错的配置低层分析部分划归作为系统管理员的专业人员去完成，而将对应用程序的WCET分析计算使用功能提供给应用用户。
4.1 主要功能
从应用的角度看，WCET模式分析器功能比较简单。该系统分为两个角色：系统管理员和应用用户。
系统管理员负责配置CPU和系统参数。配置CPU包括配置指令系统、主频和配置高速缓存。对于CISC指令系统，每条指令对应一个处理时间(cycles，节拍数)。对于RISC指令系统，定义指令的每个阶之后，对于每条指令，指定该指令每个阶(stage)占用的节拍数。可以对每一条指令进行定义，也可以通过EXCEL表按照指定格式整体录入。
对于高速缓存，主要是确定其映射方式和缓存大小。映射方式是指高速缓存与内存的映射关系，有直接映射、全相联映射和组相联映射三种方式。
4.2 设计实现
WCET模式分析器主要由三部分组成：网页响应、对象管理器和处理对象库(DLL)。处理对象库如前所述。
(1) 网页设计
WCET模式分析器的网页设计分系统管理员和应用用户。系统管理员页面比较简单，仅仅是用来配置CPU。
应用用户的显示页面除主题和页脚，主要由左中右三部分构成，左边为导航树，中间部分为主显示区，右边为辅助显示区。导航树第一部分为项目配置，后面部分为各个项目不同视角的显示。
主显示区根据导航树的选择项显示相应的内容，而辅助显示区则可能显示对应的辅助内容。比如，当导航树选择一个源文件的时候，主显示区显示该文件包含函数的模式及对应的WCET，而辅助显示区则显示对应的源文件内容，如图4所示。
图4 面向Web的WCET模式分析系统构成
网页设计简单但很琐细，网页设计的关键在于数据存储和获取，其由数据管理器来完成。
(2) 对象管理器设计
对象管理器负责WCET模式分析器中对象的组织，其顶层组织如图5所示。
图5 面向Web的WCET模式分析系统构成
COneFile的组织如前所述。CCPU对象包括指令集和高速缓存等，主要用于低层分析。
5 系统分析实例
我们选用基准集SNU-RTBenchmarkSuite进行测试，以Alpha21064为处理器模型，该处理器指令缓存1MB，用户可以直接选用。SNU-RT基准集是实时系统领域用于WCET分析的基准程序集[13]。
通过分析，SNU-RT基准集有17个程序，其中9个程序包含的程序具有模式。整体上，17个程序中有55个函数，其中23个具有模式。图6为adpcm-test.c程序对应的显示页面部分。可以看出，对于有模式的函数，WCET模式分析系统将给出其模式和模式对应的WCET值，对于没有模式(或者无法判断其模式)的函数，WCET模式分析系统将给出其函数的WCET值。
图6 面向Web的WCET模式分析系统显示页面
6 结 语
本文提出了一个自动分析程序WCET模式的新方法，并据此设计实现一种面向Web的WCET模式分析系统。该系统能够分析程序模式，计算任务以及模式的WCET，从而达到更精确地计算实时任务WCET的目的。同时，利用Web系统的特点，将繁琐的配置工作交由专业的系统管理员，应用用户可以直接使用配置好的处理器，从而使配置工作简便。通过对基准程序进行分析实验，验证了该方案的有效性。
本系统目前仅在RISC类处理器Alpha21064上实现了C语言程序WCET分析，未来还需要扩展到多种类型实时用处理器和语言上，比如ARM类处理器和C++语言。
[1]DavisRI,BurnsA.Asurveyofhardreal-timeschedulingformultiprocessorsystems[J].ACMComputingSurveys(CSUR),2011,43(4):1-41.
[2]WilhelmR,EngblomJ,ErmedahlA,etal.Theworst-caseexecution-timeproblem-overviewofmethodsandsurveyoftools[J].ACMTransactionsonEmbeddedComputingSystems(TECS),2008,7(3):196-206.
[3]PuschnerP,BurnsA.Guesteditorial:areviewofworst-caseexecution-timeanalysis[J].Real-TimeSystems,2000,18(2-3):115-128.
[4]WilhelmR,LucasP,ParshinO,etal.ImprovingtheprecisionofWCETanalysisbyinputconstraintsandmodel-derivedflowconstraints[M]//ChakrabortyS,EberspächerJ.AdvancesinReal-TimeSystems.Berlin:Springer-Verlag,2012:123-143.
[5]JiML,WangJ,LiS,etal.Automatedworst-caseexecutiontimeanalysisbasedonprogrammodes[J].TheComputerJournal,2009,52(5):530-544.
[6]BallabrigaC,ForgetJ,LipariG.Context-sensitiveparametricWCETanalysis[C]//15thInternationalWorkshoponWorst-CaseExecutionTimeAnalysis,Lund,Sweden,2015:54-64.
[7]ZwirchmayrJ,SotinP,BonenfantA,etal.IdentifyingrelevantparameterstoimproveWCETanalysis[C]//14thInternationalWorkshoponWorst-CaseExecutionTimeAnalysis,Madrid,Spain,2014:93-102.
[8]HealyCA,ArnoldRD,MuellerF,etal.Boundingpipelineandinstructioncacheperformance[J].IEEETransactionsonComputers,1999,48(1):53-70.
[9]TipF.Asurveyofprogramslicingtechniques[J].JournalofProgrammingLanguages,1995,3(3):121-189.
[10] 姬孟洛,王怀民,李梦君,等.一种基于抽象解释和通用单调数据流框架的值范围分析方法[J].计算机研究与发展,2006,43(11):2020-2026.
[11] 姬孟洛,李军,王馨,等.一种基于抽象解释的WCET自动分析工具[J].计算机工程,2006,32(14):54-56.
[12]CousotP,CousotR.Abstractinterpretation:aunifiedlatticemodelforstaticanalysisofprogramsbyconstructionorapproximationoffixpoints[C]//Proceedingsofthe4thACMSymposiumonPrinciplesofProgrammingLanguages,LosAngeles,CA,USA,1977:238-252.
[13]SATABS.SNUReal-TimeBenchmarks[OL].http://www.cprover.org/satabs/examples/SNU_Real_Time_Benchmarks/.
AN AUTOMATIC WCET ANALYSIS SYSTEM FOR WEB
Ji Mengluo1Shu Yunxing2Huang Chenlin3Gao Xiang1
1(SchoolofComputerandInformationEngineering,LuoyangInstituteofScienceandTechnology,Luoyang471023,Henan,China)2(DepartmentofForeignCooperation,LuoyangInstituteofScienceandTechnology,Luoyang471023,Henan,China)3(SchoolofComputerScience,NationalUniversityofDefenseTechnology,Changsha410073,Hunan,China)
In light of the problems of deficient precision and troublesome usage the traditional WCET analysis systems usual suffer, a new automatic analysis method based on program modes is proposed and a WCET analysis system on the idea of the method for Web is designed. Firstly, a method is presented based on the analysis of source code which produces an acyclic input parameter dependent control flow graph called ICFG by using program control flow graph and a specific program slicing under data flow framework. Secondly, by constructing a solution system for each path in ICFG, a mode and its input parameter expression maybe conducted, and the WCET value of a mode can be computed. Finally,a Dynamic link library (DLL) is implemented based on the method above for C language in order to be used by different systems,and an automated analysis system in the Web by using the DLL is realized, which is called WCET Mode Analyzer. The result for a Benchmark implemented by the analysis system shows the effectiveness of the solution and the characteristics of using conveniently.
Real-time systems WCET Program mode Program analysis
2015-12-25。河南省科技计划项目(152300410115)。姬孟洛，高级工程师，主研领域：实时系统，中间件技术，信息系统分析与设计。舒云星，教授。黄辰林，副教授。高翔，讲师。
TP311
A
10.3969/j.issn.1000-386x.2017.02.042
