{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/24504"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/24504","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"New strategies for electronic design automation problems","abstract":"As the semiconductor industry marches towards 22 nm technology and beyond, circuit design has become unprecedentedly omplicated. This presents many new challenges for EDA (electronic design automation), such as lack of effective tools for analog circuit or high-volume and high-frequency printed circuit board (PCB) design, the contradiction between complex EDA compute workloads and time-to-market pressure, manufacturing variability and power management, to name but a few. In this dissertation, we will propose several new strategies to handle the challenges in the EDA field. Wire routing is an important step in the design of PCBs. Although there are many industrial tools to handle IC routing problems, very few tools can handle the routing on high-density and high-frequency boards effectively. Nowadays, most of the PCB routing is still done by tedious and time-consuming manual work. We provide new strategies to solve an important problem in PCB routing, the escape routing problem. Our first strategy is to use Boolean satisfiability to optimally solve the escape routing problem on one PCB component. Our second strategy is to use a novel boundary routing methodology to finish escape routing from two connected PCB components simultaneously. This router can achieve much better routability than industrial tools with less CPU time. Another challenge seen in the EDA field is the increasing CPU time to handle larger and larger designs. On the other hand, many fundamental algorithms and data structures used in the EDA tools have shown great parallelism, such as the well-known BFS (breadth-first search) algorithm and the R-tree structure. Therefore, we propose strategies to use the cost-effective GPU platform to parallelize and accelerate BFS and R-tree query. These strategies are potentially applicable to many EDA problems.","abstract_html":"As the semiconductor industry marches towards 22 nm technology and beyond, circuit design has become unprecedentedly omplicated. This presents many new challenges for EDA (electronic design automation), such as lack of effective tools for analog circuit or high-volume and high-frequency printed circuit board (PCB) design, the contradiction between complex EDA compute workloads and time-to-market pressure, manufacturing variability and power management, to name but a few. In this dissertation, we will propose several new strategies to handle the challenges in the EDA field. Wire routing is an important step in the design of PCBs. Although there are many industrial tools to handle IC routing problems, very few tools can handle the routing on high-density and high-frequency boards effectively. Nowadays, most of the PCB routing is still done by tedious and time-consuming manual work. We provide new strategies to solve an important problem in PCB routing, the escape routing problem. Our first strategy is to use Boolean satisfiability to optimally solve the escape routing problem on one PCB component. Our second strategy is to use a novel boundary routing methodology to finish escape routing from two connected PCB components simultaneously. This router can achieve much better routability than industrial tools with less CPU time. Another challenge seen in the EDA field is the increasing CPU time to handle larger and larger designs. On the other hand, many fundamental algorithms and data structures used in the EDA tools have shown great parallelism, such as the well-known BFS (breadth-first search) algorithm and the R-tree structure. Therefore, we propose strategies to use the cost-effective GPU platform to parallelize and accelerate BFS and R-tree query. These strategies are potentially applicable to many EDA problems.","abstract_has_math":false,"creators":["Luo, Lijuan"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Wong, Martin D.F.","Hwu, Wen-Mei W.","Patel, Janak H.","Chen, Deming"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-25T14:24:47Z","date_published":"2011-05-25T14:24:47Z","updated_at":"2026-07-22T22:25:23Z","subjects":["printed circuit board (PCB) routing","escape routing","Boolean satisfiability","graphics processing unit (GPU)","CUDA","breadth-first search","R-tree"],"languages":["en"],"rights":["Copyright 2011 Lijuan Luo"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/24504","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Wong, Martin D.F.","Hwu, Wen-Mei W.","Patel, Janak H.","Chen, Deming"]},{"key":"dc:creator","label":"Author","values":["Luo, Lijuan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-25T14:24:47Z","2013-05-26T10:00:20Z","2011-05"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"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":["printed circuit board (PCB) routing","escape routing","Boolean satisfiability","graphics processing unit (GPU)","CUDA","breadth-first search","R-tree"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2011 Lijuan Luo"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/24504"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["As the semiconductor industry marches towards 22 nm technology and beyond, circuit design has become unprecedentedly omplicated. This presents many new challenges for EDA (electronic design automation), such as lack of effective tools for analog circuit or high-volume and high-frequency printed circuit board (PCB) design, the contradiction between complex EDA compute workloads and time-to-market pressure, manufacturing variability and power management, to name but a few. In this dissertation, we will propose several new strategies to handle the challenges in the EDA field. Wire routing is an important step in the design of PCBs. Although there are many industrial tools to handle IC routing problems, very few tools can handle the routing on high-density and high-frequency boards effectively. Nowadays, most of the PCB routing is still done by tedious and time-consuming manual work. We provide new strategies to solve an important problem in PCB routing, the escape routing problem. Our first strategy is to use Boolean satisfiability to optimally solve the escape routing problem on one PCB component. Our second strategy is to use a novel boundary routing methodology to finish escape routing from two connected PCB components simultaneously. This router can achieve much better routability than industrial tools with less CPU time. Another challenge seen in the EDA field is the increasing CPU time to handle larger and larger designs. On the other hand, many fundamental algorithms and data structures used in the EDA tools have shown great parallelism, such as the well-known BFS (breadth-first search) algorithm and the R-tree structure. Therefore, we propose strategies to use the cost-effective GPU platform to parallelize and accelerate BFS and R-tree query. These strategies are potentially applicable to many EDA problems.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2011-04-11T21:14:13Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Luo_Lijuan.pdf: 1195140 bytes, checksum: 8d11fc264b1e325052a133dca59bcdb1 (MD5)","Made available in DSpace on 2011-05-25T14:24:47Z (GMT). No. of bitstreams: 2 Luo_Lijuan.pdf: 1195140 bytes, checksum: 8d11fc264b1e325052a133dca59bcdb1 (MD5) license.txt: 4057 bytes, checksum: 7b160e7988108e7ad834a5b6c548a688 (MD5)","Item marked as restricted to the 'Administrator' Group (id=1) by William Ingram (wingram2@illinois.edu) on 2011-05-25T14:30:08Z Item is restricted until 2013-05-25T14:29:35Z","Item reinstated by Sarah Shreeves (sshreeve@illinois.edu) on 2013-05-26T10:00:20Z Item was in collections: University of Illinois Dissertations and Theses (ID: 204) Dissertations and Theses - Electrical and Computer Engineering (ID: 446) No. of bitstreams: 3 Luo_Lijuan.pdf.txt: 154610 bytes, checksum: 5faa004135c62f12ff126f927bf568a9 (MD5) Luo_Lijuan.pdf: 1195140 bytes, checksum: 8d11fc264b1e325052a133dca59bcdb1 (MD5) license.txt: 4057 bytes, checksum: 7b160e7988108e7ad834a5b6c548a688 (MD5)","Item released from any restrictions by Sarah Shreeves (sshreeve@illinois.edu) on 2013-05-26T10:00:20Z"]},{"key":"dc:title","label":"Title","values":["New strategies for electronic design automation problems"]}]}],"canonical_facts":{"dc:contributor":["Wong, Martin D.F.","Hwu, Wen-Mei W.","Patel, Janak H.","Chen, Deming"],"dc:creator":["Luo, Lijuan"],"dc:date":["2011-05-25T14:24:47Z","2013-05-26T10:00:20Z","2011-05"],"dc:description":["As the semiconductor industry marches towards 22 nm technology and beyond, circuit design has become unprecedentedly omplicated. This presents many new challenges for EDA (electronic design automation), such as lack of effective tools for analog circuit or high-volume and high-frequency printed circuit board (PCB) design, the contradiction between complex EDA compute workloads and time-to-market pressure, manufacturing variability and power management, to name but a few. In this dissertation, we will propose several new strategies to handle the challenges in the EDA field. Wire routing is an important step in the design of PCBs. Although there are many industrial tools to handle IC routing problems, very few tools can handle the routing on high-density and high-frequency boards effectively. Nowadays, most of the PCB routing is still done by tedious and time-consuming manual work. We provide new strategies to solve an important problem in PCB routing, the escape routing problem. Our first strategy is to use Boolean satisfiability to optimally solve the escape routing problem on one PCB component. Our second strategy is to use a novel boundary routing methodology to finish escape routing from two connected PCB components simultaneously. This router can achieve much better routability than industrial tools with less CPU time. Another challenge seen in the EDA field is the increasing CPU time to handle larger and larger designs. On the other hand, many fundamental algorithms and data structures used in the EDA tools have shown great parallelism, such as the well-known BFS (breadth-first search) algorithm and the R-tree structure. Therefore, we propose strategies to use the cost-effective GPU platform to parallelize and accelerate BFS and R-tree query. These strategies are potentially applicable to many EDA problems.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2011-04-11T21:14:13Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Luo_Lijuan.pdf: 1195140 bytes, checksum: 8d11fc264b1e325052a133dca59bcdb1 (MD5)","Made available in DSpace on 2011-05-25T14:24:47Z (GMT). No. of bitstreams: 2 Luo_Lijuan.pdf: 1195140 bytes, checksum: 8d11fc264b1e325052a133dca59bcdb1 (MD5) license.txt: 4057 bytes, checksum: 7b160e7988108e7ad834a5b6c548a688 (MD5)","Item marked as restricted to the 'Administrator' Group (id=1) by William Ingram (wingram2@illinois.edu) on 2011-05-25T14:30:08Z Item is restricted until 2013-05-25T14:29:35Z","Item reinstated by Sarah Shreeves (sshreeve@illinois.edu) on 2013-05-26T10:00:20Z Item was in collections: University of Illinois Dissertations and Theses (ID: 204) Dissertations and Theses - Electrical and Computer Engineering (ID: 446) No. of bitstreams: 3 Luo_Lijuan.pdf.txt: 154610 bytes, checksum: 5faa004135c62f12ff126f927bf568a9 (MD5) Luo_Lijuan.pdf: 1195140 bytes, checksum: 8d11fc264b1e325052a133dca59bcdb1 (MD5) license.txt: 4057 bytes, checksum: 7b160e7988108e7ad834a5b6c548a688 (MD5)","Item released from any restrictions by Sarah Shreeves (sshreeve@illinois.edu) on 2013-05-26T10:00:20Z"],"dc:identifier":["http://hdl.handle.net/2142/24504"],"dc:language":["en"],"dc:rights":["Copyright 2011 Lijuan Luo"],"dc:subject":["printed circuit board (PCB) routing","escape routing","Boolean satisfiability","graphics processing unit (GPU)","CUDA","breadth-first search","R-tree"],"dc:title":["New strategies for electronic design automation problems"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:23Z"}