The crossing distribution problem [IC layout]

Author

Marek-Sadowska, Malgorzata ; Sarrafzadeh, Majid

Author_Institution

Dept. of Electr. & Comput. Eng., California Univ., Santa Barbara, CA, USA

Volume

14

Issue

4

fYear

1995

fDate

4/1/1995 12:00:00 AM

Firstpage

423

Lastpage

433

Abstract

In this paper we study the problem of “properly” distributing the set of crossings (i.e., intersection of nets), of a given global routing, among the regions. Each region is assigned a quota, being the maximum number of crossings allowed in that region, which depends on its area and its complexity (e.g., the number of wets going through it and the number of terminals it contains). The crossing distribution problem (CDP) is to find a net ordering at each boundary as to minimize the total number of crossings and to satisfy the quotas. We propose an O(mn²+mξ^3/2) time algorithm for CDP, where m is the number of modules, n is the number of nets, and ξ is the number of crossings

Keywords

circuit layout CAD; graph theory; integrated circuit layout; multiterminal networks; network routing; network topology; IC layout; crossing distribution problem; global routing; net ordering; nets intersection; Analog circuits; Integrated circuit interconnections; Integrated circuit layout; Integrated circuit measurements; Routing; Shape;

fLanguage

English

Journal_Title

Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on

Publisher

ieee

ISSN

0278-0070

Type

jour

DOI

10.1109/43.372368

Filename

372368