System for designing a placement of a placement element

• US 5,475,608 A
• Filed: 10/15/1992
• Issued: 12/12/1995
• Est. Priority Date: 10/15/1991
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Masuoka, Ryusuke
• Primary Examiner(s): Trans, Vincent N.
• Application Number:
  US07/961,546
• Time in Patent Office: 1,153 Days
• Field of Search: 364/491, 364/489, 364/488, 364/490
• US Class Current: 716/124
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A system for designing a placement of a placement element comprises a placement element storage unit for storing placement element data on placement elements, a placement set unit for setting a placement of the placement element and a placement output unit for outputting the result of setting the placement. The placement set unit comprises a unit area data storage unit, a plurality of intra-virtual-placement-area placement element position storage units, a pointer storage unit and a placement control unit. A unit area data storage unit stores unit area data on unit areas each for placing a placement element. An intra-virtual-placement-area placement element position storage unit stores placement element data on placement elements in virtual placement areas. A pointer storage unit specifies placement element data stored in the intra-virtual-placement-area placement element position storage unit to which the unit areas split from the placement area correspond. A placement control unit sets the placement of placement elements in the placement area such that the placement elements whose placement element data are stored in the virtual placement areas are placed in respective unit areas stored in the unit area data storage unit.

Claims

1. A system for designing a placement of a placement element, for use in a placement designing system, comprising:

a placement element storage means for storing placement element data representing placement elements;

a placement/routing means for setting a placement of said placement element, said placement/routing means comprising,

a placement area for placing said placement elements, said placement area including a unit area data storage means for storing unit area data representing unit areas, said unit areas split from said placement area, wherein a respective placement element is placed in each unit area,

a plurality of intra-virtual-placement-area placement element position storage means, provided for each type of placement element for virtually storing placement element data in the virtual placement areas,

a pointer storage means, for specifying placement element data stored in said intra-virtual-placement-area placement element position storage means to which said unit areas correspond, and

a placement control means for setting the placement of placement elements in said placement area such that said placement elements whose placement element data are stored in said virtual placement areas are placed in respective unit areas in said unit area data storage means, according to the placement element data specified by said pointer storage means; and

a placement output means for outputting the result of setting said placement.

2. The system for designing placement of a placement element according to claim 1, wherein:

said virtual placement areas comprise multiple layers of storage areas to store the same kinds of placement element data in numbers in excess of respective limit numbers, in correspondence with said unit areas.

3. The system for designing a placement of a placement element according to claim 1, wherein

said unit area data storage means stores positions of unit areas split from said placement area and said unit areas comprise a plurality of gate array placement areas and channel areas between said gate array placement areas;

and

said plurality of gate array placement areas comprise unit areas corresponding to the dimensions of basic cells, which form units of cells in gate arrays.

4. The system for designing a placement of a placement element according to claim 1, wherein:

one of said plurality of intra-virtual-placement-area placement element position storage means comprises a degree-of-redundancy storage area for storing a degree of redundancy of placement elements placed in the same unit area in said placement area; and

said placement control means comprises,

a unit area dam creation means for splitting said placement area into unit areas and for storing the split placement area in the unit area data storage means;

a pointer creation means for creating pointers corresponding to said unit area and for storing said pointers in said pointer storage means;

a plurality of placement element creation means respectively corresponding to said plurality of intra-virtual-placement-area placement element position storage means, for creating placement element data including positions of said placement elements in said placement area;

a degree-of-redundancy determination means, including a degree-of-redundancy storage area, for determining the degrees of redundancy of placement elements whose placement element data are newly created by using an output from one of said plurality of placement element creation means corresponding to said one, of said plurality of intra-virtual-placement-area placement element position storage means and the storage content of said degree-of-redundancy storage area;

a placement data creation means for creating placement data representing a placement of placement elements in said unit areas in said placement area, by using the storage contents of said unit area data storage means and said plurality of intra-virtual-placement-area placement element position storage means, and for outputting said placement data to said placement output means;

