Patent US5838583A successfully refreshed from Google Patents.
US5838583A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Optimized placement and routing of datapaths
Assignee: Cadence Design Systems Inc
•
Filing: 1996-04-12
•
Granted: 1998-11-17
•
Expires: 2016-04-12
Abstract
Abstract A computer system, method and software product enables automatic placement and routing of datapath functions using a design methodology that preserves hiearchical and structural regularity in top down designs for datapaths. The system includes a datapath floorplanner, a datapath placer, and routing space estimator. The datapath floorplanner allows the designer to establish and maintain during floorplannning operations datapath regions that include a number of datapath functions each. The datapath floorplanner creates the datapath regions from a netlist specifying logic cell instances and connectivity information, and from a plurality of tile files. A tile file is a structured description of a datapath function, describing the relative vertical and horizontal placement of all logic cell instances within the datapath function. There is one tile file for each unique datapath function. The datapath function instances then are associated with a particular tile file by the tile file list file. The datapath floorplanner uses the tile files to integrate the placement information with the specific function instances, and further allows the specification of clusters, function interleaving, and net side constraints per region. A datapath placer places the datapath functions in each region using the relative placement information and constraints. The routing space estimator estimates the space needed for routing a placed region. All of this information is interactively provided to the circuit designer so as to allow almost real time modification of datapath placement.
Inventors
- 👤 Ravi Varadarajan
- 👤 Robert Thompson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 10:13
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 36
Claim 1
Independent Claim
168 words
In a computer aided integrated circuit design system for designing integrated circuits including a plurality of datapath regions, each datapath region including at least one datapath function, each datapath function including at least one logic cell instance, a computer memory readable by a processor in the system for determining a placement of cell instances in a datapath function from a netlist of logic cell instances for the datapath function, comprising: a first structured description of the unique relative vertical or horizontal placement of logic cell instances in a datapath function, having a plurality of instance descriptions, each instance description including: i) an instance identifier specifying a logic cell instance; ii) a bit identifier specifying a bit position in the datapath function relative to a first bit position in the datapath function; and, iii) an order identifier specifying a serial position of the logic cell instance within the specified bit position, and relative to a first serial position of other logic cell instances also assigned to the bit position.
Claim 2
Dependent Claim
168 words
In a computer aided integrated circuit design system for designing integrated circuits including a plurality of datapath regions, each datapath region including at least one datapath function, each datapath function including at least one logic cell instance, a computer memory readable by a processor in the system for determining a placement of cell instances in a datapath function from a netlist of logic cell instances for the datapath function, comprising: a first structured description of the unique relative vertical or horizontal placement of logic cell instances in a datapath function, having a plurality of instance descriptions, each instance description including: i) an instance identifier specifying a logic cell instance; ii) a bit identifier specifying a bit position in the datapath function relative to a first bit position in the datapath function; and, iii) an order identifier specifying a serial position of the logic cell instance within the specified bit position, and relative to a first serial position of other logic cell instances also assigned to the bit position.
Claim 3
Dependent Claim
50 words
The computer memory of claim 1, wherein each order identifier further comprises: iii.1) a column identifier specifying a column within the datapath function in which the logic cell instance is located; and, iii.2) a column-specific order identifier specifying a serial position of the logic cell instance within the specified column.
Claim 4
Dependent Claim
41 words
The computer memory of claim 1, further comprising: a second structured description associated with a selected datapath region, and including for the selected datapath region an identification of a first structured description for each unique datapath function within the datapath region.
Claim 5
Dependent Claim
117 words
A computer implemented method of placing a plurality of datapath functions in a datapath region, the method comprising: receiving a netlist of cell instances for a plurality of datapath functions in the datapath region; receiving for each unique datapath function in the datapath region a data file describing for the datapath function a unique relative horizontal and vertical placement of each cell instance in the datapath function; for each datapath function, associating the datapath function with one of the data files to define the relative placement of each cell instance in the datapath function; and, determining the physical placement of all datapath functions in the datapath region according to the relative placement information associated with datapath function.
Claim 6
Dependent Claim
117 words
A computer implemented method of placing a plurality of datapath functions in a datapath region, the method comprising: receiving a netlist of cell instances for a plurality of datapath functions in the datapath region; receiving for each unique datapath function in the datapath region a data file describing for the datapath function a unique relative horizontal and vertical placement of each cell instance in the datapath function; for each datapath function, associating the datapath function with one of the data files to define the relative placement of each cell instance in the datapath function; and, determining the physical placement of all datapath functions in the datapath region according to the relative placement information associated with datapath function.
Claim 7
Dependent Claim
56 words
The computer implemented method of claim 4, wherein determining the physical placement of all datapath functions comprises: determining at least one linear order of the datapath functions; determining for each linear order a placement cost determined by a weighted combination of cost functions; and, selecting the linear order of datapath functions that minimizes the placement cost.
Claim 8
Dependent Claim
35 words
The method of claim 5, further comprising: determining for each datapath function in the datapath region a range of suitable bit offsets from an origin of the datapath region for vertically placing the datapath function.
Claim 9
Dependent Claim
76 words
The method of claim 6, wherein determining for each datapath function in the datapath region a range of suitable bit offsets comprises: determining a set of (bit offset, connectivity weight) pairs, where the bit offset is a vertical offset of the datapath function from the origin of the datapath region, and the connectivity weight is a function of a number of other datapath functions that may be coupled to the datapath function at the bit offset.
Claim 10
Dependent Claim
31 words
The method of claim 6, wherein weighted combination of cost functions comprise: an estimated wire length cost function; an estimated wasted area cost function; and, an estimated overflow track cost function.
Claim 11
Dependent Claim
54 words
The method of claim 8, wherein determining at least one linear order of the datapath functions comprises selecting from the range of bit offsets a bit offset for vertically placing the datapath function that minimizes the estimated wasted area cost function by vertically stacking the datapath function over at least one other datapath function.
Claim 12
Dependent Claim
95 words
The computer implemented method of claim 4, wherein the data file includes an instance description for each cell instance in the datapath function, each instance description including: i) an instance identifier specifying a logic cell instance; ii) a bit identifier specifying a bit position in the datapath function relative to a first bit position in the datapath function; and, iii) an order identifier specifying a serial position of the logic cell instance within the specified bit position, and relative to a first serial position of other logic cell instances also assigned to the bit position.
Claim 13
Dependent Claim
107 words
A computer implemented method for designing an integrated circuit in a computer aided design system, comprising: creating a plurality of datapath functions, each datapath function including a plurality of logic cell instances, each logic cell instance having unique relative horizontal or vertical placement information within the datapath function; creating at least one datapath region, and assigning to each datapath region: i) an origin within the integrated circuit, and ii) selected ones of the plurality of datapath functions; and for each datapath region, placing each of the selected ones of the datapath functions and the logic cell instances therein using the relative placement information for the datapath function.
Claim 14
Dependent Claim
107 words
A computer implemented method for designing an integrated circuit in a computer aided design system, comprising: creating a plurality of datapath functions, each datapath function including a plurality of logic cell instances, each logic cell instance having unique relative horizontal or vertical placement information within the datapath function; creating at least one datapath region, and assigning to each datapath region: i) an origin within the integrated circuit, and ii) selected ones of the plurality of datapath functions; and for each datapath region, placing each of the selected ones of the datapath functions and the logic cell instances therein using the relative placement information for the datapath function.
Claim 15
Dependent Claim
34 words
The computer implemented method of claim 11, further comprising: for each datapath region, estimating an available space for routing each datapath function within the region using the relative placement information for the datapath function.
Claim 16
Dependent Claim
174 words
The computer implemented method of claim 11, wherein creating a plurality of datapath functions comprises: providing for each of a plurality of unique datapath functions, a structured description of the unique relative vertical or horizontal placement of logic cell instances in the datapath function, having a plurality of instance descriptions, each instance description including: i) an instance identifier specifying a logic cell instance; ii) a bit identifier specifying a bit position in the datapath function relative to a first bit position in the datapath function; and, iii) an order identifier specifying a serial position of the logic cell instance within the specified bit position, and relative to a first serial position of other logic cell instances also assigned to the bit position; reading a netlist for the integrated circuit and associating each logic cell instance in the netlist with one of the structured descriptions to establish at least one datapath function including selected logic cell instances; for each datapath function, associating the relative placement information to each logic cell instance in the datapath function.
Claim 17
Dependent Claim
53 words
The computer implemented method of claim 11, wherein creating at least one datapath region comprises for each datapath region: assigning a location of a 0 th bit of the datapath region relative to a top or bottom of the datapath region; and, specifying whether rows within the datapath region are flipped during placement.
Claim 18
Dependent Claim
64 words
The computer implemented method of claim 11, further comprising: creating in at least one datapath region a cluster and assigning to the cluster selected ones of the datapath functions or other clusters within the datapath region, such that all datapath functions assigned to a cluster are placed within the datapath region as a group relative to all other datapath functions within the datapath region.
Claim 19
Dependent Claim
43 words
The computer implemented method of claim 15, wherein each cluster is either i) ordered such that the ordering of datapath functions within the cluster is fixed, or ii) unordered such that the ordering of datapath functions within the cluster is determined during placement.
Claim 20
Dependent Claim
88 words
The computer implemented method of claim 11, further comprising for at least one datapath region: determining each net that exits the datapath region by coupling a datapath function in the datapath region to a circuit element external to the datapath region; for each net that exits the datapath region, automatically assigning a net exit value identifying a side of the datapath region on which the net is to exit the datapath region according to the relative placement of the datapath region to other datapath regions within the circuit.
Claim 21
Dependent Claim
32 words
The computer implemented method of claim 11, further comprising for each datapath region: assigning a number of rows per bit within datapath region to interleave the datapath functions within the datapath region.
Claim 22
Dependent Claim
65 words
The computer implemented method of claim 11, further comprising: specifying for at least one datapath function in at least one datapath region that the datapath function comprises random logic, such that all other datapath functions in the datapath region are placed first and then all logic cell instances within the at least one datapath function are placed in a space remaining within the datapath region.
Claim 23
Dependent Claim
79 words
The computer implemented method of claim 11, wherein placing each datapath function comprises: determining for the datapath function in the datapath region a range of suitable bit offsets from an origin of the datapath region for vertically placing the datapath function; and, selecting from the range of bit offsets a bit offset for vertically placing the datapath function that minimizes an estimated wasted area cost function by vertically stacking the datapath function over at least one other datapath function.
Claim 24
Dependent Claim
76 words
The method of claim 20, wherein determining for each datapath function in the datapath region a range of suitable bit offsets comprises: determining a set of (bit offset, connectivity weight) pairs, where the bit offset is a vertical offset of the datapath function from the origin of the datapath region, and the connectivity weight is a function of a number of other datapath functions that may be coupled to the datapath function at the bit offset.
Claim 25
Dependent Claim
176 words
A computer aided system for designing an integrated circuit including at least one datapath region having a plurality of datapath functions, comprising: a) a database storing information for a plurality of logic cell instances; b) a plurality of tile files, each tile file describing for a unique datapath function in the integrated circuit unique relative placement information for each of the logic cell instances within the datapath function; c) a tile file list file associating each datapath function within a datapath region within the integrated circuit with one of the plurality of tile files; d) a datapath floorplanner that is coupled to the database and that receives therefrom the logic cell instance, tile files and tile file list file, and instantiates within the database at least one datapath region, each datapath region having a plurality of instantiated datapath functions, each datapath function instantiated from the tile file associated in the tile file list file with the datapath function, with each logic cell instance within each instantiated datapath function having relative placement information from the tile file.
Claim 26
Dependent Claim
176 words
A computer aided system for designing an integrated circuit including at least one datapath region having a plurality of datapath functions, comprising: a) a database storing information for a plurality of logic cell instances; b) a plurality of tile files, each tile file describing for a unique datapath function in the integrated circuit unique relative placement information for each of the logic cell instances within the datapath function; c) a tile file list file associating each datapath function within a datapath region within the integrated circuit with one of the plurality of tile files; d) a datapath floorplanner that is coupled to the database and that receives therefrom the logic cell instance, tile files and tile file list file, and instantiates within the database at least one datapath region, each datapath region having a plurality of instantiated datapath functions, each datapath function instantiated from the tile file associated in the tile file list file with the datapath function, with each logic cell instance within each instantiated datapath function having relative placement information from the tile file.
Claim 27
Dependent Claim
52 words
The computer system of claim 22, further comprising: a datapath placer that is coupled to the database to receive the instantiated datapath functions, and that places each instantiated datapath function within a datapath region according to the relative placement information contained therein and a weighted combination of a plurality of cost functions.
Claim 28
Dependent Claim
38 words
The computer system of claim 23, wherein the datapath placer determines for each datapath function in the datapath region a range of suitable bit offsets from an origin of the datapath region for vertically placing the datapath function.
Claim 29
Dependent Claim
72 words
The computer system of claim 24, wherein the datapath placer determines for each datapath function in the datapath region a set of (bit offset, connectivity weight) pairs, where the bit offset is a vertical offset of the datapath function from the origin of the datapath region, and the connectivity weight is a function of a number of other datapath functions that may be coupled to the datapath function at the bit offset.
Claim 30
Dependent Claim
38 words
The computer system of claim 25, wherein the weighted combination of cost functions used by the datapath placer comprise: an estimated wire length cost function; an estimated wasted area cost function; and, an estimated overflow track cost function.
Claim 31
Dependent Claim
47 words
The computer system of claim 26, wherein the datapath placer vertically places a datapath function by selecting from the range of bit offsets a bit offset that minimizes the estimated wasted area cost function by vertically stacking the datapath function over at least one other datapath function.
Claim 32
Dependent Claim
77 words
The computer system of claim 23, further comprising: a routing space estimator that is coupled to the database to receive the datapath functions placed within a datapath region, and that estimates an available routing space within the datapath region for routing the logic cell instances within the datapath region according to the placement of datapath functions therein by the datapath placer, and relative vertical and horizontal placement information of the logic cell instances within each datapath function.
Claim 33
Dependent Claim
97 words
A computer implemented method for determining a placement of logic cell instances in an integrated circuit, comprising: a) associating selected logic cell instances with datapath functions, such that some random logic cell instances remain unassociated with any datapath function; b) placing the datapath functions in a datapath region; c) within each datapath function, placing the logic cell instances associated with the datapath function within the datapath function; d) placing selected ones of remaining random logic cell instances in any remaining area within the datapath region where no logic cell instance associated with the datapath function was placed.
Claim 34
Dependent Claim
97 words
A computer implemented method for determining a placement of logic cell instances in an integrated circuit, comprising: a) associating selected logic cell instances with datapath functions, such that some random logic cell instances remain unassociated with any datapath function; b) placing the datapath functions in a datapath region; c) within each datapath function, placing the logic cell instances associated with the datapath function within the datapath function; d) placing selected ones of remaining random logic cell instances in any remaining area within the datapath region where no logic cell instance associated with the datapath function was placed.
Claim 35
Dependent Claim
112 words
The computer implemented method of claim 29, wherein placing datapath functions in the datapath region comprises: determining a linear order and a vertical placement of each datapath function within the datapath region by simultaneously optimizing: i) an estimated wire length cost function that estimates a wire length needed to route a linear order of the datapath functions; ii) an estimated overflow track cost function that estimates a number of overflow tracks required to route a linear order of the datapath functions; and, iii) an estimated wasted area cost function that estimates the remaining area within the datapath region resulting from a linear order and vertical placement of each of the datapath functions.
Claim 36
Dependent Claim
75 words
The computer implemented method of claim 30, further comprising: determining for the datapath function in the datapath region a range of suitable bit offsets from an origin of the datapath region for vertically placing the datapath function; and, selecting from the range of bit offsets a bit offset for vertically placing the datapath function that minimizes the estimated wasted area cost function by vertically stacking the datapath function over at least one other datapath function.
References Cited (Backward Citations)
US4630219A
Cited
US4670846A
Cited
US4754408A
Cited
US4964056A
Cited
US5461577A
Cited
US4951221A
Cited
US5521836A
Cited
US5359538A
Cited
US5491640A
Cited
US5519627A
Cited
US5557532A
Cited
US5487018A
Cited
US5586047A
Cited
US5515293A
Cited
US5506788A
Cited
US5657243A
Cited
US5587923A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-11-16 | 2002-05-18 | 2002-11-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-11-16 | 2006-05-18 | 2006-11-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-11-16 | 2010-05-18 | 2010-11-17 | $7700.00 | Window Closed / Lapsed |