Application of genetic algorithm techniques in VLSI physical design - Thida Aye; Yulu, Qi; Batanov, Dentcho N.; Murai, Shunji; The Government of Finland (Bangkok : Asian Institute of Technology, 1995)
Channel Routing Problem (CRP) is an NP-hard optimization problem in detailed routing phase of the VLSI physical design. Genetic Algorithms are a new class of heuristic search and optimization strategies which have been applied successfully to find good solutions to several optimization problems. We have designed and implemented a genetic algorithm-based system to solve the CRP. Several well-known benchmark CRPs were solved using our GA-based router. It was shown that our system can produce solutions to the benchmark CRPs with the minimum number of used tracks as obtained by theory and other traditional non-GA routers. The fitness function of our system considers both the number of used tracks and the total length of vertical segments as the optimization objectives. By carefully adjusting the cost factors for these two objectives, solutions were obtained with the optimal values of total vertical length. We have also implemented two other non-GA channel routers based on some straightforward heuristics. By comparing the solutions obtained by non-GA routers with those of GA-based router, results from the GA-based system were verified.
A thesis submitted in partial fulfillment of the requirements for the degree of Master of Engineering
Thesis (M.Eng.) - Asian Institute of Technology, 1995
Keywords: Integrated circuits -- Very large scale integration