a placement change necessity determination means for determining whether a change in a placement of placement elements in said placement area is necessary or not by using placement data created by said placement data creation means;

a probability distribution creation means for creating a probability distribution for creating new coordinate values, which become the bases for creating new placement data based on an adopted placement, after said placement change necessity determination means has determined the necessity for a placement change; and

a coordinate position creation means for creating a new coordinate position for a placement by using said probability distribution created by said probability distribution creation means and for outputting the result of creating said new coordinate position to said unit area data creation means, said pointer creation means and said plurality of placement element creation means.

5. The system for designing a placement of a placement element according to claim 4, wherein:

said placement element storage means comprises a placement element file for storing cell data including a name and dimensions of a cell, terminal data including a name and type of a terminal, wire data including a wire width and via hole data representing a via hole;

said plurality of intra-virtual-placement-area placement element position storage means corresponding to said plural types of placement elements each comprising a cell placement storage means, a terminal placement storage means, a via hole placement storage means and a wire placement storage means having a degree-of-redundancy storage area; and

said plurality of placement element creation means each comprising a cell placement creation means for outputting cell placement data to said cell placement storage means, a terminal placement creation means for outputting terminal placement data to said terminal placement storage means, a via hole placement creation means for outputting via hole placement data to said via hole placement storage means, and a wire placement creation means for outputting wire data to said wire placement storage means and said degree-of-redundancy determination means.

6. The system for designing a placement of a placement element according to claim 5, wherein:

unit areas, whose positions are stored in said unit area data storage means, comprise unit areas each for placing one of a cell and a wire, and a unit area for placing one of a wire, a terminal and a via hole; and

pointers stored in said pointer storage means comprise,

a pointer for specifying a first layer in plural layers of wire areas each for storing wire data representing a wire, stored in said wire placement storage means, to be placed in said unit area,

a pointer for specifying a first layer in plural layers of cell areas for storing data representing a cell, stored in said cell placement storage means, to be placed in said unit area,

a pointer for specifying a first layer in plural layers of terminal areas for storing terminal data representing a terminal, stored in said terminal placement storage means, to be placed in said unit area, and

a pointer for specifying a via hole area for storing via hole data representing a via hole, stored in said via hole placement storage means, to be placed in said unit area.

7. The system for designing a placement of a placement element according to claim 5, wherein:

said cell placement storage means stores data representing respective parts of a single cell placed over a plurality of unit areas in said placement area, in a single one of plural layers of cell areas corresponding respectively to said unit areas.

8. The system for designing a placement of a placement element according to claim 5, wherein:

said cell placement storage means stores data representing respective parts of a single cell placed over a plurality of unit areas in said placement area, in different layers of plural layers of cell areas corresponding respectively to said unit areas.

9. The system for designing a placement of a placement element according to claim 5, wherein:

said degree-of-redundancy storage area store, as degrees of redundancy, respective numbers of identical wires placed in the same unit areas in correspondence with plural layers of a wire area in said wire placement storage means.

10. The system for designing a placement of a placement element according to claim 5, wherein:

said unit area data stored in said unit area data storage means comprises unit area numbers of respective unit areas split from said placement area, unit area data including the types of placement elements incapable of being placed in said unit area, and pointers for specifying a pointer storage position to intra-virtual-placement-area data representing a placement element to be placed in said unit area in said pointer storage means;

said pointer data stored in said pointer storage means comprises said pointers to a cell area, a wire area, a terminal area and a via hole area, respectively, in correspondence with said unit areas;

said cell placement data stored in said cell placement storage means comprises cell area data including the cell area numbers and unit area positions for placing cells, for respective cell areas in plural layers; and

said wire placement data stored in said wire placement storage means comprises wire area data including degrees of redundancies of wires and the cell numbers of cells for placing said wires, for respective wire areas in plural layers.

