{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/20676"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/20676","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Partitioning algorithms for parallel circuit simulation","abstract":"Circuit simulation is an indispensable tool in the design and analysis of Very Large Scale Integrated (VLSI) circuits. The most widely used circuit simulators rely on direct methods and offer the most accurate, reliable, and technology-independent means of simulating integrated circuits. The simulation process is inherently very computation intensive and, hence, can require a significant portion of the computational resources available for the development of VLSI circuits. With the use of multiprocessor computers becoming more widespread, there exists an opportunity to speed up the simulation by partitioning the circuit so that the computation may be spread among the processors. To accomplish this, the circuit is partitioned into subcircuits using a node tearing method. If the circuit matrix is ordered subcircuit by subcircuit followed by the tearing nodes, then the matrix takes a bordered-block-diagonal form and the LU-factorization of the diagonal blocks may take place in parallel. This thesis defines the important objectives for this partitioning task and presents two algorithms that may be used to meet the partitioning goals. The first algorithm is an iterative improvement algorithm and the second is a network flow algorithm. Partitioning results and speedups are given for a variety of circuits.","abstract_html":"Circuit simulation is an indispensable tool in the design and analysis of Very Large Scale Integrated (VLSI) circuits. The most widely used circuit simulators rely on direct methods and offer the most accurate, reliable, and technology-independent means of simulating integrated circuits. The simulation process is inherently very computation intensive and, hence, can require a significant portion of the computational resources available for the development of VLSI circuits. With the use of multiprocessor computers becoming more widespread, there exists an opportunity to speed up the simulation by partitioning the circuit so that the computation may be spread among the processors. To accomplish this, the circuit is partitioned into subcircuits using a node tearing method. If the circuit matrix is ordered subcircuit by subcircuit followed by the tearing nodes, then the matrix takes a bordered-block-diagonal form and the LU-factorization of the diagonal blocks may take place in parallel. This thesis defines the important objectives for this partitioning task and presents two algorithms that may be used to meet the partitioning goals. The first algorithm is an iterative improvement algorithm and the second is a network flow algorithm. Partitioning results and speedups are given for a variety of circuits.","abstract_has_math":false,"creators":["Yeh, David Ching-kai"],"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":["Rao, Vasant B."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T12:46:05Z","date_published":"2011-05-07T12:46:05Z","updated_at":"2026-07-22T22:25:16Z","subjects":["Engineering, Electronics and Electrical"],"languages":["eng"],"rights":["Copyright 1990 Yeh, David Ching-kai"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9026360","(UMI)AAI9026360"],"render_values":[{"text":"AAI9026360","href":null,"code":true},{"text":"(UMI)AAI9026360","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/20676","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Rao, Vasant B."]},{"key":"dc:creator","label":"Author","values":["Yeh, David Ching-kai"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T12:46:05Z","10000-01-01","1990"]},{"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 1990 Yeh, David Ching-kai"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9026360","(UMI)AAI9026360","http://hdl.handle.net/2142/20676"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Circuit simulation is an indispensable tool in the design and analysis of Very Large Scale Integrated (VLSI) circuits. The most widely used circuit simulators rely on direct methods and offer the most accurate, reliable, and technology-independent means of simulating integrated circuits. The simulation process is inherently very computation intensive and, hence, can require a significant portion of the computational resources available for the development of VLSI circuits. With the use of multiprocessor computers becoming more widespread, there exists an opportunity to speed up the simulation by partitioning the circuit so that the computation may be spread among the processors. To accomplish this, the circuit is partitioned into subcircuits using a node tearing method. If the circuit matrix is ordered subcircuit by subcircuit followed by the tearing nodes, then the matrix takes a bordered-block-diagonal form and the LU-factorization of the diagonal blocks may take place in parallel. This thesis defines the important objectives for this partitioning task and presents two algorithms that may be used to meet the partitioning goals. The first algorithm is an iterative improvement algorithm and the second is a network flow algorithm. Partitioning results and speedups are given for a variety of circuits.","Made available in DSpace on 2011-05-07T12:46:05Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9026360.pdf: 4333545 bytes, checksum: 78de25b09f58f98cac81eb07dbb8a43e (MD5) Previous issue date: 1990","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:45:31Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:20:10-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":["Partitioning algorithms for parallel circuit simulation"]}]}],"canonical_facts":{"dc:contributor":["Rao, Vasant B."],"dc:creator":["Yeh, David Ching-kai"],"dc:date":["2011-05-07T12:46:05Z","10000-01-01","1990"],"dc:description":["Circuit simulation is an indispensable tool in the design and analysis of Very Large Scale Integrated (VLSI) circuits. The most widely used circuit simulators rely on direct methods and offer the most accurate, reliable, and technology-independent means of simulating integrated circuits. The simulation process is inherently very computation intensive and, hence, can require a significant portion of the computational resources available for the development of VLSI circuits. With the use of multiprocessor computers becoming more widespread, there exists an opportunity to speed up the simulation by partitioning the circuit so that the computation may be spread among the processors. To accomplish this, the circuit is partitioned into subcircuits using a node tearing method. If the circuit matrix is ordered subcircuit by subcircuit followed by the tearing nodes, then the matrix takes a bordered-block-diagonal form and the LU-factorization of the diagonal blocks may take place in parallel. This thesis defines the important objectives for this partitioning task and presents two algorithms that may be used to meet the partitioning goals. The first algorithm is an iterative improvement algorithm and the second is a network flow algorithm. Partitioning results and speedups are given for a variety of circuits.","Made available in DSpace on 2011-05-07T12:46:05Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9026360.pdf: 4333545 bytes, checksum: 78de25b09f58f98cac81eb07dbb8a43e (MD5) Previous issue date: 1990","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:45:31Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:20:10-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":["AAI9026360","(UMI)AAI9026360","http://hdl.handle.net/2142/20676"],"dc:language":["eng"],"dc:rights":["Copyright 1990 Yeh, David Ching-kai"],"dc:subject":["Engineering, Electronics and Electrical"],"dc:title":["Partitioning algorithms for parallel circuit 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:16Z"}