Path search on rectangular floorplan

Author

Ying, C.S. ; Wong, J.S.L. ; Hong, X.L. ; Wang, E.Q.

Author_Institution

Dept. of Comput. Sci., Tsinghua Univ., Beijing, China

fYear

1990

fDate

12-15 Mar 1990

Firstpage

464

Lastpage

468

Abstract

Wiring among rectangular blocks is an important component in hierarchical layout. This paper presents algorithms for path search on rectangular floorplan. A fast Steiner tree algorithm of linear complexity is proposed based on a new heuristic of converging search. Taking into account the positional distribution of terminals on the floorplan, it finds the subconnections for each terminal simultaneously and in an order independent manner this often yields global optimum connection of terminals. Experimental results show that the new algorithm out-performs other popular sequential methods for the problem at hand in most cases

Keywords

circuit layout CAD; computational complexity; search problems; trees (mathematics); Steiner tree algorithm; converging search; global optimum connection; hierarchical layout; linear complexity; path search; positional distribution; rectangular blocks; rectangular floorplan; sequential methods; subconnections; Circuits; Design methodology; Electrons; Heuristic algorithms; Partitioning algorithms; Routing; Shortest path problem; Very large scale integration; Wires; Wiring;

fLanguage

English

Publisher

ieee

Conference_Titel

Design Automation Conference, 1990., EDAC. Proceedings of the European

Conference_Location

Glasgow

Print_ISBN

0-8186-2024-2

Type

conf

DOI

10.1109/EDAC.1990.136692

Filename

136692