{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/22819"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/22819","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Parallel algorithms for placement and routing in VLSI design","abstract":"The computational requirements for high quality synthesis, analysis, and verification of VLSI designs have rapidly increased with the fast growing complexity of these designs. Past research has focused on the development of heuristic algorithms, special purpose hardware accelerators, or parallel algorithms for the numerous design tasks to decrease the time required for solution. In this thesis, we propose two new parallel algorithms for two VLSl synthesis tasks, standard cell placement and global routing.","abstract_html":"The computational requirements for high quality synthesis, analysis, and verification of VLSI designs have rapidly increased with the fast growing complexity of these designs. Past research has focused on the development of heuristic algorithms, special purpose hardware accelerators, or parallel algorithms for the numerous design tasks to decrease the time required for solution. In this thesis, we propose two new parallel algorithms for two VLSl synthesis tasks, standard cell placement and global routing.","abstract_has_math":false,"creators":["Brouwer, Randall Jay"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical and Computer Engineering","degree_department":null,"school":null,"contributors":["Banerjee, Prithviraj"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T13:52:32Z","date_published":"2011-05-07T13:52:32Z","updated_at":"2026-07-22T22:25:20Z","subjects":["Engineering, Electronics and Electrical","Computer Science"],"languages":["eng"],"rights":["Copyright 1991 Brouwer, Randall Jay"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9136553","(UMI)AAI9136553"],"render_values":[{"text":"AAI9136553","href":null,"code":true},{"text":"(UMI)AAI9136553","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/22819","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":["Brouwer, Randall Jay"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T13:52:32Z","10000-01-01","1991"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical and Computer Engineering"]},{"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 1991 Brouwer, Randall Jay"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9136553","(UMI)AAI9136553","http://hdl.handle.net/2142/22819"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["The computational requirements for high quality synthesis, analysis, and verification of VLSI designs have rapidly increased with the fast growing complexity of these designs. Past research has focused on the development of heuristic algorithms, special purpose hardware accelerators, or parallel algorithms for the numerous design tasks to decrease the time required for solution. In this thesis, we propose two new parallel algorithms for two VLSl synthesis tasks, standard cell placement and global routing.","The first algorithm, a parallel algorithm for global routing, uses hierarchical techniques to decompose the routing problem into independent routing subproblems that are solved in parallel. Results are then presented which compare the routing quality to the results of other published global routers and which evaluate the speedups attained.","The second algorithm, a parallel algorithm for cell placement and global routing, hierarchically integrates a quadrisection placement algorithm, a bisection placement algorithm, and the previous global routing algorithm. Unique partitioning techniques are used to decompose the various stages of the algorithm into independent tasks which can be evaluated in parallel. Finally, we present results which evaluate the various algorithm alternatives and compare the algorithm performance to other placement programs, and we present measurements on the parallel speedups available.","Made available in DSpace on 2011-05-07T13:52:32Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9136553.pdf: 3489494 bytes, checksum: 5161a276fb6ec4837d987c1c9909a20b (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:00:13Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:28:28-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 placement and routing in VLSI design"]}]}],"canonical_facts":{"dc:contributor":["Banerjee, Prithviraj"],"dc:creator":["Brouwer, Randall Jay"],"dc:date":["2011-05-07T13:52:32Z","10000-01-01","1991"],"dc:description":["The computational requirements for high quality synthesis, analysis, and verification of VLSI designs have rapidly increased with the fast growing complexity of these designs. Past research has focused on the development of heuristic algorithms, special purpose hardware accelerators, or parallel algorithms for the numerous design tasks to decrease the time required for solution. In this thesis, we propose two new parallel algorithms for two VLSl synthesis tasks, standard cell placement and global routing.","The first algorithm, a parallel algorithm for global routing, uses hierarchical techniques to decompose the routing problem into independent routing subproblems that are solved in parallel. Results are then presented which compare the routing quality to the results of other published global routers and which evaluate the speedups attained.","The second algorithm, a parallel algorithm for cell placement and global routing, hierarchically integrates a quadrisection placement algorithm, a bisection placement algorithm, and the previous global routing algorithm. Unique partitioning techniques are used to decompose the various stages of the algorithm into independent tasks which can be evaluated in parallel. Finally, we present results which evaluate the various algorithm alternatives and compare the algorithm performance to other placement programs, and we present measurements on the parallel speedups available.","Made available in DSpace on 2011-05-07T13:52:32Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9136553.pdf: 3489494 bytes, checksum: 5161a276fb6ec4837d987c1c9909a20b (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:00:13Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:28:28-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":["AAI9136553","(UMI)AAI9136553","http://hdl.handle.net/2142/22819"],"dc:language":["eng"],"dc:rights":["Copyright 1991 Brouwer, Randall Jay"],"dc:subject":["Engineering, Electronics and Electrical","Computer Science"],"dc:title":["Parallel algorithms for placement and routing in VLSI design"],"dc:type":["text"],"thesis:degree_discipline":["Electrical and Computer Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:20Z"}