2026-09-19T23:17:39Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/20051 2023-07-10 col_2142_5131 col_2142_10761 com_2142_5130 com_2142_10755 com_2142_234

Lin, Kwei-Jay Yu, Albert Chuang-Shi 2011-05-07T12:27:14Z 2011-05-07T12:27:14Z 10000-01-01 1992 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. Made available in DSpace on 2011-05-07T12:27:14Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9236634.pdf: 5155567 bytes, checksum: 156173aa86dd30b70578f976b6dee52b (MD5) Previous issue date: 1992 Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:41:14Z Item is restricted indefinitely. Restriction data tranferred 2014-07-01T11:17:48-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission ETDs are only available to UIUC Users without author permission U of I Only AAI9236634 (UMI)AAI9236634 http://hdl.handle.net/2142/20051 eng Copyright 1992 Yu, Albert Chuang-Shi Computer Science Scheduling parallel real-time tasks that allow imprecise results text Computer Science Computer Science University of Illinois at Urbana-Champaign Dissertation Ph.D.