A Global Router on GPU Architecture

Developed by Yiding Han, Dr. Koushik Chakraborty, and Dr. Sanghamitra Roy of Utah State University’s Electrical and Computer Engineering Department


Technical Summary

In modern VLSI design flow, global router is often utilized to provide fast and accurate congestion analysis for upstream processes to improve the design routability. Global routing parallelization is a good candidate to speedup its runtime performance while delivering very competitive solution quality. The aggressive scaling of modern process nodes is accompanied by an increase of complexity in the VLSI designs, which leads to new challenges in circuit routability. To address these challenges, tremendous efforts have been dedicated to the maturation of the routing flow. The global routing problem has been studied in depth in recent years with some adequate solutions such as: A* search based maze routing, rip-up and re-route (RRR), and net-level concurrency (NLC).


‘A Global Router on GPU Architecture’ is a novel concurrency model to mitigate the lack of exploitable concurrency. This model exploits a fine grain concurrency and shows a significant speedup using a multi agent maze routing engine on GPU architecture. The fine grain concurrency model exploits parallelism on the Steiner edge level which mitigates the issue of limited exploitable concurrency being false data dependency in the existing parallel model. The routing engine on GPU architecture allows multi agent global routing based on an A* search multi-source, multi-sink maze routing algorithm specialized for global routing optimizations.


Competitive Advantages

This model is an effective way to parallelize global routing on GPU architecture and mitigates the lack of exploitable concurrency in emerging global routing problems. The experimental results confirm that this model produces deterministic solutions and is capable of achieving significant speedup through parallelization on GPU architecture. The router outperforms some of the most successful global routers from open literature. On Geforce GTX 470 GPU we achieve 2.51X to 3.93X speedup over NCTUgr2 as well as 5.44X to 10.20X speedup over BFG-R 2.0.


Commercial Applications

•  Multicore systems with a GPU

•  Prototyping Software



•  Yiding Han; Chakraborty, K.; Roy, S., "A global router on GPU architecture," in Computer Design (ICCD), 2013 IEEE 31st International Conference on, vol., no., pp.78-84, 6-9 Oct. 2013  doi: 10.1109/ICCD.2013.6657028


Patent Information:
Computer Science
For Information, Contact:
Christian Iverson
Utah State University
Koushik Chakraborty Sanghamitra Roy Yiding Han