{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/19803"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/19803","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Design, analysis and reconfiguration of defect-tolerant VLSI and parallel processor arrays","abstract":"In this thesis, several design, analysis and reconfiguration problems in defect-tolerant VLSI and parallel processor arrays are studied. The NP-hard memory array reconfiguration problem is formulated as a random graph problem, and a provably average-case polynomial time algorithm is presented, while all previous memory reconfiguration algorithms were given without an average-case time complexity analysis. The implemented algorithm runs faster than existing heuristics when the problem size is large. For reconfigurable pipelines, an analytical estimation of the yield is given, while all previous yield estimations were through experiments. A large area defect-tolerant tree architecture is designed that has 99% harvest rate, while all previous designs have harvest rate that is asymptotically 0%. Finally, a general framework for computing the optimal spare allocation is developed for many VLSI redundant systems.","abstract_html":"In this thesis, several design, analysis and reconfiguration problems in defect-tolerant VLSI and parallel processor arrays are studied. The NP-hard memory array reconfiguration problem is formulated as a random graph problem, and a provably average-case polynomial time algorithm is presented, while all previous memory reconfiguration algorithms were given without an average-case time complexity analysis. The implemented algorithm runs faster than existing heuristics when the problem size is large. For reconfigurable pipelines, an analytical estimation of the yield is given, while all previous yield estimations were through experiments. A large area defect-tolerant tree architecture is designed that has 99% harvest rate, while all previous designs have harvest rate that is asymptotically 0%. Finally, a general framework for computing the optimal spare allocation is developed for many VLSI redundant systems.","abstract_has_math":false,"creators":["Shi, Weiping"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Fuchs, W. Kent"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":1992,"date_issued":"1992","date_published":"1992","updated_at":"2026-07-22T22:25:14Z","subjects":["Engineering, Electronics and Electrical","Computer Science"],"languages":["eng"],"rights":["Copyright 1992 Shi, Weiping"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9305693","(UMI)AAI9305693"],"render_values":[{"text":"AAI9305693","href":null,"code":true},{"text":"(UMI)AAI9305693","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/19803","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Fuchs, W. Kent"]},{"key":"dc:creator","label":"Author","values":["Shi, Weiping"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["1992","2011-05-07T12:19:02Z","10000-01-01"]},{"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":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1992 Shi, Weiping"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9305693","(UMI)AAI9305693","http://hdl.handle.net/2142/19803"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In this thesis, several design, analysis and reconfiguration problems in defect-tolerant VLSI and parallel processor arrays are studied. The NP-hard memory array reconfiguration problem is formulated as a random graph problem, and a provably average-case polynomial time algorithm is presented, while all previous memory reconfiguration algorithms were given without an average-case time complexity analysis. The implemented algorithm runs faster than existing heuristics when the problem size is large. For reconfigurable pipelines, an analytical estimation of the yield is given, while all previous yield estimations were through experiments. A large area defect-tolerant tree architecture is designed that has 99% harvest rate, while all previous designs have harvest rate that is asymptotically 0%. Finally, a general framework for computing the optimal spare allocation is developed for many VLSI redundant systems.","Made available in DSpace on 2011-05-07T12:19:02Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9305693.pdf: 2567841 bytes, checksum: 11dc8f0d4cc327db0e1b215c32ef64b8 (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:39:32Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:16:41-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":["Design, analysis and reconfiguration of defect-tolerant VLSI and parallel processor arrays"]}]}],"canonical_facts":{"dc:contributor":["Fuchs, W. Kent"],"dc:creator":["Shi, Weiping"],"dc:date":["1992","2011-05-07T12:19:02Z","10000-01-01"],"dc:description":["In this thesis, several design, analysis and reconfiguration problems in defect-tolerant VLSI and parallel processor arrays are studied. The NP-hard memory array reconfiguration problem is formulated as a random graph problem, and a provably average-case polynomial time algorithm is presented, while all previous memory reconfiguration algorithms were given without an average-case time complexity analysis. The implemented algorithm runs faster than existing heuristics when the problem size is large. For reconfigurable pipelines, an analytical estimation of the yield is given, while all previous yield estimations were through experiments. A large area defect-tolerant tree architecture is designed that has 99% harvest rate, while all previous designs have harvest rate that is asymptotically 0%. Finally, a general framework for computing the optimal spare allocation is developed for many VLSI redundant systems.","Made available in DSpace on 2011-05-07T12:19:02Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9305693.pdf: 2567841 bytes, checksum: 11dc8f0d4cc327db0e1b215c32ef64b8 (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:39:32Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:16:41-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":["AAI9305693","(UMI)AAI9305693","http://hdl.handle.net/2142/19803"],"dc:language":["eng"],"dc:rights":["Copyright 1992 Shi, Weiping"],"dc:subject":["Engineering, Electronics and Electrical","Computer Science"],"dc:title":["Design, analysis and reconfiguration of defect-tolerant VLSI and parallel processor arrays"],"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:14Z"}