Efficient Techniques for Design Space Exploration and Optimization of Distributed Real-Time Embedded Systems

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "Efficient Techniques for Design Space Exploration and
Optimization of Distributed Real-Time Embedded Systems"

By

Mr. Xiuqiang He


Abstract

The complexity of Real-time embedded systems has been increasingly 
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) inter-connected 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 
solution techniques (e.g., model-checking, SAT, SMT), stochastic techniques 
(e.g., simulated annealing, evolutionary algorithms), 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 
applied to the optimization of FlexRay-based distributed systems (i.e., static 
segment of FlexRay protocol).

Worst-Case Response Time (WCRT) analysis is a widely-used schedulability 
analysis technique for fixed-priority scheduling and other scheduling 
algorithms such as Earliest Deadline First (EDF), which is often used as 
techniques for evaluating a single design point regarding to real-time 
properties. The transaction-based task model is an effective modeling approach 
especially useful for schedulability analysis in distributed real-time systems. 
We present effective techniques for improving the computation efficiency for 
exact and tractable 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 
algorithms.


Date:			Tuesday, 25 May 2010

Time:			2:00pm – 4:00pm

Venue:			Room 3311
 			Lifts 17/18

Chairman:		Prof. Guanghao Chen (CIVL)

Committee Members:	Prof. Jogesh Muppala (Supervisor)
 			Prof. Shing-Chi Cheung
 			Prof. Frederick Lochovsky
 			Prof. Charles Zhang
                         Prof. Chi-Ying Tsui (ECE)
                         Prof. Albert Cheng (Comp. Sci., Univ. of Houston)


**** ALL are Welcome ****