11. The system for designing a placement of a placement element according to claim 5, wherein said cell placement creation means comprises:

a first means for determining whether or not cell placement processes for all parts of a single cell placed over a plurality of unit areas have been completed;

a second means, invoked when said first means determines cell placement processes have not been completed, for selecting one of said parts in said single cell not having been processed yet;

a third means for obtaining a unit area corresponding to said part selected in said second means from the position for placing said part of said single cell and the relative position of said selected part in said single cell;

a fourth means for placing said selected part in said unit area;

a fifth means for determining whether or not the result of placing said selected part in said unit area by said fourth means is successful and returning to said first means when it is determined that placing said selected part in said unit area is successful;

a sixth means, invoked when said fifth means determines that placing said selected part in said unit area is not successful, for outputting a result indicating a failure to the outside;

a seventh means, invoked when said first means determines cell placement processes have been completed, for terminating a cell placement process.

12. The system for designing a placement of a placement element according to claim 5, wherein said cell placement creation means, said terminal placement creation means, and said via hole placement creation means respectively comprise:

a first means for receiving an instruction for changing a placement of a corresponding placement element;

a second means for determining whether said instruction is for a placement or an elimination of a placement element;

a third means, invoked when said second means determines said instruction is for a placement of a placement element, for determining whether or not a unit area desired for placing said placement element is free;

a fourth means, invoked when said third means determines a unit area desired for placing said placement element is free, for recording necessary data in a free area;

a fifth means, invoked when said third means determines a unit area desired for placing said placement element is not free, for outputting the result to the outside, if no free area is available;

a sixth means, invoked when said second means determines said instruction is for an elimination, for determining whether or not a placement element matches one instructed for an elimination from a unit area of said placement element;

a seventh means, invoked when said sixth means determines a placement element matches one instructed for an elimination from a unit area, for deleting data from unit areas of said placement element; and

an eighth means, invoked when said sixth means determines a placement element does not match one instructed for an elimination from a unit area, for outputting a message informing of a mismatch with an instructed placement element to the outside.

13. The system for designing a placement of a placement element according to claim 5, wherein said wire placement creation means comprises:

a first means for receiving an instruction for changing a placement of a wire;

a second means for determining whether an instruction is for a placement or an elimination of a wire;

a third means, invoked when said second means determines said instruction is for a placement of a wire, for determining whether a unit area desired for placing said wire has one matching said wire;

a fourth means, invoked when said third means determines a unit area for placing said wire does not have one matching wire, for determining whether or not a unit area desired for placing the placement element has a free area;

a fifth means, invoked when said fourth means determines said unit area desired for placing the placement element has a free area, for recording necessary data in a free unit area, and writing one as a degree of redundancy in the corresponding virtual area;

a sixth means, invoked when said fourth means determines said unit area desired for placing the placement element does not have a free area, for outputting the result to the outside;

a seventh means, invoked when said third means determines a trait area for placing said wire has one matching wire, for incrementing the degree of redundancy of said wire in said unit area by one;

an eighth means, invoked when said second means determines said instruction is for an elimination of a placement element, for determining whether or not a wire matches one instructed for elimination from a unit area;

a ninth means, invoked when said eighth means determines a wire matched one instructed for elimination from a unit area, for determining whether or not the degree of redundancy in the area corresponding to the placement element is one;

a tenth means, invoked when said ninth means determines that the degree of redundancy on the area corresponding to the placement element is one, for setting the degree of redundancy to zero and deleting associated data in said virtual placement area simultaneously;

an eleventh means, invoked when said ninth means determines that the degree of redundancy in the area corresponding to the placement element is not one, for decrementing, by one, the degrees of redundancy not being one; and

a twelfth means, invoked when said eighth means determines a wire does not match one instructed for elimination from a unit area, for outputting to the outside that no wire matches one instructed for elimination from a unit area.

14. The system for designing a placement of a placement element according to claim 5, wherein:

