Generation and Optimization of Real-Time Code for Embedded Multiprocess and Multiprocessor Systems

许多嵌入式系统都是安全关键型实时系统，必须满足严格的最后期限。在这样的系统的设计过程中，它们的行为是在一个较高的抽象级别上指定的。编译器将这些规范转换为可执行的实现。对于单核和单进程，编译器最近已经扩展到支持实时属性。对于多进程和多处理器系统，编译器目前缺乏这样的支持。在这个项目的过程中，我们提出了一些新的分析来约束几个进程和处理器之间的干扰。在抢占式多进程系统中，被抢占任务的运行时可能会由于被抢占任务清除缓存而增长。因此，我们设计了一种新的缓存分析来估计这些额外的缓存缺失。对于多处理器系统，我们对基于tdma的总线进行了分析，该总线可以精确地估计各个处理器访问共享内存的时间。总体而言，基于tdma的多处理器的第一个统一的最坏情况执行时间（WCET）分析框架已经发布。此外，我们首次提出了编译器优化以减少多进程/多处理器系统中的干扰。第一种技术消除了混合临界系统中任务之间与缓存相关的干扰。第二个组合优化考虑了具有异构本地和共享内存的多处理器系统中的调度和内存分配。该项目的第一阶段侧重于整个系统的单个组件的WCET。然而，这并不令人满意，因为没有考虑整个系统的最坏情况响应时间（wcrt）和可调度性。因此，这方面是第二个项目阶段的重点。我们的总体目标是通过编译器优化来提高组合多进程和多处理器系统的可调度性。为此，我们首先研究一个正式模型，该模型允许在编译器级别对多进程/多处理器系统进行面向wcr的分析和优化。在此模型之上，将开发新的面向wcr的优化，在考虑单个任务的截止日期的情况下提高整个系统的可调度性。这些优化将首先分别针对多进程和多处理器系统进行开发。之后，这些单独的优化将扩展到组合的、合作的方法。在考虑整个系统的可调度性的情况下，找到组合多进程/多处理器系统的帕累托最优解。

Many embedded systems are safety-critical real-time systems that have to meet stringent deadlines. During the design of such systems, their behavior is specified at a high abstraction level. Compilers translate these specifications into executable implementations. For single-cores and single processes, compilers have recently been extended to support real-time properties during this translation. For multiprocess- and multiprocessor-systems, compilers currently lack such a support.In the course of this project, we have proposed a couple of novel analyses to bound the interference between several processes and processors. In preemptive multiprocess-systems, the runtime of preempted tasks can grow due to cache evictions by a preempting task. We thus have designed a novel cache analysis to estimate these additional cache misses. For multiprocessor-systems, we came up with an analysis of TDMA-based buses that precisely estimates the timing of accesses to shared memory by individual processors. Overall, the first unified Worst-Case Execution Time (WCET) analysis framework for TDMA-based multiprocessors has been published.Furthermore, first compiler optimizations to reduce interferences in multiprocess-/multiprocessor-systems have been proposed by us. A first technique eliminates cache-related interferences between tasks in mixed-criticality systems. A second combined optimization considers both scheduling and memory allocation in multiprocessor-systems with heterogeneous local and shared memories.The first phase of this project focused on the WCET of single components of an entire system. This is, however, unsatisfying since in particular Worst-Case Response Times (WCRTs) and schedulability of an entire system are not considered. This aspect thus is the focus of the second project phase. Our overall goal is to improve schedulability of combined multiprocess- and multiprocessor-systems using compiler optimizations. For this purpose, we first of all investigate a formal model allowing the WCRT-oriented analysis and optimization of multiprocess-/multiprocessor-systems at compiler level.On top of this model, novel WCRT-oriented optimizations will be developed which improve schedulability of an entire system under consideration of deadlines for individual tasks. These optimizations will first be developed individually for multiprocess- and multiprocessor-systems. After that, these individual optimizations will be extended towards combined, cooperative approaches. Under consideration of the whole systems's schedulability, Pareto-optimal solutions for combined multiprocess-/multiprocessor-systems shall be found.