GPU Floorplanning Algorithm for Circuit Design

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

Technical Summary

The Electronic Design Automation (EDA) industry uses sophisticated design tools and algorithms that provide critical platforms for modern integrated circuit (IC) designs composed of multi-billion transistors. Unfortunately, most of these algorithms are sequential, with limited or no ability to exploit concurrency. The advent of commodity multicores provides an opportunity to embrace concurrency, i.e. calculations processed at the same time, in many fields, including EDA algorithms. This opportunity is now fast gaining urgency with the evolution of Graphics Processor Units (GPUs).

Modern GPUs have concurrent design capabilities that demonstrate tremendous computation bandwidth and allow non-graphics applications to harness their computing prowess. “Floorplanning Using Graphical Processor Units” is a patented floorplanning algorithm designed to exploit the GPUs considerable capabilities in EDA IC design. Figure 1 shows a typical, sequential algorithm flow, while Figure 2 shows the improved method flow using concurrency.


Competitive Advantages

GPU Floorplanning performs computations more quickly and efficiently by using both the CPU and the GPU. For example, compared to the sequential algorithm, GPU Floorplanning achieves a speed increase of 9.4-14.6x and 10-17x on G92 and Tesla C1060 machines, while delivering comparable or better solution quality.


Commercial Applications

•  Very Large Scale Integration (VLSI) Circuit Design

•  Any prototyping or CAD related software


Additional Information



•  U.S. Patent 8,549,456 – System and Method for Circuit Design Floorplanning

•  Yiding Han; Chakraborty, K.; Roy, S.; Kuntamukkala, V., "A GPU Algorithm for IC Floorplanning: Specification, Analysis and Optimization," in VLSI Design (VLSI Design), 2011 24th International Conference on , vol., no., pp.159-164, 2-7 Jan. 2011


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