MULTIPROCESSOR REAL-TIME COMPUTING: FORMAL FOUNDATIONS
The Challenge. As real-time
embedded systems become ever more prevalent, important, and complex,
it is becoming imperative that the formal foundations upon which the
design and analysis of such systems are based keep pace with
technological innovations. In this research project, we focus on two
of the more fundamental advances that have occurred in the real-time
and embedded systems domain: first, the software
that comprises such
systems is becoming increasingly more complex; and second, such
systems are increasingly coming to be implemented on
execution platforms
comprised of multiple processing units. We propose to
enhance our understanding of the behavior of complex, multiprocessor,
real-time systems by providing a firm theoretical foundation for the
analysis of timing constraints in such systems, and to obtain new
tools, techniques, and methodologies for the analysis of such systems.
The Approach.
We plan to achieve these objectives by pursuing the following specific goals.
- Deriving new abstract models of real-time
tasks that accurately capture salient features of real-life
application systems that are to be implemented on multiprocessor
platforms, and identifying rules for mapping application systems onto
the most appropriate models.
- Designing new run-time
multiprocessor scheduling algorithms that are provably better than
ones currently used, both in terms of run-time efficiency and in terms
of tractability of off-line analysis.
- Analyzing various (current and new) task models in order to
enhance our understanding of what intrinsic properties render a model
intractable from a timing analysis point of view, and to identify
very general classes of tractable models.
- Constructing "proof-of-concept" software
that validates the usefulness of the theoretical results obtained
during the course of this research.
By achieving these goals, we would have significantly enhanced our
capabilities to design, reason about, and implement real-time systems
on multiprocessor platforms.
Significance.
Almost all prior
results from multiprocessor real-time scheduling theory consider
extremely simple ("pure" periodic or rate-based) task models; the
importance of the proposed research is underscored by the observation
that in the case of uniprocessor real-time scheduling, moving
from these simple task models to more general ones changed what was
then current industry practice in a dramatic manner. We are hopeful
that corresponding advances in multiprocessor scheduling theory will
bring about similar changes in current industry practice in the
real-time and embedded applications domains today. That is, it is our
expectation that success in this project, by creating a new design and
analysis framework for multiprocessor real-time systems, will
translate into a significantly enhanced ability for embedded and
safety-critical real-time systems designers to provide formally
verified systems at a significantly lower cost.
Associated Personnel.
Funding provided by:
The National Science Foundation
Last updated on 2006/01/20 by SkB.