high performance computing on graphics processing units: hgpu.org

This dissertation presents research focusing on reshaping the design paradigm of electronic design automation (EDA) applications to embrace the computational throughput of a massively parallel computing architecture. The EDA industry has gone through major evolution in algorithm designs over the past several decades, delivering improved and more sophisticated design tools. Today, these tools provide a critical platform for modern integrated circuit (IC) designs composed of multi-billion transistors. However, most of these algorithms, although showcasing tremendous improvements in their capabilities, are based on a sequential Von Neumann machine, with limited or no ability to exploit concurrency. While such limitation did not pose any significant end effect in the past, the advent of commodity multicores during the beginning of this decade created a need to embrace concurrency in many fields, including EDA algorithms. This need is now fast gaining urgency with the recent trends in the emergence of the general purpose computation on graphics processor units (GPU). Through algorithmic overhaul, and novel solution space exploration strategies, this research has shown a concrete path in which inherently sequential problems can benefit from the massively parallel hardware, and gain higher computation throughput. Broadly, two important EDA topics are discussed in this dissertation: (1) A floorplanner using a GPU-based simulated annealing algorithm, and (2) a global router framework using GPU architecture and a fast congestion analysis framework. Both topics aim to use GPU as a testbed for high throughput computation. Optimization strategies are studied for the GPU implementations. The GPU-based floorplanning algorithm is able to render 4-166X speedup, while achieving similar or improved solutions compared with the sequential algorithm. The GPU-based global routing algorithm is shown to achieve significant speedup against existing state-of-the-art global routers, while delivering competitive solution quality. The proposed methodology of a design paradigm shift for sequential EDA algorithms has a profound impact on the efficiency and design quality of future IC design flow.