Seventh International Conference on Real-Time Computing Systems and Applications (RTCSA'00)
Optimal scheduling of imprecise computation tasks in the presence of multiple faults
Cheju Island, South Korea
December 12-December 14
ISBN: 0-7695-0930-4
H. Aydin, Dept. of Comput. Sci., Pittsburgh Univ., PA, USA
R. Melhem, Dept. of Comput. Sci., Pittsburgh Univ., PA, USA
D. Mosse, Dept. of Comput. Sci., Pittsburgh Univ., PA, USA
With the advance of applications such as multimedia, image/speech processing and real-time AI, real-time computing models allowing to express the "timeliness versus precision" trade-off are becoming increasingly popular. In the imprecise computation model, a task is divided into a mandatory part and an optional part. The mandatory part should be completed by the deadline even under worst-case scenario; however, the optional part refines the output of a mandatory part within the limits of the available computing capacity. A non-decreasing reward function is associated with the execution of each optional part. Since the mandatory parts have hard deadlines, provisions should be taken against faults which may occur during execution. An FT-Optimal framework allows the computation of a schedule that simultaneously maximizes the total reward and tolerates transient faults of mandatory parts. We extend the framework to a set of tasks with multiple deadlines, multiple recovery blocks and precedence constraints among them. To this aim, we first obtain the exact characterization of imprecise computation schedules which can tolerate up to k faults, without missing any deadlines of mandatory parts. Then, we show how to generate FT-Optimal schedules in an efficient way. Our solution works for both linear and general concave reward functions.
Index Terms:
scheduling; software fault tolerance; real-time systems; optimal scheduling; imprecise computation tasks; multiple faults; multimedia; image processing; speech processing; real-time computing models; nondecreasing reward function; FT Optimal framework; transient fault tolerance
Citation:
H. Aydin, R. Melhem, D. Mosse, "Optimal scheduling of imprecise computation tasks in the presence of multiple faults," rtcsa, pp.289, Seventh International Conference on Real-Time Computing Systems and Applications (RTCSA'00), 2000