CprE 458/558: Real-Time SystemsImprecise Computational ModelPrecise vs Imprecise resultsMonotone vs 0/1 constraint tasksApplications of Imprecise ComputationsApplications (Contd’)Error Function & Objective FunctionsAlgo F (Min Total Error, monotone task, identical weights, optimal, O(n logn))Scheduling to Minimize Total Error (for IC tasks with 0/1 constraints)Algorithm LDFScheduling periodic tasks(m,k)-firm deadline modelReferencesCprE 545 Iowa State UniversityCprE 458/558: Real-Time SystemsLecture 18Imprecise Computations2CprE 458/558 G. Manimaran (ISU)Imprecise Computational ModelA way to avoid timing faults during transient overloads and a way to introduce fault-tolerance by graceful degradation is the use of Imprecise Computation (IC) technique.The IC model provides scheduling flexibility by trading off result quality to meet task deadlines. A task is divided into a mandatory and an optional part. The mandatory part must be completed before the task's deadline for an acceptable quality of result.3CprE 458/558 G. Manimaran (ISU)Precise vs Imprecise resultsThe optional part, which can be skipped in order to conserve system resources, refines the result. A task is said to have produced a precise result if it has executed its mandatory as well as optional parts before its deadline;otherwise it is said to have produced imprecise (i.e., approximate) result when it executes the mandatory part alone.4CprE 458/558 G. Manimaran (ISU)Monotone vs 0/1 constraint tasksThere are two types of imprecise computational tasks, namely, monotone tasks and 0/1 constraint tasks. A task is monotone if the quality of its intermediate result does not decrease as it executes longer.An imprecise task with 0/1 constraint requires the optional part to be either fully executed or not at all.5CprE 458/558 G. Manimaran (ISU)Applications of Imprecise ComputationsApplications are where one may prefer timely imprecise results to late precise results.In image processing, it is often better to have frames of fuzzy images in time than perfect images.In radar tracking, it is often better to have estimates of target locations in time than accurate location data too late.6CprE 458/558 G. Manimaran (ISU)Applications (Contd’)For example, in a tracking and control system, a transient fault may cause tracking computation to terminate prematurely and produce an approximate result. No recovery action is needed if the result still allows the system to maintain a track of its targets.Similarly, as long as the approximate result produced by a control law computation is sufficiently accurate for the controlled system to remain stable, the fault that causes the computation to terminate prematurely can be tolerated.7CprE 458/558 G. Manimaran (ISU)Error Function & Objective FunctionsMonotone task, Ti: (mi, oi, di)Mandatory comp. Time (mi), optional comp time (oi), deadline (di)Error ei = F(oi – ki) where ei: Error incurred by task Ti ki: optional portion completedMinimize the total errorMinimize the number of optional tasks discardedShortest processing time first strategyMinimize the number of tardy tasks8CprE 458/558 G. Manimaran (ISU)Algo F (Min Total Error, monotone task, identical weights, optimal, O(n logn))Treat all mandatory tasks as optional.Use ED policy to schedule all the tasks. (St)If a feasible schedule is found, precise schedule is obtained, stop.Else use ED to schedule mandatory tasks. (Sm) If feasible schedule is not found, infeasible schedule, stop.Else use Sm as a template, transform St into an optimal schedule that is feasible and minimizes the total error.(ED policy is a variation of EDF -- stops at deadline)(Example: Refer to textbook, page 118)9CprE 458/558 G. Manimaran (ISU)Scheduling to Minimize Total Error (for IC tasks with 0/1 constraints)The general problem of optimal scheduling of IC tasks with 0/1 constraints is NP-complete.Optimal schedule: A schedule in which the number of discarded optional tasks is minimum. Special case: Optional tasks have equal computation timeLDF algorithm Same ready timeO(n logn) complexityDFS algorithmArbitrary ready timeO(n^2) complexity10CprE 458/558 G. Manimaran (ISU)Algorithm LDFUse ED to find a schedule Sm of the mandatory tasks.If Sm is not feasible, then task set is not feasible.Else do the followingUse Sm as the template to obtain So (So: optimal schedule)Use latest deadline first fashion to adjust the scheduleDetails of the algorithm & example: Refer to pages 119-120 in the book.11CprE 458/558 G. Manimaran (ISU)Scheduling periodic tasksError-cumulativeTracking and control applicationsErron-non-cumulativeImage enhancement and speech processing applications12CprE 458/558 G. Manimaran (ISU)(m,k)-firm deadline modelA periodic task is said to have an (m,k)-firm guarantee if it is adequate to meet the deadlines of m out of k consecutive instances of the task, where m <= k.Periodic task: (pi, ci, mi, ki)A flexible method for expressing timing requirements.Allows “graceful degradation” during overloads.Choose values for m and k such that desired m/k is obtained.(1,1)-firm  hard real-time task.Apps: Radar tracking, Automobile control(m,k) vs. imprecise computation (IC): In (m,k) model instances can be dropped in full; in IC, portion of a instance can be dropped.13CprE 458/558 G. Manimaran (ISU)ReferencesJ.W.S. Liu, K.J. Lin, W.K. Shih, A.C. Yu, J.Y.Chung, and W. Zhao, “Algorithms for scheduling imprecise computations,” IEEE Computer, vol.24, no.5, pp.58-68, May 1991. P. Ramanathan, “Graceful degradation in real-time control applications using (m,k)-firm guarantee,” In Proc. of Fault-Tolerant Computing Symposium, pp.132-141,