- Identification of Complexity-Reduction Techniques for Optimal Scheduling in Embedded Distributed Real-Time Systems
- Project no: 9811-3
- 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 98-12-09.
- Start 99-05-01 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 Complexity-Reduction Techniques for Optimal Scheduling in Embedded Distributed Real-Time 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
- Real-Time Computing Laboratory
- USA
- Project: Identification of Complexity Reduction Techniques for Optimal Scheduling in Embedded Real-Time Systems
-
- Kang G. Shin
- University of Michigan
- Real-Time Computing Laboratory
- USA
- Project: Identification of Complexity Reduction Techniques for Optimal Scheduling in Embedded Real-Time Systems
Overview
The application of optimal search strategies to scheduling for distributed
real-time 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 sub-optimal scheduling
technique. This project aims at demonstrating that optimal scheduling is, in
fact, a viable alternative for many real-time scheduling scenarios. Our
approach is based on the hypothesis that, with detailed knowledge about the
real-time 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 real-time 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 branch-and-bound 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.
Co-operation
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 Real-Time
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 00-12,
Department of Computer Engineering, April 2000.
- Cecilia Ekelin and Jan Jonsson: Real-Time System Constraints: Where do
They Come From and Where do They Go? Proceedings of the International
Workshop on Real-Time Constraints, Alexandria, Virginia, October 1999.
- Jan Jonsson and Kang G. Shin: On the Practical Application of the
Branch-and-Bound Algorithm to Real-Time Multiprocessor Scheduling.
(in journal submission), Technical Report, Department of Computer
Engineering, January 2000.
|
