Linköping University: Students Alumni Trade and Industry/Society Internal Search

Design Environment for Real-Time Embedded Systems in Control-Related Applications (ISIS project)

Project Description

This project started in October 1999. Until May 2003, this project has been carried out, within the framework of the ISIS Competence Center, at the Embedded Systems Laboratory (ESLAB), Linköping University (LIU). Nowadays, the work on this project continues under another funding source.

In this project we will concentrate on issues related to the design of distributed embedded systems for control-related applications. Embedded systems are becoming increasingly complex and have to fulfill extremely tough requirements in a highly competitive market. One of the main sources of complexity in current and future embedded systems is their highly heterogeneous nature, enbodying hardware and software components from various sources, including commercials/off-the-self and pre-designed legacy blocks. These embedded systems can be characterized as real-time systems which strongly interact with their environment under application-imposed time constraints.

Given the complexity of such a design task, only an adequate design environment can effectively support decisions leading in an acceptable time to cost-efficient, reliable and high performance solutions. The environment has to support a design process which starts from specifications at a high level of abstraction and assist the designer from the early phases of the design. The input specification only describes the overall functionality of the designed system and includes the imposed constraints (timing, power consumption, cost, etc.). Starting from such a system specification, the design environment supports the automatic or interactive exploration of a large design space leading to high performance and cost effective hardware/software implementations.

Project Goals

Our goal in this research project is the development of system level methodologies and design tools integrated in a design environment for embedded hardware/software systems. Starting form a high level and implementation independent specification, these methodologies, algorithms and tools support the designer during design space exploration, refinement and synthesis. We concentrate on aspects which are not sufficiently explored and are generated by recent developments in the area. Our focus in this project is on:

  1. Specific aspects related to distributed embedded systems for automotive and avionics applications.

  2. Design space exploration, with emphasis on scheduling of mixed control and data-flow systems considering communication aspects in a realistic manner.

  3. Architecture selection and modelling, with emphasis on an iterative design process.

Some Background Results Significant for this Project

UML Based Modeling of Real-Time Systems
In order to manage large specifications in an efficient manner and to support system level reuse, an object-oriented methodology based on UML and Java has been investigated with special emphasis on simulation in the context of real-time constraints and on reusability aspects. The model of a GSM Base-Station Transceiver has been elaborated. This has been performed in cooperation with Ericsson Radio Systems.
Scheduling of Systems with Control and Data Dependencies
In order to capture both the data-flow and the control aspects of a given application, a conditional process graph representation has been defined by us earlier. Algorithms for static, time-driven scheduling of conditional process graphs on distributed systems have been developed and implemented. Recently we have extended this approach to include systems with priority based preemptive scheduling. This is important because many control oriented applications are event driven by their nature. Our main contribution in this area is the development of an efficient scheduling technique, taking into account both data and control dependency.
Communication Synthesis for Distributed Real-Time Systems
Communication is becoming the dominant aspect in many distributed real-time systems. In this context we have extended our scheduling algorithms, considering a Time Division Multiple Access (TDMA) protocol for inter-processor communication. Such a protocol is typical for safety-critical applications. At the same time, we have developed algorithms in order to optimize the parameters of the protocol such that specific requirements and constraints imposed by the application are satisfied. We have also investigated schedulability aspects of applications implemented with priority-based preemptive scheduling, on top of the TDMA-based communication support. In this context, we have developed algorithms for optimization of protocol parameters. The particular case study is based on a vehicle cruise controller.

Project Results

Support for an Incremental Design Process for Embedded Real-Time Systems
Current research efforts concerning the codesign of embedded systems concentrate almost exclusively on the design, from scratch, of a new system optimized for a particular application. For many application areas, however, such a situation is extremely uncommon and only rarely appears in design practice. It is much more likely that one has to start from an already existing system running a certain application and the design problem is to implement new functionality (including also upgrades to the existing one) on this system. In such a context it is very important to make as few as possible modifications to the already running applications. The main reason for this is to avoid unnecessarily large design and testing times. Performing modifications on the (potentially large) existing applications increases design time and, even more, testing time (instead of only testing the newly implemented functionality, the old application, or at least a part of it, has also to be retested). However, this is not the only aspect to be considered. Such an incremental design process, in which a design is periodically upgraded with new features, is going through several iterations. Therefore, after new functionality has been implemented, the resulting system has to be structured such that additional functionality, later to be mapped, can easily be accommodated. Considering the design of distributed embedded systems in the context of an incremental design process implies that we perform mapping and scheduling of new functionality so that certain design constraints are satisfied and:
  • already running applications are disturbed as little as possible;

  • there is a good chance that new functionality can, later, easily be mapped on the resulted system.

Supporting such a design process is of critical importance for current and future industrial practice, as the time interval between successive generations of a product is continuously decreasing, while the complexity due to increased sophistication of new functionality is growing rapidly.

More information on this topic can be found here and here .

Current Work

Design of Heterogeneous Event and Time-Triggered Systems
There has been a lot of debate in the literature on the suitability of the event-triggered paradigm as opposed to the time-triggered one for implementation of real-time systems. Several arguments have been brought concerning flexibility, fault tolerance, jitter control or efficiency in processor utilization. Recently, the discussion has also been extended to the communication infrastructure which can also be handled according to the time-triggered or event-triggered paradigm. Thus, a typical time-triggered communication protocol for automotive applications and avionics is the TTP, as opposed to CAN which is the de facto standard event-triggered communication protocol. However, the growing amount and diversity of functions to be implemented on current and future cars and airplanes has clearly shown that time-triggered and event-triggered functions have to coexist on the computing nodes and to interact over the communication infrastructure.

