Scheduling of embedded time-triggered systems

ABSTRACT

Distributed system composition is the main trend in creating safety-critical (SC) real-time systems like automotive, aerospace, and industrial control systems. Their growing complexity (e.g. tens of control units in a modern car) led to an integrated architecture concept [7]. It supports the sharing of hardware resources between different sub-applications for the sake of cost reduction, but still keeps the overall system safety by properly isolating jobs from each other.

Validation and certification of SC sytems are a key problem. They are especially hard, if not impossible at all, if the behavior of the system is non-deterministic. The time triggered (TT) paradigm (such as TTP/C [14] and FlexRay [4]) uses a strictly deterministic, static, design time generated schedule for both the computation jobs in the processing nodes and the internode communication tasks.

Current tools create the intranode job and interjob communication allocation and scheduling in two distinct steps in order to reduce the total computational complexity to a feasible level. However, this separation of the two design steps despite their strong mutual influence may result in sub-optimal resource utilization, thus additional costs.

The rapid growth in the computational power commonly available to the designer justifies re-visiting the potential of single phased global optimization. The recent paper introduces a novel approach calculating resource allocation and task schedules in a single step by using a standard mixed integer linear programming (MILP) solver covering extra-functional requirements as well. At first, optimization is used to explore the boundaries of the design space from the points of view of cost, throughput, robustness and extensibility. Subsequently, the designer can formulate his priorities between these, frequently contradicting goals by creating a weighted objective funtion. Optimization is accelerated by heuristic lower and upper estimates.

REFERENCES

• 1: TTTech AG. TTTech company website. http://www.tttech.com/.
• 2: András Balogh , Dániel Varró, Advanced model transformation language constructs in the VIATRA2 framework, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France [doi>10.1145/1141277.1141575]
• 3: A. Balogh, G. Varró, D. Varró, and A. Pataricza. Model-based optimization of enterprise application and service deployment. In M. Malek, E. Nett, and N. Suri, eds., Second International Service Availability Symposium, ISAS 2005, volume 3694 of LNCS, pages 84--98. Springer, 2005.
• 4: Flexray Consortium. Flexray protocol information portal, http://www.flexray.com/.
• 5: DECOS. Dependable components and systems, an eu framework 6 integrated project, http://www.decos.at/.
• 6: Mentor Graphics. Volcano network design tools homepage. http://www.mentor.com/products/vnd/.
• 7: H. Kopetz, R. Obermaisser, P. Peti and N. Suri. From a federated to an integrated architecture for real-time embedded systems. Technical report, TU Wien, 2004.
• 8: I. Majzik P. Domokos and M. Magyar. Tool-supported dependability evaluation of redundant architectures in computer based control systems. In Proc. FORMS/FORMAT 2007, the 6th Symposium on Formal Methods for Automation and Safety in Railway and Automotive Systems, pages 342--352, January 2007.
• 9: ILOG. Ilog opl studio. http://www.ilog.com/products/oplstudio/.
• 10: L. Almeida, J. A. Fonseca. P. Fonseca Flexible time-triggered communication on a controller area networ. In Presented at the WiP session of RTSSŠ98, December 1998.
• 11: George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
• 12: Paul Pop , Petru Eles , Zebo Peng, Scheduling with optimized communication for time-triggered embedded systems, Proceedings of the seventh international workshop on Hardware/software codesign, p.178-182, March 1999, Rome, Italy [doi>10.1145/301177.303812]
• 13: R. S. Kaplan. D. P. Norton. The Balanced Scorecard: Translating Strategy into Action. Harvard Business School Press, 1996.
• 14: S. Poledna, G. Kroiss. The time-triggered communication protocol TTP/C. Real-Time Magazine, 4:98--101, 1998.
• 15: Klaus Schild , Jörg Würtz, Scheduling of Time-Triggered Real-Time Systems, Constraints, v.5 n.4, p.335-357, October 2000 [doi>10.1023/A:1009804226473]
• 16: Gy. Csertán, Shariful Islam and W. Herzner. Multi variable optimization approach for SW-HW integration. In IEEE High Assurance Systems Engineering Conference(HASE2005), Heidelberg, Germany, pages 178--182, October 2005.

INDEX TERMS

Keywords:
FlexRay, TTP/C, scheduling, time-triggered systems