Placement and global routing of VLSI macro-Cell layouts using genetic algorithms

Abstract

The topic of this Ph.D. thesis is the application of evolution-based algorithms (EAs) to various highly constrained combinatorial optimization problems arising in layout synthesis of VLSI integrated circuits. The purpose is to investigate which performance can be obtained by EAs compared to traditional methods, to identify strengths and weaknesses of EAs within this application domain and to identify possible EA design principles yielding the best performance.

In particular, the study focuses on genetic algorithms (GAs) for placement and global routing of macro-cell layouts. GAs for the these problems are developed, and their performance compared to that of existing state-of-the-art tools, in terms of absolute solution quality and absolute runtime. The main results are new GAs for both macro-cell placement and global routing, which are comparable to or better than the current state-of-the-art approaches. Especially, a GA for the Steiner problem in a graph is presented, which to our knowledge is the current best heuristic for this problem, in terms of solution quality as well as runtime.

Finally, various design principles significantly affecting algorithm performance are identified, of which the constraint handling method is of utmost importance. Within the application domain considered, enforcing constraint satisfaction at all times is found to consistently outperform methods based on penalty terms.