Parallelization of Pattern Routing Algorithms in Chip Design
dc.contributor.advisor | Burtscher, Martin | |
dc.contributor.author | Kothari, Aarti Pravinkumar | |
dc.contributor.committeeMember | Qasem, Apan | |
dc.contributor.committeeMember | Guirguis, Mina | |
dc.date.accessioned | 2020-05-14T18:59:07Z | |
dc.date.available | 2020-05-14T18:59:07Z | |
dc.date.issued | 2020-05 | |
dc.description.abstract | In VLSI design, minimizing wirelength is critical to maximize chip performance and minimize power consumption. A router determines the paths taken by the wires in a chip while satisfying design manufacturing rules. For modern circuit designs, a chip may contain billions of devices connected by millions of such nets. Due to the complex constraints and dependencies that need to be considered during routing, serial routing algorithms are ruling the industry today. In this thesis, I developed parallel routing algorithms for execution on multicore CPUs and GPUs. I created two routing algorithms such that they can simultaneously route pin pairs and update edge capacities while keeping wirelengths short and congestion low. Compared to a preexisting serial router routing netlists with between 0.2 and 2.6 million nets, my serial implementation is over 6x faster and requires 0.38% less wirelength. My deterministic parallel implementation produces the same result and is 2.5x faster than my serial code. | |
dc.description.department | Computer Science | |
dc.format | Text | |
dc.format.extent | 50 pages | |
dc.format.medium | 1 file (.pdf) | |
dc.identifier.citation | Kothari, A. P. (2020). Parallelization of pattern routing algorithms in chip design (Unpublished thesis). Texas State University, San Marcos, Texas. | |
dc.identifier.uri | https://hdl.handle.net/10877/9910 | |
dc.language.iso | en | |
dc.subject | pattern routing | |
dc.subject | routing | |
dc.subject | parallelized global router | |
dc.subject | global routing | |
dc.subject | routing on GPU | |
dc.title | Parallelization of Pattern Routing Algorithms in Chip Design | |
dc.type | Thesis | |
thesis.degree.department | Computer Science | |
thesis.degree.discipline | Computer Science | |
thesis.degree.grantor | Texas State University | |
thesis.degree.level | Masters | |
thesis.degree.name | Master of Science |