University of Houston
Department of Computer Science
In partial fulfillment of the Requirements for the Degree of
Master of Science
Rong Wang
will defend her thesis
A New Scheduling Algorithm and a Compensation Strategy
for Imprecise Computation
Abstract
Nowadays both the periodic multiframe task models and the imprecise computation
techniques are developed elaborately in the real-time system area. We introduce
the imprecise computation concept into the periodic multiframe task model and
derive a novel scheduling algorithm and a compensation strategy. The thesis mainly
focuses on the soft real time system and pays attention to the imprecise
computation input error, which was often neglected in previous studies.
The basic idea of the scheduling algorithm is an error compensation strategy
that works on the basis of the traditional Largest-Weight-First algorithm (LWF). The LWF
algorithm guarantees that the largest weighted task executes first, thus minimizing the
weighted total error in the task set; our error compensation strategy enhances the error
tolerance during the scheduling and thus takes maximum advantage of the processor idle
time to improve the processor utilization.
The experimental results show that the new task model and the new
compensation strategy are practical in improving the schedulability and the processor
utilization. The high error tolerance results in high schedulability, and 100% processor
utilization can be achieved in our algorithm. Moreover, the scheduling algorithm is able to deal with different laxity cases. Combining the error tolerance
coefficient and the error compensation strategy can achieve a good tradeoff between the
result quality and the available processor time.
Date: Wednesday, November 21, 2001
Time: 2:30 PM
Place: 550-PGH
Faculty, students, and the
general public are invited.
Thesis Advisor: Dr. Albert Cheng