LEGAL: an algorithm for simultaneous net routing

Author

De Oliveira Johann, Marcelo ; Da Luz Reis, Ricardo Augusto

Author_Institution

Dept. de Inf., Pontificia Univ. Catolica do Rio Grande do Sul, Uruguaiana, Brazil

fYear

2001

fDate

2001

Firstpage

180

Lastpage

185

Abstract

Presents LEGAL, a new routing algorithm that may be especially interesting for area routing problems. It is a generalization of two of the most important channel routing techniques, Left-Edge and Greedy algorithms. Area routing is an important problem today due to the fact that the availability of several metal layers allows all the routing to be done over the cells. Therefore, the circuit is not partitioned into well defined blocks and routing regions anymore. We seek the use of an algorithm that processes all nets simultaneously as an alternative to standard "net by net" routing or independent global cells routing. LEGAL is demonstrated to perform efficiently for small problems in three different implementations, generating complete routing solutions in orders of magnitude less time as compared to maze routers

Keywords

VLSI; cellular arrays; circuit layout CAD; integrated circuit layout; logic CAD; logic arrays; network routing; CAD tools; LEGAL; VLSI; area routing problems; channel routing techniques; layout models; metal layers; routing solutions; simultaneous net routing; Capacitance; Cost function; Law; Legal factors; Pins; Radio control; Resource management; Routing; Search methods; Target tracking;

fLanguage

English

Publisher

ieee

Conference_Titel

Integrated Circuits and Systems Design, 2001, 14th Symposium on.

Conference_Location

Pirenopolis

Print_ISBN

0-7695-1333-6

Type

conf

DOI

10.1109/SBCCI.2001.953024

Filename

953024