论文部分内容阅读
摘要： 关键词： 中图分类号： 文献标志码： A文章编号： 2095-2163（2017）06-0173-05
Abstract： To make it clear whether refactoring can optimize WCET， the basic theory of WCET estimation is firstly analyzed， and then the basic principle of WCET optimization is proposed. According to the principle， seven refactoring methods are selected from traditional source code refactoring to optimize WCET. The experimental results show that source code refactoring can reduce WCET， but the result is affected by the configuration of target processor， the control structure of testing program and the optimization level of the compiler. Compared with the traditional compilerbased performance optimization， source code refactoring is more suitable to be used at an early phase of program development. Reasonable usage of refactoring will be helpful to repair timeliness defect in time and then guarantee the timeliness safety of software.
0引言
最差情况执行时间（worstcase execution time， WCET）是指程序P在目标处理器X上的执行时间T，对于任何输入，P在X上的执行时间都不会超过T。在实时系统中，尤其是新兴的、安全关键的信息物理系统，例如，汽车的主动刹车系统、无人机的自动巡航系统、智能电网的继电保护系统等，程序的执行时间通常是至关重要的，即使是在最差情况下也不能超出截止期，否则可能造成灾难性后果。因此，WCET已经成为评估软件时效安全性的一个非常重要的指标和参数。
为了获得理想的WCET，程序员会在性能优化阶段（通常是在系统开发后期）利用编译器对目标代码进行优化 ＼[1＼]。然而，随着信息物理系统的兴起，程序的规模越来越大，结构也越来越复杂，上述做法面临以下问题：首先，优化时机太迟，如果WCET无法满足要求，此时修复时效缺陷的成本会远高于编码阶段；其次，优化对象是目标代码，只能在程序具备编译、链接条件后才能优化，且优化后的目标代码不具备可移植性；最后，优化依赖于编译器，且以平均性能的优化为主，优化WCET的效果并不稳定；此外，编译器优化还会给代码调试造成不便，因而在早期编码阶段常常被禁用。
事实上，为了保证软件的时效安全，安全关键实时系统的开发应当采用时间预算法＼[2＼]。即，在设计阶段为每一个组件预先分配一定资源，包括执行轨迹和执行时间。编码时，程序员要时刻关注每个组件的WCET，一旦发现超时，则认为程序存在时效缺陷，应立即予以修复＼[3-4＼]。相较于传统方法，源码重构的优点在于：
1）重构是在早期编码阶段设计发生，因而有助于及时修复时效缺陷。
2）重构对象是源码，更换目标处理器后无需修改即可复用，有利于降低新系统的开发成本。
3）重構专门针对WCET，且不受编译器优化规则的限制，因而优化更灵活，效果更稳定。
1源码重构
重构（refactoring）是指在不改变软件可观察行为的前提下，使用一系列重构手法调整代码结构。重构的目的原本是改善代码设计，提高软件的可理解性，降低其修改成本＼[2＼]。而在本文中，重构的目的是在不改变软件可观察行为的前提下，通过对源码结构的调整降低WCET。
1.1优化原则分析
程序的WCET受到代码结构、处理器配置等软硬件方面的多重影响，当程序规模较大、处理器结构较为复杂时，获得实际WCET的可能性很小。人们只能采用变通的方法去估计WCET，例如，隐藏路径枚举技术（implicit path enumeration technology， IPET）。
基于IPET的WCET分析大致可以分为3步：底层分析、高层分析和WCET计算。其中，底层分析主要是为目标处理器建模，包括Cache、流水线、分支预测和指令执行时间等。高层分析主要是构建控制流图、分析可行路径和循环边界等。WCET计算则是使用整数线性规划寻求公式（1）的最优解，所得结果就是整个程序的WCET。公式（1）的数学表述如下：WCET=max（∑ni=1Wceti×Counti） （1）式中，n代表程序的目标代码被划分成基本块的数量；Wceti代表基本块Bi的WCET；Counti是Bi的执行次数，需要利用整数线性规划在定理1的约束下求解。显然，若Counti=0，则基本块Bi对于程序的WCET没有贡献；相反，所有满足Counti>0的基本块则构成了程序的最差情况执行路径（worst-case execution path， WCEP）。
Abstract： To make it clear whether refactoring can optimize WCET， the basic theory of WCET estimation is firstly analyzed， and then the basic principle of WCET optimization is proposed. According to the principle， seven refactoring methods are selected from traditional source code refactoring to optimize WCET. The experimental results show that source code refactoring can reduce WCET， but the result is affected by the configuration of target processor， the control structure of testing program and the optimization level of the compiler. Compared with the traditional compilerbased performance optimization， source code refactoring is more suitable to be used at an early phase of program development. Reasonable usage of refactoring will be helpful to repair timeliness defect in time and then guarantee the timeliness safety of software.
0引言
最差情况执行时间（worstcase execution time， WCET）是指程序P在目标处理器X上的执行时间T，对于任何输入，P在X上的执行时间都不会超过T。在实时系统中，尤其是新兴的、安全关键的信息物理系统，例如，汽车的主动刹车系统、无人机的自动巡航系统、智能电网的继电保护系统等，程序的执行时间通常是至关重要的，即使是在最差情况下也不能超出截止期，否则可能造成灾难性后果。因此，WCET已经成为评估软件时效安全性的一个非常重要的指标和参数。
为了获得理想的WCET，程序员会在性能优化阶段（通常是在系统开发后期）利用编译器对目标代码进行优化 ＼[1＼]。然而，随着信息物理系统的兴起，程序的规模越来越大，结构也越来越复杂，上述做法面临以下问题：首先，优化时机太迟，如果WCET无法满足要求，此时修复时效缺陷的成本会远高于编码阶段；其次，优化对象是目标代码，只能在程序具备编译、链接条件后才能优化，且优化后的目标代码不具备可移植性；最后，优化依赖于编译器，且以平均性能的优化为主，优化WCET的效果并不稳定；此外，编译器优化还会给代码调试造成不便，因而在早期编码阶段常常被禁用。
事实上，为了保证软件的时效安全，安全关键实时系统的开发应当采用时间预算法＼[2＼]。即，在设计阶段为每一个组件预先分配一定资源，包括执行轨迹和执行时间。编码时，程序员要时刻关注每个组件的WCET，一旦发现超时，则认为程序存在时效缺陷，应立即予以修复＼[3-4＼]。相较于传统方法，源码重构的优点在于：
1）重构是在早期编码阶段设计发生，因而有助于及时修复时效缺陷。
2）重构对象是源码，更换目标处理器后无需修改即可复用，有利于降低新系统的开发成本。
3）重構专门针对WCET，且不受编译器优化规则的限制，因而优化更灵活，效果更稳定。
1源码重构
重构（refactoring）是指在不改变软件可观察行为的前提下，使用一系列重构手法调整代码结构。重构的目的原本是改善代码设计，提高软件的可理解性，降低其修改成本＼[2＼]。而在本文中，重构的目的是在不改变软件可观察行为的前提下，通过对源码结构的调整降低WCET。
1.1优化原则分析
程序的WCET受到代码结构、处理器配置等软硬件方面的多重影响，当程序规模较大、处理器结构较为复杂时，获得实际WCET的可能性很小。人们只能采用变通的方法去估计WCET，例如，隐藏路径枚举技术（implicit path enumeration technology， IPET）。
基于IPET的WCET分析大致可以分为3步：底层分析、高层分析和WCET计算。其中，底层分析主要是为目标处理器建模，包括Cache、流水线、分支预测和指令执行时间等。高层分析主要是构建控制流图、分析可行路径和循环边界等。WCET计算则是使用整数线性规划寻求公式（1）的最优解，所得结果就是整个程序的WCET。公式（1）的数学表述如下：WCET=max（∑ni=1Wceti×Counti） （1）式中，n代表程序的目标代码被划分成基本块的数量；Wceti代表基本块Bi的WCET；Counti是Bi的执行次数，需要利用整数线性规划在定理1的约束下求解。显然，若Counti=0，则基本块Bi对于程序的WCET没有贡献；相反，所有满足Counti>0的基本块则构成了程序的最差情况执行路径（worst-case execution path， WCEP）。