Placement optimization system aided by CAD

• US 5,187,668 A
• Filed: 12/04/1990
• Issued: 02/16/1993
• Est. Priority Date: 12/04/1989
• Status: Expired due to Fees

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Akino, Toshiro, Toyonaga, Masahiko, Okude, Hiroaki
• Primary Examiner(s): Smith, Jerry
• Assistant Examiner(s): GORDON, PAUL P
• Application Number:
  US07/621,893
• Time in Patent Office: 805 Days
• Field of Search: 364/148, 364/149, 364/150, 364/468, 364/469, 364/488, 364/489, 364/490, 364/491, 364/578
• US Class Current: 716/123
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

There is provided a placement optimization system for determining layout in printed circuits and semiconductor substrates, comprising input means for inputting circuit connection information, placement optimization means for deriving wiring density distribution on the basis of the circuit connection information, evaluating the height and/or width of the wiring region statistically estimated from the wiring density distribution, and output means for outputting the resultant placement position information. Further, the placement optimization system may comprise means for collecting placement elements into sets, determining placement of the sets, then developing the sets into elements, and determining optimum placement positions of the elements.

Claims

1. A placement optimization system aided by CAD comprising:

input means for inputting circuit connection information including a plurality of placement elements;

placement optimization means for determining a degree of wiring crowdedness based on said circuit connection information and optimizing placement positions of said placement elements by conducting an evaluation of a height of a wiring region statistically approximated from a distribution of the degree of wiring crowdedness and by performing repetitive improvement of the placement positions based on said evaluation; and

output means for outputting placement position information derived by said placement optimization means.

2. A placement optimization system aided by CAD according to claim 1, wherein said placement optimization means comprises:

placement element collection means for collecting a plurality of placement elements having close connection relations in circuit connection information into a plurality of placement element sets, the sets having equal areas;

modeling means for modeling placement element sets and wiring region lattices derived by said placement element collection means into lattice-like models;

placement element set placement optimization means for determining optimum placement positions in lattice-like models of all placement element sets by repeating placement improvement on the basis of connection information between said placement element sets, and

set development means for opening said plurality of placement element sets and for determining placement positions of all placement elements forming respective placement element sets.

3. A placement optimization system aided by CAD according to claim 2, wherein said placement optimization means generates a plurality of rectangles by considering rough wiring on the basis of extent of placement elements or placement element sets connected to each wiring on the basis of circuit connection information, and said placement optimization means sets the degree of wiring crowdedness on the basis of said plurality of rectangles.

4. A placement optimization system aided by CAD according to claim 1, wherein said placement optimization means generates a plurality of rectangles by considering rough wiring on the basis of extent of placement elements or placement element sets connected to each wiring on the basis of circuit connection information, and said placement optimization means sets the degree of wiring crowdedness on the basis of said plurality of rectangles.

5. A placement optimization system aided by CAD for optimizing, in a circuit including mutually related placement elements, placement positions of the placement elements, said placement optimization system comprising:

input means for inputting circuit connection information including a plurality of placement elements and shape information of said placement elements;

initial placement means for initially placing said placement elements at respective placement positions;

placement alternation means for moving and interchanging said placement elements and for locally altering the placement positions;

final area estimation means for calculating, on the basis of a placement state obtained at each time of placement alteration, an area of a final layout result expected in said placement state and defining the calculated area as an evaluation function value assigned to the respective placement alteration;

alternation condition judgment means for evaluating a difference between said evaluation function value assigned to a first said placement alteration and the evaluation function value assigned to a second said placement alteration successive to the first placement alteration and thereby judging satisfaction of a condition of the second placement alteration;

placement alteration cancellation means responsive to nonsatisfaction of said condition of said second placement alteration in said alteration condition judgment means to cancel said second placement alteration and restore the placement state and the evaluation function value assigned to said first placement alteration; and

end condition judgment means for judging satisfaction of a given end condition, said end condition judgment means being responsive to satisfaction of said end condition to cause an output means to generate placement position information of said placement elements and responsive to nonsatisfaction of said end condition to activate said placement alteration means.

6. A placement optimization system aided by CAD according to claim 5, wherein said final area estimation means comprises:

