Efficient techniques for design space exploration and optimization of distributed real-time embedded systems

The complexity of real-time embedded systems has been increasing dramatically, especially for highly distributed real-time embedded systems in automotive or avionics systems. Today's cars have increasingly sophisticated in-vehicle electronic control systems with multiple ECUs (Electronic Controller Units) interconnected via multiple networking protocols, including FlexRay, CAN and TTP. Development of such real-time distributed systems is very challenging due to complex and heterogeneous HW platforms, increasing application complexity, and increasing concurrency in both application and HW platform. Design Space Exploration (DSE) is the process of searching through the vast design space to find a solution that satisfies certain design constraints and/or optimizes certain design objectives. DSE has been advocated as an effective approach to dealing with the design problem of such complex embedded systems. The DSE problem generally considers two orthogonal issues: 1. how can a single design point be evaluated, 2. how can the design space be covered during the exploration process? The search problem is typically a NP-hard problem, and exhaustive exploration of the design space is usually prohibitive due to the sheer size of the design space. In this thesis, we target on TTP-based distributed real-time embedded systems and present efficient techniques for design space exploration and optimization of these systems, including exact techniques (e.g., model-checking), stochastic techniques (e.g., simulated annealing), and hierarchical integration of several search techniques (e.g., LBBD-based optimization framework). Due to the similarity between TTP and FlexRay (de-facto standard protocol for in-vehicle communication), the proposed techniques can potentially be applied to the optimization of FlexRay-based distributed systems. Worst-Case Response Time (WCRT) analysis is a widely-used schedulability analysis technique for Fixed-Priority Scheduling (FPS) and other scheduling algorithms such as Earliest Deadline First (EDF), which is often used as techniques for evaluating a single design point regarding the real-time properties in DSE. Transaction-based task model is an effective modeling approach especially useful for schedulability analysis in distributed real-time systems. In this thesis, We also present effective techniques for improving the computational efficiency of exact WCRT analysis for transaction-based task model, where both FPS and EDF are considered as the processor scheduling strategies. Extensive experiments prove the effectiveness and efficiency of our proposed techniques