80《理论计算机科学电子札记》65卷第5期（2002）网址：http://www.elsevier.nl/locate/entcs/volume65.html15页SAXO-RT：口译E星语义上顺序执行结构Etienne Cévillas，Michel Poize，Jacques Pulou1Patrick Venier，Daniel Weil1法国TelecomR&D，28cheminduVieuxChene，38243Meylancedex，法国摘要SAXO-RT编译器实现了将并发同步语言ESTEREL编译为顺序C代码的原始方法 该方法针对内存和实时约束非常严格的嵌入式系统进行了优化，并在工业规模的示例中显示出显着的性能改善。源代码被切成称为控制点的小代码序列，静态调度，以便与E STEREL语义兼容。通过在每次反应时仅执行活动代码序列，在不增加代码大小的情况下优化了速度反应 在本文中，我们详细介绍了如何在我们的执行结构上解释E sterel语义。1介绍嵌入在飞机、卫星或GSM移动电话等系统中的实时应用程序具有双重关键性：首先，因为系统的安全性取决于它们（故障可能导致系统崩溃），其次，它们通常具有非常严格的乍一看，用有限状态自动机方法设计这些系统似乎是合适的，但它不适合系统复杂性的增加。复杂的嵌入式系统需要被设计成模块化的、可组合的（或并发的）基本组件.因此，同步语言似乎是指定和实现这些系统的关键部分的自然选择：它们提供了描述有限状态自动机的高级接口，因此非常适合自动证明技术，即使是在工业规模的系统上。在本文中，我们认为这些系统的软件方面。像LUSTRE[5]这样的面向数据流的同步语言现在广泛用于许多控制命令系统。用LUSTRE编写的应用程序包含一个1电子邮件：firstname. rd.francetelecom.com2002年2月出版，电子科学和B。 V. 操作访问根据C CB Y-NC-N D许可证进行。C.C.等81一组关于信号的并发方程，通常由周期性的钟表卢斯特雷编译技术现在已经成熟，嵌入在空中客车飞机等关键系统中的高效代码，核电站但是LUSTRE对于开发人员来说，一个更好的选择是面向控制的同步语言，如ES-TEREL[2]。E星主要区别于数据流同步局域网，语言由命令式编程风格（而不是等式式）和描述层次自动机的能力。不幸的是，如果在硬件目标上编译ESTEREL已经做了很多工作[7]，传统的ESTEREL编译方法对于软件目标。 ESTEREL经典编译方法的复杂性分析ODS显示，对于大多数工业应用，全局自动机编译[6]具有指数代码和数据大小，而布尔方程编译[7]产生的代码反应时间太慢因此，一个好的方法是将代码切割成小的静态调度序列，仅在需要时执行，并尽可能避免[13]，[14]中关于从并行代码生成顺序代码的工作证实了这种方法的这种兴趣：线性化是基于从输入并行语言中提取的控制流图。在我们的情况下，困难在于找到右控制流图，它捕捉E星然后将该图序列化并将其映射到高效的执行结构上。到目前为止，已经提出了两种方法S. Edwards [8] [9]从ESTEREL中间代码（IC）表示的执行树中构建控制流程图，并以分层执行机为目标，该分层执行机再现了源代码并行和分支结构。我们的方法，其原理首次以法语出版[10]，几乎与[8]同时出版，以英语出版，并进行了工业规模的测试例子[11]。 主要区别是ESTEREL的语义是直接解释成控制流程图。顺序码序列然后从该图中提取，静态调度并映射到执行结构上，该执行结构主要是可扩展的而不是分层的。[11]中提出的缺点要求我们的编译器使用[12]中不久暴露的更精细的调度算法进行本文详细介绍了如何在我们的执行结构上解释E sterel语义（§2）。每个E STEREL内核指令首先被转换为事件图（§3和§4）。这个图被转换成顺序控制流程图（§5和§6）和顺序代码（§7）。性能比较见§9。··C.C.等82§2基于顺序释词结构的Esterel语义解释2.1ESTERELsemanticESTEREL构造性语义依赖于四个基本规则[4]：反应性：给定一组输入，总是至少有一组可能的决定论：给定一组输入，永远不会有多于一组可能的输出。信号相干性定律（也称为信号原子性）：当且仅当信号S在同一同步反应期间发射时，信号S可以存在构造性：对信号状态不执行推测性计算：换句话说，因果关系分析是单调的（并且必须遵守序列运算符在顺序执行结构上执行E-STEREL下面介绍的真理需要ESTEREL建设性的解释，mantic，归纳为以下规则：R1：信号的设置或重置必须始终在该信号的任何测试之前（信号相干性定律和构造性）。R2：并行构造的终止测试必须总是在每个并行分支终止之后进行R3：保护强抢占（中止和挂起）的测试总是在执行指令体之前进行评估。R4：通过嵌套在并行构造中的出口终止陷阱构造必须在其他并行分支遇到暂停或终止之后发生2.2执行结构将ESTEREL语法图转换为事件图（EG）。与[13]中使用的程序依赖图或[8]的并发控制流图（CCFG）不同，事件图不仅表示节点之间的依赖关系，而且表示节点对其他节点的动作。在本文中，唯一可能的动作是为下一个或当前的同步反应打开或关闭一个节点，并测试一个节点的状态。为了生成可在顺序机上执行的代码，事件图被分解成一个执行结构，我们称之为顺序控制流图（SCFG）。建造EG（cf. 3)由该执行结构的特征决定（图2）：• SCFG节点是EG的全序子集C.C.等83ǁ信号出口在每个同步反应中，仅执行活动节点的子集，总顺序由SCFG定义。每个节点关联两个布尔值Scurrent（n）和Snext（n），当且仅当n被调度用于当前反应（分别用于下一反应）时，这两个布尔值分别为真。节点n可以改变Scurrent（nJ）当且仅当n nJ，其中• 节点n可以改变任何节点NJ的状态Snext（NJ）。• 节点n可以测试状态Scurrent（nJ），只有当nJ>-Pon发射R+onPon>>发射R？一个没有什么根发射{{{{没有什么对C.C.等95V3V5V5+ O点SAX O R T + O p tEC100 00 001000000100 00 0100 00100 0100101000001000010001001011图五. 反应时间六、代码+数据大小9结果和比较性能分析实验已经运行，以比较我们的编译器SAXO-RT的性能，从V3自动机编译器，V5布尔方程编译器（免费提供http://www.esterel.org）和S。爱德华兹除了最大的例子，它不会终止，由布尔方程编译器产生的代码已经优化的blifopt工具的基础上的SIS逻辑优化器由伯克利分校开发。我们使用的基准或多或少与[9]中使用的基准相同在11个基准上获得的结果从小到大的工业规模的例子进行排序图5和图6显示了这些基准测试在带有SUN C编译器的SPARC处理器上获得的结果，包括反应时间和代码大小。V3编译器（自动编译）不会在非常大的例如，由于状态空间爆炸。SAXO-RT获得反应时间比布尔方程方法（优化）好1.5到100倍使用Blifopt）。在最大的例子（mca200和合唱团），我们获得的反应时间比Esterel V5编译器好5至25倍，同时保持代码大小约4倍小。与EC编译器的比较显示了惊人的相似结果。10结论我们已经提出了一个原始的方式解释ESTEREL语义到一个事件图。该图由SAXO-RT编译器转换成顺序控制流程图，并由此生成高效的顺序代码。介绍，使ESTEREL的使用嵌入式系统与紧密的连接，能量和内存限制。在大的例子中，使用SAXO-RT通常比使用布尔等式好5到20倍编译。的SAXO-RT编译器接受任何非循环的E星程序，并已在几个工业原型验证。 它有现在达到了工业质量，并正在集成到CAD工具中ESTEREL STUDIO，由Esterel Technologies开发。此外，虽然我们使用了非常不同的执行结构，但S.爱德华兹认为，性能很容易V3V5V5+可选SAXORT+OptECC.C.等96结合两种编译方法的优点进行改进引用[1] N.陈文，反应式系统的同步程序设计，清华大学出版社，1993。[2] G.Berry，G.贡蒂耶E星同步编程语言：设计，语义，实现，计算机编程科学，卷19-2，页。87-152，1992年。[3] G.Berry ， TheESTERELPrime r ， EcoledesMines ， CenetredeMath'ematiqueshouqu'ees，Sophia-Anti polis，http://www-sop.inria.fr/meije/este re l.[4] G.贝瑞，埃斯特雷尔的基础，在证明，语言和互动：纪念罗宾米尔纳的散文。G. Plotkin，C.Stirling和M.托夫特编辑们麻省理工学院出版社，计算基础系列，2000年[5] N. Halbwachs，P. Caspi，P. Raymond，D.李文，同步数据流程序设计语言LUSTRE.1991年9月，IEEE学报，第79卷[6] G. 接着，S′emantiquesetmod`eles[7] F. 米格纳德，汇编 迪朗阿格E星方程的系统boo l'eennes，Th'esedel 'Ecole des Mines de Paris，o ctobre 1994.[8] S.A.陈志华，[9] S.A. Edwards，[10] 诉Bertin，M. Poize，J. Pulou，[11] D. Weil，V.Bertin，E.Czech，M.Poize，P.Venier，J.普卢汇编E星实时嵌入式系统《案例》，2000年，第100页。2-8，圣何塞，2000年11月。[12] E. Czech，M. Poize，J. Pulou，P. Venier，D. Weil，SAXO-RT：E.汇编E星实时嵌入式系统IWACT'01，pp. 83-86，布加勒斯特，2001年7月。[13] Ferrante和M. Mace，[14] B. Simons，D.陈志荣，
我的内容管理
展开
