Title :
Application of an EACS algorithm to obstacle detour routing in VLSI physical design
Author :
Li, Jing ; Liu, He-zhou ; Yang, Bo ; Yu, Jue-bang ; Xu, Ning ; Li, Chun-hui
Author_Institution :
Sch. of Electron. Eng., Univ. of Electron. Sci. & Technol. of China, Chengdu, China
Abstract :
This paper presents a new gridless routing algorithm for solving obstacle detoured routing problem in physical design of VLSI circuits. Firstly, this algorithm maps a given routing instance to the corresponding graph model (path graph), which is a kind of asymmetric grid graph suitable for BBL (building block layout) mode layout. After that, we complete the main routing process based on an EACS (evolutionary ant colony system) algorithm in which the crossover operation in genetic algorithm (GA) is introduced into the ACS (ant colony system). Comparative simulation experiments with respect to the ACS demonstrate that the evolutionary parallel computation algorithm EACS is more effective than the original ACS algorithm in obstacle detoured routing of VLSI circuit physic al design.
Keywords :
VLSI; circuit CAD; genetic algorithms; graph theory; network routing; parallel algorithms; GA; VLSI physical design; evolutionary ant colony system algorithm; evolutionary parallel computation; genetic algorithm; graph model; gridless routing algorithm; obstacle detour routing; path graph; very large scale integrated circuit; Algorithm design and analysis; Ant colony optimization; Artificial neural networks; Circuits; Computational modeling; Computer integrated manufacturing; Genetic algorithms; Physics computing; Routing; Very large scale integration;
Conference_Titel :
Machine Learning and Cybernetics, 2003 International Conference on
Print_ISBN :
0-7803-8131-9
DOI :
10.1109/ICMLC.2003.1259742
