WCET analysis and optimization for multi-core real-time systems
WCET analysis and optimization for multi-core real-time systems
复制标题
多核实时系统的WCET分析与优化
DOI：
10.17877/de290r-7209
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Timon Kelter
中科院分区：
文献类型：
--
作者：
Timon Kelter
在安全关键实时系统的设计过程中，开发人员必须能够验证系统对外部事件的及时反应。为了实现这一点，在这样的系统中的每个任务的最坏情况下的执行时间（WCET）必须确定。WCET用于可扩展性分析，以验证所有任务是否满足其最后期限，并验证系统的总体时序。不幸的是，任务的执行时间取决于任务的输入值、初始系统状态、由于在同一核上执行的任务而引起的抢占以及由于在其他核上并行执行的任务而引起的干扰。这些依赖性使得几乎不可能覆盖测量中的每个可行的定时行为。最好创建一个静态分析，该分析基于安全的数学模型确定WCET。目前可用的静态WCET分析工具仅限于在单核系统上不间断地运行的单个任务。这些工具还有一些扩展，可以捕捉多任务处理的效果，即，优先级较高的任务抢占，在WCET上的某些明确定义的场景。这些工具现在已经用于验证工业实时软件，例如，在汽车和航空电子领域。到目前为止，还没有成熟的工具可以处理多核平台上的并行任务的情况下，任务可能会相互干扰。本文提出了多种方法对不同类型的多核系统的WCET分析。他们是基于以前的工作对硬件和程序行为的建模，但扩展到共享资源的处理，如共享缓存和共享总线。我们提出了将共享总线分析集成到经典WCET分析框架中的多种方法，并表明可以高精度地有效分析时间触发的总线仲裁策略。为了得到精确的WCET估计的情况下，共享缓存，我们提出了一个有效的分析，利用定时信息，以减少搜索空间的并行系统中的相互作用。所有的分析都在一个研究C编译器中实现。对实时基准的广泛评估表明，它们比以前的方法精确11.96倍。最后，我们提出了两个编译器优化，这是专门针对优化的WCET的任务在多核系统中，即一个渐进式优化的共享资源调度和指令调度，使用WCET分析结果，以最佳的地方共享资源请求的个别任务。实验结果表明，这两种组合优化能够实现平均33%的WCET减少。在本论文的研究过程中，开发了一个完整的WCET分析框架，该框架可用于进一步的工作，如将多任务和多核感知技术集成到单个分析器中。
During the design of safety-critical real-time systems, developers must be able to verify that a system shows a timely reaction to external events. To achieve this, the Worst-Case Execution Time (WCET) of each task in such a system must be determined. The WCET is used in the schedulability analysis in order to verify that all tasks will meet their deadlines and to verify the overall timing of the system. Unfortunately, the execution time of a task depends on the task’s input values, the initial system state, the preemptions due to tasks executing on the same core and on the interference due to tasks executing in parallel on other cores. These dependencies render it close to impossible to cover every feasible timing behavior in measurements. It is preferable to create a static analysis which determines the WCET based on a safe mathematical model. The static WCET analysis tools which are currently available are restricted to a single task running uninterruptedly on a single-core system. There are also extensions of these tools which can capture the effects of multi-tasking, i.e., preemptions by higher-priority tasks, on the WCET for certain well-defined scenarios. These tools are nowadays already used to verify industrial real-time software, e.g., in the automotive and avionics domain. Up to now, there are no mature tools which can handle the case of parallel tasks on a multi-core platform, where the tasks potentially interfere with each other. This dissertation presents multiple approaches towards a WCET analysis for different types of multi-core systems. They are based upon previous work on the modeling of hardware and program behavior but extend it to the treatment of shared resources like shared caches and shared buses. We present multiple methods of integrating shared bus analysis into the classical WCET analysis framework and show that time-triggered bus arbitration policies can be efficiently analyzed with high precision. In order to get precise WCET estimations for the case of shared caches, we present an efficient analysis of interactions in parallel systems which utilizes timing information to cut down the search space. All of the analyses were implemented in a research C compiler. Extensive evaluations on real-time benchmarks show that they are up to 11.96 times more precise than previous approaches. Finally, we present two compiler optimizations which are tailored towards the optimization of the WCET of tasks in multi-core systems, namely an evolutionary optimization of shared resource schedules and an instruction scheduling which uses WCET analysis results to optimally place shared resource requests of individual tasks. Experiments show that the two combined optimizations are able to achieve an average WCET reduction of 33%. During the course of this thesis, a complete WCET analysis framework was developed which can be used for further work like the integration of multi-task and multi-core-aware techniques into a single analyzer.
在嵌入式 SMT 处理器上实现 AUTOSAR 调度和资源管理
DOI：
10.1145/1543820.1543828
发表时间：
2009
期刊：
影响因子：
--
作者：
Florian Kluge;Chenglong Yu;Jörg Mische;Sascha Uhrig;Theo Ungerer
通讯作者：
Theo Ungerer
如何增强超标量处理器以提供硬实时功能的有序 SMT
DOI：
10.1007/978-3-642-11950-7_2
发表时间：
2010
期刊：
影响因子：
--
作者：
Jörg Mische;Irakli Guliashvili;Sascha Uhrig;Theo Ungerer
通讯作者：
Theo Ungerer
利用执行硬实时线程的有序 SMT 处理器的备用资源
DOI：
10.1109/iccd.2008.4751887
发表时间：
2008
期刊：
2008 IEEE International Conference on Computer Design
影响因子：
--
作者：
Jörg Mische;Sascha Uhrig;Florian Kluge;Theo Ungerer
通讯作者：
Theo Ungerer