（电路与系统专业论文）嵌入式实时系统的最坏情况执行时间（wcet）分析.pdf

东南大学硕士学位论文 摘要 嵌入式实时系统的正确性不仅取决于系统的逻辑计算结果，还和产生结果所花费的时 间有关，系统必须保证在一个可预测的时间段内对外部事件做出反应。程序晟坏情况执行 时间( w o r s tc a s ee x e c u t i o nt i m e ) 是指程序在运行过程中所花费的最大执行时问。它在操 作系统实时调度、任务优先级仲裁、资源冲突仲裁、任务间通信以及软硬件划分等研究领 域中有着很重要的作用。本文主要针对特定的硬件平台( a r m 7 t d m i 微处理器) ，对g a r f i e l d 系统m p 3 解码程序的最坏情况执行时间( w c e t ) 进行评估，对m p 3 解码程序的优化给 出客观的评判，同时也为m p 3 子模块的软硬件划分提供重要的依据。 程序最坏情况执行时间( w c e t ) 的计算主要涉及到两个方面：高层分析( h i g h l e v e l a n a l y s i s ) 和底层建模( l o w l e v e lm o d e l i n g ) 。高层分析主要是在高级语言环境中分析程序 结构，找出最坏情况下的指令序列，而底层建模是在汇编环境中建立硬件模型，得到已知 指令序列的最坏情况执行时间。w c e t 计算的复杂性限制了被分析程序的人小和计算的 准确性。 本文详细介绍了一种有效计算最坏情况执行时间( w c e t ) 的方法，并开发了路径分 析工具c r y i n g c a t 。该路径分析工具从底层模型中得到指令执行时间，将其反标到由高 层分析提取出来的控制流图( c o n t r o lf l o wg r a p h ) 上，然后利用含有执行时间信息的控制 流幽米建立整数线性规划模型，最后通过求解整数线性规划模型来得到程序的最坏情况执 行时间( w c e t ) 。 本文使用路径分析t 具c r y i n g c a t 对g a r f i e l d 系统m p 3 解码程序的最坏情况执行时 间进行计算和分析，以实例验证了路径分析上具c r y i n g c a t 的有效性和准确性。实验结 果显示，在一定数量测试向量的前提下，对于g a r f i e l d 系统m p 3 解码程序中已优化的函数， 计算所得到的w c e t 和模拟器仿真所得到的值相差只有1 ，而对于结构复杂的函数或者 是未经优化的函数，计算所得w c e t 值和不同测试向量集下的a r m u l a t o r 模拟器仿真值相 差5 至3 0 。这说明模拟器仿真要么不能找到最长执行时间的路径，要么需要数目庞大 的测试向量集。由上面的分析可见，路径分析工具c r y i n g c a t 可以有效简便地计算出 m p 3 解码程序( c 语言程序) 的最坏情况执行时间( w c e t ) 。 关键词 嵌入式实时系统程序最坏情况执行时间高层分析底层建模整数线性规划 东南大学硕士学位论文 a b s t r a c t w h e t h e rr e a l 。t i m es y s t e mi sc o r r e c to rn o ti sn o to n l yb u i l to nt h er e s u l to l l o g i c c o m p u t a t i o n ，b u ta l s or e l a t e dt ot h et i m ef o rp r o d u c i n go fi t r e a l t i m es y s t e ms h o u l db e r e s p o n s et oi n t e r n a le v e n ti ns a f e t ya n dp r e d i c t a b l et i m ep e d o d t h ew o r s t - c a s ee x e c u t i o nt i m e r e f e rt ot h em a x i m u me x e c u t i o nt i m eo fr e a l - t i m ep r o g r a r mi ti s i m p o r t a n ti nt h ef o l l o w i n g f i e l d s ：s y s t e ms c h e m a ；t a s kp r i o ra r b i t r a t i o n ；r e s o u r c ec o n f l i c ta r b i t r a t i o n ；c o m m u n i c a t i o n b e t w e e nt a s k sa n dp a r t i t i o nb e t w e e ns o f t w a r ea n dh a r d w a r e c o n c e r n i n gt oag i v e np r o c e s s o r a r m 7 t d m i ，t h i sp a p e ri sg o i n gt oe v a l u a t et h ew o r s t c a s ee x e c u t i o nt i m eo fm p 3 s u b s y s t e m ，o f f e rai m p e r s o n a lo p i n i o na b o u tt h eo p t i m i z a t i o no fm p 3p r o g r a m s ，m e a n w h i l e ， g i v ea l li m p o r t a n tb a s ef o rt h es o f t w a r ea n dh a r d w a r ep a r t i t i o ni nm p 3m o d u l e t h e r ea r et w oi m p o r t a n ti s s u e si nc a l c u l a t i n gw c e r ph i g h l e v e la n a l y s i sa n dl o w - l e v e l m o d e l i n g ，t h a ti s ，p r o g r a mp a t ha n a l y s i sa n dm i c r o a r c h i t e c t u r em o d e l i n g u n d e rt h ea d v a n c e d p r o g r a ml a n g u a g e ，h i g h - l e v e la n a l y s i s m o s tp u r c h a s ei n a n a l y z i n gp r o g r a ms t r u c t u r e ， d e t e r m i n i n gw h a ts e q u e n c eo fi n s t m c t i o n sw i l lb ee x e c u t e di nt h ew o r s tc a s e ，a n dc o n s t r u c t i n g c o r r e s p o n d i n gc o n t r o lf l o wg r a p h l o w - l e v e lm o d e l i n gw i l lb u i l du ph a r d w a r em o d e lu n d e rt h e a s s e m b l el a n g u a g e ，t h e no b t a i nt h ew c e to fak n o w ns e q u e n c eo fi n s t r u c t i o n s t h e c o m p l e x i t yo fc a l c u l a t i n gw c e t l i m i t st h ea c c u r a c yo ft h ee s t i m a t e db o u n da n dt h es i z eo ft h e p r o g r a mt h a tc a l lb ea n a l y z e d i nt h i sp a p e r , w ep r e s e n ta ne f f e c t i v em e t h o dt od e t e r m i n eat i g h tb o u n do nap r o g r a m s w o r s tc a s ee x e c u t i o nt i m e t h em e t h o di n c l u d e sad i r e c t - m a p p e di n s t r u c t i o nc a c h ea n a l y s i sa n d p i p e l i n eu n i t sa n a l y s i s a n du s ea ni n t e g e rl i n e a rp r o g r a m m i n gf o r m u l a t i o nt os o l v ew c e z 1 1 1 i s s o l u t i o ni si m p l e m e n t e di nt h et o o lc r y i n g c a tw h i c hi sd e v e l o p e db yl e xa n db i s o na n d c u r r e n t l yt a r g e t st h ea r m t i d m ip r o c e s s o r c o n s i d e r i n gp i p e l i n e di n s t r u c t i o ne x e c u t i o nu n i t s a n dc a c h e dm e m o r ys y s t e m s t h et o o lc r y i n g c a tc o n s t r u c t sp i p e l i n em o d e la n dc a c h e m o d e l u s i n gt h e s em o d e l ，w ec a no b t a i nt h ep r e c i s ei n s t r u c t i o ne x e c u t i o nt i m e f i n a l l y , s i n c e t h el i n e a rc o n s t r a i n t sa r em o s t l yd e r i v e df r o mt h en e t w o r kf l o wg m p h s ，t h ei l pp m b l e m sa r e t y p i c a l l ys o l v e de f f i c i e n t l yb yi l ps o l v e r a sa ne x p e r i m e n t w ec a l c u l a t e dm p 3s u b s y s t e m w c e tu s i n gt h i st 0 0 1 k e y w o r d s r e a l t i m es y s t e mw o r s t - c a s ee x e c u t i o nt i m e h i g h - - l e v e la n a l y s i s l o w l e v e lm o d e l i n gi n t e g e rl i n e a rp r o g r a m m i n g 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均己在论文中作了明确的说明并表示了谢意。 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学 位论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。 本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外， 允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文 的公布( 包括刊登) 授权东南入学研究生院办理。 研究生签名：丑；! ：导师签名： 网 哑型 日期：y 筑j 第一章绪论 1 1 课题选题背景及意义 第一章绪论 嵌入式系统是嵌入到对象体系中的计算机应用系统，包含一个或多个控制用微处理器 以及针对特定应用环境而开发的高层软件。和通用计算机最大的不同是，嵌入式系统把软 件作为和其系统紧密相关的一部分，一般情况下最终用户是不会改变的。典型的嵌入式系 统包括打印机、移动电话、汽车引擎控制单元等。以前，系统复杂度不是很高，一般都可 由单纯的电路来搭建。但近些年来，系统复杂度要求越来越高，同时系统成本要求越来越 低、系统开发周期要求越来越短，这使得电路的搭建变得越来越困难。和硬件电路相比， 软件可以执行复杂的算法，而且软件的可编程性极大地增加了嵌入式系统的应用。在相同 硬件结构下加载不同版本的软件形成系列产品，可以满足不同的市场需求；在相同硬件结 构下开发不同的软件，可以快速地增强系统功能，增强同类产品的竞争力。同时，硬件电 路的复用，大大缩短了系统开发周期，降低了开发成本。 随着微处理器性能的增强和系统复杂度的提高嵌入式系统开发前景变得越来越广阔。 未来，构成计算基本单元的逻辑门必然会被在嵌入式微处理器上执行的指令所取代，因此 我们应将分析优化的目标由逻辑i 、j 阵列扩展到嵌入式系统性能方面。嵌入式系统的性能指 标有很多项，其中重要的一项就是嵌入式系统的实时性能。嵌入式系统可以被看作是一个 激励一响应系统，都有一个从激励输入到响应输出的时间，即激励一响应周期，它表现为 系统的响应能力。对外部事件响应时间很短的嵌入式系统通常被称为“实时嵌入式系统”。 对于实时嵌入式系统而言，系统韵正确性不仅取决于计算的逻辑结果，也取决于产生结果 所花费的时间。一般来说，这意味着实时嵌入式系统必须保证在一个可预测的时间段内对 外部事件做出反应。如果没有达到上述要求，那么系统就会做出错误的操作。实时嵌入式 系统通常又可以分为两大类：软实时嵌入式系统和硬实时嵌入式系统。两者之间最大的区 别就是软实时嵌入式系统可以有限地允许由于系统执行时间超出规定的最人响应时间而产 生的错误，而硬实时系统则不能允许此类错误。 实时嵌入式系统包括硬件和软件两个方面，由硬件平台、嵌入式实时操作系统及其他 系统软件模块、实时应用程序三个部分组成，如图l 所示。 h 操作系统内核网络黄央存储管理模块 岁 图1 嵌入式实时系统的结构 k 口 ) 操作系统 ) 硬件环境 实时性是一个相对概念，表明系统在可预见的时间内响应和处理外部事件的能力。从 东南大学硕十学位论文 嵌入式系统软件的角度上来说，软件要在一定时问范围内对外部事件做出可靠的响应，设 计者必须保证软仲的最坏情况执行时间( w c e t ) 小丁所规定的最大响应时间。 在某个矧定的硬件平台上，随着系统初始状态和输入数据的不同，同一用户任务的执 行时间也会有很人的差别。在系统设计中，软件的最坏情况执行时问( w c e t ) 是指用户 任务在其生命周期中每个作业执行时间的最大可能值，它可能影响到软件及整个系统的运 行，实时操作系统调度、任务优先级仲裁、资源冲突仲裁及任务间通信等方面的研究均假 设程序最坏情况执行时间( w c e t ) 是一个已知值。而且程序的最坏情况执行时间( w c e t ) 也是软件和硬什资源合理划分的一个重要依据，冈为软硬件划分需要考虑性能要求，在满 足性能的前提下尽量用软件来实现。和硬件实现相比，软件实现灵活性好且易验证。 近些年来，国内外的很多专家学者对嵌入式系统程序最坏情况执行时间( w c e t ) 都有 一定的研究，并将其作为实时系统理论架构的一部分。程序最坏情况执行时间( w c e t ) 的 计算通常是采用静态分析的方法k l i g e r m a n 和s t o l y e n k o 专门定义了一种实时编程语言 r e a l t i m ee u l c i d ，它能对任何程序的虽坏情况执行时间进行分析。为了使最坏情况执行 时间的分析评估能接近真实值，r e a l - t i m ee u l c i d 语言更多地关注上下文关系的表达。但作 为一种新的实时编程语言，需要为它开发一套全新的开发工具，需要对程序员进行专门的培 训，而且它还存在一个致命的缺陷，那就是缺少带有目标代码优化功能的编译器，这使得由 r e a l t i m e e u l c i d 语言的编译器编译山来的代码和使用其他编译器编译出来的代码有很大的 差别，从而影响到w c e t 分析评估的准确性。目前关丁：w c e t 分析的研究集中在如何将其集 成到编译器内，使得程序在编译时就能自动给出w c e t 的计算结果。p a r k 、p u s c h n e r 等1 2 1 【4 l 【 1 1 6 1 【1 8 1 利用i n f o r m a t i o n d e s c r i p t i o n l a n g u a g e ( i d l ) 来分析程序的执行路径，形成高级语 言注释文件；a m e r a s i n g h ee ta l 、s t e v e nl i 等1 2 n 开发软件工具进行汇编语言和可执行代码 的w c e t 分析研究：v r c h o t i c k y 等1 2 0 1 1 2 2 1 i t 2 4 1 着力丁编译器原型的开发，将含有路径信息高级 语言注释文件翻译成可进行w c e t 分析的代码。以上这些方法都是将w c e t 的分析计算集成 在编译器中，但在保证评估准确性的同时会使编译器变得更加复杂，而且软件开发人员不得 不使用特殊的编译器。因此尽管在这些领域有很多的研究成果，但市场上仍没有在编译期间 就支持w c e t 分析功能的成熟商用编译器，这使得用高级语言编程的程序员无法对自己写的 程序进行w c e t 分析。 1 2 所作工作 我们已开发出基于a r m 7 t d m i 处理器内核和0 2 5 u r n 标准c m o s 丁艺的g a r f i e l d 系 统级芯片，它研制开发的目标就是能够以较低的成本在短时间内生产山一种使用嵌入式系 统的手持式设备，具有与其他设备进行通信的能力，并且能够流畅地实时播放m p 3 音乐。 m p 3 实时播放功能对系统的实时性要求比较高。为此还在g a r f i e l d 系统级芯片中专门添加 了一小块专用集成电路，专门负责处理m p 3 解码过程中最复杂的部分运算过程。 本课题对g a r f i e l d 系统n p 3 解码程序进行静态分析，获得m p 3 解码程序最坏情况执行 时间( w c e t ) 的评估值，建立和硬件结构相荚的物理模型来使评估值更接近实际的最坏 情况执行时间，并由此给软件的优化和系统软硬件划分提供现实依据。 理论上，仿真只有遍历了所有可能的系统初始状态和输入数据的组合后才能得到实 际的软件最坏情况执行时间，但由于仿真数目极其巨人，实际的程序最坏情况执行时间根 本无法得剑。本文提出了一种新的计算程序最坏情况执行时间( w c e t ) 的方法，开发了 路径分析t 具c r y i n g c a t ，利用它来建立整数线性规划模型( i n t e g e rl i n e a rp r o g r a m m i n g m o d e l i n g ) ，然后通过整数线性规划模型解析器( i n t e g e rl i n e a rp r o g r a m m i n gs o l v e r ) 来计 算得到m p 3 解码程序的最坏情况执行时间。 第一章绪论 图2w c e t 分析框图 本课题的设计流程如图2 所示，分成以f5 步： 1 本文利用通用的词法解析器生成1 二具l e x 和语法解析器生成工具b i s o n 开发了路 径分析工具c r y i n g c a t ，并用c r y i n g c a t 分析了m p 3 解码程序的程序路径， 构造出m p 3 解码程序的控制流图( c o n t r o lf l o wg r a p h ) 。 2 建立带c a c h e 的存储器模型，得到c a c h e 命中率约束。 3 利用a r m 公司的a r me x t e n d e dd e b u g g e r ( a x d ) 符号调试环境进行p i p e l i n e 模型分析，获得指令的执行时间和相邻指令间的修正时问。 4 使用路径分析工具c r y i n g c a t 将第3 步得到的执行时间和修止时间反标到 c f g 图中，根据控制流图建立整数线性规划模型。 5 使用整数线性规划解析器( i l ps o l v e r ) 对整数线性规划模型进行计算和分析，得 到m p 3 解码程序最坏情况执行时间的评估值。 和一般的设计方法所不同的是，本文将硬件模型分析所得到的执行时间信息反标到由 高级语言提取出的控制流图( c f g ) 中而一般基于编译器的设计方法都是将高级语言的 路径信息标注到所对应的汇编语言中。本文提出的方法使得w c e t 的分析不必依赖于特殊 的编译器。程序员利用路径分析工具c r y i n g c a t ，就能提取出程序的路径信息，建立整 数线性规划模型，用整数线性规划解析器( i l ps o l v e r ) 分析计算，从而得到程序的最坏情 况执行时间。 1 3 本文结构 本文由六章组成。第一章绪论，对课题的选题背景、目的和意义做了简单概述。第二 章分析了程序最坏情况执行时间计算主要涉及的两个方面：高层分析( h i g h l e v e la n a l y s i s ) 和底层建模( l o w l e v e lm o d e l i n g ) 卸程序路径分析和硬件执行环境的建模；详细研究了 程序的路径分析原理以及c a c h e 存储器原理和流水线策略，并建立了c a c h e 存储器模型和 p i p e l i n e 模型。第三章在简要介绍词法和语法分析原理后，详细说明了如何利用词法解析 器成生工具l e x 和语法解析器生成上具b i s o n 生成相应的词法和语法解析器，开发出路径 3 东南大学硕士学位论文 分析丁具c r y i n g c a t 。第四章介绍了建立整数线性规划模型的算法和过程：利用路径分 析j 二具c r y i n g c a t 提取g a r f i e l d 系统m p 3 解码程序的控制流图( c f g ) ，根据p i p e l i n e 模型采集到m p 3 解码程序的执行时问信息，将其反标到控制流图( c f g ) 中，然后再通过 路径分析工具c r y i n g c a t 将控制流图( c f g ) 转换为整数线性规划模型。第五章利用整 数线性规划解析器( i l ps o l v e r ) 计算出m p 3 解码程序的最主1 i 情况执行时间，并将计算得 到的w c e t 值和在一定测试向量集r 解码程序的模拟器仿真值进行比较分析。最后在第六 章对论文工作进行总结和展望，指出了本文的不足之处。 4 第二章嵌入式系统w c e t 分析 第二章嵌入式系统w c e t 分析 嵌入式系统软件分析方法通常分为两种：动态分析和静态分析。动态分析一般需要在 h o s t 环境或者t a r g e t 环境中实际运行程序，通过测试用倒去分析软件的性能。而静态分析 不实际运行软件，主要是从编程格式和程序结构方面对软件性能进行评估。静态结构分析 主要是以图形方式表现程序的内部结构，例如函数调用关系图、函数内部控制流图等。程 序最坏情况执行时间( w c e t ) 的分析就是建立在对程序进行静态分析基础上的。通常， 程序员为嵌入式程序选择数据结构和算法时，都认为对程序进行w c e t 分析和评估相当容 易。然而，k l i g e r m a n 、s t o y e n k o 、p u s c h n e r 等人通过研究发现【l 】 4 1 ，并不是任意一个程序 都可以进行w c e t 分析评估的。程序只有满足下列条件时才能对它进行w c e t 分析评估： 1 程序在执行过程中不能被硬件或操作系统中断。 2 程序不能含有递归函数，因为没有办法预知递归的深度。 3 程序不能含有动态数据结构，例如动态数组、指针数组等。网为动态存储空间的 分配时间具有一定的不可预测性。 对程序虽坏情况执行时间( w c e t ) 分析主要包括程序路径分析和硬件结构分析这两 个方面。 程序路径分析就是寻找最坏情况f 指令的执行序列。通过解析高级语言源程序，从中 提取出控制流图( c f g ) ，利用绝对路径穷举法得到具体的指令执行序列，计算出执行时间 的实际范围。但是随着程序复杂度的提高，分支和循环的增多，程序路径的数量呈指数级 上升，贯穿程序的独立路径数是个天文数字，简单利用绝对路径穷举法来分折指令执行序 列的效率非常低。综合考虑效率和准确性因素，本文对c 语言程序代码的语法、语义结构 进行分析提取程序控制流图( c f g 图) ，构造线性约束条件，建立整数线性规划模型( i n t e g e r l i n e a r p r o g r a m m i n g m o d e l ) ，通过整数线性规划解析器( i l p s o l v e r ) 来计算程序最坏情况 执行时间( w c e t ) 。整数线性规划( i n t e g e rl i n e a rp r o g r a m m i n g ) 分析方法使分析效率大 大提高，同时，完整的程序路径分析和合理的硬什结构模型使评估范围非常接近实际范围， 如图3 所示。 实际范围 e 一 k 。瓦m 、。+ 。 7 1 一 f m 执行时间 k 迁笪蔓国 * “”“。 图3 评估范围【m n ，m a x 】包含实际范围【1 m i n ，1m a x 】 一 个 编译器在将高级语言编译成可执行代码的过程中通常都会进行一些优化，同样地，在 嵌入式系统硬件设计中通常也会对硬什结构进行某些优化。为了能捕捉到这些优化信息， 硬什模型必须建立在汇编语言级上。 以前，硬件结构的分析相对比较简单，只需将每条指令的执行时间视为常数，程序最 坏情况执行时间( w c e t ) 只是指令序列执行时间的简单累加。然而，现代嵌入式系统为 了提高系统性能，普遍采用带有p i p e l i n e 指令执行单元的微处理器和带有c a c h e 的存储器。 这些技术的运 j 大大增加了硬件结构分析的难度。指令的执行时间不再仅仅依赖于指令自 5 东南大学硕士学位论文 身，而且还和指令的上r 文环境有关，这给计算总的指令执行时间增加了很多不确定的因 素。 研究表明k 7 “0 】 1 1 】程序最坏情况执行时间的主要分析误筹已从程序路径分析误差 转变为硬件结构模型分析的误差。和带有c a c h e 的存储器相比，含有p i p e l i n e 流水线技术 的微处理器分析和建模相对容易一些，因为指令只受与其毗邻的指令影响。而建立c a c h e 模型，分析指令是否在存储器的c a c h e 中，需要分析在该指令前已执行的若干条指令。取 一条不在c a c h e 中的指令会使得该指令以及它周围的指令一起被调入c a c h e 槽( s l o t ) 中 这个指令置换动作会产生两个影响： 1 、下一条指令很有可能直接从c a c h e 中取山。 2 、被置换出来的c a c h e 槽中的指令有可能会被再次调用，这样又会导致再一次的c a c h e 调用。 因此，在程序路径分析阶段，只要程序有任何的跳转，整个指令序列的c a c h e 槽状态都要 受到影响，并且需要重新分析。任何疏忽都会造成评估范围的极度膨胀，这些给建立合理 的带有c a c h e 的存储器模型带来相当大的挑战。 这一章首先简单介绍了嵌入式系统程序的最坏情况执行时间分析方法，然后对程序执 行路径和硬什结构进行了详细地分析，建立了c a c h e 模型和p i p e l i n e 模型。 2 1 程序路径分析 在对程序路径进行分析前，为了分解问题的复杂性，我们先建立一个简单的硬件结构 模型，即每一条指令的执行时间都是一个常数。这种粗略的模型在后面会被含有指令c a c h e 的存储器模型和p i p e l i n e 模型所代替。 绝对路径穷举法通过正则表达式米描述程序所有的指令路径，利用i d l 语言 ( i n f o r m a t i o nd e s c r i p t i o nl a n g u a g e ) 排除不可执行的路径，将所有可执行路径辨别出来， 然后遍历所有可能路释得到程序的最坏情况执行时间( w c e t ) 。辨别可执行路径，排除不 可执行路径通常采用的方法是将程序语句t e f j 止则表选式来描述通过计算正则表达式的交 叉点来寻找程序可执行的路径。这种方法计算十分复杂，只能近似求解，而且程序绝对路 径数鼍和程序的大小呈指数关系，计算量极其庞大，图4 充分地说明了这一点。： f o r ( i = o ：i o 5 ) j + + ： e l s e k + + ： ) r a n d ( ) 函数产生 o ，1 】的随机数 图4 路径数量呈指数增长 图4 为一段很简单地代码，但它的循环有2 ”种可能的路径，若采用绝对路释穷举法 则要花费很长地搜索时间。如果i + + 和k + + 所花的时间相同的话，那么很显然所有可能的 路径都是最坏情况下的路径，由此可以看出绝对路径穷举法效率非常低。本文提山的评估 程序最坏情况执行时间的方法，有效地避免了寻找具体的最坏情况执行路径，是通过建立 和分析程序的控制流图( c f g ) ，把评估最坏情况执行时问的问题转变为求解整数线性规划 6 第二章嵌入式系统w c e t 分析 模型的问题。 根据前面的假设，每条指令的执行时间是阎定的，程序总的执行时间等于每一条指令 执行时间和其执行次数乘积之和。顺序指令的集合具有相同的执行次数，可以视为一个结 点b ；，设结点墨的执行次数是薯，c ；为结点马的执行时问，那么 n 程序总的执行时间= c ( 1 ) i 对于有n 个结点的程序来说，其最坏情况执行时闻等于公式( 1 ) 的最大值。在没有其他 附加信息的前提下，由于工没有约束条件，公式( 1 ) 的最大值为一。但是从程序控制流 上看，结点执行次数置问一定存在着某种线性约束条件。通过分析可知，结点执行次数工 的线性约束主要分为程序结构性约束和程序功能性约束两部分。程序结构性约束可以从程 序的控制流图( c f g ) 中获得。程序控制流图( c f g ) 是一种抽象的数据结构，是对程序 的抽象描述，它由结点和有向边组成。结点可以是单条语句，也可以是连续多条语句。但 若是连续多条语句，那么语句间必须是顺序结构，中间不能出现分支、循环和跳转结构。 有向边连接着结点，表示结点间的控制流向。通常，控制流图中有两个特殊的结点：起始 结点和终止结点。起始结点控制着控制流图的起始入口，控制流必须经过起始结点才能进 入控制流图；控制流必须经过终止结点才能离开控制流图。程序控制流图中若有分支，则 表明程序中有条件判断语句，如i f 语句等：程序控制流图中若有封闭的圆环。则表明程序 中有循环语句，如w h i l e 语句等。程序功能性约束是指包含循环次数约束在内的相关路径 信息，这些路径信息可以从程序语义中获得，或者通过人工添加的方式来得到。程序结构 性约束的建立如图5 所示。 幸 k = 0 s = k ； w h i l e ( k ( 1 0 ) i f ( o k ) j ”； e l s e j = o ；k = 5 ； o k = t r u e ； k + + ： r = j ； ( 2 ) c f g 图5 线性约束的建立 7 东南大学硕士学位论文 图5 是w h i l e 循环内嵌套i f 分支结构的控制流图( c f g ) 。在该图中，e 代表c f g 图中的 一个结点为结点b i 的执行次数，用来表示程序控制流向的有向边，记做d i ，c f g 图 其实就是一个标准网络流图，对它的分析就是对标准网络流图的分析。结点b i 的执行次数 等于控制流流入结点b i 的次数，也等于控制流流出结点b i 的次数。由图5 2 我们可以得 到一系列的等式： d l = l ( 2 ) x l = d l = d 2 ( 3 ) z 22 d 2 + d 82 d 3 + d 9 ( 4 ) 屯= d 3 = d 4 - - i - d 5 x 5 = d 5 = d 7 k = d 6 十d 7 = d 8 ( 5 ) ( 6 ) ( 7 ) ( 8 ) x 7 = d 9 = d l o ( 9 ) 代码段只执行一次，因此添加约束( 2 ) 。 函数中基本结点b i 的执行次数j ，的定义是建立在该函数只被执行一次前提卜的。但在 程序中，一个函数可能会被多次调用。为了统一这个矛盾在构造程序的c f g 图时，增加 一个新的向量( 有向边f ) 来表示函数调用。函数被调用，则有向边，指向被调用函数 c f g 图的一个实例。这种方式类似于将被调用函数看作内联函数来分析。有向边f 的值工 表示函数已被调用的次数t 而被调用函数c f g 国的变量后都要加上后缀“工”以区别于 该函数c f g 图的其他实例。 8 第二章嵌入式系统w c e t 分析 丑 皿 v o i dm a i n 0 慧鼢 v o i di n c ( i n t 却i ) 最木p i + + ( 1 ) 程序代码 ( 2 ) 含有函数i n c0 两个实例的c f g 图 图6 带有函数调用的c f g 图 在图6 1 中，函数i n c ( ) 被函数m a i n ( ) 调用了两次 图中可以得到如下程序结构性约束： d i = 1 z 1 = d 1 = ，l x ：= ，l = ，2 d ：，l = ，1 x rf t = d rj l = d r ，l d rj t = 1 1 而，2 = d ：，2 = d ，2 x 32x 3 ，l + x 3 ，2 图6 2 为其c f g 图。自c f g 公式( 1 7 ) 将函数i n c ( ) 基本结点b f 的执行次数t 和该函数两个实例的执行次数x 3 ，l 、 x r ，2 联系在了一起。 关于循环的约束信息，程序结构性约束无法提供，只能作为程序功能性约束进行人工 添加。在图5 的例子中，k 的初始值大于等于0 循环体执行的次数在0 与1 0 之间，那么 这个约束信息可以表示为： o x l x 3 l o x l ( 1 8 ) e l s e 语句在循环体内最多只会执行一次，那么，这个约束信息义可以表示为： 如l x l 、 ( 1 9 ) 9 d ” ” 们 ；( 东南大学硕十学位论文 通过对代码的深入分析可以得到更为复杂的路径信息。从图5 的代码中可以看出，如果e l s e 语句被执行了，那么循环体将会执行5 次，这个约束信息可以表示成： ( 屯= o ) l ( x 5 l x 3 = 5 而) ( 2 0 ) 虽然约束( 2 0 ) 不是一个线性约束，但可以看成两个线性约束子集的并集。 程序最坏情况执行时间( w c e t ) 的计算方法就是将程序功能性约束子集和程序结构 性约束一起作为公式( 1 ) 的约束条件，利用整数线性规划解析器( i l ps o l v e r ) 来求解公 式( 1 ) 的最大值。 2 2 硬件结构分析 微电子技术的发展，尤其是超人规模集成电路的飞速发展，使得处理器部件的尺寸越 来越小。部件之间的距离越来越短，从而提高了系统运行速度。然而，和早期的计算机组 织结构相比，近年来处理器速度上的增益主要是来自于处理器和存储器组织设计技术的更 新这包括了高速缓存c a c h e 的运用和p i p e l i n e 流水线处理技术等。所有这些技术的出发 点都是最大限度地使处理器保持运行状态。 2 2 1 c a c h e 存储器 c a c h em e m o r y ( 高速缓存，以r 简称c a c h e ) 的目的是为了给出逼近最快存储器的速 度，同时以较便宜的半导体存储器的价格提供一个大存储器容量。图7 说明了这个概念， 相对容量较大、速度较慢的主存储器与容量较小、速度较快的c a c h e 连在一起，c a c h e 中 存放主存储器中的部分副本。当c p u 试图从存储器中读取一个字时，检杏这个字是否在 c a c h e 中。如果是，则这个字传送给c p u ：如果不是，则主存储器中一块捌定数目的字读 入c a c h e ，然后再把这个字传送给c p u 。由于访问局部性，当把一块数据取入c a c h e ，以 满足某次存储器访问时，将来访问块中的其他字时极其可能的。 块传送 宁传送广_ l i 主存储器 图7 c a c h e 和主存储器 图8 描述了c a c h e 主存储器系统的结构。主存储器有多达2 “个可寻址的字组成，每个字有 唯一的n 位地址。为了实现映射，把存储器看成由许多定长的块组成，每个块有k 个字， 即有m = 2 “，k 个块。c a c h e 由c 个行组成，每个行有k 个字。行的数量远远小于主存储 器块的数目( c ( i ) ( 2 ) 一 k 整数 ( 3 ) 一 1 ( + 1 ) ( 4 ) 一 i | ( 整数 e ( 有符号绍数 i e ( 5 ) 一+ | - i + i ，| | = i = 、+ = 、 = 、i l 、+ + 、一等 界限符； 、： 、 、) 、【、】、( 、) 等 其中关键字、运算符和界限符的数目是一定的，每一个赋予它一个类号，形成一一对应 关系。而标识符与常数是由用户任意使用的，其数目无限。标识符统一1 月为一类，用内码 来区分不同的标识符名，通过构造符号表，将标识符的符号表入口地址当作输出二元式的 内码，如表l 所示。 表1符号表和输出二元式 字符串名类型属性地址 ka n g4 i n t 简单变量 k + ml e n g t h6 r e a l 数组 k + na 22i n t 简单变量 输出二元式 ( x ，k ) ( x ，k + m ) ( x ，k + n ) 其中x 为标识符韵类号，k 为符号表的起始地址，m 、n 分别表示为标识符l e n g t h 和a 2 第三章c 语言词法和语法分析 的符号表入口地址偏移最。 将常数分为若干类：整型常数、实型常数、字符常数、布尔常数。每一类建立一张常 数表，它们的常数表入口地址也用来当作输出二元式的内码，表2 为实型常数的常数表。 实常数 3 1 4 1 5 9 2 6 2 5 3 0 0 0 5 表2 实常量表和输出二元式 实常量表 0 3 1 4 1 5 9 2 6 1 0 1 0 2 5 3 * 1 0 2 0 5 1 0 。2 输出的二元式 ( v ，n + 0 ) ( y ，n + 4 ) ( v ，n + 8 ) 由此可见，词法分析的主要工作就是实现状态转换，当状态转换时，执行相应的语义动作 譬如查造符号表等。 3 2 语法分析原理 语法分析阶段的任务是组词成句。每一种语言都有一组语法规则，根据这些语法规则， 可以将单词组合成语法单位，如短语、语句、函数和程序。语法分析就是通过语法规则分 析，确定整个输入串是否能在语法上构成正确的句子或语句。语法分析有两种分析方法： 推导和归约。推导是从文法的起始符号开始，按照语法规则，每次选择规则右部的一个候 选式取代左部，直至识别了句子或者找出错误为i