connection net extraction means for extracting all nets connected to the placement elements altered in placement;

wiring path determination means for determining a shape of wiring path and expectation of wiring density with respect to the nets extracted by said connection net extraction means;

wiring density setting means for setting expectation of said wiring density into the wiring path determined by said wiring path determination means;

wiring region height estimation means for estimating a height of a wiring region in the final layout result on the basis of said placement state expected from a distribution state of the wiring density in each placement state;

final width estimation means for estimating a width of said final layout result expected from said placement state; and

expected final area calculation means for calculating the area of the final layout result on the basis of the wiring region height estimated by said wiring region height estimation means and said expected final width estimated by said final width estimation means.

7. A placement optimization system aided by CAD according to claim 6, wherein on the basis of positional relationship information of placement positions of all placement elements connected to the nets, the wiring path determination means determines a type of an expected wiring path according to a number of the placement elements connected to said nets and a shape representing said placement positional relationship information and determines a shape of the wiring path formed of partial paths including a fixed wiring path and a stochastic wiring path and an expectation value of a wiring density in each of the partial paths.

8. A placement optimization system aided by CAD according to claim 6, wherein said wiring density setting means comprises wiring density accumulators provided in the wiring region and means for adding the expectation values of the wiring density relating to said nets to contents of all the wiring density accumulators provided on the expected wiring path determined by said wiring path determination means.

9. A placement optimization system aided by CAD according to claim 8, wherein on the basis of distribution situation of wiring density set in said wiring density accumulators for all nets, said wiring region height estimation means calculates the height of wiring region by handling said wiring density distribution statistically and calculates the height of final layout result expected in that placement state.

10. A placement optimization system aided by CAD according to claim 6, wherein said final width estimation means calculates the width of the final layout result statistically on the basis of distribution of wiring region length.

11. A placement optimization system aided by CAD for optimizing, in a circuit including mutually related placement elements, placement positions of the placement elements, said placement optimization system comprising:

input means for inputting circuit connection information including a plurality of placement elements and shape information of said placement elements;

placement element collection means for generating placement element sets by collecting the placement elements having a close connection relationship in said circuit connection information in each set so as to make areas of the respective sets nearly equal to each other, and defining the placement element sets as new placement elements, and for generating circuit connection information relating to said placement elements sets, and defining the circuit connection information as new circuit connection information;

modeling means for assigning the placement elements to placement region lattices of a lattice model including placement region lattices and wiring region lattices;

placement alteration means for interchanging said placement elements on the lattice model to perform local placement interchange;

final area estimation means for calculating, on the basis of a placement state obtained at each time of execution of placement alteration, an area of a final layout result expected in said placement state and defining the area thus calculated as an evaluation function value assigned to the respective placement alteration;

alteration condition judgment means for evaluating a difference between said evaluation function value assigned to a first said placement alteration and the evaluation function value assigned to a second said placement alteration successive to said first placement alteration and for judging, on the basis of the evaluation, satisfaction of the second placement alteration;

placement alteration cancellation means responsive to nonsatisfaction of said second placement alteration in said alteration condition judgment means to cancel said second placement alteration and restore the placement state and the evaluation function value assigned to said first placement alteration;

end condition judgment means for judging satisfaction of an end condition, said end condition judgment means being responsive to satisfaction of the end condition to cause advancement to succeeding processing and responsive to nonsatisfaction of the end condition to activate said placement alteration means;

placement element set development means for opening all placement elements sets assigned to respective placement region lattices of said lattice model and for determining placement positions of all placement elements included in each placement element set; and

output means for outputting placement position information.

12. A placement optimization system aided by CAD according to claim 11, wherein said final area estimation means eliminates influence of interchange on other placement element sets by interchanging placement element sets assigned to said placement region lattices in the lattice model, between said placement region lattices.

13. A placement optimization system aided by CAD according to claim 11, wherein said final area estimation means representatively detects wiring density by setting a wiring density accumulator for each of said wiring region lattices in the lattice model.

14. A placement optimization system aided by CAD according to claim 11, wherein said placement element set development means develops placement element sets assigned to placement region lattices of said lattice model and determines placement positions of all placement elements included in said placement element sets.