{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/72094"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/72094","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Reconfiguration of Fault-Tolerant VLSI Systems","abstract":"Advances in VLSI (Very Large Scale Integration) allow increasingly larger and more complex systems to be fabricated on a single chip or wafer. As the number of elements in these systems increases, the problem of tolerating faulty elements becomes more and more important. This thesis addresses reconfiguration problems for several important fault tolerant architectures. We show that for some fault tolerant architectures the corresponding reconfiguration problems can be solved in polynomial time while for other related architectures reconfiguration is NP-hard. For those reconfiguration problems that can be solved in polynomial time, we present fast (and in many cases asymptotically optimal) algorithms. For the NP-hard reconfiguration problems, we propose several strategies. For some problems, polynomial time approximation algorithms are presented that yield provably good, but not necessarily optimal, solutions. For some reconfiguration problems, however, approximation algorithms are not meaningful. For these problems effective search strategies and heuristics are proposed.","abstract_html":"Advances in VLSI (Very Large Scale Integration) allow increasingly larger and more complex systems to be fabricated on a single chip or wafer. As the number of elements in these systems increases, the problem of tolerating faulty elements becomes more and more important. This thesis addresses reconfiguration problems for several important fault tolerant architectures. We show that for some fault tolerant architectures the corresponding reconfiguration problems can be solved in polynomial time while for other related architectures reconfiguration is NP-hard. For those reconfiguration problems that can be solved in polynomial time, we present fast (and in many cases asymptotically optimal) algorithms. For the NP-hard reconfiguration problems, we propose several strategies. For some problems, polynomial time approximation algorithms are presented that yield provably good, but not necessarily optimal, solutions. For some reconfiguration problems, however, approximation algorithms are not meaningful. For these problems effective search strategies and heuristics are proposed.","abstract_has_math":false,"creators":["Libeskind-Hadas, Ran"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Liu, C."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-17T20:00:45Z","date_published":"2014-12-17T20:00:45Z","updated_at":"2026-07-22T22:26:06Z","subjects":["Engineering, Electronics and Electrical","Computer Science"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI9411689"],"render_values":[{"text":"(UMI)AAI9411689","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/72094","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Liu, C."]},{"key":"dc:creator","label":"Author","values":["Libeskind-Hadas, Ran"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-17T20:00:45Z","10000-01-01","1993"]},{"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":["Engineering, Electronics and Electrical","Computer Science"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/72094","(UMI)AAI9411689"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Advances in VLSI (Very Large Scale Integration) allow increasingly larger and more complex systems to be fabricated on a single chip or wafer. As the number of elements in these systems increases, the problem of tolerating faulty elements becomes more and more important. This thesis addresses reconfiguration problems for several important fault tolerant architectures. We show that for some fault tolerant architectures the corresponding reconfiguration problems can be solved in polynomial time while for other related architectures reconfiguration is NP-hard. For those reconfiguration problems that can be solved in polynomial time, we present fast (and in many cases asymptotically optimal) algorithms. For the NP-hard reconfiguration problems, we propose several strategies. For some problems, polynomial time approximation algorithms are presented that yield provably good, but not necessarily optimal, solutions. For some reconfiguration problems, however, approximation algorithms are not meaningful. For these problems effective search strategies and heuristics are proposed.","Made available in DSpace on 2014-12-17T20:00:45Z (GMT). No. of bitstreams: 1 9411689.pdf: 6056370 bytes, checksum: 21855f2922df525d3e51f690fc43211f (MD5) Previous issue date: 1993","Embargo set by: Seth Robbins for item 72262 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","150 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1993."]},{"key":"dc:title","label":"Title","values":["Reconfiguration of Fault-Tolerant VLSI Systems"]}]}],"canonical_facts":{"dc:contributor":["Liu, C."],"dc:creator":["Libeskind-Hadas, Ran"],"dc:date":["2014-12-17T20:00:45Z","10000-01-01","1993"],"dc:description":["Advances in VLSI (Very Large Scale Integration) allow increasingly larger and more complex systems to be fabricated on a single chip or wafer. As the number of elements in these systems increases, the problem of tolerating faulty elements becomes more and more important. This thesis addresses reconfiguration problems for several important fault tolerant architectures. We show that for some fault tolerant architectures the corresponding reconfiguration problems can be solved in polynomial time while for other related architectures reconfiguration is NP-hard. For those reconfiguration problems that can be solved in polynomial time, we present fast (and in many cases asymptotically optimal) algorithms. For the NP-hard reconfiguration problems, we propose several strategies. For some problems, polynomial time approximation algorithms are presented that yield provably good, but not necessarily optimal, solutions. For some reconfiguration problems, however, approximation algorithms are not meaningful. For these problems effective search strategies and heuristics are proposed.","Made available in DSpace on 2014-12-17T20:00:45Z (GMT). No. of bitstreams: 1 9411689.pdf: 6056370 bytes, checksum: 21855f2922df525d3e51f690fc43211f (MD5) Previous issue date: 1993","Embargo set by: Seth Robbins for item 72262 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","150 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1993."],"dc:identifier":["http://hdl.handle.net/2142/72094","(UMI)AAI9411689"],"dc:subject":["Engineering, Electronics and Electrical","Computer Science"],"dc:title":["Reconfiguration of Fault-Tolerant VLSI Systems"],"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:26:06Z"}