Several new and interesting problems can be identified as result of this development:

  • Elaboration of a holistic schedulability analysis for heterogeneous task sets which interact according to the Universal Communication Model

  • Use of the holistic schedulability analysis in order to guide decisions during the design process

  • Design optimization along the following dimensions:

    1. Application level: partitioning the task-set and the messages into the time-triggered and event-triggered domains.

    2. Optimizations related to communication synthesis: find the most appropriate structure of the communication cycle and determine the optimal configurations of the time-triggered and even-triggered phases.

    3. Global system optimization: determine the underlying architecture and the most suitable mapping of functionality.

So far, we have concentrated on the following aspects:

Holistic Scheduling: We have developed a schedulability analysis and scheduling method for real-time systems consisting of time-triggered(TT) and event-triggered(ET) tasks. The communication infrastructure can be a mixed ET/TT bus, according to the Universal Communication Model. The TT functionality can be statically scheduled so that TT and ET activities interfere as little as possible with each other. First, for the ET sub-system, we developed a schedulability analysis which takes into consideration the influence of a given static schedule. This analysis was then used during the static scheduling process of the TT sub-system, allowing us to control the influence of TT activities on the response times of ET ones.

Bus Access Optimization: The configuration of the bus access cycle has a strong impact on the global performance of the system. The parameters of this cycle have to be optimised such that they fit the particular application and the timing requirements at the task level. Parameters to be optimised are the number of static and dynamic phases during a communication cycle, as well as the length and order of these phases. Considering the static phases, parameters to be fixed are the order, number, and length of slots assigned to the different nodes. In particular, we have considered a bus access optimization problem and have shown that the system performance can be improved by carefully adapting the bus cycle to the particular requirements of the application.

System Optimization: At this point of our work we consider the global optimization of the distributed embedded system. Thus, not only optimization of the bus access is taken into consideration but also partitioning of the functionality and mapping of the tasks to the system nodes.
We consider a system specification consisting of time-triggered (TT) and event-triggered (ET) tasks. The communication infrastructure can be a mixed ET/TT bus, according to the Universal Communication Model. We also consider that some of the tasks are already mapped to nodes and their domain (TT or ET) is already fixed. However, we assume that there are tasks which are not mapped yet and some of the tasks are not yet associated to one of the two domains. Our goal is:

  • to partition the system functionality into ET and TT activities;
  • to map the tasks onto the processors in the architecture;
  • to optimize the parameters of the communication protocol.

The above tasks have to be performed such that the timing constraints of the resulted system are satisfied.

Project Members

Selected Publications

  • Traian Pop, Petru Eles, Zebo Peng: Design Optimization of Mixed Time/Event-Triggered Distributed Embedded Systems, CODES+ISSS, Newport Beach, CA, USA, 2003. PDF

  • Traian Pop, Petru Eles, Zebo Peng: Schedulability Analysis for Distributed Heterogeneous Time/Event Triggered Real-Time Systems, 15th Euromicro Conference on Real-Time Systems, Porto, Portugal, 2003. PDF

  • Paul Pop, Petru Eles, Traian Pop and Zebo Peng: Minimizing System Modification in an Incremental Design Approach, 9th International Symposium on Hardware/Software Codesign, Copenhagen, April, 2001. PDF

  • Paul Pop, Petru Eles, Traian Pop and Zebo Peng: An Approach to Incremental Design of Distributed Embedded Systems, 38th Design Automation Conference (DAC), Las Vegas, USA, June, 2001. PDF

  • Petru Eles, Alex Doboli, Paul Pop and Zebo Peng: Scheduling with Bus Access Optimization for Distributed Embedded Systems, IEEE Transactions on VLSI Systems, Vol. 8, No. 5, pp. 472-491, October, 2000. PS

Other Publications Related the Project

  • Traian Pop: Scheduling and Optimisation of Heterogeneous Time/Event-Triggered Distributed Embedded Systems, Licentiate Thesis No. 1022, Linköping Studies in Science and Technology, 2003. PDF

  • Paul Pop, Petru Eles, Zebo Peng and Traian Pop: Flexibility Driven Incremental Design of Distributed Embedded Systems, submitted for publication.

  • Traian Pop, Petru Eles and Zebo Peng: Holistic Scheduling and Analysis of Mixed Time/Event-Triggered Distributed Embedded Systems, 10th International Symposium on Hardware/Software Codesign, Estes Park, CO, USA, 2002. PDF

  • Daniel Karlsson: A Front-End for a Java-Based Environment for the Design of Embedded Systems, 4th IEEE DDECS Workshop, Gyor, Hungary, April 2001 PDF

  • Razvan Jigorea, Sorin Manolache and Petru Eles: Modelling of Real-Time Embedded Systems in an Object-Oriented Design Environment with UML, IEEE International Symposium on Object-oriented Real-time Distributed Computing (ISORC 2000), Newport Beach, California, 2000. PS

  • Paul Pop, Petru Eles and Zebo Peng: Bus Access Optimization for Distributed Embedded Systems Based on Schedulability Analysis, Proc. Design Automation and Test in Europe (DATE'2000), Paris, 2000. PS

  • Paul Pop, Petru Eles and Zebo Peng: Schedulability Analysis for Systems with Data and Control Dependencies, Proc. 12th Euromicro Real-Time Conference, Stockholm, 2000. PS

  • Paul Pop, Petru Eles and Zebo Peng: Performance Estimation for Embedded Systems with Data and Control Dependencies, 8th International Workshop on Hardware/Software Codesign, San Diego, 2000. PS