Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2000-01-26
2004-09-14
Thompson, A. M. (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
06792585
ABSTRACT:
BACKGROUND INFORMATION
1. Field of the Invention
The invention relates to computer-aided design (CAD) of integrated circuits, and particularly to placement of cells in datapath design.
2. Description of Related Art
Two general categories of placement methods are used, the first one random placement and the second one is structural placement. For random placement, cells are connected by list of nets. The objective of placement is to minimize a cost function that relates to total sum of net length with fixed constraints of placement area, routability, and timing. Several conventional placement algorithms relating to this type of placement method have been disclosed.
In bonding cell instances, a conventional solution places wires at locations between cell instances which produce shortest net lengths. Such approach produces an undesirable random or irregular structure arisen from the placement of uncorrelated cell instances. Another conventional solution places cell instances in a rigid structure by matching pin locations between cell instances. This technique is prohibitively restrictive since adjacent cell instances must be aligned with matching pin locations and hence introduces many dead placement spaces.
In a density map partitioning, conventional solution adopts a uniform grid partitioning. This approach requires substantial computation time in calculating the density forces of a given point on a partition map. Because each square or rectangle in the grid is uniform in size, the computation time is greater if the grid size of a cell instance is smaller which produces a high number of cells.
Accordingly, it is desirable to place cell instances in an optimized structure bonding. It is further desirable to have a density map partition which is non-uniform in computing a force update vector in reducing the extensive computational complexity time.
SUMMARY OF THE INVENTION
The invention discloses a relative placement of datapath elements by keeping the relativity of cell instances in a datapath group without rigid alignments between cells. In one embodiment, 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 therefore achieves objectives of minimizing the sum of net lengths while encouraging cells instances to form in a desirable structure, such as a column structure, a row structure, or a square structure.
In a further aspect of the invention, a non-uniform partitioning of a density map for calculating a force update vector is disclosed. 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.
Advantageously, the structure bonding reduces the dimension of a chip by minimizing dead placement spaces in a datapath structure for efficient utilization. Moreover, the structure bonding minimizes data skew of datapath. The structure bonding of cell instances with pseudo elements also encourages low timing delays. Additionally, the exponential portioning advantageously reduces significantly on the computational time in the determination of a force update vector on a given cell instances arisen from attractive and repelling forces.
REFERENCES:
patent: 4577276 (1986-03-01), Dunlop et al.
patent: 5218551 (1993-06-01), Agrawal et al.
patent: 5506788 (1996-04-01), Cheng et al.
patent: 5519627 (1996-05-01), Mahmood et al.
patent: 5619419 (1997-04-01), D'Haeseleer et al.
patent: 5627999 (1997-05-01), Cheng et al.
patent: 5666290 (1997-09-01), Li et al.
patent: 5726902 (1998-03-01), Mahmood et al.
patent: 5815406 (1998-09-01), Golla et al.
patent: 5844811 (1998-12-01), Scepanovic et al.
patent: 5930499 (1999-07-01), Chen et al.
patent: 6148433 (2000-11-01), Chowdhary et al.
patent: 6189130 (2001-02-01), Gofman et al.
patent: 6594808 (2003-07-01), Kale et al.
patent: 6598215 (2003-07-01), Das et al.
patent: 2002/0087939 (2002-07-01), Greidinger et al.
M.C. Yildiz et al., Global Objectives for Standard Cell Placement, Proceedings of the 2001 Conference on Great lakes Symposium on VLSI, pp. 68-72, Mar. 2001.*
Tsu-Wei Ku et al., Minimal Overhead Modification of Iterative Logic Arrays for C-Testability, , IEEE Test Conference, pp. 964-969, Sep. 1990.*
H. Shiraishi et al., Efficient Placement and Routing Techniques for Master Slice LSI, Proceedings of the 14thDesign Automation Conference, pp. 458-464, Jun. 1977.*
C-I Eric Cheng, RISA: Accurate and Efficient Placement Routability Modeling, IEEE/ACM International Conference on Computer-Aided Design, pp. 690-695, Nov. 1994.*
F. Mo et al., A Force-Directed Macro-Cell Placer, IEEE/ACM Conference on Computer Aided Design, pp. 177-180, Nov. 2000.*
G. J. Wipfler et al., A Combined Force and Cut Algorithm for Hierarchical VLSI Layout, Proceedings of 19thDesign Automation Conference, pp. 671-677, Jun. 1982.*
H. Chen, Pseudo Pin Assignment for Single-Layer Over-the-Cell Routing, Proceedings of 1990 Conference on Computer Design: VLSI in Computers and Processors, pp. 343-346, Sep. 1990.*
C. J. Alpert et al., Faster Minimization of Linear Wirelength for Global Placement, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pp. 3-13, Jan. 1998.*
Eisenmann, H., et al., Geheric Global Placement and Floorplanning, pp. 269-274, vol. 17.1, ACM, San Francisco, 1998.
Shahookar, K., et al, VLSI Cell Placement Techniques, ACM computing Surveys, Jun. 1991, pp. 143-220, vol. 23, ACM.
Fadavi-Ardekani, J., MXN Booth Encoded Multiplier Generator Using Optimized Wallace Trees, IEEE Transactions on very Large Scale Integration (VLSI) Systems, Jun. 1993, pp. 120-123, vol. 1, No. 2, IEEE.
Kim, J., et al., A Timing-driven Data Path Layout Synthesis with Integer Programming, Computer-Aided Design, 1995, pp. 716-719, 1063-6757105, IEEE.
Chen Duan-Ping
Chia Wei-Kong
Ku Tsu-Wei
Wang Yung-Hung
Woodward Scot A.
Arcadia Design Systems, Inc.
Fernandez Dennis S.
Fernandez & Associates LLP
Thompson A. M.
LandOfFree
Method and apparatus of relative datapath cell placement... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus of relative datapath cell placement..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus of relative datapath cell placement... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3248268