Files in this item



application/pdf9236634.pdf (5MB)Restricted to U of Illinois
(no description provided)PDF


Title:Scheduling parallel real-time tasks that allow imprecise results
Author(s):Yu, Albert Chuang-Shi
Doctoral Committee Chair(s):Lin, Kwei-Jay
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Computer Science
Abstract:Imprecise computation and parallel processing are two techniques for avoiding timing faults and tolerating hardware faults in hard real-time systems. When a result of the desired quality cannot be produced in time, hard real-time systems can produce an intermediate result of acceptable quality by imprecise computation, reduce the response time of the result by parallel processing, or both, to avoid timing faults. To mask hardware faults, a real-time task is replicated into several copies which are executed on distinct processing elements. The imprecise computation technique provides hard real-time systems with flexible functionality by trading off the quality of the result produced by a task with the amount of the computational resources required to produce it and thus enables the systems to reduce their computational loads in case of hardware faults. These two techniques permit the performance of hard real-time systems to remain predictable and to degrade gracefully.
This thesis describes efficient algorithms for scheduling two different task models on multiprocessors. Both task models support the imprecise computation technique whereby each task is logically decomposed into a hard task and a soft task. The hard task must be completed before the deadline to produce an acceptable result. The soft task refines the result produced by the hard task until the deadline. In the parallelizable task model, each task may be decomposed into concurrent subtasks which are processed simultaneously by multiple processing elements. The overhead associated with concurrent processing is assumed to be a linear function of the degree of parallelism. The scheduling algorithm for this model is optimal, if the multiprocessing overhead is indeed a linear function of the degree of parallelism. In the replicated task model, the replicas of a task must be assigned to distinct processing elements. The performance of the scheduling algorithms for this model is evaluated by stochastic analysis and computer simulations.
Issue Date:1992
Rights Information:Copyright 1992 Yu, Albert Chuang-Shi
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9236634
OCLC Identifier:(UMI)AAI9236634

This item appears in the following Collection(s)

Item Statistics