Parallelization of Pattern Routing Algorithms in Chip Design
Date
2020-05
Authors
Kothari, Aarti Pravinkumar
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Keywords
Pattern routing, Routing, Parallelized global router, Global routing, Routing on GPU
Citation
Kothari, A. P. (2020). <i>Parallelization of pattern routing algorithms in chip design</i> (Unpublished thesis). Texas State University, San Marcos, Texas.