Title :
Optimal scheduling of imprecise computation tasks in the presence of multiple faults
Author :
Aydin, Hakan ; Melhem, Rami ; Mossé, Daniel
Author_Institution :
Dept. of Comput. Sci., Pittsburgh Univ., PA, USA
Abstract :
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
Keywords :
real-time systems; scheduling; software fault tolerance; FT Optimal framework; image processing; imprecise computation tasks; multimedia; multiple faults; nondecreasing reward function; optimal scheduling; real-time computing models; speech processing; transient fault tolerance; Application software; Artificial intelligence; Computer science; Delay; Fault tolerance; Integrated circuit modeling; Iris; Multimedia computing; Optimal scheduling; Processor scheduling;
Conference_Titel :
Real-Time Computing Systems and Applications, 2000. Proceedings. Seventh International Conference on
Conference_Location :
Cheju Island
Print_ISBN :
0-7695-0930-4
DOI :
10.1109/RTCSA.2000.896404