{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/20051"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/20051","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Scheduling parallel real-time tasks that allow imprecise results","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Yu, Albert Chuang-Shi"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Lin, Kwei-Jay"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T12:27:14Z","date_published":"2011-05-07T12:27:14Z","updated_at":"2026-07-22T22:25:15Z","subjects":["Computer Science"],"languages":["eng"],"rights":["Copyright 1992 Yu, Albert Chuang-Shi"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9236634","(UMI)AAI9236634"],"render_values":[{"text":"AAI9236634","href":null,"code":true},{"text":"(UMI)AAI9236634","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/20051","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Lin, Kwei-Jay"]},{"key":"dc:creator","label":"Author","values":["Yu, Albert Chuang-Shi"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T12:27:14Z","10000-01-01","1992"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1992 Yu, Albert Chuang-Shi"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9236634","(UMI)AAI9236634","http://hdl.handle.net/2142/20051"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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"]},{"key":"dc:title","label":"Title","values":["Scheduling parallel real-time tasks that allow imprecise results"]}]}],"canonical_facts":{"dc:contributor":["Lin, Kwei-Jay"],"dc:creator":["Yu, Albert Chuang-Shi"],"dc:date":["2011-05-07T12:27:14Z","10000-01-01","1992"],"dc:description":["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"],"dc:identifier":["AAI9236634","(UMI)AAI9236634","http://hdl.handle.net/2142/20051"],"dc:language":["eng"],"dc:rights":["Copyright 1992 Yu, Albert Chuang-Shi"],"dc:subject":["Computer Science"],"dc:title":["Scheduling parallel real-time tasks that allow imprecise results"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:15Z"}