Home
Patent Search
IMT Blog
REGISTER
|
SIGN IN
United States Patent
6412097
Kikuchi , ; et al.
June 25, 2002
Title
COMPACTING METHOD OF CIRCUIT LAYOUT BY MOVING COMPONENTS USING MARGINS AND BUNDLE WIDTHS IN COMPLIANCE WITH THE DESIGN RULE, A DEVICE USING THE METHOD AND A COMPUTER PRODUCT ENABLING PROCESSOR TO PERFORM THE METHOD
Abstract
A layout compaction method adapted to be embodied in computer program product and adapted for compacting a circuit layout having a plurality of layers on which moving objects form layer patterns, wherein the moving objects comprising components and wires. The method assumes a graph problem under condition which prevent the compacted result from violation of the design rule, and then, solves the graph problem to determine a moving order, a moving direction, and a moving distance of each component for moving the components to thereby perform the compacting the circuit layout. After that, the method moves each component according to the moving order, the moving direction and the moving distance to obtain a compacted circuit layout.
Inventors:
Kikuchi; Hideo
(Tokyo,
JP
)
, Nagano; Keiji
(Tokyo,
JP
)
, Akimoto; Yutaka
(Tokyo,
JP
)
Assignee:
NEC Corporation
(,
JP
)
Appl. No.:
495804
Filed:
February 1, 2000
Foreign Application Priority Data
Feb 02, 1999 [JP] 11-025310
Current U.S. Class:
716/2
Current International Class:
G06F 17/50 (20060101)
Field of Search:
716/2,4,5,7,9-12
U.S. Patent Documents
5625568
April 1997
Edwards
6035108
March 2000
Kikuchi
Foreign Patent Documents
10-242285
Sep., 1998
JP
10-3491
Jan., 1998
JP
5-274392
Oct., 1993
JP
Other References
Two-Dimensional Compaction by "Zone Refining" Hyunchul Shin, Alberto L. Sangiovanni-Vincentelli and Carol H. Sequin/Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, CA., 23rd Design Automation Conference, 1986 IEEE, Paper 7.3, pp. 115-122. .
Kikuchi Hideo "Printed Board Diagonal Wire Compaction Method and Its Evaluation", Joho Shori Gakkai Kenkyu Hoko, (Information Management Society Research Report) (98-DA-88), May 22, 1998, vol. No. 98 Issue No. 43, pp. 29-34..~
Primary Examiner:
Smith; Matthew
Assistant Examiner:
Do; Thuan
Attorney, Agent or Firm:
Hayes Soloway P.C.
Claims
What is claimed is:
1. A method of compacting a circuit layout having a plurality of layers on which moving objects form layer patterns, the moving objects comprising components and wires, ones of the wires being laid on the respective layers in bundles to form wire bundles, each of the wires having a wire width and a pattern shape as a wire pattern shape, each of the wire bundles having a pattern shape as a bundle pattern shape and a bundle width defined by a total width of wires of each wire bundle, said method comprising, for each of the layer patterns on each of the layers:
assuming a graph problem where a graph comprises nodes corresponding to the components and edges corresponding to moving vectors of the components under first through fourth condition;
the first condition being that the wire widths of the wires are fixed at constant wire width values;
the second condition being that belt widths of wire belts are fixed at constant belt width values, the wire belts defined by adding predetermined margins to both sides in a width direction of each of the wire bundles in compliance with a design rule, each of the belt widths being equal to a sum of each of the bundle widths and the predetermined margins;
the third condition being that component-wire spaces are variable, each of the component-wire spaces being defined to be a distance from the component to edges in the width direction of the wire belts and/or the wires; and
the fourth condition being that wire pattern shape and the bundle pattern shape are changeable for compacting;
solving the graph problem to determine a moving order, a moving direction, and a moving distance of each component for moving the components to thereby perform the compacting the circuit layout; and
moving each components according to the moving order, the moving direction and the moving distance.
2. A compacting method as claimed in claim 1, the components having terminals, wherein the assuming comprises, for each layer pattern:
extracting the terminals from the components;
defining a terminal constraint graph in relation to a pair of particular terminals selected among the terminals of all components, the particular terminals being close to each other in a predetermined direction and belonging to different components from one to another, the particular terminals being assigned to nodes at both ends of the terminal constraint graph, the terminal constraint graph having, as a weight, a maximum movable range of one of the particular terminals in a case where the one particular terminals is moved for the other particular terminal in the predetermined direction; and
processing the terminal constraint graph with reference to the components having the terminals defined as the nodes for the terminal constraint graph to obtain the graph.
3. A compacting method as claimed in claim 2, wherein the maximum movable range has a minus value in a case where the wire and/or the wire belt are laid traversely to a virtual line connecting between the particular terminals and whether or not a length of the virtual line is shorter than another length required by the design rule in accordance with the wire width and/or the belt width, otherwise the maximum movable range has a plus value.
4. A compacting method as claimed in claim 3, wherein the processing comprises, after the defining is executed for all of the layer patterns, determining a component constraint graph on the basis of the terminal constraint graphs of all layer patterns, the component constraint graph having, as a weight, a minimum one among the weights of the terminal constraint graphs, the particular terminals being assigned to nodes at both ends of the components constraint graph, the graph comprising the component constraint graph.
5. A compacting method as claimed in claim 4, wherein:
the defining is repeatedly executed for all pairs of the particular terminals each selected among the terminals of all components at every layer pattern, so as to obtain the terminal constraint graphs in relation to all pairs;
the determining being repeatedly executed for all of the terminal constraint graphs; and
the processing further comprising, for each layer pattern and after the determining being executed for all of the terminal constraint graphs, joining the component constraint graphs with reference to the nodes for the component constrain graphs to obtain the graph.
6. A compacting method as claimed in claim 5, wherein the graph problem is a shortest path problem, the graph having a particular nodes as a starting point.
7. A compacting method as claimed in claim 6, wherein the solving utilizes the Dijkstra method.
8. A compacting method as claimed in claim 6, wherein:
the circuit layout is formed on a substrate region having a corner;
the assuming further comprising, prior to the defining, picking up the corner to handle the corner as the terminal;
the defining further defining, for each layer pattern, the terminal constraint graph in a chase where the corner and the terminal closest to the corner are handled as the pair of particular terminals, the closest terminal serving as the one particular terminal, while the corner serving as the other particular terminal, the node corresponding to the corner being the particular node in the graph.
9. A compacting method as claimed in claim 8, further comprising, after the moving: judging whether the wire and/or the wire belt are laid traversely to a virtual line connecting between the particular terminals; and rewiring the wire and/or the wire belt, in question, in consideration of an allowable form of the design rule.
10. A compacting method as claimed in claim 9, wherein the substrate region has a bottom line extending from the corner and the allowable form is a selected one of a vertical form, a horizontal form, and a diagonal form to the bottom line, and a combination thereof.
11. A compacting method as claimed in claim 6, wherein:
the defining is further adapted to define additional terminal constraint graphs relating to the pairs of the particular terminals in the case of compacting in a perpendicular direction to the predetermined direction, according to the same way of defining the terminal constraint graphs;
the determining being further adapted to determine additional component constraint graphs on the basis of the additional terminal constraint graphs of all layer patterns, according to the same way of determining the component constraint graphs;
the joining being further adapted to join the additional component constraint graphs with reference to the nodes for the additional component constraint graphs to obtain an additional graph;
the assuming being further adapted to assume an additional graph problem as an additional shortest path problem in consideration of the additional graph;
the solving being further adapted to solve the additional graph problem to determine a moving order and a moving distance of each component in case of compacting in the perpendicular direction; and
the moving being further adapted to move each of the components in the perpendicular direction, according to the moving order and the moving distance.
12. A compacting method as claimed in claim 11, wherein:
the circuit layout is formed on a substrate region, a shape of the substrate region being a rectangular having vertical lines and horizontal lines in the predetermined and perpendicular directions, respectively;
said comprising method further comprising, for each layer pattern and after the components being moved in both of the predetermined and the perpendicular directions, and thereby, the circuit layout being once compacted;
deciding a target substrate region, a shape of the target substrate region being another rectangular having target vertical lines and target horizontal lines smaller than the vertical lines and horizontal lines in the predetermined and perpendicular directions, respectively;
identifying an particular one of the pairs, the movement in the predetermined direction of the one particular terminal of the particular pair causing the once compacted circuit layout to be over the target substrate region in the perpendicular direction; and
removing the terminal constraint graph of the particular pair;
the assuming being further adapted to re-assume the graph problem as a re-assumed graph problem in consideration of the removing;
the solving being further adapted to solve the re-assumed graph problem; and
the moving being further adapted to move each component in the predetermined direction.
13. A compacting method as claimed in claim 5, wherein:
the circuit layout is formed on a substrate region;
the assuming further comprising: after the extracting and prior to the defining, partitioning the substrate region with a plurality of vertical partition lines and a plurality of horizontal partition lines, into a plurality of sections; and picking up the vertical and horizontal partition lines to handle the vertical and horizontal partition lines as the terminals.
14. A compacting method as claimed in claim 13, wherein the assuming further comprising, after the picking up and prior to the defining: detecting whether or not the terminals except for the vertical and horizontal partition lines belong to one of the sections; and supposing an empty terminal to be placed as the terminal at a center of the one section, in a case where no terminals except for the vertical and horizontal partition lines belong to the one sections; the defining being repeatedly executed, in the one section, for all of pairs of particular terminals selected among the vertical and horizontal partition lines and the empty terminal.
15. A compacting method as claimed in claim 14, wherein, in a case where a plurality of the terminals except for the vertical and horizontal partition lines belong to the one section, the defining is repeatedly executed, in the one section, for all of the pairs of particular terminals selected among the terminals including the vertical and horizontal partition lines.
16. A compacting method as claimed in claim 15, wherein, in a case where only one terminal except for the vertical and horizontal partition lines belongs to the one section, the defining is repeatedly executed, in the one section, for all of the pairs of particular terminals selected among the vertical and horizontal partition lines and the only one terminal.
17. A compacting method as claimed in claim 13, wherein the moving is further adapted to move the vertical and horizontal partition lines, with the movements of the components which have the particular terminals except for the vertical and horizontal partition lines.
18. A compacting method as claimed in claim 2, wherein the assuming further comprises, after the defining and prior to the processing: detecting whether or not the pair of particular terminals are given the same signal; and removing the terminal constraint graph relating to the pair of particular terminal given the same signal.
19. A compacting method as claimed in claim 2, wherein the assuming further comprises, prior to the defining, fixing an octagonal restricted region adapted to forbid a center of the one particular terminals to enter inside of the octagonal restriction region, and thereby, to restrict the movement of the one particular terminal, the octagonal restricted region and the other particular terminal having a common center, the defining being carried out under the restriction of the octagonal restricted region.
20. A compacting method as claimed in claim 19, wherein the fixing comprises:
approximating the other particular terminals to obtain a first octagon having a first distance from a center to an edge of the first octagon;
adding the belt width to each of edges of the first octagon to obtain a second octagon having a second distance from a center to an edge of the section octagon, the second distance being equal to a sum of the belt width and the first distance;
approximating the one particular terminal to obtain a third octagon having a third distance from a center to an edge of the third octagon; and
adding the third distance to each of edges of the second octagon to determine a shape and a size of the octagonal restricted region, the shape having a fourth distance from a center to an edge of the shape, in question, the fourth distance being equal to a sum of the second distance and the third distance.
21. A compacting method as claimed in claim 2, further comprising, prior to the assuming, designating a target moving vector having a target direction and a target distance in the moving of each component, the defining being executed in accordance with the target moving vector.
22. A compacting method as claimed in claim 1, wherein:
the moving objects further comprise via-holes and semiconductor cells;
parts of the via-hole at every layer, the semiconductor cells, profiles of the components being handled as the terminals;
a combination unit of the component and the via-hole being, as a whole, handled as single component; and
the via-hole connected to only wire being handled as one of the components.
23. A compacting method as claimed in claim 1, wherein:
the moving objects further comprise polygons obtained by approximating conductors;
each of the polygons being handled as the component while edges of the edge polygon being handled as the terminals.
24. A layout compaction apparatus adapted, responsive to original layout data of a circuit layout, to virtually compact the circuit layout, and thereby, to produce compacted layout data of a compacted circuit layout, the circuit layout having a plurality of layers on which moving objects form layer patterns, the moving objects comprising components and wires, ones of the wires being laid on the respective layers in bundles to form wire bundles, each of the wires having a wire width and a pattern shape as a wire pattern shape, each of the wire bundles having a pattern shape as a bundle pattern shape and a bundle width defined by a total width of wires of each wire bundle, said layout compaction apparatus comprising:
a processor; and
a memory including software instructions adapted to enable said processor to cause the layout compaction apparatus to perform, for each of the layer patterns on each of the layers;
assuming a graph problem where a graph comprises nodes corresponding to the components and edges corresponding to moving vectors of the components under first through fourth condition;
the first condition being that the wire widths of the wires are fixed at constant wire width values;
the second condition being that belt widths of wire belts are fixed at constant belt width values, the wire belts defined by adding predetermined margins to both sides in a width direction of each of the wire bundles in compliance with a design rule, each of the belt widths being equal to a sum of each of the bundle widths and the predetermined margins;
the third condition being that component-wire spaces are variable, each of the component-wire spaces being defined to be a distance from the component to edges in the width direction of the wire belts and/or the wires; and
the fourth condition being that wire pattern shape and the bundle pattern shape are changeable for compacting;
solving the graph problem to determine a moving order, a moving direction, and a moving distance of each component; and
virtually moving each component according to the moving order, the moving direction and the moving distance, to obtain the compacted layout data of the compacted circuit layout.
25. A layout compaction apparatus as claimed in claim 24, the components having terminals, wherein the memory further includes software instructions adapted to enable the layout compaction apparatus further to perform the assuming so as to include, for each layer pattern:
extracting the terminals from the components;
defining a terminal constraint graph in relation to a pair of particular terminals selected among the terminals of all components, the particular terminals being close to each other in a predetermined direction and belonging to different components from one to another, the particular terminals being assigned to nodes at both ends of the terminal constraint graph, the terminal constraint graph having, as a weight, a maximum movable range of one of the particular terminals in a case where the one particular terminals is moved for the other particular terminal in the predetermined direction; and
processing the terminal constraint graph with reference to the components having the terminals defined as the nodes for the terminal constraint graph to obtain the graph bringing out the compacted layout data of the circuit layout compacted in the predetermined direction.
26. A layout compaction apparatus as claimed in claim 25, wherein the memory further includes software instructions adapted to enable the layout compaction apparatus further to perform the defining so as to include assigning a minus value to the weight of the terminal constraint graph in a case where the wire and/or the wire belt are laid traversely to a virtual line connecting between the particular terminals and whether or not a length of the virtual line is shorter than another length required by the design rule in accordance with the wire width and/or the belt within, otherwise assigning a plus value to the weight.
27. A layout compaction apparatus as claimed in claim 26, wherein the memory further includes software instructions adapted to enable the layout compaction apparatus further to perform the processing so as to include, after the defining being executed for all of the layer patterns, determining a component constraint graph on the basis of the terminal constraint graphs of all layer patterns, the component constraint graph having, as a weight, a minimum one among the weights of the terminal constrain graphs, the particular terminals being assigned to nodes at both ends of the component constraint graph, the graph comprising the component constraint graph.
28. A layout compaction apparatus as claimed in claim 27, wherein the memory further includes software instructions adapted to enable the layout compaction apparatus further to perform the assuming so that:
the defining is repeatedly executed for all pairs of the particular terminals each selected among the terminals of all components at every layer pattern, to obtain the terminal constraint graphs in relation to all pairs;
the determining is repeatedly executed for all of the terminal constraint graphs; and
the processing is further performed, for each layer pattern and after the determining being executed for all of the terminal constraint graphs, by joining the component constraint graphs with reference to the nodes for the component constraint graphs to obtain the graph.
29. A layout compaction apparatus as claimed in claim 28, wherein the memory further includes software instructions adapted to enable the layout compaction apparatus further to perform the assuming so as to assume a shortest path problem as the graph problem, the graph having a particular nodes as a starting point.
30. A layout compaction apparatus as claimed in claim 29, wherein the memory further includes software instructions adapted to enable the layout compaction apparatus further to perform the solving so as to include utilizing the Dijkstra method.
31. A layout compaction apparatus as claimed in claim 29, the circuit layout being formed on a substrate region having a corner, wherein the memory further includes software instructions adapted to enable the layout compaction apparatus further to perform the assuming so as to include:
prior to the defining, picking up the corner to handle the corner as the terminal; and
further defining, for each layer pattern, the terminal constraint graph in a chase where the corner and the terminal closed to the corner are handled as the pair of particular terminals, the closest terminal serving as the one particular terminal, while the corner serving as the other particular terminal, the node corresponding to the corner being the particular node in the graph.
32. A layout compaction apparatus as claimed in claim 31, wherein the memory further includes software instructions adapted to enable the layout compaction apparatus further to perform, after the virtually moving judging whether the wire and/or the wire belt are laid traversely to a virtual line connecting between the particular terminals; and re-wiring the wire and/or the wire belt, in question, in consideration of an allowable form of the design rule.
33. A layout compaction apparatus as claimed in claim 32, the substrate region having a bottom line extending from the corner, wherein the memory further includes software instructions adapted to enable the layout compaction apparatus further to perform the re-wiring so as to include selecting, as the allowable form, one of a vertical form, a horizontal form, and a diagonal form to the bottom line, and a combination thereof.
34. A layout compaction apparatus as claimed in claim 28, wherein the memory further includes software instructions adapted to enable the layout compaction apparatus further to perform:
defining additional terminal constraint graphs relating to the pairs of the particular terminals in the case of compacting in a perpendicular direction to the predetermined direction, according to the same way of defining the terminal constraint graphs;
determining additional component constraint graphs on the basis of the additional terminal constraint graphs of all layer patterns, according to the same way of determining the component constraint graphs;
joining additional component constraint graphs with reference to the nodes for the additional component constraint graphs to obtain an additional graph;
assuming an additional graph problem as an additional shortest path problem in consideration of the additional graph;
solving the additional graph problem to determine a moving order and a moving distance of each component in case of compacting in the perpendicular direction; and
virtually moving each components in the perpendicular direction, according to the moving order and the moving distance, to obtain the compacted layout data of the circuit layout compacted in the perpendicular direction.
35. A layout compaction apparatus as claimed in claim 34, the circuit layout being formed on a substrate region, a shape of the substrate region being a rectangular having vertical lines and horizontal lines in the predetermined and perpendicular directions, respectively, the layout compaction apparatus further comprising an input device adapted to designate a target substrate region, a shape of the target substrate region being another rectangular having target vertical lines and target horizontal lines smaller than the vertical lines and horizontal lines in the predetermined and perpendicular directions, respectively, wherein:
the memory further includes software instructions adapted to enable the layout compaction apparatus further to perform, for each layer pattern and after the components being virtually moved in both the predetermined and the perpendicular directions, and thereby, the circuit layout being once compacted:
identifying an paticular one of the pairs, the movement in the predetermined direction of the one particular terminal of the particular pair causing the once compacted circuit layout to be over the target substrate region in the perpendicular direction; and
removing the terminal constraint graph of the particular pair;
re-assuming the graph problem as a re-assumed graph problem in consideration of the removing;
solving the re-assumed graph problem; and
virtually moving each component in the predetermined direction.
36. A layout compaction apparatus as claimed in claim 28, the circuit layout being formed on a substrate region, wherein the memory further includes software instructions adapted to enable the layout compaction apparatus further to perform the assuming so as to include, after the extracting and prior to the defining: partitioning the substrate region with a plurality of vertical partition lines and a plurality of horizontal partition lines, into a plurality of sections; and picking up the vertical and horizontal partition lines to handle the vertical and horizontal partition lines as the terminals.
37. A layout compaction apparatus as claimed in claim 36, wherein the memory further includes software instructions adapted to enable the layout compaction apparatus further to perform the assuming so as to include, after the picking up end prior to the defining:
detecting whether or not the terminals except for the vertical and horizontal partition lines belong to one of the sections; and
supposing an empty terminal to be placed as the terminal at a center of the one section, in a case where no terminals except for the vertical and horizontal partition lines belong to the one sections.
38. A layout compaction apparatus as claimed in claim 37, wherein the memory further includes software instructions adapted to enable the layout compaction apparatus further to perform the defining so as to, in the case where no terminals except for the vertical and horizontal partition lines belong to the one sections, be repeatedly executed for all of pairs of particular terminals selected among the vertical and horizontal partition lines and the empty terminal in the one section.
39. A layout compaction apparatus as claimed in claim 38, wherein the memory further includes software instructions adapted to enable the layout compaction apparatus further to perform the defining so as to, in a case where a plurality of the terminals except for the vertical and horizontal partition lines belong to the one section, be repeatedly executed for all of the pairs of particular terminals selected among the all terminals which belong to the one section and include the vertical and horizontal partition lines for the one section.
40. A layout compaction apparatus as claimed in claim 39, wherein the memory further includes software instructions adapted to enable the layout compaction apparatus further to perform the defining so as to, in a case where only one terminal except for the vertical and horizontal partition lines belongs to the one section, be repeatedly executed for all of the pairs of particular terminals selected among the vertical and horizontal partition lines and the only one terminal in the one section.
41. A layout compaction apparatus as claimed in claim 39, wherein the memory further includes software instructions adapted to enable the layout compaction apparatus further to perform the virtually moving so as to include virtually moving the vertical and horizontal partition lines, with the movements of the components which have the particular terminals except for the vertical and horizontal partition lines.
42. A layout compaction apparatus as claimed in claim 36, further comprising a display, wherein the memory further includes software instructions adapted to enable the layout compaction apparatus further to perform:
judging whether or not the component of the compacted circuit layout belongs to a predetermined area for the component to be arranged thereon; and
displaying with special emphasis, in the display, an area enclosed with the vertical and the horizontal partition lines, as regard the predetermined area, when the component does not arranged on the predetermined area.
43. A layout compaction apparatus as claimed in claim 25, wherein the memory further includes software instructions adapted to enable the layout compaction apparatus further to perform the assuming so as to include, after the defining and prior to the processing: detecting whether or not the pair of particular terminals are given the same signal; and removing the terminal constraint graph relating to the pair of particular terminals given the same signal.
44. A layout compaction apparatus as claimed in claim 25, wherein the memory further includes software instructions adapted to enable the layout compaction apparatus further to perform the assuming so as to include, prior to the defining, fixing an octagonal restricted region adapted to forbid a center of the one particular terminal to enter inside of the octagonal restriction region, and thereby, to restrict the movement of the one particular terminal, the octagonal restricted region and the other particular terminal having a common center, the defining being carried out under the restriction of the octagonal restricted region.
45. A layout compaction apparatus as claimed in claim 44, wherein the memory further includes software instructions adapted to enable the layout compaction apparatus further to perform the fixing so as to include:
approximating the other particular terminal to obtain a first octagon having a first distance from a center to an edge of the first octagon;
adding the belt width to each of edges of the first octagon to obtain a second octagon having a second distance from a center to an edge of the second octagon, the second distance being equal to a sum of the belt with and the first distance;
approximating the one particular terminal to obtain a third octagon having a third distance from a center to an edge of the third octagon; and
adding the third distance to each of edges of the second octagon to determine a shape and a size of the octagonal restricted region, the shape having a fourth distance from a center to an edge of the shape, in question, the fourth distance being equal to a sum of the second distance and the third distance.
46. A layout compaction apparatus as claimed in claim 25, further comprising an input device adapted to designable a target moving vector having a target direction and a target distance in the virtually moving of each component, wherein the memory further includes software instructions adapted to enable the layout compaction apparatus further to perform the defining so as to be executed in accordance with the target moving vector.
47. A layout compaction apparatus as claimed in claim 24, the moving objects further comprising via-holes and semiconductor cells, wherein the memory further includes software instructions adapted to enable the layout compaction apparatus further to perform the assuming so as to include:
handling parts of the via-hole at every layer, the semiconductor cells, profiles of the components as the terminals;
handling a combination unit of the component and the via-hole being, as a whole, as single component; and
handling the via-hole connected to only wire as one of the components.
48. A layout compaction apparatus as claimed in claim 24, the moving objects further comprising polygons obtained by approximating conductors, wherein the memory further includes software instructions adapted to enable the layout compaction apparatus further to perform the assuming so as to include:
handling each of the polygons as the component; and
handling edges of the each polygon as the terminals.
49. A layout compaction apparatus as claimed in claim 24, further comprising an input device adapted to designate a change of an arrangement of the component and the wire in the original layout data, wherein the memory further includes software instructions adapted to enable the layout compaction apparatus further to perform:
changing the arrangement of the component and the wire in the original layout data, according to the designation with the input device, to produce a newly layout data; and
inputting the newly layout data into the assuming.
50. A layout compaction apparatus as claimed in claim 49, further comprising a display, wherein the memory further includes software instructions adapted to enable the layout compaction apparatus further to perform:
judging whether or not the changing brings about a violation of the design rule; and
displaying with special emphasis, in the display, an area on the circuit layout in accordance with the violation.
51. A layout compaction apparatus as claimed in claim 24, further comprising an input device adapted to designate a mutual replacement between one of the components and one of the wires, or between ones of the wires, wherein the memory further includes software instructions adapted to enable the layout compaction apparatus further to perform executing the mutual replacement for layout data.
52. A computer program product for enabling a processor to work as a layout compaction apparatus adapted, responsive to original layout data of a circuit layout, to virtually compacted the circuit layout, and thereby, to produce compacted layout data of a compacted circuit layout, the circuit layout having a plurality of layers on which moving objects form layer patterns, the moving objects comprising components and wires, ones of the wires being laid on the respective layers in bundles to form wire bundles, each of the wires having a wire width and a pattern shape as a wire pattern shape, each of the wire bundles having a pattern shape as a bundle pattern shape and a bundle width defined by a total width of wires of each wire bundle, said computer program, product comprising:
software instructions for enabling the processor to perform predetermined operations; and
a computer readable medium bearing the software instructions;
the predetermined operations including, for each of the layer patterns on each of the layers;
assuming a graph problem where a graph comprises nodes corresponding to the components and edges corresponding to moving vectors of the components under first through fourth condition;
the first condition being the wire widths of the wires are fixed at constant wire width values;
the second condition being that bell widths of wire belts are fixed at constant belt width values, the wire bells defined by adding predetermined margins to both sides in a width direction of each of the wire bundles in compliance with a design rule, each of the belt widths being equal to a sum of each of the bundle widths and the predetermined margins;
the third condition being that component-wire spaces are variable, each of the component-wire spaces being defined to be a distance from the component to edges in the width direction of the wire belts and/or the wires; and
the fourth condition being that wire pattern shape and the bundle pattern shape are changeable for compacting;
solving the graph problem to determine a moving order, a moving direction, and a moving distance of each component; and
virtually moving each component according to the moving order, the moving direction and the moving distance, to obtain the compacted layout data of the compacted circuit layout.
53. A computer program product as claimed in claim 52, the components having terminals, wherein the assuming is performed so as to include, for each layer pattern:
extracting the terminals from the components;
defining a terminal constraint graph in relation to a pair of particular terminals selected among the terminals of all components, the particular terminals being close to each other in a predetermined direction and belonging to different components from one to another, the particular terminals being assigned to nodes at both ends of the terminal constraint graph, the terminal constraint graph having, as a weight, a maximum movable range of one of the particular terminals in a case where the one particular terminals is moved for the other particular terminal in the predetermined direction; and
processing the terminal constraint graph with reference to the components having the terminals defined as the nodes for the terminal constraint graph to obtain the graph bringing out the compacted layout data of the circuit layout compacted in the predetermined direction.
54. A computer program product as claimed in claim 53, wherein the defining is performed so as to include assigning a minus value to the weight of the terminal constraint graph in a case where the wire and/or the wire belt are laid traversely to a virtual line connecting between the particular terminals and whether or not a length of the virtual line is shorter than another length required by the design rule in accordance with the wire width and/or the belt width, otherwise assigning a pus value to the weight.
55. A computer program product as claimed in claim 54, wherein the processing is performed so as to include, after the defining being executed for all of the layer patterns, determining a component constraint graph on the basis of the terminal constraint graphs of all layer patterns, the component constraint graph having, as a weight, a minimum one among the weights of the terminal constraint graphs, the particular terminals being assigned to nodes at both ends of the component constraint graph, the graph comprising the component constraint graph.
56. A computer program product as claimed in claim 55, wherein the assuming is performed so that:
the defining is repeatedly executed for all pairs of the particular terminals each selected among the terminals of all components at every layer pattern, to obtain the terminal constraint graphs in relation to all pairs;
the determining is repeatedly executed for all the terminal constraint graphs; and
the processing is further performed, for each layer pattern and after the determining being executed for all of the terminal constraint graphs, by joining the component constraint graphs with reference to the nodes for the component constraint graphs to obtain the graph.
57. A computer program product as claimed in claim 56, wherein the assuming is performed so as to assume a shortest path problem as the graph problem, the graph having a particular nodes as a starting point.
58. A computer program product as claimed in claim 57, wherein the solving is performed so as to include utilizing the Dijkstra method.
59. A computer program product as claimed in claim 57, the circuit layout being formed on a substrate region having a corner, wherein the assuming is performed so as to include:
prior to the defining, picking up the corner to handle the corner as the terminal; and
defining, for each layer pattern, the terminal constraint graph in a case where the corner and the terminal closest to the corner are handled as the pair of particular terminals, the closest terminal serving as the one particular terminal, while the corner serving as the other particular terminal, the mode corresponding to the corner being the particular node in the graph.
60. A computer program product as claimed in claim 59, wherein the predetermined operations including, after the virtually moving: judging whether the wire and/or the wire belt are laid traversely to a virtual line connecting between the particular terminal; and re-wiring the wire and/or the wire belt, in question, in consideration of an allowable form of the design rule.
61. A computer program product as claimed in claim 60, the substrate region having a bottom line extending from the corner, wherein the re-wiring is performed so as to include selecting, as the allowable form, one of a vertical form, a horizontal form, and a diagonal form to the bottom line, and a combination thereof.
62. A computer program product as claimed in claim 57, wherein the predetermined operations further includes:
defining additional terminal constraint graphs relating to the pairs of the particular terminals in the case of compacting in a perpendicular direction to the predetermined direction, according to the same way of defining the terminal constraint graphs;
determining additional component constraint graphs on the basis of the additional terminal constraint graphs of all layer patterns, according to the same way of determining the component constraint graphs;
joining additional component constraint graphs with reference to the nodes for the additional component constraint graphs to obtain an additional graph;
assuming an additional graph problem as an additional shortest path problem in consideration of the additional graph;
solving the additional graph problem to determine a moving order and a moving distance of each component in case of compacting in the perpendicular direction; and
virtually moving each components in the perpendicular direction, according to the moving order and the moving distance, to obtain the compacted layout data of the circuit layout compacted in the perpendicular direction.
63. A computer program product as claimed in claim 62, the circuit layout being formed on a substrate region, a shape of the substrate region being a rectangular having vertical lines and horizontal lines in the predetermined and perpendicular directions, respectively, the computer program further for enabling the processor to execute a processing in accordance with requests inputted through an input device, the input device adapted to designate a target substrate region, a shape of the target substrate region being another rectangular having target vertical lines and target horizontal lines smaller than the vertical lines and horizontal lines in the predetermined and perpendicular directions, respectively, wherein:
the predetermined operations further include, for each layer pattern and after the components being virtually moved in both of the predetermined and the perpendicular directions, and thereby, the circuit layout being once compacted:
identifying an particular one of the pairs, the movement in the predetermined direction of the one particular terminal of the particular pair causing the once compacted circuit layout to be over the target substrate region in the perpendicular direction; and
removing the terminal constraint graph of the particular pair;
re-assuming the graph problem as a re-assumed graph problem in consideration of the removing.
solving the re-assumed graph problem; and
virtually moving each component in the predetermined direction.
64. A computer program product as claimed in claim 56, the circuit layout being formed on a substrate region, wherein the assuming is performed so as to include, after the extracting and prior in the defining partitioning the substrate region with a plurality of vertical partition lines and a plurality of horizontal partition lines, into a plurality of sections; and picking up the vertical and horizontal partition lines to handle the vertical and horizontal partition lines as the terminals.
65. A computer program product as claimed in claim 64, wherein the assuming is performed so as to include, after the picking up and prior to the defining:
detecting whether or not the terminals except for the vertical and horizontal partition lines belong to one of the sections; and
supposing an empty terminal to be placed as the terminal at a center of the one section, in a case where no terminals except for the vertical and horizontal partition lines belong to the one sections.
66. A computer program product as claimed in claim 65, wherein the defining is performed so as to, in the case where no terminals except for the vertical and horizontal partition lines belong to the one sections, be repeatedly executed for all of pairs of particular terminals selected among the vertical and horizontal partition lines and the empty terminal in the one section.
67. A computer program product as claimed in claim 66, wherein the defining is performed so as to, in a case where a plurality of the terminals except for the vertical and horizontal partition lines belong to the one section, be repeatedly executed for all of the pairs of particular terminals selected among the all terminals which belong to the one section and include the vertical and horizontal partition lines for the one section.
68. A computer program product as claimed in claim 67, wherein the defining is performed so as to, in a case where only one terminal except for the vertical and horizontal partition lines belongs to the one section, be repeatedly executed for all of the pairs of particular terminals selected among the vertical and horizontal partition lines and the only one terminal in the one section.
69. A computer program product as claimed in claim 64, wherein the virtually moving is performed so as to include virtually moving the vertical and horizontal partition lines, with the movements of the components which have the particular terminals except for the vertical and horizontal partition lines.
70. A computer program product as claimed in claim 64, further for enabling the processor to control displaying in a display, wherein the predetermined operations further include:
judging whether or not the component of the compacted circuit layout belongs to a predetermined area for the component to be arranged thereon; and
displaying with special emphasis, in the display, an area enclosed with the vertical and the horizontal partition lines, as regard the predetermined area, when the component does not arranged on the predetermined area.
71. A computer program product as claimed in claim 53, wherein the assuming is performed so as to include, after the defining and prior to the processing: detecting whether or not the pair of particular terminals are given the same signal; and removing the terminal constraint graph relating to the pair of particular terminal given the same signal.
72. A computer program product as claimed in claim 53, wherein the assuming is performed so as to include, prior to the defining, fixing an octagonal restricted region adapted to forbid a center of the one particular terminal to enter inside of the octagonal restriction region, and thereby, to restrict the movement of the one particular terminal, the octagonal restricted region and the other particular terminal having a common center, the defining being carried out under the restriction of the octagonal restricted region.
73. A computer program product as claimed in claim 72, wherein the fixing is performed so as to include:
approximating the other particular terminal to obtain a first octagon having a first distance from a center to an edge of the first octagon;
adding the belt width to each of edges of the first octagon to obtain a second octagon having a second distance from a center to an edge of the second octagon, the second distance being equal to a sum of the belt width and the first distance;
approximating the one particular terminal to obtain a third octagon having a third distance from a center to an edge of the third octagon; and
adding the third distance to each of edges of the second octagon to determine a shape and a size of the octagonal restricted region, the shape having a fourth distance from a center to an edge of the shape, in question, the fourth distance being equal to a sum of the second distance and the third distance.
74. A computer program product as claimed in claim 53, further for enabling the processor to execute a processing in accordance with requests inputted through an input device, the input device adapted to designate a target moving vector having a target direction and a target distance in the virtually moving of each component, wherein the defining is performed so as to be executed in accordance with the target moving vector.
75. A computer program product as claimed in claim 52, the moving objects further comprising via-holes and semiconductor cells, wherein the assuming is performed so as to include:
handling parts of the via-hole at every layer, the semiconductor cells, profiles of the components as the terminals;
handling a combination unit of the component and the via-hole being, as a whole, as single component; and
handling the via-hole connected to only wire as one of the components.
76. A computer program product as claimed in claim 52, the moving objects further comprising polygons obtained by approximating conductors, wherein the assuming is performed so as to include:
handling each of the polygons as the component; and
handling edges of the each polygon as the terminals.
77. A computer program product as claimed in claim 52, further for enabling the processor to execute a processing in accordance with requests inputted through an input device, the input device adapted to designate a change of an arrangement of the component and the wire in the original layout data, wherein the predetermined operations further include:
changing the arrangement of the component and the wire in the original layout data, according to the designation with the input device, to produce a newly layout data; and
inputting the newly layout data into the assuming.
78. A computer program product as claimed in claim 77, further for enabling the processor to control displaying in a display, wherein the predetermined operations further include:
judging whether or not the changing brings about a violation of the design rule; and
displaying with special emphasis, in the display, an area on the circuit design rule; and
displaying with special emphasis, in the display, an area on the circuit layout in accordance with the violation.
79. A computer program product as claimed in claim 52, further for enabling the processor to execute a processing in accordance with requests inputted through an input device, the input device adapted to designate a mutual replacement between one of the components and one of the wires, or between ones of the wires, wherein the predetermined operations further include executing the mutual replacement for layout data.
Description
BACKGROUND OF THE INVENTION
This invention relates to a layout compaction system as used in designing a layout of VLSI or another layout on a printed circuit board, and, in particular, to the compaction system which can automatically provide a small-sized VLSI.
The VLSI has been of high density, so that human can no longer manually design the VLSI. To aid the designing of the VLSI, some kind of EDA (electronic design automation) tools are used in the art of the VLSI design. Especially, layout compaction systems are adapted to automatically compact a circuit layout and work in a layout design phase.
In general, the circuit layout is formed on a substrate and comprises a plurality of layers on each of which objects are arranged as a layer pattern. When the objects are moved in a certain direction, free space is obtained in the opposite direction and enables the layout compaction system to compact the circuit layout. Such objects will be called moving objects, hereinafter.
In detail, the moving objects comprise components, wires, via-holes, semiconductor cells, and so on. Among them, some of the wires are laid on the respective layers in bundles, and some of the components extend over layers. Although each of the components has terminals, all terminals belonging to one component may exist on layers.
The layout compaction system requires taking the complicated structure of the circuit layout into consideration, otherwise the compacted circuit layout may not perform correctly. Besides, there is requirement for the compaction to be high rate. To respond these requirements, various kinds of the compacting methods have been developed and proposed.
In some of the proposed methods, the circuit layout is compacted by moving components as moving objects in relation with each other.
One of them relates to two-dimensional compaction, where the components are simultaneously moved in two directions. Such compacting method is, for example, disclosed in "Two-Dimensional Compaction by `Zone Refining`: Hynchul Shin, Alberto L. Sangiovanni-Vincentelli, Carlo H. Sequin; Proc. of 23rd Design Automation Conference, 1986, pp. 115-122." In summary, the compacting method moves the semiconductor cells in a vertical direction of the circuit layout from upper side one to down, and simultaneously moves the semiconductor cells in a horizontal direction of the circuit layout.
Another compacting method is disclosed in Japanese Unexamined Patent Publication No. Hei 5-274392, namely, JP-A 5-274392. In this method, the substrate is divided at positions of wires into a plurality of regions. That is, on all boundaries between the regions, the wires are always laid. Under the condition, the compaction in the horizontal direction is executed from the regions closer to the left side of the substrate to right, and simultaneously the compaction in the vertical direction is executed from the regions closer to the upper side of the substrate to down. Thus, the method keeps an arrangement of the regions, and provides uniformly compacted circuit layout.
However, the above-mentioned methods can not handle wiring of the diagonal form, and therefore, can not accomplish the high rate of the compaction.
On the other hand, the method which can handle wiring of the diagonal form, is disclosed in Japanese Unexamined Patent Publication (JP-A) No. Hei 10-3491, namely, JP-A 10-3491. This method removes all of the wires from the circuit layout, and then, compacts the circuit layout by moving the component together with re-wiring of newly wires.
It is however noted that the newly wires bring about another problem since consideration has been made about only the moving of the component. Some of wires are laid on the layers in bundle to form wire bundle. If not taking the characteristic of the circuit into consideration, the wire bundle has a width substantially equal to the total sum of the width of the wires comprising the wire bundle. Actually, predetermined margins however are required between the adjacent wires, to prevent cross talk from occurring between the adjacent wires. Such margins are fixed in the design rule for the compaction targets, such as the VLSI. The above method of JP-A 10-3491 does not consider such characteristic, and thereby, may violate the design rule.
SUMMARY OF THE INVENTION
This invention therefore provides a compacting method which can handle wiring of the diagonal form with a relationship of the components and the wires kept, and which can meet the design rule.
According to one aspect of this invention, a compacting method compacts a circuit layout having a plurality of layers on which moving objects form layer patterns. For example, the moving objects comprise components having terminals, wires, via-holes, semiconductor cells, conductors having predetermined pattern shapes. In this specification, parts of the via-hole at every layer, the semiconductor cells, profiles of the components may be handled as the terminal. A combination unit of the component and the via-hole may be, as a whole, handled as single component. The via-hole connected to only wire may be handled as one of the components. The conductors may be approximated into polygons, each of the polygons being handled as the component, while edges of each polygon begin handled as the terminals. These handling are for the sake of clarity and for readily processing, which do not restrict this invention.
Some of the wires are laid on the respective layers in bundles to form wire bundles. Each of the wires having a wire width and a pattern shape as a wire pattern shape. Each of the wire bundles having a pattern shape as a bundle pattern shape and a bundle width which is defined by a total width of wires comprising each wire bundle.
The method comprises the following three steps for each of the layer patterns on each of the layers.
First, a graph problem is assumed under first through fourth condition, wherein a graph comprises nodes corresponding to the components and edges corresponding to moving vectors of the components. The first condition is that the wire widths of the wires are fixed at constant wire width values. The second condition is that belt widths of wire belts are fixed at constant belt width values. The wire belts are defined by adding predetermined margins to both sides in a width direction of each of the wire bundles in compliance with a design rule. Each of the belt widths is equal to a sum of each of the bundle widths and the predetermined margins. The third condition is that component-wire spaces are variable. Each of the component-wire spaces is defined to be a distance from the component to edges in the width direction of the wire belts and/or the wires. The fourth condition is that wire pattern shape and the bundle pattern shape are changeable for compacting.
When assumed, the graph problem is solved so that a moving order, a moving direction, and a moving distance of each component are determined for moving the components. And then, each component is moved according to the moving order, the moving direction and the moving distance.
With this method, the compacted circuit layout does not have the problem, such as cross talk, because the assumption of the graph problem takes the design rule into consideration and, as the solution, the moving vectors of the components are determined. The method may be in the form of software instructions and be executed on a computer (or by a processor) virtually. In this case, the computer applies the method original layout data of the circuit layout to produce compacted layout data of the compacted circuit layout.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a view for use in describing definitions of wire bundle, wire belt and so forth;
FIG. 2 is a view for use in describing the extracting terminals from components;
FIG. 3 is a view for use in describing the defining terminal constraint graph;
FIG. 4 is a view for use in describing the determining component constraint graph;
FIG. 5 is a view for use in describing the assuming graph problem;
FIG. 6 is a view for use in describing the solving graph problem;
FIG. 7 is a view of use in describing the moving components;
FIG. 8 is a view for use in describing the octagonal restricted region;
FIG. 9 is a view for use in describing the fixing octagonal restricted region;
FIG. 10 is a view for use in describing the partitioning substrate region into sections;
FIG. 11 is a view for use in describing the assuming empty terminal;
FIG. 12 shows, in schematic form, a computer system of a layout compaction apparatus;
FIG. 13 is a flow-chart showing operations according to a first example;
FIG. 14 shows a data structure of piece data of a terminal, a part of via-hole, and so on;
FIG. 15 shows a data structure of piece data of a wire, an edge of polygon, and so forth;
FIG. 16 shows a data structure of location data;
FIG. 17 shows a data structure of shape data;
FIG. 18 shows a data structure of section data;
FIG. 19 shows a data structure of piece data of a partition line;
FIG. 20 is a view for use in describing the accommodating the terminals into the section;
FIG. 21 shows a data structure of constraint graph data;
FIG. 22 shows a data structure of constraint graph order data;
FIG. 23 shows a data structure of terminal constraint graph data;
FIG. 24 shows a data structure of component constraint graph data;
FIG. 25 is a view for use in describing the defining the terminal constraint graph;
FIG. 26 is a view for use in describing the calculating maximum movable range;
FIG. 27 shows a data structure of wire limited location data;
FIG. 28 is a view for use in describing the fixing restricted region of wiring;
FIG. 29 is a view for use in describing an operation of the first example;
FIG. 30 is a view for use in describing another operation of the first example;
FIG. 31 is a view for use in describing another operation of the first example;
FIG. 32 is a flow-chart showing operations of a second example;
FIG. 33 is a view for use in describing an operation of the second example;
FIG. 34 is a view for use in describing an allowable distance of the component;
FIG. 35 is a view for use in describing another operation of the second example;
FIG. 36 is a view for use in describing an actual width between the terminals in the X-direction;
FIG. 37 is a view for use in describing another operation of the second example;
FIG. 38 is a view for use in describing another operation of the second example;
FIG. 39 shows a data structure of component moving vector data;
FIG. 40 is a view for use in describing another operation of the second example;
FIG. 41 is a view for use in describing another operation of the second example;
FIGS. 42A and 42B are views for use in describing another operation of the second example;
FIG. 43 is a flow-chart showing operations of a third example;
FIG. 44 is a view for use in describing an operation of a fourth example;
FIG. 45 is a view for use in describing another operation of the fourth example;
FIG. 46 is a view for use in describing another operation of the fourth example;
FIG. 47 is a view for use in describing an operation of a fifth example;
FIG. 48 is a view for use in describing another operation of the fifth example;
FIG. 49 is a view for use in describing another operation of the fifth example;
FIG. 50 is a view for use in describing another operation of the fifth example;
FIG. 51 is a view for use in describing another operation of the sixth example;
FIG. 52 is a view for use in describing another operation of the sixth example;
FIG. 53 is a view for use in describing another operation of the sixth example;
FIG. 54 is a view for use in describing another operation of the sixth example;
FIG. 55 is a view for use in describing another operation of the sixth example;
FIG. 56 is a view for use in describing another operation of the sixth example; and
FIG. 57 is a view for use in describing another operation of the sixth example;
DESCRIPTION OF THE PREFERRED EMBODIMENTS
On actual circuit layout, a wire bundle is arranged, as illustrated in upper side of FIG. 1, and required margins to prevent the mutual interference from occurring. Taking this into consideration, a wire belt is defined in this specification, as shown in lower side of FIG. 1. Provided that widths of the wire, the wire bundle, and the margin are W.sub.W, W.sub.B (=total of W.sub.W) and W.sub.M, respectively, the wire belt has a belt width W.sub.WB equal to W.sub.B and W.sub.M s. Specifically, the compacting method of this invention fixes both the belt width W.sub.WB and the wire width W.sub.W at constant values and, on the other hand, the pattern shapes of the wire and the wire bundle are changeable. Besides, component-wire spaces are variable, each of the component-wire spaces being defined to be a distance from the component to edges in the width direction of the wire belts and/or the wires.
Under the condition, the graph problem is assumed for each layer pattern, wherein a graph comprises nodes corresponding to components and edges corresponding to moving vectors of the components.
In detail, terminals are extracted from the components for each layer pattern, as illustrated in FIG. 2. Parts of via-holes are handled as the terminals, and are represented at each layer pattern. Also, semiconductor cells and profiles of the components are handled as the terminal, in this embodiment. A combination unit of the component and the via-hole is, as a whole, handled as single component and the via-hole connected to only wire may be handled as one of the components, in this embodiment. Furthermore, conductors are approximated into polygons, each of the polygons being handled as the component, while edges of each polygon being handled as the terminals, in this embodiment.
Each terminal T.sub.ij,k is given a unique terminal number "i" at each layer, a component number "j" indicative of the component corresponding to the terminal, and a layer number "k", so as to be distinguish from other terminals. For example, the terminal T.sub.1,1,1 and the terminal T.sub.2,1,1 exist on the first layer and belong to the same component C.sub.1, but the terminal T.sub.3,2,1 and the terminal T.sub.1,1,3 are exist on layers different from each other, and besides, belong to different components C.sub.2, C.sub.1.
In this embodiment, compaction process is repeatedly carried out for first and second compaction directions which are perpendicular to each other, such as X- and Y- direction on X-Y coordinates.
When terminals T.sub.ij,k are obtained, the first compaction direction is selected and terminal constraint graphs (TCGs) for the first compaction direction are defined, as shown in FIG. 3. Such definitions are executed for each layer pattern. Each of the terminal constraint graphs relates to a pair of particular terminals selected among the terminals of all components. The particular terminals are close to each other in the first compaction direction and belong to different components from one to another. Specifically, one of the particular terminals, which is down one in the first compaction direction, is also represented by "T.sub.D ", while the other particular terminal, which is upper one in the first compaction direction, is also represented by "T.sub.U."
The particular terminals T.sub.D and T.sub.U are assigned to nodes at both ends of the terminal constraint graph. The nodes for the terminal constraint graph are represented by N.sub.ij,k, where "i", "j" and "k" mean the same ones of the T.sub.ij,k.
The terminal constraint graph has, as a weight, a maximum movable range of the particular terminal T.sub.D when the particular terminal T.sub.D is moved for the particular terminal T.sub.U in the first compaction direction. If the wire or the wire bundle traverses between the particular terminals T.sub.D and T.sub.U, the movable range is restricted by the wire width or the belt width, and thereby, the weight of the terminal constraint graph becomes light in comparison with the case of no wire traversing. Furthermore, there is a case where the distance between the particular terminals T.sub.D and T.sub.U in the first compaction direction is shorter than another distance required by the design rule in accordance with the wire width and/or the belt width. In this case, the maximum movable range has a minus value, so that the weight of the terminal constraint graph is negative. Otherwise, the maximum movable range has a plus value, so that the weigh of the terminal constraint graph is positive.
Such defining of the terminal constraint graph is repeatedly executed for all pairs of the particular terminals T.sub.U and T.sub.D, each pair of which are selected among the terminals of all components at every layer pattern, so as to obtain the terminal constraint graphs in relation to all pairs.
At this time, a corner of a substrate region, on which the circuit layout is formed, is handled as the terminal, in this embodiment. The corner is upper one of both of the first and second compaction directions, such as lower-left corner in a case of the first and second compaction directions being toward left and lower, respectively. Also, the above definition of the terminal constraint graph is executed in relation with a case where the corner and the terminal closes to the corner are handled as the pair of particular terminals. The pair including the corner is called a particular pair, wherein the closest terminal serves as the particular terminal T.sub.D, while the corner serves as the particular terminal T.sub.U. The node corresponding to the corner is called a particular node in the graph and is utilized, in solving the shortest path problem of the graph, as a starting point. About this, detail explanation will be made in later.
After the definition of all terminal constraint graphs for all of the layer patterns, determination is made about component constraint graphs (CCGs) on the basis of the terminal constraint graphs of all layer patterns, as shown in FIG. 4.
With reference to nodes for the terminal constraint graphs, a group of the pairs, in which the particular terminals belong two certain components, are selected. In FIG. 4, the nodes corresponding to the components C.sub.1 and C.sub.4 are selected so that the terminal constraint graphs are also selected. And then, the components C.sub.1 and C.sub.4 are assigned to nodes for the component constraint graph. The nodes for the component constraint graph are referred to as N.sub.cj, where "j" is used as the same meaning "j" of T.sub.ij,k, and especially, the node corresponding to the corner is represented as N.sub.0.0.
A weight of each component constraint graph is determined to be a minimum one among the weights of the terminal constraint graphs relating to the respective pairs. For example, the weight of the terminal constraint graph on the second layer is smaller than the weights of the terminal constraint graphs on the first and the other layers, in FIG. 4. Therefore, the weight of the component constraint graph is selected so as to be the weight of the terminal constraint graph on the second layer. Such determination of the component constraint graphs is repeatedly executed for all of the terminal constraint graphs.
When the determining is executed for all of the terminal constraint graphs, the graph is, for each layer pattern, created about all components existing of the layer, in question. In detail, the component constraint graphs are joined, with reference to the nodes for the component constraint graphs, so that the graph is obtained, as shown in FIG. 5. The illustrated graph is for the first layer, where numbers added to edges indicate the weights of the edges, respectively.
On the basis of the above graph, the graph problem is solved to determine a moving order and a moving distance of each component on each layer responding to the graph. Specifically, the graph problem is the shortest path problem, wherein the particular node N.sub.0,0 is the starting point. The shortest path problem is solved by utilizing, for example, the Dijkstra method. The solution of the graph problem shown in FIG. 5 is illustrated in FIG. 6, where lengths of shortest paths to the respective nodes are written into the circle representative of the nodes. The shortest path shows that the components C.sub.1.about.C.sub.7 should be moved in order of C.sub.1, C.sub.2, C.sub.7, C.sub.3, C.sub.4, C.sub.6, and C.sub.5, and that the moving distances of the components C.sub.1.about.C.sub.7 should be 1, 3, 6, 7, 10, 8, and 4, respectively.
After the solving, each component is moved according to the moving order and the moving distance in the compaction direction. In the above example, the components C.sub.1, C.sub.2, C.sub.7, C.sub.3, C.sub.4, C.sub.8, and C.sub.5 are moved in this order and with the moving distances 1, 3, 4, 6, 7, 8, and 10, respectively. The above solving and the moving are executed for all layer patterns, so that the compaction in the first compaction direction is achieved.
After the compaction in the first compaction direction, next compaction is executed in the second compaction direction, by the same way of the first compaction direction. As the result, each of the components is moved in the second compaction direction, according to the moving order and the moving distance obtained by solving the graph problem in a case of the second compaction direction. Thus, the compactions are executed in both compaction directions, resulting in the compacted circuit layout.
With this method, the widths of the wire and the wire bundle are considered at the defining step of the terminal constraint graph. In addition, the component constraint graph is determined, in consideration of the terminal constraint graphs of all layers, so that the movements of the components on every layer are consistent with each other. Thus, the compacted circuit layout can meed the requirement of the design rule.
The above-mentioned method may comprise the following steps, in connection with wiring. After the moving of the component, the method may at first judge whether the wire and/or the wire belt are laid transversely to a virtual line connecting between the particular terminals. And then, the method may execute re-wiring of the wire and/or the wire bundle (wire belt), in question, in consideration of an allowable form of the design rule. Such allowable form may be a selected one of a vertical form, a horizontal form, and a diagonal form to the bottom line of the substrate region, and a combination thereof.
The above-mentioned method can adopt the following modification, prior to the definition of the terminal constraint graphs. If the wire and the wire bundle are changeable in a selected one of the vertical form, the horizontal form and the diagonal form, and the combination thereof, a restricted region for the particular terminal T.sub.D may be an octagon which has a center common to the particular terminal T.sub.U, as shown in FIG. 8. In this modification, an octagonal restricted region is therefore fixed so as to forbid a center of the particular terminal T.sub.D to enter inside of the octagonal restriction region, and thereby, to restrict the movement of the particular terminal T.sub.U within an allowable range of the design rule. And then, the defining of the terminal constraint graph is carried out under the restriction of the octagonal restricted region.
The fixing of the octagonal restricted region may adopt the following steps. Referring to FIG. 9, the particular terminal T.sub.U is at first approximated into a first octagon having a first distance D.sub.1 from a center to an edge of the first octagon. The first distance D.sub.1 is substantially equal to the radius of the circle representative of the particular terminal T.sub.U.
The first octagon is added the belt width to each of the edges of the first octagon, so that a second octagon is obtained. The second octagon has a second distance D.sub.2 from a center to an edge of the second octagon, the second distance D.sub.2 being equal to a sum of the belt width W.sub.WB and the first distance D.sub.1. If the wire bundle does not traverse between the particular terminals, but if the wire traverses between the particular terminals, the second distance D.sub.2 may be a sum of the wire width W.sub.W and the first distance D.sub.1. If no wire is laid between the particular terminals, the second distance D.sub.2 may be equal to the first distance D.sub.1 or a sum of the first distance and a margin width compliant to the design rule.
On the other hand, the particular terminal T.sub.D is also approximated into a third octagon which has a third distance D.sub.3 from a center to an edge of the third octagon.
And then, the third distance D.sub.3 is added to each of edges of the second octagon so that the octagonal restricted region is determined in size and in shape. The octagonal restricted region is a octagon with a fourth distance D.sub.4 from a center to an edge of the octagon, the fourth distance D.sub.4 being equal to a sum of the second distance D.sub.2 and the third distance D.sub.3.
The compacting method according to this embodiment can further adopt the following modification.
Prior to the definition of the terminal constraint graphs, the substrate region is partitioned with a plurality of vertical partition lines (VPLs) and a plurality of horizontal partition lines (HPLs), so that a plurality of sections are obtained, as illustrated in FIG. 10. The illustrated vertical and horizontal partition lines are arranged in the form of hound's-tooth check. Both of the vertical and the horizontal partition lines are also correctively referred to as partition lines (PL). Each length of the vertical and the horizontal partition lines is variable, and accordingly, each size of the sections is variable. The vertical and horizontal partition lines are picked up on the defining, to be handled as the terminals. Herein, the part of the via-hole, the semiconductor cell and the edges of the conductor which is approximated into the polygon, are depicted in FIG. 10, but all are handled as terminals, as mentioned above.
After the partitioning, the sections are changed in size, to accommodate the terminals therewithin, if possible. The number of the terminals accommodated in each section can be selected at the designer direction. With this modification, it serves a lot of trouble if the appropriate partitioning is executed, because it causes the defining to be executed for each section, instead of entire substrate region.
It is then detected whether or not the terminals except for the partition lines belong to one of the sections. As the result, if no terminal belong to the one section, an empty terminal is supposed to be placed as the terminal at a center of the one section, as illustrated in FIG. 11. Besides, the defining step of the terminal constraint graph is repeatedly executed, in the one section, for all of pairs of particular terminals selected among the partition lines and the empty terminal.
If the resultant of the detecting shows that a plurality of the terminals except for the partition lines belong to the one section, the defining is repeatedly executed, in the one section, for all of the pairs of particular terminals selected among the terminals including the partition lines. If only one terminal except for the partition lines belongs to the one section, the defining is repeatedly executed, in the one section, for all of the pairs of particular terminals selected among the partition lines and the only one terminal.
Herein, in case of adopting the concept of section divided, when the components are moved, the partition lines may be also moved in accordance with the movements of the components.
Furthermore, the above-mentioned method of the embodiment can be modified as the following. After the defining of the terminal constraint graph and prior to the determining of the component constraint graph, it is detected whether or not the pair of particular terminals are given the same signal. According to the detecting, the terminal constraint graph relating to the pair of particular terminals given the same signal is removed, and then, the component constraint graph is determined. This removing makes the calculation of the determination easy.
It may be further adopted that a target moving vector is designated, prior to the assuming step of the graph problem. Herein, the target moving vector has a target direction and a target distance in the moving of each component. In this event, the defining of the terminal constraint graph may be executed in accordance with the target moving vector.
Moreover, the above-mentioned method can adopt the following modification, after the circuit layout has been once compacted. It may be required that the compacted circuit layout want to be included within a target size. To meet the requirement, the following modification is effective.
For the sake of clarity, a shape of the substrate region is supposed to be a rectangular having vertical lines and horizontal lines in the predetermined and perpendicular directions, respectively. Also, a shape of a target substrate region is decided to be another rectangular having target vertical lines and target horizontal lines smaller than the vertical lines and horizontal lines in the predetermined and perpendicular direction, respectively.
In this modification, a particular one of the pairs of the particular terminals is identified for each layer pattern, after the circuit layout has been compacted once. If one pair of the particular terminals satisfies a requirement that the movement in the first compaction direction of the particular terminal T.sub.D causes the once compacted circuit layout to be over the target substrate region in the second compaction direction, the one pair is the particular pair. That is, if the path corresponding to the pair is selected in the solving step of the shortest path problem, the compacted circuit layout is not included within a desired size. Therefore, the terminal constraint graph of the particular pair is removed, and then, the graph problem is re-assumed as a re-assumed graph problem in consideration of the removing. When the re-assumed graph problem is solved, and accordingly, each component is moved in the first compaction direction, a sized of the compacted circuit layout comes to be included within or to get closer to the desired size.
It will be appreciated that the above-mentioned embodiment and modifications may be embodied in a computer system for a layout compaction apparatus that contains hardware and software enabling it to perform the foregoing compaction operations, so that the layout compaction apparatus obtains a compacted layout data of the compacted circuit layout from original layout data of the circuit layout.
Now, detail examples will be concretely made about a layout compaction apparatus according to embodiments of the invention, with reference to some drawings. The layout compaction apparatus is adapted, responsive to the original layout data of the circuit layout, to virtually move the components, and thereby, to virtually compact the circuit layout. As the result of virtually compaction, the layout compaction apparatus produces the compacted layout data of the compacted circuit layout.
Such layout compaction apparatus comprises a processor, a memory, an input device and a display, as shown in FIG. 12. I/O interface and various kinds of other computer's components are omitted in FIG. 12, for the sake of simplicity. The illustrated memory includes software instructions adapted to enable the processor to cause the layout compaction apparatus to perform the above-mentioned method. In other ward, the illustrated processor always performs in accordance with the software instructions included in the illustrated memory. The illustrated memory is further adapted to store data processed and/or to be processed by the processor. The memory comprises, for example, an integrated circuit and a hard disk drive. The illustrated input device may comprise a mouse, a keyboard, and a touch-panel apparatus.
In a layout compaction apparatus according to a first example, the processor performs as illustrated in FIG. 13.
When layout data are inputted, the processor produces piece data from the layout data, in the step S100 shown in FIG. 12. Herein, `pieces` are objects to be processed by the processor, and comprise the above-mentioned `terminals` and parts of `wires`, and so forth. In detail, the layout data are separated into the terminals, the wires, the via-holes, the polygons (conductors), profiles of the components, profiles of the substrate, and letters of `marking pattern`, and so on. Especially, the wire is further separated at a turning and a junction thereof, and a crossing between the wire and the terminal. Similarly, the polygon is further separated into edges thereof. The results of separation are all handled as pieces.
When pieces are obtained, for each piece, piece data, location data and shape data are produced to be stored into the memory with data structures illustrated in FIGS. 14, 15, 16 and 17. Herein, the producing of the data are executed for the each layer pattern.
As for piece obtained from the terminal, via-hole, or the like, piece data comprise a piece number, a component number, a shape number, a location number, a signal name, and section number, as shown in FIG. 14. The piece number indicates the piece itself, and corresponds to, for example, the above-mentioned `terminal number i`. The component number represents the component that the piece belongs to, and corresponds to, for example, the above-mentioned `component number j`. That is, if a plurality of the pieces belong to one component, all of the pieces has the same component number. For example, although the pieces of the via-hole have different piece data at respective layers, all have a common component number. The shape number is for linking the piece data with the shape data indicative of the shape of the piece. The location data is for linking the piece data with the location data representative of the location of the piece on the layout pattern and the layer on which the piece is arranged. As regards the shape data and the location data, explanation will be made in later. The signal name represents a name of a signal that the piece receives. The section number indicates a section to which the piece belongs. Herein, the section is an area enclosed with the partition lines, which will be described in later.
On the other hand, as for the piece obtained from the wire, the polygon, or the like, the piece data comprise a piece number, a shape number, two location numbers, a signal name, and a distinction of `fixed` and `variable` of the pattern shape, as shown in FIG. 15. The piece number, the shape number, and the signal name are as same as ones in FIG. 14. The piece of the wire, the polygon, or the like, has two ends, and the location data are produced for each end, so that the piece data has two location numbers, as described in later. Furthermore, if one end of the wire is connected to the terminal, the end of the wire has the same location number as the terminal. Similarly, if one end of one wire is connected to another end of another wire, two ends have the same location number as to each other. In addition, if the piece data are for the piece of the wire, the item of the distinction is `variable`, while, if for the piece of the polygon, the item of the distinction is `fixed`.
The location data comprise the location number, an X-coordinate value, a Y-coordinate value, a layer number and the component number, as shown in FIG. 16. The location number indicates the location data itself, and is used in linked with the piece data. The X-coordinate vale and the Y-coordinate value are of the X-Y coordinates, which are supposed on the substrate region and have the origin at the lower-left corner. As mentioned above, since the piece of the wire or the polygon has two pairs of the X- and Y-coordinate values, two location data are made for each piece obtained from the wire and so on. The layer number indicates the layer where the corresponding piece belongs. The component number indicates the component of the corresponding piece. The layer number represents the layer to which the corresponding piece belongs, and corresponds to, for example, the above-mentioned `layer number k`.
In detail, the layer number is assigned, in accordance with the layers, as the followings. For example, each piece obtained from the terminal belongs to a signaling layer, a power-supply layer, or a ground layer, and each piece obtained from the wire also does. Each piece obtained from the profile of the component belongs to a component profile layer. Each piece obtained from the letter belongs to a marking-pattern layer, and each piece obtained form a marking restricted region pattern also does. The marking restricted region pattern is a processing hole relating to the marking letter, and so forth.
The shape data have data of an octagon obtained by approximating the piece and comprise the shape number, and pattern widths in X-, Y-, X.angle.45.degree.-, X.angle.-45.degree.-directions. The shape number indicates the shape data itself, and linked with the corresponding piece. The pattern width in X-direction is width between opposite sides of the corresponding piece in X-direction. The pattern width in Y-direction is width between opposite sides of the corresponding piece in Y-direction. The pattern width in X.angle.45.degree.-direction is width from the lower-left side to the upper-right side of the corresponding piece. The pattern width in X.angle.-45.degree.-direction is width from the lower-right side to the upper-left side of the corresponding piece.
It should be noted here that, even if the violation for the design rule exists on the original layout data of the circuit layout, this apparatus allows the existence. If the original layout data does not meet the design rule, the apparatus corrects the violation, taking the design rule into consideration, for example, in the process of the defining of the terminal constraint graph.
After the pieces data, the shape data, and the location data are produced and stored in the memory, the substrate region is partitioned into a plurality of sections with partition lines (PL), in the step S100 shown in FIG. 12.
In detail, the vertical partition lines (VPLs) and the horizontal partition lines (HPLs) are arranged in a lattice form, while a shape of the section is a square having edges, each of which has a length equal to a minimum size of the terminal.
Such section is stored in the memory as section data having the data structure illustrated in FIG. 18. The section data comprise a section number, the layer number, the location numbers of the corners of the section, the piece numbers of the partition lines enclosing the section, and the piece numbers of the terminal included within the section.
The section number is assigned to the section and has a unique number on the layer which the section exists on. Concretely, the section number comprises, for example, a vertical order in the Y-direction and a horizontal order in the X-direction. That is, the vertical order has a lower number if the corresponding piece is closer to the bottom of the substrate region, while the horizontal order has a lower number if the corresponding piece is close to the left of the substrate region. Thus, the section number is a unique on a layer. Herein, as regards a plurality of the layers, although there are the sections having the same section numbers, they are distinguished from each other by referring to the layer number.
Furthermore, it is detected where the corners of the section locate, and thereby, the detected locations are stored in the form of the foregoing location data. To be linked with the location data, each location number of the corners is stored in the section data. Also, as key to know the partition lines enclosing the section, the piece numbers of the partition lines are stored in the section data.
The piece numbers, which are for the terminals included within the section, are determined, as the followings. At first, as for a center of the piece, a location is calculated, and then, it is identified which section the calculated location corresponds to. The section data of the identified section store the piece number of the piece, in question, as shown in FIG. 18. On the other hand, the section number of the identified section is stored in the piece data of the piece, in question, as shown in FIG. 14.
Moreover, for each of the partition lines, piece data are produced, as shown in FIG. 19. The piece data of the partition line comprise a piece number of the partition line, and the component number of the partition line, the shape number of the partition line, and the location number, and a joint direction. Among them, the piece number, the component number, and the shape number are assigned in the same way to ones of other pieces. A location of the partition line is decided on the basis of the middle point of the partition line, in question, and thereby, the location data of the partition line are produced and the location number of the location data is stored in the piece data of the partition line.
The joint direction is determined as the result of the following processes. In an initial condition, no partition line is joined with the others, although partition lines form the sections. Under the condition, as for one corner of the section, two vertical partition lines extending from the one corner is at first directed, and then, the number of the wires traversing to the vertical partition lines, which will be a first number. Similarly, two horizontal partition lines extending from the one corner is directed, and then, the number of the wires traversing to the horizontal partition lines, which will be a second number. The difference between the first and the second number is calculated, and the calculated difference is compared with a predetermined number. For example, the predetermined number is five and represents a result of subtracting the first number from the second number. As a result of the comparison, if the difference is smaller than the predetermined number, the vertical partition lines are joined with each other at the one corner, while the horizontal partition lines are not. In this event, the piece data of the partition lines have, as the joint direction, the Y-direction. This joining process is executed for all of the corners of the section. The joining process may be executed in a condition that the vertical partition lines and the horizontal partition lines are replaced with each other.
Specifically, there is a case where the result of the comparison can not determine the joint direction of the partition lines. In this case, as for the corners close to each other, the joint directions are different from the each other. If the joining process applies to all of the corners of the sections, all partition lines are arranged in the form of hound's-tooth check, as illustrated in the above-referred FIG. 10.
After the joining of the partition lines, the piece numbers of the partition lines are updated in the section data, accordingly.
At this point, the partition lines are cross on the terminals, via-holes, and so on, as shown in FIG. 10. To correct this, the sizes of the sections are required to be varied, so that the terminals, etc. are accommodated within the sections. Therefore, the lengths of the partition lines are varied, and together, the partition lines are moved, and thereby, the terminals are accommodated in the sections, as illustrated in FIG. 20. After the accommodating, the varied lengths of the partition lines and the moved locations of the partition lines are updated in the corresponding piece data, location data, and shape data. The varying size of the section is executed for each layer.
Particularly, the moving of the partition line meets the following condition. Each of the partition lines is moved toward the lower-left corner, under a condition that the moving does not bring about a newly crossing of the partition line and the terminals, and so forth. And then, the corresponding location data are stored with the location of the partition line closest to the lower-left corner compliant to this condition. In addition, when the partitioning is first executed, if a plurality of terminals belong to one section, the succeeding partitioning also keeps the relationship between the plurality of terminals and the one section. Furthermore, if the partition line is moved to cancel one crossing of the partition lines and the terminal, while the moving brings about a newly crossing of another partition line and the terminals, the cancellation of the one crossing are not executed.
After the terminals are almost accommodated within the sections, the processor defines a constraint graph (CG) in a case where the compaction direction is a first compaction direction. And then, the processor stores the memory with constraint graph data of the constraint graph, as shown in FIG. 21. The constraint graph data comprise a edge number, the compaction direction, and the piece numbers. The edge number is assigned to the constraint graph and is a unique one at each layer. The piece numbers are the numbers of the pieces assigned to nodes at both ends of the constraint graph. As understood from the data structure, the constraint graph itself has no weight.
In this example, the first compaction direction is the X-direction, and accordingly, the constraint graph and the constraint graph data for the first compaction direction will be also referred to as X-constraint graph and X-constraint graph data, respectively. The defining of the X-constraint graph is executed each section on each layer.
With reference to the piece data of the piece included in the section and the location data corresponding to the piece data, the arrangement of the pieces in the X-direction is decided. And then, the pieces close to each other are selected, and their piece number is written into the X-constraint graph data as the piece numbers. Herein, the first node for the X-constraint graph is one of the pieces that locates on lower side of the substrate, while the second node is the other one. Needless to say, the X-direction is also written into the X-constraint graph data as the compaction direction. When these are memorized into the X-constraint graph data, the edge number is assigned the lower number of the numbers, which has not been assigned to any edge.
Specifically, as for the selected pieces, if the piece data have the same signal name, the X-constraint graph is not defined for the selected pieces. Instead, the upper one of the selected pieces is assumed to be transparent seen from the lower one, and another piece is selected as the newly upper one. And then, the X-constraint graph is defined for the lower piece and the newly upper piece.
Furthermore, the order of the constraint graph in the X-direction is calculated to be memorized order data of the constraint graph, as shown in FIG. 22. One X-constraint graph is directed as a first edge, and then, key-piece is detected to be the piece arranged on lower side of the substrate region for the first edge. When the key-piece is detected, second edges are detected to be the X-constraint graphs having the X-constraint graph data including the piece data of the key-piece. If all of the second edges have been determined the order themselves, the order of the first edge is determined to be the lower number of the numbers, which has not been assigned to any edge. Otherwise, the second edge not having the order is directed as a newly first edge, and then, the above processing is repeated. Thus, the orders of all X-constraint graphs are determined.
When the constraint graph data and the order data is determined for the X-direction, and then, such determination is executed for the Y-direction, in the same way of the X-constraint graph data and the order data thereof. Herein, the constraint graph for the Y-direction and the data thereof will be also referred to as Y-constraint graph and Y-constraint graph data, respectively.
In steps of S104 through S106 shown in FIG. 13, the terminal constraint graphs for the X-direction are defined, and then, the component constraint graphs for the X-direction are determined. Their data are stored in the memory with the data structures as shown in FIGS. 23 and 24. The terminal constraint graph and the terminal constraint graph data for X-direction will be also referred to as X-terminal constraint graph and X-terminal constraint graph data, respectively. The component constraint graph and the component constraint graph data for X-direction will be also referred to as X-component constraint graph and X-component constraint graph data, respectively.
Referring to FIG. 23, terminal constraint graph data comprise a compaction direction, the piece numbers of the pieces corresponding to first and second nodes, a belt width, a maximum movable range (MMR) of the second node for the first node, the shape number of the octagonal restricted region, a number of wires traversing between the pieces, the piece numbers corresponding to the traversing wires. Herein, the pieces corresponding to the first and second nodes are the above-mentioned `particular terminals`, and the first and the second nodes correspond to the particular terminals T.sub.U and T.sub.D, respectively.
Referring to FIG. 24, the component constraint graph data comprise the compaction direction, the component numbers of the component corresponding to first and second nodes, a terminal constraint graph number, and a minimum one of the maximum movable ranges of the corresponding terminal constraint graphs.
In detail, these data shown in FIGS. 23 and 24 are produced as the described in later.
At first, the X-direction is written into the terminal constraint graph data, as the compaction direction.
After than, it is directed to first and second terminals arranged at opposite side of each other relative to the vertical partition line, as shown in FIG. 25. The first and second terminals become the particular terminals, and the piece numbers corresponding to the first and second terminals are written into the terminal constraint graph data. If one of the first and second terminals does not exist, an empty terminal is assumed to be arranged on a center of the corresponding sections and to be handled as the other one terminal.
And then, the wires traversing the particular terminals are detected, with reference to a plurality of the piece data and a plurality of the location data both corresponding to the particular terminals and the wires. When the number of the wires traversing between the particular terminals is detected, the total width of the traversing wires can be calculated. At this point, the number of the traversing wires and the piece numbers corresponding to the traversing wires are written into the terminal constraint graph data.
And then, the belt width is obtained by adding, to the total width, the margins compliant to the design rule. As understood from the calculation, the term `belt width` in this process is slightly different from the above-mentioned `belt width`, because of causing the handling in the computer to be easy. That is, the belt width hereinafter includes not only wire bundle case, but also one wire case and no wire case. In one wire case, the belt width comes to be equal to the wire width, while, in no wire case, the belt width comes to be `zero` or a predetermined width required by the design rule. The obtained belt width is written into the terminal constraint graph data.
After that, it is judged whether the belt width W.sub.WB is smaller that the distance D.sub.X in the X-direction between the particular terminals or not. If the belt width W.sub.WB is smaller than distance D.sub.X, and then, the step S105 is executed, else the step S106 is executed, as shown in FIG. 13.
In step 105 of FIG. 13, `zero` is written into the terminal constraint graph data, as the maximum movable range, because W.sub.WB <D.sub.X. And then, the component constraint graph data are produced on the basis of the terminal constraint graphs including one having `zero` as the maximum movable range. The determining of the component constraint graph is executed in the way described above with reference to FIG. 4. Therefore, the component constraint graph data have `zero` as the selected maximum movable range in FIG. 24. At this time, the processor stores the component constraint graph data with the terminal constraint graph having `zero` as the maximum movable range.
Herein, if both of the existing component constraint graph data and the newly produced ones include the same component numbers, it is identified which data include the maximum movable range smaller than the other, and then, both of the data are updated to the identified data.
On the other hand, when the belt width W.sub.WB is not smaller than the distance D.sub.X, in step S104 of FIG. 13, the maximum movable range is calculated for the terminal constraint graph, as the followings. Herein, the calculation of the maximum movable range can be applied to the terminal constraint graphs except for one having `zero` as the maximum movable range.
To calculate the maximum movable range (M), some of the variables are defined with reference to FIG. 3. The particular terminal T.sub.D is assumed to be arranged on the relative space where a position of the particular terminal T.sub.U is the origin, that will be depicted in FIG. 26. And then, the particular terminal T.sub.D locates at a position of (x, y) on the X'-Y' coordinates. The particular terminals T.sub.U and T.sub.D have lengths of b.sub.X1 and b.sub.X2 in X'-direction, and lengths of b.sub.Y1 and b.sub.Y2 in Y'-direction. Under the circumstance, Bx is defined as a sum of the b.sub.X1 and b.sub.X2, while By is defined as a sum of the b.sub.Y1 and b.sub.Y2. Furthermore, when both of the particular terminals T.sub.U and T.sub.D are projected onto the line represented by `x+y`, Bz is defined as a distance between the centers thereof. Similarly, when both of the particular terminals T.sub.U and T.sub.D are projected onto the line represented by `y-x`, Bw is defined as a distance between the centers thereof.
Under the definition of the variables, if the following inequality (1) stands up, the maximum movable range (M) are calculated, by using the following equations (2) through (6).
When the maximum movable range is calculated for each of the X-terminal constraint graphs, the X-component constraint graph is calculated on the basis of the corresponding X-terminal constraint graphs, as described above with reference to FIG. 4. Herein, if both of the existing component constraint graph data and the newly produced ones include the same component numbers, it is also identified which data include the maximum movable range smaller than the other, and then, both of the data are updated to the identified data, again.
In almost cases, the step 106 is executed after the step S104. The maximum movable range in the X-direction serves the restriction of the moving in the X-direction, because the moving distance of the component can not exceed the maximum movable range in the X-direction. As the result, even if the moving of the component in the X-direction is executed, the components have a movable space therebetween in the Y-direction.
Herein, the above-mentioned calculation of the terminal constraint graph can be replaced with the following calculation.
At first, the particular terminals are selected to be the first and the second terminals between which a virtual line having an inclination of the least degrees relative to the X-axis is defined. After that, the vertical partition line traversing between the selected first and second terminals is handled as the terminal.
Besides, the terminal constraint graph is defined for the particular terminals that are the selected second terminal and the vertical partition line. In the illustrated in FIG. 25, such terminal constraint graph data has "0" as the belt width and "0" as the maximum movable range, and accordingly, the component constraint graph has zero of the selected maximum movable range.
Similarly, the terminal constraint graph is defined for the particular terminals that are the selected first terminal and the vertical partition line. In the illustrated in FIG. 25, such particular terminals has a wire bundle therebetween, and therefore, the defining of the terminal constraint graphs is executed, according to the calculation of the maximum movable range, and so on. And then, the component constraint graph is calculated on the basis of the corresponding terminal constraint graphs.
After that, the newly second terminal is selected among the terminals except for the already selected first and second terminals, in such that a virtual line between the newly second terminal and the first terminal has an inclination of the least degrees relative to the X-axis. And then, a subtraction is carried out in such that the belt width assumed between the first terminal and the vertical partition line is subtracted from the belt width assumed between the first and second terminals.
The result of the subtraction is stored in the terminal constraint graph data of the terminal constraint graph, which is for the newly second terminal and the vertical partition line. In addition, the terminal constraint graph data are stored with the number of the wires traversing between the newly second terminal and the vertical partition line and the piece numbers of the traversing wire.
Besides, the maximum movable range for the particular terminals is calculated, and thereby, the terminal constraint graph, which is for the newly second terminal and the vertical partition line, is defined. Furthermore, the component constraint graph is determined on the basis of the corresponding terminal constraint graphs.
After that, the newly first terminal is selected among the terminals except for the already selected first and second terminals, in such that a virtual line between the newly first terminal and the second terminal has an inclination of the least degrees relative to the X-axis. And then, a subtraction is carried out in such that the belt width assumed between the second terminal and the vertical partition line is subtracted from the belt width assumed between the first and second terminals.
The result of the subtraction is stored in the terminal constraint graph data of the terminal constraint graph, which is for the newly first terminal and the vertical partition line. In addition, the terminal constraint graph data are stored with the number of the wires traversing between the newly first terminal and the vertical partition line and the piece numbers of the traversing wire.
Besides, the maximum movable range for the particular terminals is calculated, and thereby, the terminal constraint graph, which is for the newly first terminal and the vertical partition line, is defined. Furthermore, the component constraint graph is determined on the basis of the corresponding terminal constraint graphs.
After that, the above processing is repeatedly executed. That is, a still selected terminal is selected among the terminals except for the already selected terminals. The still selected terminal locates at opposite side of the already selected terminal relative to the vertical partition line. Also, a virtual line between the still selected and the already selected terminals has an inclination of the least degrees relative to the X-axis. And then, the terminal constraint graph is defined for the still selected and the already selected terminals. Furthermore, the component constraint graph is determined on the basis of the corresponding terminal constraint graphs.
When the modification is applied to the defining of the terminal constraint graph, the number of the terminal constraint graph to be processed becomes small. In detail, if the sizes of the sections are determined to be large in the pre-processing of the step S106, the number of the terminals accommodated in each section becomes many. As the result, the number of the terminal constraint graph also increases, for the terminals belonging to different sections from each other, so as to be multiplied the number of the terminals belonging to one section and the number of the terminals belonging to the other section. However, if the modification is adopted to the defining of the terminal constraint graph, the number of the terminal constraint graph is decreased to be the total number of the terminals belonging to the sections.
To decrease the number of the terminal constraint graph, the followings are effective. The followings relate to the combination of the particular terminals in one section.
In one section, pairs of two terminals are selected among all terminals belonging to the one section. Among them, only the pairs, which meet the following condition are, selected the pairs of the particular terminals:
(1) The second terminal locates at a position closer to the right side (the upper side) than the first terminal; and
(2) The first and second terminals are meet the equation of (A-1).times.(B-1)=0. A is defined as the number of the terminals T.sub.A. The terminal T.sub.A are selected among the terminals locating at a position closer to the right side (the upper side) than the first terminal. Furthermore, provided that a distance D.sub.A between the terminal T.sub.A and the first terminal, and the distance D.sub.0 between the first and second terminals, D.sub.A.ltoreq.D.sub.0. Also, B is defined as the number of the terminals T.sub.B. The terminal T.sub.B are selected among the terminals locating at position closer to the left side (the lower side) than the second terminal. Furthermore, provided that a distance D.sub.B between the terminal T.sub.B and the second terminal, and the distance D.sub.0, D.sub.A.ltoreq.D.sub.0 ; where the phrases in parentheses correspond to the case of compacting in the Y-direction.
If the first and the second terminals meet the above requirements, then the first and the second terminals are the particular terminals. Such selection of the particular terminals causes the number of the terminal constraint graph to decrease.
Turning to FIG. 13, after the steps S104 through S106 are executed, and thereby, the X-component constraint graphs are obtained, the same steps S104 through S106 are executed with the X-direction replaced with the Y-direction, in a step S107. As the result, the Y-component constraint graphed are also obtained.
Herein, the next step is step S110 in FIG. 13 and it is detected whether the compacting is