| Title | The crossing distribution problem [IC layout] |
| Publication Type | Journal Article |
| Year of Publication | 1995 |
| Authors | Marek-Sadowska, M, Sarrafzadeh, M |
| Journal | Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on |
| Volume | 14 |
| Pagination | 423 -433 |
| Date Published | apr |
| ISSN | 0278-0070 |
| Keywords | circuit layout CAD, crossing distribution problem, global routing, graph theory, IC layout, integrated circuit layout, multiterminal networks, net ordering, nets intersection, network routing, network topology |
| Abstract | In this paper we study the problem of ldquo;properly rdquo; 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(mn2+m xi;3/2) time algorithm for CDP, where m is the number of modules, n is the number of nets, and xi; is the number of crossings |
| DOI | 10.1109/43.372368 |
