Method and apparatus of relative datapath cell placement with structure bonding

• US 6,792,585 B1
• Filed: 01/26/2000
• Issued: 09/14/2004
• Est. Priority Date: 01/26/2000
• Status: Expired due to Fees

• Current Assignee: Arcadia Design Systems Incorporated
• Original Assignee: Arcadia Design Systems Incorporated
• Inventors: Wang, Yung-Hung, Chen, Duan-Ping, Ku, Tsu-Wei, Woodward, Scot A., Chia, Wei-Kong
• Primary Examiner(s): THOMPSON, ANNETTE M
• Application Number:
  US09/491,389
• Time in Patent Office: 1,693 Days
• Field of Search: 716/10, 716/8, 716/13
• US Class Current: 716/122
• CPC Class Codes: G06F 30/30 Circuit design
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

The invention discloses a relative structure placement of datapath of cell instances in a column structure, a row structure, or an array structure. To encourage placement of a desirable structure, pseudo cells, pseudo pins, and pseudo nets are selected to be placed at certain locations with respect to real cell instances. The end result produces a cluster of real cell instances that form a desirable structure while minimizing the length of nets. The invention further discloses a non-uniform partitioning of a density map for calculating a force update vector. The partitioning is taken over a region A to compute Riemann sum approximations of a function F over the region A. A force update vector is calculated for a given cell instance within the region A where neighboring cell instances have an exponentially larger grid size as cell instances extend further away from the given cell instance.

Claims

1. A datapath structure, comprising:

one or more cell instances, each cell instance having a pin;

one or more pseudo cell instances, each pseudo cell instance having a pseudo pin, each pseudo cell instance in the one or more pseudo cell instances being placed at a location relative to the one or more cell instances in encouraging a predetermined structure; and

one or more pseudo nets, a first pseudo net connecting between a pin of a first cell instance in the one or more cell instances and a pin in a first pseudo cell instance in the one or more pseudo cell instances, wherein the first pseudo cell instance being placed at a location relative to the first real cell instance produces a zero or greater than zero length in the first pseudo net.

2. The structure of claim 1 further comprising a first relative position between the first cell instance and the first pseudo cell instance.

3. The structure of claim 1 wherein the predetermined structure comprises a column structure, a row structure, or a square structure.

4. A computerized method for encouraging a structure bonding, comprising the steps of:

placing a first pseudo cell instance at a location relative to a first cell instance in a plurality of cell instances for encouraging a predetermined structure bonding in the plurality of cell instances;

connecting a pseudo net between the cell instance and the pseudo cell instance; and

providing a first offset between the pseudo cell instance and the first cell instance.

5. The method of claim 4 further comprising the step of minimizing a wire length in the pseudo net from the placement of the first pseudo cell instance relative to the first cell instance.

6. The method of claim 4 wherein the predetermined structure comprises a column structure, a row structure, or a square.

7. A computerized method for encouraging a structure bonding, comprising:

placing a first pseudo cell instance at a location relative to a first cell instance in a plurality of cell instances for encouraging a predetermined structure bonding in the plurality of cell instances;

connecting a pseudo net between the cell instance and the pseudo cell instance;

providing a first offset between the pseudo cell instance and the first cell instance; and

determining a second offset between the pseudo cell instance and a second cell instance in the plurality of cell instances.

8. A computerized method for encouraging a structure bonding, comprising:

placing a first pseudo cell instance at a location relative to a first cell instance in a plurality of cell instances for encouraging a predetermined structure bonding in the plurality of cell instances; and

connecting a pseudo net between the cell instance and the pseudo cell instance;

wherein the placing step comprises the step of placement without introducing extra dead placement spaces.