Title :
Graph-based approach to evaluate net routability of a floorplan
Author :
Waropas, N. ; Rajendar, Koltur ; Chrzanowska-Jeske, Malgorzata
Author_Institution :
Dept. of Electr. & Comput. Eng., Portland State Univ., OR, USA
Abstract :
This paper presents a fast graph-based algorithm to evaluate routability of a floorplan. A simplified global routing problem is formulated as a constrained maximum independent set problem, and we use a limited number of routing options within a given number of routing layers. To test our approach, we use floorplans generated by the ELF-SP floorplanner that uses an evolutionary algorithm in conjunction with Lagrangian Relaxation. Experimental results show the effectiveness of our method.
Keywords :
circuit layout CAD; evolutionary computation; graph theory; network routing; set theory; ELF-SP floorplanner; Lagrangian relaxation; constrained maximum independent set problem; evolutionary algorithm; floorplan routability; global routing; graph algorithm; Cost function; Evolutionary computation; Genetic algorithms; Lagrangian functions; Performance evaluation; Routing; Simulated annealing; Testing; Timing; Wire;
Conference_Titel :
Circuits and Systems, 2003. ISCAS '03. Proceedings of the 2003 International Symposium on
Print_ISBN :
0-7803-7761-3
DOI :
10.1109/ISCAS.2003.1206318
