 Identification of ComplexityReduction Techniques for Optimal Scheduling in Embedded Distributed RealTime Systems
 Project no: 98113
 Jan Jonsson, Mikael Strömberg
 Chalmers University of Technology, Department of Computer Engineering
 Application as pdf, ps,
Complement to application as pdf
ps, support letter from Mecel AB and University of Micihgan, K.G. Shin and P Khargoneker
 Support: 1 PhD student for 2 years decided 981209.
 Start 990501 with Cecilia Ekelin as Phd student.
 Reports:
 Local web: http://www.ce.chalmers.se/~case/hpcag/echidna.html

Industry contacts
 Lars Magnusson lars.magnusson@mecel.se
 Mecel AB
 Göteborg
 Project 1: A tool environment for the development of embedded systems
 Project 2: Identification of ComplexityReduction Techniques for Optimal Scheduling in Embedded Distributed RealTime Systems
 Project 3: Hierarchical Design and Analysis of Timed Systems
 Project 4: Flexible reliable timing constraints
 Project 5: RATAD,
Reliability And Timing Analysis of Distributed systems
 Project 6: Extension of Project “Flexible Reliable
Timing Constraints”

 Pramod Khargoneker pramod@eecs.umich.edu
 University of Michigan
 RealTime Computing Laboratory
 USA
 Project: Identification of Complexity Reduction Techniques for Optimal Scheduling in Embedded RealTime Systems

 Kang G. Shin
 University of Michigan
 RealTime Computing Laboratory
 USA
 Project: Identification of Complexity Reduction Techniques for Optimal Scheduling in Embedded RealTime Systems
Overview
The application of optimal search strategies to scheduling for distributed
realtime systems is, in general, plagued by an inherent computational
complexity. This has effectively prevented the integration of existing
search strategies in scheduling frameworks and tools used in practice today.
The integration of an optimal scheduling strategy could lead to, for example,
higher application schedulability, better utilization of scarce resources,
or higher system reliability, than can be attained for a suboptimal scheduling
technique. This project aims at demonstrating that optimal scheduling is, in
fact, a viable alternative for many realtime scheduling scenarios. Our
approach is based on the hypothesis that, with detailed knowledge about the
realtime application and its characteristics, it is possible to make
intelligent choices in the configuration of the search algorithm in such a
way that the time it takes to generate an optimal assignment of tasks to
system resources is reduced to a tractable value on the average.
Results
A scheduling framework based on SICStus Prolog and its integrated constraint
programming (CP) environment has been developed [1,2]. The framework provides
support for scheduling embedded distributed realtime applications with regular
(timing, precedence, exclusion) and special (locality, clustering, replication)
design constraints. The modeling approach used in the CP environment allows the
system designer to retain valid information from the system specification during
the scheduling process, which often yields optimal results within reasonable time.
The framework will be made available for the industrial partner during 2000 for
an evaluation in a practical context.
The international collaboration with Professor Kang G. Shin at University
of Michigan has resulted in a research manuscript [3] which reports several
effective methods for configuring a branchandbound algorithm for the
scheduling problem. The proposed methods are shown to contribute to a
significant (orders of magnitude) reduction in the average search complexity
of the algorithm.
Cooperation
Collaboration with the project industrial partners
There are regular meetings with the industrial partner (Mecel AB) where
research problems and industrial needs are discussed. The industrial partner
also provides case studies that allows for the evaluation of the tools and
methods developed at Chalmers.
International collaborations
The project has collaboration with Professor Kang G. Shin at The RealTime
Computing Laboratory, University of Michigan. A visit at RTCL by Cecilia Ekelin
is planned during 2001.
Swedish collaborations
The project has ongoing interactions with other ARTES projects led by
Dr. Gerhard Fohler at Mälardalen University.
Publications
 Cecilia Ekelin and Jan Jonsson: Solving Embedded System Scheduling
using Constraint Programming, (in submission), Technical Report 0012,
Department of Computer Engineering, April 2000.
 Cecilia Ekelin and Jan Jonsson: RealTime System Constraints: Where do
They Come From and Where do They Go? Proceedings of the International
Workshop on RealTime Constraints, Alexandria, Virginia, October 1999.
 Jan Jonsson and Kang G. Shin: On the Practical Application of the
BranchandBound Algorithm to RealTime Multiprocessor Scheduling.
(in journal submission), Technical Report, Department of Computer
Engineering, January 2000.
