Parallelization of Pattern Routing Algorithms in Chip Design
MetadataShow full metadata
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.