{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/22981"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/22981","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Parallel algorithms for test generation and fault simulation","abstract":"With increase in complexity of digital circuits, it has become extremely important to detect faults to ensure correct operation of a digital circuit. Since test generation and fault simulation for circuits of VLSI complexity can take a prohibitive amount of time, speeding up test generation and fault simulation algorithms by either using better uniprocessor heuristics or by using the tremendous computing power available on multiprocessors thus becomes important. The design and analysis of parallel algorithms for test generation and fault simulation are the focus of this thesis research.","abstract_html":"With increase in complexity of digital circuits, it has become extremely important to detect faults to ensure correct operation of a digital circuit. Since test generation and fault simulation for circuits of VLSI complexity can take a prohibitive amount of time, speeding up test generation and fault simulation algorithms by either using better uniprocessor heuristics or by using the tremendous computing power available on multiprocessors thus becomes important. The design and analysis of parallel algorithms for test generation and fault simulation are the focus of this thesis research.","abstract_has_math":false,"creators":["Patil, Srinivas"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Engineering, Electronics and Electrical","degree_department":null,"school":null,"contributors":["Banerjee, Prithviraj"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T13:57:57Z","date_published":"2011-05-07T13:57:57Z","updated_at":"2026-07-22T22:25:21Z","subjects":["Engineering, Electronics and Electrical"],"languages":["eng"],"rights":["Copyright 1991 Patil, Srinivas"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9124467","(UMI)AAI9124467"],"render_values":[{"text":"AAI9124467","href":null,"code":true},{"text":"(UMI)AAI9124467","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/22981","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Banerjee, Prithviraj"]},{"key":"dc:creator","label":"Author","values":["Patil, Srinivas"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T13:57:57Z","10000-01-01","1991"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Engineering, Electronics and Electrical"]},{"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"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1991 Patil, Srinivas"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9124467","(UMI)AAI9124467","http://hdl.handle.net/2142/22981"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["With increase in complexity of digital circuits, it has become extremely important to detect faults to ensure correct operation of a digital circuit. Since test generation and fault simulation for circuits of VLSI complexity can take a prohibitive amount of time, speeding up test generation and fault simulation algorithms by either using better uniprocessor heuristics or by using the tremendous computing power available on multiprocessors thus becomes important. The design and analysis of parallel algorithms for test generation and fault simulation are the focus of this thesis research.","We first categorize various parallel processing techniques available for test generation and fault simulation. We then propose a parallel search method to overcome the deficiencies of inaccurate search heuristics. We show that this method not only results in faster execution of the test generation algorithm but also results in a better quality of the solution. We also propose a performance model to evaluate the parallel search technique.","We then propose fault partitioning techniques to speed up test generation for faults which are relatively easy to detect. The objective of the fault partitioning techniques is to maximize concurrency without affecting the quality of the overall solution. We propose load balancing techniques which try to minimize the processor idle time with very low communication overhead. We propose a performance model which takes into account the various trade-offs in exploiting parallelism in a test generation/fault simulation environment.","Finally, we present a parallel test generation system for sequential circuits. A parallel search technique is used to accelerate test generation for hard to detect faults, and a circuit partitioned approach is used to accelerate fault simulation.","Made available in DSpace on 2011-05-07T13:57:57Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9124467.pdf: 5751613 bytes, checksum: aaf96417e7558989f9c47080fdf0db4c (MD5) Previous issue date: 1991","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T15:01:21Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:29:06-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":["Parallel algorithms for test generation and fault simulation"]}]}],"canonical_facts":{"dc:contributor":["Banerjee, Prithviraj"],"dc:creator":["Patil, Srinivas"],"dc:date":["2011-05-07T13:57:57Z","10000-01-01","1991"],"dc:description":["With increase in complexity of digital circuits, it has become extremely important to detect faults to ensure correct operation of a digital circuit. Since test generation and fault simulation for circuits of VLSI complexity can take a prohibitive amount of time, speeding up test generation and fault simulation algorithms by either using better uniprocessor heuristics or by using the tremendous computing power available on multiprocessors thus becomes important. The design and analysis of parallel algorithms for test generation and fault simulation are the focus of this thesis research.","We first categorize various parallel processing techniques available for test generation and fault simulation. We then propose a parallel search method to overcome the deficiencies of inaccurate search heuristics. We show that this method not only results in faster execution of the test generation algorithm but also results in a better quality of the solution. We also propose a performance model to evaluate the parallel search technique.","We then propose fault partitioning techniques to speed up test generation for faults which are relatively easy to detect. The objective of the fault partitioning techniques is to maximize concurrency without affecting the quality of the overall solution. We propose load balancing techniques which try to minimize the processor idle time with very low communication overhead. We propose a performance model which takes into account the various trade-offs in exploiting parallelism in a test generation/fault simulation environment.","Finally, we present a parallel test generation system for sequential circuits. A parallel search technique is used to accelerate test generation for hard to detect faults, and a circuit partitioned approach is used to accelerate fault simulation.","Made available in DSpace on 2011-05-07T13:57:57Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9124467.pdf: 5751613 bytes, checksum: aaf96417e7558989f9c47080fdf0db4c (MD5) Previous issue date: 1991","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T15:01:21Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:29:06-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":["AAI9124467","(UMI)AAI9124467","http://hdl.handle.net/2142/22981"],"dc:language":["eng"],"dc:rights":["Copyright 1991 Patil, Srinivas"],"dc:subject":["Engineering, Electronics and Electrical"],"dc:title":["Parallel algorithms for test generation and fault simulation"],"dc:type":["text"],"thesis:degree_discipline":["Engineering, Electronics and Electrical"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:21Z"}