Browse Prior Art Database

Global Router with Simultaneous Length and Density Minimization

IP.com Disclosure Number: IPCOM000111446D
Original Publication Date: 1994-Feb-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 2 page(s) / 80K

Publishing Venue

IBM

Related People

Chiang, C: AUTHOR [+2]

Abstract

A program is disclosed that aims to simultaneously minimize wire lengths and density through the regions in global routing. This task is accomplished by introducing the concept of weighted Steiner trees: consider a set of weighted regions in an arbitrary-style layout, where weight of a region is proportional to its density and its area. A weighted Steiner tree is a Steiner tree with weighted lengths, that is, an edge with length scriptl in a region with weight .op omega has weighted length scriptl bullet .op omega .

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Global Router with Simultaneous Length and Density Minimization

      A program is disclosed that aims to simultaneously minimize
wire lengths and density through the regions in global routing.  This
task is accomplished by introducing the concept of weighted Steiner
trees: consider a set of weighted regions in an arbitrary-style
layout, where weight of a region is proportional to its density and
its area.  A weighted Steiner tree is a Steiner tree with weighted
lengths, that is, an edge with length  scriptl in a region with
weight  .op omega  has weighted length
scriptl bullet .op omega .

      The strategy is to route the nets one by one.  First, an
ordering of nets to be processed is decided.  Then for each net we
obtain a global routing with small weight.  The first step is to
assign a distinct number, called the  order   number , to each net.

In general, the order number of a net is a function (e.g., the sum)
of
 priority,   weight,  and  multiplicity  numbers, where multiplicity
is the number of terminals of the net.

      The second step is a Steiner tree problem.  Given a set of
weighted regions, it aims to obtain a Steiner tree, called weighted
Steiner tree, whose total weight is minimized over all such trees.  A
fast algorithm is proposed for obtaining an "efficient" weighted
Steiner tree.  In an instance ( eta ,C) of global routing, let
 N sub i be the  current  net to be processed.  Consider the pair
(R,W sub i), where  R  is the set of regions and  W sub i is the
weight of regions just before processing  N sub i .  The weight of a
region
 R sub a increases as more nets go through it.  A weighted Steiner
tree of  (R, W sub i) dictates a global routing that simultaneously
minimizes traffic in the regions and length of the current net.  Each
net requires  O(n sup 2 + eloge) processing time, where  n is the
number of terminals of  N sub i and  e  is...