said cell placement creation means for checking a cell placement possibility, said terminal placement creation means for checking a terminal placement possibility, said via hole placement creation means for checking a via hole placement possibility and said wire placement creation means for checking a wire placement possibility respectively comprise;

a first means for receiving an instruction for placing a placement element in a unit area whose position is specified by a coordinate value (x, y);

a second means for obtaining a virtual placement area storing placement element data of a placement element to be placed in said unit area specified by said coordinate value;

a third means for determining whether or not said virtual placement area has a void;

a fourth means, invoked when said third means determines said virtual placement area has a void, for determining that said placement element can be placed; and

a fifth means, invoked when said third means determines said virtual placement area does not have a void, for determining that said placement element cannot be placed.

15. The system for designing a placement of a placement element according to claim 4, further comprising:

a placement dam input means for inputting placement data, including wire data of a circuit, to said placement control means and for inputting a parameter, including a constant for creating a probability distribution, to a probability distribution creation means in said placement control means.

16. The system for designing a placement of a placement element according to claim 15, wherein:

said probability distribution creation means creates probability distributions for creating a new coordinate value (X, Y) according to normal distributions having means equal to a current coordinate value (x, y) by using variances Ux and Uy supplied as parts of parameters from said placement data input means

space="preserve" listing-type="equation">f(X)=(2π

).sup.-1/2 Ux.sup.-1 exp.[-(X-x).sup.2 /2Ux.sup.2 ]

space="preserve" listing-type="equation">f(Y)=(2π

).sup.-1/2 Uy.sup.-1 exp.[-(Y-y).sup.2 /2Uy.sup.2 ]

and

said coordinate value creation means creates a new coordinate position according to said probability distributions.

17. The system for designing a placement of a placement element according to claim 15, wherein:

said probability distribution creation means creates probability distributions for creating a new coordinate value (X, Y) according to normal distributions having means equal to a current coordinate value (x, y) by using variances Ux and Uy supplied as parts of parameters from said placement data input means and s as dimensions of a single cell defined by the number of unit areas over which said single cell is placed,

space="preserve" listing-type="equation">f(X)=(2π

).sup.-1/2 (Ux/s).sup.-1 exp.[-(X-x).sup.2 /2(Ux/s).sup.2 ]

space="preserve" listing-type="equation">f(Y)=(2π

).sup.-1/2 (Uy/s).sup.-1 exp.[-(Y-y).sup.2 /2(Uy/s).sup.2 ]

and

said coordinate position creation means creates a new coordinate position according to said probability distributions.

18. The system for designing a placement of a placement element according to claim 15, wherein:

said probability distribution creation means creates, by using a current coordinate value (x, y), a positive real number a_odd and a negative real number a_even, a first set of probability distributions having means X+a_odd and y+a_odd and a second set of probability distributions having means x+a_even and y+a_even ; and

said coordinate position creation means creates a new coordinate position based on a current coordinate value (x, y) by using either one [1] of said first set of probability distributions and said second set of probability distributions.

19. The system for designing a placement of a placement element according to claim 15, wherein:

said probability distribution creation means comprises

a random number generation means for generating a random number,

a coordinate position calculation means for calculating a coordinate value,

a control means for controlling said random number generation means and said coordinate position calculation means; and

said coordinate position creation means further comprises a parameter storage means for storing a parameter inputted from said parameter data input means.

20. The system for designing a placement of a placement element according to claim 19, wherein:

said coordinate position creation means receives an instruction for creating a coordinate position in a coordinate position creation process;

said control means receives a random number generated by said random number generation means;

said control means supplies said received random number to said coordinate position calculation means;

said control means reads the coordinate value calculated by said coordinate position calculation means;

said control means determines whether said read coordinate value is appropriate or inappropriate; and

said control means outputs a coordinate value determined to be appropriate, otherwise repeats its processes by receiving a random number generated by said random number generation means.