Browse Prior Art Database

Congestion Driven Placement System Using Mid-Cut Partitioning

IP.com Disclosure Number: IPCOM000015325D
Original Publication Date: 2002-Feb-03
Included in the Prior Art Database: 2003-Jun-20
Document File: 3 page(s) / 142K

Publishing Venue

IBM

Abstract

This invention describes a novel wiring congestion metric and proposes placement methods that use this metric in top-down physical design of v ery l arge s cale i ntegrated (VLSI) circuits so that routability is improved. Due to lack of a clearly defined congestion measure, previous approaches have addressed routability indirectly by focussing on minimizing cut size (in a partitioning based placement algorithm) and/or total wire length. Using proposed metric a new congestion driven the placement problem is formulated and efficient solutions for same are presented.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 38% of the total text.

Page 1 of 3

Congestion Driven Placement System Using Mid-Cut Partitioning

  This invention describes a novel wiring congestion metric and proposes placement methods that use this metric in top-down physical design of very large scale integrated (VLSI) circuits so that routability is improved. Due to lack of a clearly defined congestion measure, previous approaches have addressed routability indirectly by focussing on minimizing cut size (in a partitioning based placement algorithm) and/or total wire length. Using proposed metric a new congestion driven the placement problem is formulated and efficient solutions for same are presented.

Introduction:Many researchers have tried to loosely define a measure of congestion based on average wire densities and have shown that such a measure is directly related to wire length itself because the chip area is usually fixed. This concept of global congestion however is not meaningful as local hot spots will never be taken into account by such a measure. For example, a very high congestion in a small area and a low congestion everywhere else would still lead to a low average congestion. In this study we propose a new measure of congestion and propose partitioning based placement algorithms that can alleviate congestion.

Wire Congestion: This disclosure overcomes the problem and
illustrates the application of a new measure of routability based
on maximum expected wire length per unit area anywhere on the

chip in placement algorithms. Consider a VLSI chip design D

consisting of a set P ={p1, p2, ...pn} of placeable objects. The goal

of placement is to physically locate n placeable objects in such

a way that D is routable and certain constraints such as delay,

noise, etc. are not violated. Let the region RD in which design
D is to be placed be embedded in a Cartesian plane such that its
edges are parallel to X-axis and Y-axis, respectively, of the

plane. Let WD be the length of wiring that lies within the

region RD of area AD . For each sub region Rd of RD with area Ad

, let Wd be the length of the wiring that lies within Rd . For any

such region Rd a portion of the wire length Wd is contributed by

nets with one or more terminals in Rd (and the rest possibly

outside), and the rest by nets with no terminals in Rd . Let the
coordinates of the lower left hand and upper right hand corners

of Rd be (xld, yld) and (xud, yud) , respectively. Congestion for the

AW region Rd is defined as Cd =d d . Let RI ={Rd1, Rd2, ...Rdm} be regions of interest defined within RD where congestion is to be minimized. Figure 1 shows a chip with regions
Ra = a , Ra1 = a1 , and Ra2 = a2. Congestion to be minimized CRI is to be CRI = max rxcRI Crx . Congestion Driven Placement Problem (CDPP): is one of assigning a space in RD for each of placeable objects pi c P such that no two placeable objects occupy overlapping spaces and such that for any given set of regions RI ={Rd1, Rd2,..., Rdm} , congestion CRI is minimized. Region

1

Page 2 of 3

RD...