System and method for compacting a graphic layout

[0002] This invention relates to a graphic layout compaction system and a graphic layout compaction method.

[0003] An automatic layout system is utilized for designing a layout of a large-scale semiconductor integrated circuit or a printed-circuit board. The large-scale semiconductor integrated circuit includes a lot of semiconductor cells. The printed-circuit board mounts a lot of parts thereon. The semiconductor cells may be merely referred to cells. The semiconductor cells and the parts are collectively called components in the present specification. Although each component has at least one terminal which is called a component terminal, the component terminal may be called the component. In addition, in the automatic layout system of the type, various compaction techniques for moving components with the components linked are already proposed.

[0004] A conventional graphic compaction system is disclosed in Japanese Unexamined Patent Publication (JP-A) No. 9-204461 (204461/1997) (Publication 1). In this system, the layout of a plurality of components is compacted with relative position relationship of the components held. However, this graphic compaction system is disadvantageous in that it is impossible to compact a pattern having routes or wires between component terminals. This is because this graphic compaction system places or arranges only the parts (the components) on a printed-circuit board in a stage prior to routing or wiring between terminals (the component terminals) of the parts and then compacts its placement or arrangement.

[0005] Another conventional graphic compaction system is disclosed in Japanese Unexamined Patent Publication (JP-A) No. 1-279373 (279373/1989) (Publication 2). The graphic compaction system compacts semiconductor cells (the components) and routes or wires in a stage after routing or wiring between terminals (the component terminals) of cells on designing of an integrated circuit.

[0006] As disclosed in Japanese Unexamined Patent Publications (JP-A) Nos. 62-78681 (78681/1987) (Publication 3) and 63-214880 (214380/1988) (Publication 4), compaction of the routes or wires together with semiconductor cells or parts (components) frequently adopts a scheme using a constraint graph. For the compaction using the constraint graph, proposal is made of a jog insertion compaction technique by W. Yanamoto et al in their articles “A Chip Compaction Method on Constraint Graph and the Experimental Result”, Technical Report of IEICE VLD91-43, pp. 41—48, 1991 (Article 1), “A Chip Spacing Method for layouts with Design-Rule Violations”, Technical Report of IEICE VLD91-120, pp. 37-44, Feb. 7, 1992 (Article 2), and “A Chip Spacer with Automatic 45° Diagonal Wiring Generation”, Technical Report of IEICE VID91-123, pp. 17-24, 1992 (Article 3). The jog insertion compaction technique modifies structure of the constraint graph by inserting a bend part called “jog” in the routing or wiring to thereby enable to reduce an area of the layout and to correct places with design-rule violations.

[0007] Referring to FIG. 1, a conventional layout compaction system comprises a cell placement processing unit (cell arrangement processing unit) 710, an inter-cell routing processing unit 720, a longest route searching unit 730, a layout enlarging unit 740, a layout correction designating unit 750, an automatic layout compressing unit (compaction unit) 760, a layout data memory 770, and a layout result display unit 780.

[0008] The conventional layout compaction system having such structure operates in a following manner.

[0009] The cell placement processing unit 710 carries out processing of placement or arrangement for cells as known in the art and stores cell layout data indicative of a layout of the cells in the layout data memory 770.

[0010] As known in the art, the inter-cell routing processing unit 720 carries out processing of routing or wiring between cells and stores routing layout data (wiring layout data) indicative of a layout of the routing or the wiring in the data Emory 770.

[0011] The longest route searching unit 730 searches a series of graphic elements having the longest route in the layout stored in the layout data memory 770 in order to compact a layout of each cell and the routing or wiring on an LSI chip into a smaller area and displays it in the layout data memory 770 and displays the longest route in the layout result display 780 as depicted by oblique lines in FIG. 2A.

[0012] As illustrated in FIG. 2B, the layout enlarging unit 740 inserts a space crossing the longest route of its constraint graph in the layout as shown in FIG. 2B.

[0013] Responsive to a request from an operator, the layout correction designating unit 750 moves a particular part from the longest route of the constraint graph so as to shorten the longest route. In the example illustrated in FIG. 2B, the particular part is the second part from a lower end and is moved rightward.

[0014] The automatic layout compressing unit (compaction unit) 760 compacts the layout indicative of a corrected result in up and down of FIG. 2B.

[0015] However, in a case of carrying out the compaction of the layout BO as to reduce the layout in both longitudinal and lateral directions, the conventional compactor 760 reduces the layout in two steps so as to first reduce it in one direction (e. g. the longitudinal direction) and to subsequently reduce it in another direction (e. g. the lateral direction). Therefore, when the layout is first reduced in the longitudinal direction, the cells or the components crowd in the longitudinal direction and it results in preventing reduction of placement or arrangement of the cells or the components and the layout of the routing or the wiring in the lateral direction.

[0016] In addition, those skilled in the art may hit upon a method comprising the steps of extending the Dijkstra method, of simultaneously evaluating a movable distance of the longitudinal direction and another movable distance of the lateral direction for each part or component, and of moving the parts or the components in order ascending the movable distances in its direction to place or arrange the parts or the components. However, this method is disadvantageous in that placement or arrangement of the parts or the components crowded in a particular direction selected from the longitudinal direction and the lateral direction prevents the parts or the components from subsequently moving in a direction perpendicular to the particular direction.

[0017] The reason for this defect is as follows. This conventional compaction system carries out compaction of the layout so as to first move all of the parts or the components pushed to touch a substrate end and to subsequently move all of the parts or the components pushed to touch the substrate end. Therefore, an initial result of placement or arrangement for semiconductor cells or parts is not reflected to the layout after compaction and compaction in an initial direction results in unbalancing placement or arrangement of the parts or the components. As a result, compaction of the semiconductor cells or the parts in the next direction is prevented.

[0018] In addition, to improve this defect, still another conventional graphic compaction system is disclosed in Japanese Unexamined Patent Publication (JP-A) No. 63-181349 (181349/1988) (Publication 5). The graphic compaction system moves semiconductor cells in a symmetrical direction towards a center of the layout for a chip before routing or wiring process for an LSI, compacts the layout so that the semiconductor cells collect in a center direction of the chip, and makes routing or wiring between the semiconductor cells.

[0019] However, the compaction system described in Publication 5 divides an area of the layout about the center of the chip into four divided areas and carries out compaction in the respective divided areas. In addition, in each divided area, the compaction system carries out primary compaction of the semiconductor cells in a first direction and subsequently carries out secondary compaction of the semiconductor cells in a second direction perpendicular to the first direction. As a result, a result of the primary compaction may prevent the semiconductor cells from moving in the second direction in the secondary compaction.

[0020] The reason for this defect is as follows. That is, the conventional compaction system carries out compaction of the layout so as to move the layout in a predetermined designated direction in spite of moving the semiconductor cells (the parts) either in the longitudinal direction or in the lateral direction. As a result, when a difficulty occurs in the designated direction for moving the parts or the components, movement of the parts or the components is prevented.

[0021] In order to remove this defect, two-dimensional compaction is proposed in E. Shin et al “Two-Dimensional Compaction by Zone Refining”, Proc. of 23rd Design Automation Conference, 1986, pp. 115-122 (Article 4). The two-dimnsional compaction is a technique in which a component is moved simultaneously in two directions. Specifically, constraint graphs in longitudinal and lateral directions are prepared and semiconductor cells are successively moved downward in the longitudinal direction. Each cell is moved simultaneously in the longitudinal and the lateral directions to be located at an appropriate position. Routing are carried out by pulling the route or wire downward with folds or jogs produced therein.

[0022] In Japanese Unexamined Patent Publication (JP-A) 5-274392 (274392/1993) (Publication 6), a different conventional graphic compaction system is disclosed which includes a pattern division section for dividing a substrate into a plurality of partial areas each having routing or wiring as a boundary and a plurality of partial pattern compression sections for the respective partial areas. The partial pattern compression sections compress the shape of the partial areas in the substrate to the left or right from a left-hand end of the substrate and compress the shape of the partial areas in the substrate to up and down from an upper end of the substrate. Therefore, the graphic compaction system uniformly compacts the entire area of the substrate with relationship up and down and left and right in the area maintained.

[0023] In addition, a method based on the Bounded Sliceline-Grid (BSG) is proposed which comprises the step of designating a rectangular area enclosing parts by the BSG and the step of concurrently compacting the area in the longitudinal and lateral directions by changing a size of the area (K. Sakanushi et al “Concurrent Representation and Optimization of Placement and Route on BSG”, Technical Report of IEICE, VIM97-40, pp. 175-182, June 1997 (Article 5)).

[0024] In the above-mentioned conventional techniques, it is possible to compress the partial areas of the substrate by two-dimensional compaction or partial compaction. However, the routes (or wires) must be arranged in the longitudinal and the lateral directions. By compressing the routes (or wires) in the longitudinal and the lateral directions, the partial areas are compressed. Thus, diagonal routes or wires can not be used.

[0025] Japanese Unexamined Patent Publication (JP-A) 10-3491 (3491/1998) (Publication 7) discloses a technique of erasing all of existing routes or wires and arranging new routes or wires simultaneously with compaction. In this technique, diagonal routes or wires can be used.

[0026] In Publication 7, however, the routes or wires are pulled in a compaction direction and closely gathered. Therefore, it is difficult to reserve a sufficient space between the routes or wires so as to suppress occurrence of crosstalk therebetween.

[0027] Upon compaction of a layout with routes or wires connected among a large number of component terminals in a printed-circuit board, it is difficult in any one of the conventional techniques described above to move all component terminals of multi-terminal components with the wires connected therebetween.

[0028] Throughout the instant specification, technical terms may be defined as follows. Components may comprise either parts on a printed-circuit board or semiconductor cells in a large-scale semiconductor circuit. Each component has one or more component terminals which may be called the component. A layout comprises at least one layer of pattern. The pattern comprises routes or wires, terminals, via holes, and polygonal conductor configurations which are placed or arranged on a two-dimensional space. Each of the terminals, the via holes, and the polygonal conductor shapes may be also called the component terminal. Accordingly, the layout comprises the routes or the wires and the component terminals or the components. A graph consists of nodes and edges for connecting between the nodes. The nodes are also called vertices. The edges are also called branches.

[0029] It is therefore an object of this invention to provide a system and a method for graphic layout compaction, which is capable of preventing interference between compaction in a first direction and compaction in a second direction perpendicular to the first direction.

[0030] It is another object of this invention to provide a system and a method for graphic layout compaction, which is capable of modifying an arrangement of a component as an obstacle against compaction to achieve a small layout area.

[0031] It is still another object of this invention to provide a system and a method for graphic layout compaction, which is capable of maintaining a positional relationship between components in longitudinal and lateral directions by determining a moving distance of each component so that the layout of the components is uniformly compressed.

[0032] A graphic layout compaction system to which this invention is applicable is for use in compacting a pattern of at least one layer including wires, component terminals, via holes, and polygonal conductor configurations (or shapes). According to this invention, the graphic layout compaction system is supplied with layout data to divide the component terminals and the via holes into segment data per layer and to divide the routes (or wires) and the polygonal conductor shapes into segment data per bending point and branching point. These segment data linked to each other are assigned with a common component number. Herein, each individual via hole is represented by a single component number (hereinafter, each via hole will also be called a component). The graphic layout compaction system comprises a terminal constraint graph generator for preparing terminal constraint graph data and component constraint graph data representative of (a) a pair of adjacent component terminals adjacent in a longitudinal or a lateral direction in each layer and (b) a limit movable distance within which one of the adjacent component terminals is allowed to move towards the other adjacent component terminal with a routing (wiring) zone including routes (wires) and a necessary gap interposed therebetween, a compactor for compacting the components with reference to the component constraint graph data, and a rerouting unit for shaping and rearranging the routes (wires).

[0033] To avoid interference between compaction in a first direction and compaction in a second direction perpendicular to the first direction, a particular component resulting in the interference is modified in its position to thereby narrow a layout area.

[0034] A movable distance of each component is determined so that the arrangement of the components is uniformly compacted. Thus, compaction is carried out in the manner such that a positional relationship between the components in longitudinal and lateral directions is maintained. It is thus possible to prevent occurrence of the interference upon compaction.

[0035] The terminal constraint graph generator prepares the terminal constraint graph data with the component terminals (except the routes) included as nodes. Calculation is made of the limit movable distance within which one node is movable towards the other node in a moving direction via the routing zone including the routes and the necessary gap interposed therebetween. The limit movable distance is memorized as a component relative movement limit length. The terminal constraint graph generator prepares the component constraint graph data having a graph length which is a minimum value of the component relative movement limit length with respect to the one component terminal. The component compactor compacts the arrangement of the components with reference to the component constraint graph data.

[0036] FIG. 1 is a block diagram of a conventional layout compaction system;

[0037] FIGS. 2A and 2B are views for describing an operation of the conventional layout compaction system in FIG. 1;

[0038] FIG. 3 is a block diagram of a graphic layout compaction system according to a first embodiment of this invention;

[0039] FIG. 4 is a flow chart for describing an operation of the graphic layout compaction system in FIG. 3;

[0040] FIG. 5 is a flow chart for describing in detail a part of the operation in FIG. 4;

[0041] FIGS. 6A through 6E are views showing various kinds of data used in the graphic layout compaction system in FIG. 3;

[0042] FIGS. 7A through 7D are views showing other various kinds of data used in the graphic layout compaction system in FIG. 3;

[0043] FIG. 8 is a view showing a layout used in the graphic layout compaction system in FIG. 3;

[0044] FIG. 9 is a view showing an initial state of the layout;

[0045] FIG. 10 is a view showing the layout in FIG. 9 after compaction in one direction;

[0046] FIG. 11 is a view showing the layout in FIG. 10 after rearrangement of wires;

[0047] FIG. 12 is a view showing the layout in FIG. 11 together with a component constraint graph;

[0048] FIG. 13 is a view showing the layout in FIG. 12 after compaction in the other direction and rearrangement of the wires;

[0049] FIG. 14 is a block diagram of a graphic layout compaction system according to a second embodiment of this invention;

[0050] FIG. 15 is a flow chart for describing an operation of the graphic layout compaction system illustrated in FIG. 14;

[0051] FIG. 16 is a flow chart showing in detail a part of the operation in FIG. 15;

[0052] FIG. 17 is a flow chart showing in detail another part of the operation in FIG. 15;

[0053] FIG. 18 is a plan view for describing the operation of the graphic layout compaction system illustrated in FIG. 14;

[0054] FIGS. 19A through 19C are views for describing the operation of the graphic layout compaction system illustrated in FIG. 14;

[0055] FIGS. 20A through 20C are views for describing a specific example of operation of the graphic layout compaction system illustrated in FIG. 14;

[0056] FIG. 21 is a flow chart for describing an operation of a graphic layout compaction method according to a third embodiment of this invention;

[0057] FIG. 22 is a flow chart for describing an operation of a graphic layout compaction method according to a fourth embodiment of this invention;

[0058] FIG. 23 is a plan view for describing the operation of the graphic layout compaction method illustrated in FIG. 22;

[0059] FIG. 24 is a plan view showing the layout in FIG. 23 after compaction;

[0060] FIG. 25 is a plan view showing the layout after completion of the operation of the graphic layout compaction method illustrated in FIG. 22;

[0061] FIG. 26 is a flow chart for describing an operation of a graphic layout compaction method according to a fifth embodiment of this invention;

[0062] FIGS. 27A and 27B are views for describing the operation of the graphic layout compaction method in FIG. 26;

[0063] FIGS. 28A and 28B are views for describing the operation of the graphic layout compaction method in FIG. 26; and

[0064] FIGS. 29A and 29B are views for describing the operation of the graphic layout compaction method in FIG. 26.

[0065] Now, several preferred embodiments of this invention will be described in detail with reference to the drawing.

[0066] Referring to FIG. 3, a graphic layout compaction system according to a first embodiment of this invention comprises a computer 100 operated under control of a program, a display unit 101, and a console unit 102. The computer 100 may comprise a central processing unit, a processor, or a data processor. The display unit 101 may comprise a CRT display or a liquid crystal display. The console unit 102 may comprise a keyboard and a mouse or a tablet.

[0067] The computer 100 comprises a layout data converter 111, an operator command input device 110, a constraint graph generator 103, a terminal constraint graph generator 104, an order data generator 105, a component compactor 107, a routing compactor 108, a rerouting unit 109, a layout data memory 20, a segment data memory 30, a constraint graph data memory 40, a terminal constraint graph data memory 50, and a component constraint graph data memory 60.

[0068] Supplied with layout data of a printed-circuit board from the layout data memory 20, the layout data converter 111 produces segment data to be memorized in the segment data memory 30. Specifically, each configuration in the layout data is decomposed into a plurality of segments represented by the segment data. Each segment is assigned with a segment number 31.

[0069] From the segment data memory 30, the constraint graph generator 103 extracts those segment data which correspond to component terminals, via holes, or routes (wires) adjacent in a direction Y or X. The constraint graph generator 103 prepares constraint graph data representing a Y-direction or an X-direction constraint graph connecting adjacent ones of the segment numbers adjacent in the direction Y or X. The constraint graph data are memorized in the constraint graph data memory 40. in the present specification, the via holes and board ends are also referred to as components.

[0070] The terminal constraint graph generator 104 prepares terminal constraint graph data representing a pair of component terminals or component contours (configurations) as opposite nodes and a terminal relative movement limit length 62. The terminal relative movement limit length 62 represents a limit of movement within which one of the nodes is allowed to move towards the other node. The terminal constraint graph data are assigned with a terminal constraint graph number 51 and memorized in the terminal constraint graph data memory 40. In addition, the terminal constraint graph generator 104 prepares component constraint graph data representing a pair of component numbers 32 as opposite nodes, the component relative movement limit length 62, and the terminal constraint graph number 51. The component constraint graph data are memorized in the component constraint graph data memory 60.

[0071] The order data generator 105 selects, among the component constraint graph data memorized in the component constraint graph data memory 60, those component constraint graph data giving a shortest route length.

[0072] The component compactor 107 moves the components in the direction X or Y (quantizing direction) by the shortest route length.

[0073] The routing compactor 10 prepares routing limit position data representative of a routing (wiring) limit position For a particular route interposed between the component terminals as the opposite nodes of the terminal constraint graph data, the routing lint position is defined along the contour of one of the component terminals in the form of an octagonal configuration. The routing limit position data are memorized in the routing limit position data memory 80.

[0074] The rerouting unit 109 shapes the route (wire) into a configuration including diagonal parts and rearranges the route (wire). A resultant layout is memorized in the layout data memory 20.

[0075] Next referring to FIGS. 4 and 5 together with FIGS. 9 through 13, the operation of the graphic layout compaction system will be described.

[0076] Referring to FIG. 4, the layout data converter 111 is supplied with the layout data illustrated in FIG. 9 and prepares the segment data. Specifically, various graphic elements in a layout pattern, such as the component terminals, the via holes, the wires, polygonal conductor configurations, component contours, substrate contour lines, and marking patterns and characters are decomposed per each layer plane into the segments each of which is approximated to an octagonal configuration. The segment data representative of each segment have data structures illustrated in FIGS. 6A and 6B (step S100).

[0077] More specifically, the layout data converter 111 arranges the component terminals and the wires on a signal layer plane and a power supply and ground layer plane while the component contours are arranged on a component contour layer plane The layout data converter 111 arranges on a marking layer plane the marking patterns and characters together with a marking inhibiting region such as working hole positions interfering the marking patterns and characters. In addition, the layout data converter 111 decomposes the routes for each of the signal layer plane and the power supply and ground layer plane into route segments divided at bending points, branching points, and intersecting points with the component terminals. The polygonal conductor configurations are decomposed into a plurality of sides. Thus, the segment data are prepared for the routes and the polygonal conductor configurations.

[0078] The layout data converter 111 assigns the segment data of the components decomposed per layer plane with the individual component numbers 32. Likewise, the via holes are assigned with the individual component numbers 32. The sides of the substrate contour lines are assigned with a common component number 32. These component numbers 32 are recorded in the segment data. In the present specification, the substrate contour lines and the via holes are also called the components.

[0079] Referring to FIGS. 6A and 6B, the data structures of the segment data prepared by the layout data converter 111 will be described.

[0080] As illustrated in FIG. 6A, the segment data of the component terminal or the via hole include the component number 32. The component number 32 is common to all segment data of the terminals associated with a single component. The component number 32 is common to all segment data of a single via hole 3 in all layer planes. In addition, the segment data of the component terminal or the via hole include a configuration number 36 of configuration data 35 (FIG. 6D) representing the configuration of the segment.

[0081] As illustrated in FIG. 6B, the segment data of the route (wire) 2 connected to the component terminal 1 or the via hole 3 include a pair of position numbers 33 for first and second ends of the route 2. Each of the position numbers 33 of the route 2 is common to that of the terminal 1, the via hole 3, or the end of another route 2 connected to each corresponding end of the route 2. In addition, the segment data of the route 2 include the configuration number 36 representative of the width of the route (wire).

[0082] As illustrated in FIG. 6C, position data 34 include the position number 33, X and Y coordinate values, a layer plans number, and the component number 32 associated with the position number 33.

[0083] Referring to FIG. 6D, the configuration of each graphic element is described and memorized as the configuration data 35. The configuration data 35 include the configuration number 36, and the widths of the graphic element in the longitudinal, the lateral, first diagonal (rotated by 45° counterclockwise from the lateral direction), and second diagonal (rotated by 45° clockwise from the lateral direction) to represent the graphic pattern as an octagonal configuration. The segment data of the polygonal conductor configuration 4 are prepared for a line segment as each side thereof and have the data structure illustrated in FIG. 6B, including the indication of a fixed configuration.

[0084] In the initial layout of the printed-circuit board, a gap between adjacent ones of the wires 2, the terminals 1, the via holes 3, and the polygonal conductor configurations 4 may be smaller than a minimum allowable gap defined in the design rule. According to the first embodiment, such smaller gap is modified as will later be described.

[0085] Then, in a step S101, the direction Y is selected as a first compaction direction. The step S101 is followed by steps S102 through S112 Then, the operation returns to the step S101 to select the direction X as a second compaction direction. Again, the steps S102 through S112 are carried out. When compaction is completed in both of the first and the second compaction directions, the operation will come to an end.

[0086] In the step S102 following the step S101, the constraint graph generator 103 reads per layer plane the segment data from the segment data memory 30 in the order of the X coordinate values in the layer plane. The order of arrangement of the segment numbers 31 in the direction Y is determined with reference to the Y coordinate values to obtain each pair of adjacent ones of the sat numbers 31 adjacent in the direction Y as the first compaction direction. As illustrated in FIG. 7A, preparation is made of Y-direction constraint graph data which represent the above-mentioned pair of segment numbers 31 as first and second nodes in the order of the Y coordinate values. In preparing the constraint graph data, the segment numbers 31 having a common signal name 37 are assumed to be transparent to each other. These segment numbers 31 having the common signal name 37 are connected in parallel from another segment number 31 having a different signal name 37. The constraint graph generator 103 calculates the order of the constraint graph data in the order of the segment numbers 31 included therein from the lowermost one in the direction Y. The order of the constraint graph data is recorded as Y-direction constraint graph order data (not shown).

[0087] In steps S1031 through S1036 illustrated in FIG. 5, the terminal constraint graph generator 104 calculates a route connecting the segment data for which the adjacency is memorized in the Y-direction constraint graph data. Thus, the route having the component terminals at both ends is obtained and the Y-direction terminal constraint graph data having a data structure illustrated in FIG. 7B are prepared.

[0088] At first in the step S1031, the terminal constraint graph generator 104 reads all of the Y-direction constraint graph data from the constraint graph data memory 40 in the order from a lower substrate end to an upper substrate end with reference to the Y-direction constraint graph order data to obtain the segment numbers 31 of their nodes. The lower and the upper segments will be called first and second segments, respectively.

[0089] Next, the terminal constraint graph generator 104 extracts seed terminal graph data 53 (prepared in the step S1032 which will later be described) to record the first segment. The seed terminal graph data 53 are illustrated in FIG. 7C. In absence of the seed terminal graph data 53 corresponding to the first segment and if the first segment is a component terminal, the operation proceeds to the step S1032. On the other hand, in presence of the seed terminal graph data 53 recording the first segment, the operation proceeds to the step S1034 and the step S1035 when the second segment is the route and the component terminal, respectively. After processing all of the constraint graph data in the Y-direction constraint graph order data, the operation proceeds to the step S104.

[0090] In the step S1032, the terminal constraint graph generator 104 prepares, when the first segment is the component terminal, the seed terminal graph data 53 with the segment number 31 (lower segment) of the component terminal as a lower end. In the seed terminal graph data 53, the route segment number 31 on the constraint graph data is recorded as an interposed route segment number 31. With respect to the seed terminal graph data 53, the terminal constraint graph generator 104 calculates a routing zone width 52 which is a bus of the width of the route and the widths of necessary gaps above and below the route. The routing zone width 52 is recorded in the seed terminal graph data 53. Calculation is made of a routing restraint area width which is a sum of the width of the lower component terminal in the lateral direction (direction X) and the routing zone width 52. The routing restraint area width is memorized in the seed terminal graph data 52. Then, the operation returns to the step S1031.

[0091] In the step S1034, the terminal constraint graph generator 104 extracts the seed terminal graph data 53 recording the first segment when the second segment is the route. The following operation is carried out for every seed terminal graph data 53.

[0092] Specifically, the terminal constraint graph generator 104 duplicates the seed terminal graph data 53 into new seed terminal graph data 53 when the X-coordinate width between the both ends of the route as the second segment overlaps the X-coordinate width of the routing restraint area in the seed terminal graph data 53. The new data are recorded with the segment number 31 of the second segment added thereto. The terminal constraint graph generator 104 calculates a new routing restraint area width which is a sum of the routing restraint area width in the old data, the width of the additional route, and the necessary gap. The new routing restraint area width thus calculated is recorded in the seed terminal graph data 53. Likewise, a new shield region width is calculated as a sum of an old shield region width, the width of the routing as the upper segment, and the necessary gap. The new shield region width thus calculated is recorded in the seed terminal graph data 53. The terminal constraint graph generator 104 records the X-coordinate width of the second segment as the shield region width in the seed terminal graph data 53 as the old data. When the routing restraint area of the seed terminal graph data 53 is completely covered with the shield region, the terminal constraint graph generator 104 erases the seed terminal graph data 53.

[0093] In the step S1035, the terminal constraint graph generator 104 extracts, when the second segment is a component terminal, the seed terminal graph data 53 recording the first segment and carries out the following operation for every seed terminal graph data 53. When all of the seed terminal graph data 53 are processed, the operation returns to the step S1031.

[0094] Specifically, when the X coordinate width of the second segment overlaps the X coordinate width of the routing restraint area in the seed terminal graph data 53 (when Equation (1) later described is satisfied), the terminal constraint graph generator 104 prepares the terminal constraint graph data illustrated in FIG. 7B. Specifically, the terminal constraint graph data include, as nodes, the component terminal segment number 31 of the second segment as an upper-end component terminal and the component terminal segment number 31 at the lower end of the seed terminal graph data 53. The terminal constraint graph data further include the routing zone width 52 of the seed terminal graph data 53 as the routing zone width 52 between the nodes. Furthermore, in the seed terminal graph data 53, the terminal constraint graph generator 104 records, as the shield region width, the X-coordinate width of the segment data associated with the component terminal of the upper segment. When the routing restraint area of the seed terminal graph data 53 is completely covered with the shield region, the terminal constraint graph generator 104 erases the seed terminal graph data 53. Then, the operation proceeds to the next step S1036. In the above-mentioned step S1035, the terminal constraint graph generator 104 can prepare, even if the upper and the lower segments are spaced at a predetermined distance in the direction X, the terminal constraint graph data with those segments as the both ends. This is achieved by enlarging the X-coordinate width of the segment data of the upper segment by the predetermined distance. In addition, the terminal constraint graph generator 104 can perform the step S103 and the subsequent steps in the following condition. Specifically, the routing restraint area by the lower segment is shaped as a rectangle and the sum of the width of the lower segment in each of the directions X and Y and the routing zone width 52 is used as the width of the routing restraint area in each of the directions X and Y.

[0095] In the step S1036, the terminal constraint graph generator 104 calculates the Y-direction component relative movement limit length 62 shown in FIG. 8, in the manner which will presently be described. The component relative movement limit length 62 (M) is a loft within which the component is movable in a moving direction with the routing zone freely diagonally bendable between the upper and the lower segments. Specifically, a coordinate axis in the direction Y is labelled a Q axis while the direction X perpendicular thereto is labelled a V axis, as illustrated in FIG. B. Then, a relative coordinate of each of the upper and the lower component terminals is represented by (V, Q). The sum of the radii of the both terminals in the direction V [=Y] and the wiring zone width 52 is represented by Bv. Likewise, the sum of the radii of the both terminals in the direction Q [=X] and the routing zone width 52 is represented by Bq. The sum of the radii and the routing zone width 52 as a measure from the center of the one terminal to the other terminal is represented by Bz, when the both terminals are projected onto the coordinate V+Q. The sum of the radii and the routing zone width 52 as a measure from the center of the one terminal to the other terminal is represented by Bw, when the both terminals are projected on the coordinate Q−V. The minimum value of M is calculated by the following equations and used as the component relative movement limit length 62.

[0096] −Bv<V>Bv  (1)

[0097] U≦Bq  (2)

[0098] U≦Bz−V  (3)

[0099] U≦Bw+V  (4)

[0100] M=Q−U  (5)

[0101] The terminal constraint graph generator 104 prepares the terminal constraint graph data having a graph length equal to the component relative movement limit length 62 in the direction Y. The terminal constraint graph data are memorized in the terminal constraint graph data memory 50.

[0102] The terminal constraint graph generator 104 prepares the component constraint graph data depicted by dotted lines in FIG. 9. As illustrated in FIG. 7D, the component constraint graph data include as nodes the component numbers 32 of the terminals at opposite ends of the X-direction terminal constraint graph data, the Y-direction component relative movement limit length 62, and the terminal constraint graph number 51. The component constraint graph data are memorized in the component constraint graph data memory 60. Herein, when existing component constraint graph data are memorized in the component constraint graph data memory 60, the terminal constraint graph generator 104 renews the Y-direction component relative movement lent length 62 into a smaller value. Next, the step S1035 is repeated for another seed terminal graph data 53.

[0103] In the subsequent step S104, the order data generator 105 calculates a shortest route in the direction Y. Using a compaction technique based on the Dijkstra method, the order data generator 105 extracts the Y-direction component, constraint graph data (a) having as a core the shortest route of the Y-direction component constraint graph data from the board end and (b) connected to the component terminal as the node of the shortest route. The order data generator 105 calculates, as a Y-direction route length of the component number 32 at the other end, the sum of the shortest route length of the component connected thereto and the component relative movement limit length 62 of the component constraint graph data. The order data generator 105 selects as a selected graph one of the component constraint graph data which has a shortest route length. The route length of the selected graph is used as the shortest route length of the component number 32 at that end The component constraint graph data are added to the shortest route. In the present specification, the component number 32 at that node (branch-side node) will be called a selected component.

[0104] In the step S105, the component compactor 107 extracts as selected terminals respective terminals of the selected component. The selected terminals are successively moved in the direction Y by the shortest route length and located at appropriate positions. When all of the selected terminals of the selected component are processed, the operation returns to the step S104.

[0105] By repeating the steps S104 and S105, the component constraint graph data 60 are successively registered in the shortest route and the layout of the components is compacted. If the gap between adjacent ones of the routes 2, the terminals 1, the via holes 3, and the polygonal conductor configurations 4 in the initial layout of the printed wiring board is smaller than the minimum allowable gap in the design rule, such smaller gap is modified in the above-mentioned process.

[0106] In the step S111, the routing compactor 103 reads the route segment numbers 31 in the order memorized in the Y-direction constraint graph order data and extracts from the terminal constraint graph data memory 50 the terminal constraint graph data including each routing segment number 31. The routing compactor 108 calculates the routing zone width 52 which is a half of the sum of the width of another route present between the component terminals at both ends of the terminal constraint graph data thus extracted, a necessary gap, and the width of the processed wire segment. The routing zone width 52 is reserved along the contour of each component terminal in eight directions (opposite directions in each of longitudinal, lateral, and first and second diagonal directions) to prepare the configuration data 35 of the routing restraint area having an octagonal configuration around the component terminal.

[0107] If any route already fixed in position is present therebetween, the routing compactor 103 prepares the configuration data 35 of the routing restraint area having an octagonal configuration around the fixed route as a fixed configuration. The routing restraint area is prepared assuming unfixed and deformable routes are freely bent to surround the fixed route. The routing compactor 108 records the configuration number 36, the processed wire segment number 31, the component terminal segment number 31, and the component terminal position number 33 in the routing limit position data having a data structure shown in FIG. 6E.

[0108] In the step S112, the rerouting unit 109 shapes the processed route into a trimmed configuration including diagonal parts and rearranges the processed route outside of the routing restraint area in the routing limit position data.

[0109] Then, the operation returns to the step S101 to repeat the similar process in the direction X to perform compaction in the direction X.

[0110] As described above, compaction in the direction Y is performed through the steps S101 through S112 and compaction in the direction X is performed by repeating the similar process.

[0111] Next referring to FIGS. 9 through 13, the operation of the graphic layout compaction system according to the first embodiment will be described in conjunction with a specific example.

[0112] Referring to FIG. 9, the printed-circuit board has an initial arrangement illustrated in the figure. At first, the compaction direction is set at the direction Y. The component compactor 107 compacts the components downward to obtain a modified arrangement in FIG. 10. Then, the routing compactor 108 calculates the routing limit position data, as depicted by a dotted line in FIG. 10. The rerouting unit 109 reroutes or rearranges the routes into a trimmed configuration including diagonal parts, as illustrated in FIG. 11.

[0113] Next, the compaction direction is set at the direction X. The terminal constraint graph generator 104 prepares the component constraint graph data, as illustrated in FIG. 12. The component compactor 107 compacts the components leftward to obtain a modified arrangement illustrated in FIG. 13. The routing compactor 108 and the rerouting unit 109 rearrange the route in a trimmed configuration including diagonal parts, as illustrated in FIG. 13.

[0114] The above-mentioned graphic layout compaction system has the following effects.

[0115] As a first effect, it is possible to arrange the route in a flexible configuration without being biased in the compaction direction and with a gap kept from each of the component terminals and the routes therearound. This is because the compaction of the components is at first performed with a sufficient routing region reserved and thereafter the routing limit position data are calculated. Within the limited range, the route is arranged in a flexible configuration.

[0116] As a second effect, those routes having a common signal name 37 can be freely arranged without any constraint from their mutual relationship in the initial arrangement and without any influence of one's position upon the other. This is because the constraint graph data are prepared assuming those routes having the common signal name 37 to be transparent to each other.

[0117] Referring to FIG. 14, a graphic layout compaction system according to a second embodiment of this invention comprises a computer 100 operated under control of a program, a display unit 101, and a console section 102, like the first embodiment. The computer 100 may comprise a central processing unit, a processor, or a data processor. The display unit 101 may comprise a CRT display or a liquid crystal display. The console unit 102 may comprise a keyboard and a mouse or a tablet.

[0118] The graphic layout compaction system according to the second embodiment is similar in structure to the first embodiment except that the computer 100 further comprises a constraint graph updating unit 112.

[0119] The constraint graph updating unit 112 is for calculating modification of the constraint graph data resulting from the movement of the components and the routes connected thereto to update the constraint graph data.

[0120] Next referring to FIGS. 15 through 17, the operation of the graphic layout compaction system according to the second embodiment will be described in detail.

[0121] At first, the layout data converter 111 is supplied with the layout data and prepares the segment data in the manner similar to the first embodiment (step S100).

[0122] In a step S202 following the step S100, the constraint graph generator 103 reads per layer plane the segment data from the segment data memory 30 in the order of the X coordinate values in the layer plane. The order of arrangement of the segment data in the direction Y is determined with reference to the Y coordinate values to obtain each pair of adjacent ones of the segment numbers 31 adjacent in the direction Y as the first compaction direction. As illustrated in FIG. 7A, preparation is made of Y-direction constraint graph data which represent the above-mentioned pair of segment numbers 31 as first and second nodes in the order of the Y coordinate values. The constraint graph generator 103 calculates the order of the constraint graph data in the order of the segment numbers 31 included therein from the lowest one in the direction Y. The order of constraint graph numbers 41 of the constraint graph data is recorded as the Y-direction constraint graph order data. In the second embodiment, the constraint graph generator 103 also prepares constraint graph data for the direction X and X-direction constraint graph order data.

[0123] Next, in the manner similar to the first embodiment, the terminal constraint graph generator 104 calculates a route connecting the segment data for which the adjacency is memorized in the Y-direction constraint graph data (steps S1031-S1036 in FIG. 5). Thus, the route having the component terminals at both ends is obtained and the Y-direction terminal constraint graph data having the data structure shown in FIG. 7B are prepared.

[0124] In a subsequent step S204, the order data generator 105 calculates a shortest route in the direction Y. Using a compaction technique based on the Dijkstra method, the order data generator 105 extracts from a terminal constraint graph data memory 40 the Y-direction component constraint graph data (a) having as a core the shortest route of the Y-direction component constraint graph data from the substrate end and (b) connected to the component terminal as the node of the shortest route. The order data generator 105 calculates, as a Y-direction route length of the component number 32 at the other end, the sum of the shortest route length of the component connected thereto and the component relative movement limit length 62 of the component constraint graph data The order data generator 105 selects as a selected graph one of the component constraint graph data which has a shortest route length. The route length of the selected graph is used as the shortest route length of the component number 32 at that end. The component constraint graph data are added to the shortest route. In the present specification, the component number 32 at that node (branch-side node) will be called a selected component. The order data generator 105 memorizes a set of data required to reproduce in a later step S216 the original data state before selection of the selected graph and calculation of the shortest route length.

[0125] Turning to FIG. 16, in a step S205, the component compactor 107 extracts as selected terminals respective terminals of the selected component. The selected terminals are successively moved in the direction X by the shortest route length and located at appropriate positions. Then, the operation proceeds to a following step S206. When all of the selected terminals of the selected component are processed, the operation proceeds to a step S210.

[0126] In case where the route segment number 31 is connected at the upper end to the selected terminal before movement, like a wire 3 connected to a terminal 1 in FIG. 19A, the operation proceeds to the step S206. Otherwise, the operation proceeds to a step S207. In the step S206, the constraint graph updating unit 112 calculates, with respect to the segment numbers 31 connected by the X-direction constraint graph data on the left and the right to the modified route segment before movement, whether or not the adjacency in the direction x is cancelled as a result of the downward movement of the modified route segment in the direction Y (the movement within a range such that upper and lower ends of the modified route segment are not reversed by the movement of the selected terminal. For example, as a result of the movement of the terminal 1 in the layout illustrated in FIG. 19A, the adjacency represented by the X-direction constraint graph data is cancelled for the routes 3 and 7, the routes 3 and 4, and the routes 3 and 8, as illustrated in FIG. 19B. The constraint graph updating unit 112 erases the X-direction constraint graph data for which the adjacency is cancelled as described above. In FIG. 19B, a new adjacency is created for the routes 4 and 8. The constraint graph updating unit 112 calculates whether or not a new adjacency is produced for those segment numbers 31 outside of the erased constraint graph data to prepare new constraint graph data representative of the new adjacency.

[0127] The constraint graph updating unit 112 calculates, with respect to the X-direction terminal constraint graph data including the modified route segment number 31, the width of the routing zones at both ends of the terminal constraint graph data by the use of the result of modification of the modified route segment to update the recorded value. The routing zone is added to the lefthand terminal in the direction X to calculate the routing restraint area. Likewise, the routing restraint area is calculated with respect to the righthand terminal. Then, calculation is made of overlapping of the Y-coordinate widths of the routing restraint area. When the overlapping is cancelled, the constraint graph updating unit 112 deletes the X-direction terminal constraint graph data. If not deleted, the relative movement lout length 62 in the direction X is updated. Then, the operation proceeds to the step S207.

[0128] In the step S207, the constraint graph updating unit 112 extracts the segment numbers 31 (adjacent segments), such as the routes 7, 4, and 8 in FIG. 19A, connected by the X-direction constraint graph data to the selected terminal and the modified route segment, such as the terminal 1 and the route 3 in FIG. 19A. Among these adjacent segments, the segment numbers 31 of the segments, such as the routes 4 and 8, having lower ends lower than the selected terminal and the lower end of the modified wire segment are extracted as first extracted segments.

[0129] Next, in a step S208, the constraint graph updating unit 112 extracts, among the X-direction constraint graph data connected to the extracted segments, the X-direction constraint graph data (between the routes 4 and 8, for example) meeting the following conditions:

[0130] (1) The X coordinate of the selected terminal is interposed between the X coordinates of the segment numbers 31 (third segment) at both ends of the X-direction constraint graph data.

[0131] (2) The uppermost ends of the segments at both ends are located above the lowermost end of the selected terminal after the downward movement in the direction Y.

[0132] (3) The X-direction constraint graph data overlap the track of the movement of the selected terminal.

[0133] The X-direction constraint graph data thus extracted are called an extracted graph. The constraint graph updating unit 112 deletes those of a plurality of the extracted segments which are not connected to the extracted graph.

[0134] Next, the constraint graph updating section 112 extracts the segment numbers 31 connected by the X-direction constraint graph data to the extracted segment, like the route 5 (FIG. 19A) connected to the route 4 as the extracted segment (except those already selected as the extracted segments). Among those segment numbers 31, the segment having an upper end lower than the upper end of the extracted segment connected thereto is added as a new extracted segment. The constraint graph updating unit 112 successively extracts extracted graphs connected to the new extracted segments, such as the routes 5 and 9 and the routes 6 and 10. At this time, the constraint graph updating unit 112 memorizes the extracted graph in a split graph array when the lower end of the modified route segment is connected to the selected terminal by the movement of the selected terminal, as the lower end of the route 3 is connected to the terminal 1 in FIG. 19C. Thus, the extracted segments and the extracted graphs are successively extracted. If any new extracted segment no longer exists, the operation proceeds to a step S209.

[0135] In the step S209, the constraint graph updating unit 112 reads the extracted graph from the split graph array and prepares X-direction constraint graph data recording the segment numbers 31 at the both ends and the modified route segment. The constraint graph updating unit 112 calculates the adjacency of the selected terminal after the movement and the segment number(s) 31 of the extracted graph in the direction X. In presence of the adjacency, the X-direction constraint graph data recording the selected terminal and the segment number(s) 31 are prepared.

[0136] The constraint graph updating unit 112 erases the constraint graph data if the adjacency of the segment numbers 31 at both ends of the extracted graph in the direction X is prevented by insertion of the modified route segment.

[0137] The constraint graph updating unit 112 updates the X-direction constraint graph order data by modification of the modified route segment. Then, the operation returns to the step S205.

[0138] Referring to FIGS. 17, the terminal constraint graph generator 104 prepares, for each selected terminal moved in the direction Y, the terminal constraint graph data connected thereto in the direction X and the component constraint graph data (steps S210 through S213).

[0139] At first in the step S210, the terminal constraint graph generator 104 prepares (left) seed terminal graph data 53 recording the selected terminal at a left end and (right) seed terminal graph data 53 recording the selected terminal at a right end. The terminal constraint graph generator 104 calculates the Y-coordinate width of the routing restraint area of an octagonal configuration surrounding the selected terminal and having eight sides spaced at a necessary gap from the contour of the selected terminal in eight directions (opposite directions in longitudinal, transversal, first and second diagonal directions). The calculated width is memorized in the seed terminal graph data 53.

[0140] Then, in the step S211, the terminal constraint graph generator 104 reads, for each of the (left and right) seed terminal graph data 53, the constraint graph data connected to the selected terminal in the order memorized in the X-direction constraint graph order data (from right to left) to obtain the segment numbers 31 recorded by the constraint graph data. The segments near to and remote from the selected terminal are called first and second segments. When the first segment is recorded in the seed terminal graph data 53, the operation proceeds to the steps S212 and S213 if the second segment is a wire and a component terminal, respectively. When the first segment is not recorded in the seed terminal graph data 53, the terminal constraint graph generator 104 further reads the X-direction constraint graph data and performs similar processing. When all of the seed terminal graph data 53 have been processed, the operation proceeds to the step S214.

[0141] In the step S212, the terminal constraint graph generator 104 duplicates, if the second segment is a route and if the Y-coordinate width between both ends of the route overlaps the Y-coordinate width of the routing restraint area of the seed terminal graph data 53, the seed terminal graph data 53 into new seed terminal graph data 53. The new data are recorded with the segment number 31 of the second segment added thereto. In addition, the routing width of the second segment and the necessary gap are added to the routing restraint area width of the old data to calculate a new routing restraint area width to be recorded. The routing width of the second segment and the necessary gap are added to the shield region width of the old data to calculate a new shield region width to be recorded. In the old data, the terminal constraint graph generator 104 records the Y-coordinate width of the second segment as the shield region width. When the routing restraint area of the seed terminal graph data 53 is completely covered with the shield region, the seed terminal graph data 53 are erased. Then, the operation returns to the step S211.

[0142] In the step S213, the terminal constraint graph generator 104 records, if the second segment is a component terminal and if the Y-coordinate width of the second segment overlaps the Y-coordinate width of the routing restraint area of the seed terminal graph data 53, the second segment and the selected terminal as opposite nodes. In the manner similar to the step S1035 in FIG. 5, the terminal constraint graph generator 104 calculates the X-direction component relative movement limit length 62 and prepares the X-direction term al constraint graph data and the component constraint graph data recording the above-mentioned limit length. In the seed terminal graph data 53, the terminal constraint graph generator 104 records as the shield region width the Y-coordinate width of the component terminal segment data of the upper segment. When the routing restraint area of the seed terminal graph data 53 is completely covered with the shield region, the terminal constraint graph generator 104 erases the seed terminal graph data 53. Then, the operation returns to the step S211 to process next seed terminal graph data 53.

[0143] In the step S214, the terminal constraint graph generator 104 extracts the X-direction constraint graph data recording at the left end the segment number 31 of the modified route segment connected to the component terminal of the selected component and obtains the segment number 31 (right segment) at the right end. Then, the terminal constraint graph generator 104 extracts the X-direction terminal constraint graph data recording the right segment mentioned above and extracts the segment number 31 (right terminal) of the component terminal at the right end. The terminal constraint graph number 51 of the constraint graph data thus extracted and the segment number 31 of the right terminal are recorded in a right terminal array (not shown). Likewise, the terminal constraint graph generator extracts the X-direction constraint graph data recording the modified route segment at the right end and obtains the segment number 31 (left segment) at the left end. The terminal constraint graph generator 104 extracts the X-direction terminal constraint graph data recording the left segment mentioned above and extracts the segment number 31 (left terminal) of the component terminal at the left end. The terminal constraint graph number 51 of the constraint graph data thus extracted and the segment number 31 of the left terminal are recorded in a left terminal array (not shown).

[0144] The terminal constraint graph generator 104 combines the left and the right terminal arrays and reads the segment numbers 31 of the wires from the left terminal in the left terminal constraint graph data to the modified wire segment. The terminal constraint graph generator 104 also reads the segment numbers 31 of the routes from the right terminal in the right terminal constraint graph data to the modified route segment. The terminal constraint graph generator 104 calculates a total sum of the widths of the routes of the segment numbers 31 from the left terminals to the right terminals, the width of the modified wire segment, and the necessary gaps to obtain the routing zone width 52. When the sum of the routing zone width and the radii of the left and the right terminals in the direction Y (on confronting sides) is not smaller than the gap between the both terminals in the direction Y, the terminal constraint graph generator 104 prepares the terminal constraint graph data having the left and the right terminals at both ends. In the manner similar to the step S1036 in FIG. 5 (the first embodiment), the terminal constraint graph generator 104 calculates the component relative movement limit length 62 in the direction X and records the calculated limit length in the X-direction terminal constraint graph data and the component constraint graph data. The above-mentioned operation is performed for all combinations of the right and the left terminal arrays 72 and 73. Thereafter, the operation proceeds to the step S215.

[0145] In the step S215, among all component constraint graph data including newly prepared X-direction component constraint graph data, the terminal constraint graph generator 104 calculates a shortest route of the component constraint graph data by the use of the Dijkstra method. Specifically, the component constraint graph data giving shortest routes are successively connected from the leftmost end to the rightmost end of the board in the direction X. The shortest route length means the traveling distance over which the rightmost end of the board travels towards the leftmost end. The terminal constraint graph generator 104 compares the shortest route length with a required reduction distance of the substrate end by compaction. If the shortest route length is smaller than the required reduction distance, detection is made of a compaction neck in the direction X. In this event, the operation proceeds to the step S216. Otherwise, the operation returns to the step S204 to repeat the processing.

[0146] Turning back to FIG. 15, in the step 5216, the terminal constraint graph generator 104 calculates the terminal constraint graph data having as opposite nodes the terminal of the selected component and a terminal of the mating component connected to the terminal of the selected component by the X-direction terminal constraint graph data. Assuming that the terminals at the both ends are projected in the direction Y, calculation is made of the Y-direction traveling distance to a position where their images most approach each other with the routing zone interposed therebetween. Preparation is made of the Y-direction component constraint graph data (terminal elimination graph 43) with the above-mentioned traveling distance as the Y-direction component relative 3movement limit length 62 The terminal constraint graph generator 104 recovers the record of the Y-direction shortest route of the component constraint graph data to that before selection of the selected component in the step S204.

[0147] In the above-mentioned manner, the steps S204 through S216 illustrated in FIGS. 16 and 17 are repeated to control the compaction so that the component layout in the direction X does not deviate from the limited range. In this process, the component constraint graph data are successively recorded.

[0148] In a step S217, the component compactor 107 moves each component in the direction X by the shortest route length to arrange the component.

[0149] Then, in a step Sill, the wire compactor 108 prepares the wiring limit position data in the manner similar to the step S111 in the first embodiment.

[0150] Finally, in a step S112, the rewiring unit 109 shapes the processed wire into a trimmed configuration including diagonal parts and rearranges the processed wire outside of the routing restraint area of the routing limit position data, in the manner similar to the step S112 in the first embodiment.

[0151] Next referring to FIGS. 20A through 20C, the operation of the graphic layout compaction system according to the second embodiment will be described in detail in conjunction with a specific example.

[0152] Referring to FIG. 20A, the layout to be compacted has an initial arrangement illustrated in the figure. As a result of downward compaction, a modified arrangement illustrated in FIG. 20B is obtained. Herein, the X-direction constraint graph data of the components are limited in route length to four components. Therefore, the components 1 through 4 are moved downward while the component 5 is not. This is because, if the component 5 is moved together, the route length of the X-direction constraint graph data exceeds the limit Therefore, the component 5 is arranged in a next or second row. Then, the components 6 through 8 are moved downward to be arranged in the second row, following the component 5. At this time, the component 9 is not moved downward and arranged in a third row because, if the component 9 is added to the second row, the route length of the X-direction constraint graph data exceeds the limit. In the third row, the components 10 through 12 are arranged, following the component 9. The component 13 is left in a fourth row. In the fourth row, the components 14 through 16 are arranged.

[0153] The layout in FIG. 20B obtained by the downward compaction is further subjected to leftward compaction to obtain the layout illustrated in FIG. 20C.

[0154] The graphic layout compaction system according to the second embodiment has the following effect.

[0155] In the layout formed by the Y-direction compaction, a longest route length in the direction X can be suppressed within the limit value. Therefore, the board dimension in the direction X can be suppressed within the limited range after the X-direction compaction subsequently carried out.

[0156] This is because the graphic layout compaction system. has two functions which will presently be described.

[0157] The first function is to automatically calculate the moving positions of the components upon compaction. Specifically, preparation is made of the component constraint graph data with the length of the graph connecting the component numbers 32 as the component relative movement limit length 62 of the components at the opposite ends. Calculation is made of the shortest route length from the substrate end to the component at the node of the graph as the compaction traveling distance of the component.

[0158] The second function is to control the density of the components in the direction perpendicular to the compaction direction. Specifically, detection is made of the component resulting in shortage of the compactable distance of the board end perpendicular to the compaction direction below the required distance. Preparation of made of a terminal elimination graph 43 connecting in the compaction direction the component in question and another component adjacent thereto by the use of the component constraint graph data.

[0159] A graphic layout compaction system according to a third embodiment of this invention has a structure similar to that of the first embodiment (FIG. 3) except the computer 100 further comprises a shortest route cancelling unit which will presently be described. The shortest route cancelling unit is for cancelling, after the component compactor 107 calculates the shortest route of the component constraint graph data, the shortest route by moving the via hole in the shortest route in a shortest route cancelling direction to thereby remove the interference against the compaction.

[0160] Referring to FIG. 21, the operation of the graphic layout compaction system according to the third embodiment will be described in detail.

[0161] At first in a step S100, the layout data converter 111 is supplied with the layout data and prepares the segment data, in the manner similar to the step S100 in the first embodiment.

[0162] In a step S202 following the step S100, the constraint graph generator 103 prepares the Y-direction and the X-direction constraint graph data in the manner similar to the second embodiment.

[0163] Then, through steps S1031 through S1036, the terminal constraint graph generator 104 prepares the Y-direction terminal constraint graph data and the Y-direction component constraint graph data in the manner similar to the steps S1031 through S1036 (FIG. 5) in the first embodiment.

[0164] In a step S204, the order data generator 105 selects the component constraint graph data (selected graph) of the shortest route in the direction Y and the component (selected component) at the end thereof, in the manner similar to the step S204 in the second embodiment.

[0165] In the manner similar to the steps S205 through S215 in FIGS. 16 and 17 in the second embodiment, the selected component is moved in the direction Y by the shortest route length. The component constraint graph data in the x direction is calculated. The shortest route length between the substrate ends is calculated and compared with the allowable range. If the shortest route length is not smaller than the required reduction distance in the direction X, the operation returns to the step S204 to continue the processing. Otherwise, the operation proceeds to a step S316.

[0166] In the step S316, the shortest route cancelling unit extracts, among the components at the nodes of the shortest route in the direction X, the via holes or the few-terminal components. Among the extracted components, selection is made of the component (displaced component) which is not used as the node of the shortest route of the component constraint graph in the direction T. In the following manner, the displaced component is eliminated from the shortest route of the X-direction compaction.

[0167] Specifically, the shortest route cancelling unit prepares the Y-direction terminal elimination graph 43 (component constraint graph data 60 connecting the displaced component and the component number 32 coupled to the displaced component by the X-direction component constraint graph data, in the manner similar to the first embodiment.

[0168] Next, the shortest route cancelling unit adds to the component constraint graph data the Y-direction terminal elimination graph 43 connected to the displaced component. By this addition, it is necessary to again search the shortest route of the component constraint graph data and to update the shortest route of the X-direction component constraint graph data following the change in traveling distance of the component. For this purpose, the operation returns to the step S204.

[0169] In the above-mentioned manner, the steps S204 through S316 are repeated to control the compaction so that the component layout in the direction X does not deviate from the limited range. In this process, the component constraint graph data are successively recorded.

[0170] Then, in a step S217, the component compactor 107 moves each component in the direction X by the shortest route length of the component constraint graph data to arrange the component.

[0171] Next, in a step S111, the wire compactor 108 prepares the wiring limit position data in the manner similar to the step Sill in the first embodiment.

[0172] Finally, in a step S112, the rewiring unit 109 shapes the wire into a trimmed configuration including diagonal parts and rearranges the wire, in the manner similar to the step S112 in the first embodiment.

[0173] The above-mentioned graphic layout compaction system according to the third embodiment has the following effect.

[0174] According to the third embodiment, the via hole as an obstacle against the movement of the component in the moving direction is moved in the direction perpendicular to the moving direction. Thus, the obstacle against the movement of the component is automatically cancelled to enable the movement of the component. This is because the shortest route cancelling unit serves to detect the via hole becoming the obstacle in the direction X as a result of the Y-direction compaction and to move the via hole in the direction Y.

[0175] A graphic layout compaction system according to a fourth embodiment of this invention comprises a computer 100 operated under control of a program, a display section 101, and an operating section 102, like the first embodiment (FIG. 3). In addition to the structure described in conjunction with the first embodiment, the computer 100 further comprises a component movement designating unit which will presently be described. The component movement designating unit is for setting component movement target vector data 63 (FIG. 23) designating the moving direction of each component and directed to any desired position in the layout.

[0176] Next referring to FIG. 22, the operation of the graphic layout compaction system according to the fourth embodiment will be described in detail.

[0177] At first in a step S100, the layout data converter 111 is supplied with the layout data and prepares the segment data, in the manner similar to the step S100 in the first embodiment.

[0178] Then, the component movement designating unit sets the component movement target vector data 63 directing each component to a target position 630 at a desired position in the layout. Specifically, when the operator command input device 110 is supplied with an operator s command through manipulation of a mouse or a keyboard, the component movement designating unit prepares for each component the component movement target vector data 63 representative of a vector extending from its initial position to the target position 630. The component movement designating unit can read through a communication channel or from a magnetic recording medium a group of the component movement target vector data 63 for a plurality of components.

[0179] In the fourth embodiment, a fixed point to serve as a movement target start point is recorded as a node of the component constraint graph. The Y-direction component constraint graph data are prepared with the Y-direction (downward) component movement target distance used as a graph length, the movement target start point as a first node, and a component number 32 as a second node. Likewise, the X-direction component constraint graph data are prepared with the X-direction (leftward) component movement target distance used as a graph length. By preparing the component constraint graph data connecting the movement target start point and the component as described above, it is possible to move the component along the movement target vector data 63.

[0180] In the fourth embodiment, it is possible to collectively set the component movement target vector data 63 (step S301). Specifically, by collectively setting the component movement target vector data 63 to direct the moving directions of all components toward a desired layout position, the component layout can be converged. On the other hand, by collectively setting the component movement target vector data 63 to direct the moving directions reversely, the component layout can be enlarged.

[0181] Next, in the manner similar to the steps S101 through S1036 in the first embodiment, another component constraint graph data are added to the component constraint graph data connecting the movement target start point and the component number 32. Through the steps S104 and S105, the component layout is compacted by the use of the component constraint graph data.

[0182] Then, in the steps Sill and S112, the routing limit position data are calculated. In a space inside the limit position, the route is rearranged in a flexible configuration having diagonal parts.

[0183] In the fourth embodiment, it is possible to compact the layout by the operation of the second or the third embodiment after the component movement designating unit sets the component movement target vector data 63.

[0184] Next referring to FIGS. 22 through 24, the operation of the graphic layout compaction system according to the fourth embodiment will be described in conjunction with a specific example.

[0185] At first referring to FIG. 22, compaction by the graphic layout compaction system will be described with respect to the layout illustrated in FIG. 23.

[0186] In response to the operator's command, the component movement designating unit designates the component movement target vector data 63 for each individual component, as illustrated in FIG. 23. Furthermore, a new route to be inserted is designated (step S301).

[0187] As illustrated in FIG. 24, the component compactor 107 performs compaction of the arrangement. Specifically, starting from a component whose terminal has a minimum movement limit length in the direction X or Y, the components are successively moved in the direction X or Y towards the target position 630 of the movement target vector. In FIG. 24, a routing image is illustrated although the exact arrangement of routes is not yet determined at this stage.

[0188] Next, the routing compactor 108 prepares routing limit position data representative of a routing limit position. For a particular route interposed between the component terminals as the opposite nodes of the terminal constraint graph data, the routing limit position is defined along the contour of one of the component terminals in the form of an octagonal configuration. The routing limit position data are memorized in the routing limit position data memory 80 (step S111).

[0189] Finally, the rerouting unit 109 shapes the route into a trimmed configuration including diagonal parts and reroutes the route (step S112). The result is shown in FIG. 25.

[0190] The graphic layout compaction system according to the fourth embodiment has a principal effect as follows.

[0191] As described above, it is possible according to the fourth embodiment of this invention to move the component to any desired position. For example, it is possible to enlarge the layout of the components. This is because the fourth embodiment comprises the component movement designating unit designating the moving direction of the component by the use of a movement target position, and the component compactor 107 for moving the component towards the movement target position.

[0192] A graphic layout compaction system according to a fifth embodiment of this invention is similar to the fourth embodiment. In the fifth embodiment, the component movement designating unit sets the component movement target vector data 63 directed to enlarged positions such that the distances between the positions of all components and the center of the layout are analogously enlarged.

[0193] Then, the compaction described in the fourth embodiment is performed to obtain the layout in which the components are arranged in the enlarged positions. Thus, according to the fifth embodiment, the layout of the components can be enlarged with longitudinal and lateral orders maintained.

[0194] Next, unconnected portions between the component terminals are interconnected by an ordinary automatic routing device such as a maze router and a channel router. Alternatively, in the enlarged arrangement, the components or the interconnections are modified by manipulation on a display screen.

[0195] Then, the component movement designating unit described in the fourth embodiment sets the component movement target vector data 63 directed to compressed positions obtained by analogously compressing the distances between the positions of all components and the center of the layout.

[0196] Then, the compaction in the fourth embodiment is performed to arrange the components at the compressed positions.

[0197] The graphic layout compaction system according to the fifth embodiment has a principal effect described in the following.

[0198] In the fifth embodiment, the interconnection between the components or design modification is performed in a sufficiently wide space and thereafter the components and the routes are compacted. Therefore, high-density interconnection is readily achieved. Furthermore, the compaction in the fifth embodiment arranges the components at the positions where the longitudinal and the lateral orders are maintained Therefore, the compaction in a first direction hardly produces an obstacle against the compaction in a second direction perpendicular to the first direction.

[0199] This is because the component compactor 107 at first moves the components to widen the gap between the component and the route. In the compaction to compress the layout, the component movement target vector data 63 are designated so that the longitudinal and the lateral relationship between the components are maintained.

[0200] A graphic layout compaction system according to a sixth embodiment of this invention basically has a structure similar to that of the first embodiment except that the computer 100 further comprises a route updating unit which will presently be described. The route updating unit serves to exchange the order of a designated route and a designated component terminal or route.

[0201] Referring to FIG. 26, the operation of the graphic layout compaction system according to the sixth embodiment will be described in detail.

[0202] At first in a step S100, the layout data converter Ill is supplied with the layout data and prepares the segment data, in the manner similar to the step S100 in the first embodiment.

[0203] Next, in the manner similar to the step S202 in the second embodiment, the constraint graph generator 103 prepares the Y-direction constraint graph data and the X-direction constraint graph data.

[0204] Then, in a step S504, the instruction input device 110 displays the layout of the routes and, in response to an operator's command, designate a via hole D (designated via hole) and a route adjacent thereto, as illustrated in FIG. 27A.

[0205] Next, the route updating unit arranges the route (first route) to surround the designated via hole, as illustrated in FIG. 27B.

[0206] Specifically, the route updating unit extracts the designated via hole and the segment number 31 connected thereto by the constraint graph data in a layer plane where the first route is present. In addition, the segment number 31 connected to the first route by the constraint graph data is extracted. The route updating unit modifies the first route into a configuration surrounding the designated via hole as illustrated in FIG. 27B within a space between the segments thus extracted. Herein, it is not essential to satisfy the required gap from the segments therearound. Thus, the segment data of the route are updated The constraint graph generator 103 prepares new constraint graph data recording the segment number 31 of the route in that route and the segment number 31 of an adjacent segment adjacent thereto in the direction X or Y (step S505).

[0207] Then, in the following manner, the route updating unit removes a loop of the route. Specifically, when the one of the position numbers 33 recorded in the segment data indicative of the surrounding route is shared only by the route segment (adjacent segment) adjacent thereto via the constraint graph data, the route updating unit alters the position number 33 (shared position) into the position number 33 at the other end of the segment data connected thereto. Then, the route updating unit calculates, by the use of the existing constraint graph data recording the route segment number 31 with the position number 33 at one end modified as mentioned above and another segment number 31, whether or not the both segment numbers 31 interferes with each other in the direction Y. If the both segment numbers 31 no longer interfere, the route updating unit deletes the constraint graph data (step S506).

[0208] Thus, as illustrated in FIG. 28A, the route surrounding the via hole is formed.

[0209] Referring to FIG. 29A, a via hole A is a designated via hole to be changed in relative position with the first route. The designated via hole A is connected to another route (second route) on the layer plane where the first route is present. In a range in which the second route runs in parallel to the first route in the direction X, each of the first and the second routes forms a single continuous line without any branch. One ends of the first and the second routes within the above-mentioned range are connected to the via holes B and A, respectively. In this event, the route updating unit changes the positions of the first and the second routes in the following manner.

[0210] Specifically, the route updating unit extracts the constraint graph data (first constraint graphs) recording the segment number 31 of the first route. The constraint graph numbers 41 are memorized in a first route array (not shown) in the order from the designated via hole A to the component terminal (via hole B) at the terminating end of the first route. The route updating unit memorizes the segment number 31 of the component terminal (via hole B) connected to the terminating end of the first route.

[0211] Then, the route updating unit extracts the constraint graph data (second constraint graphs) recording the segment number 31 of the second route. The constraint graph numbers 41 are memorized in a second route array (not shown) in the order from the designated via hole A at the top end of the second route to the via hole (component terminal C) at the terminating end. The route updating unit memorizes the segment number 31 of the via hole (component terminal C) represented by the position number 33 indicative of the terminating end of the second route (step S507).

[0212] Next, the route updating unit compares the first route array and the second route array. In case where both of the first and the last constraint graph numbers 41 in the second route array are recorded in the first route array, the start end and the terminating end of the second route are covered with the first route. In this case, the route updating unit changes the order of the first and the second routes in the following manner.

[0213] Specifically, the route updating unit deletes a part of the second route, i.e. the segment data of the second route directly coupled to the via holes at the both ends to separate the route configuration from the via holes. The route updating unit deletes those portions of the first route which are adjacent to the via holes in the direction Y to separate the route configuration. The route updating unit prepares a route configuration such that the portion of the first route between the via holes is coupled to the second via holes. The route updating unit prepares another route configuration such that the portions of the first route left on the both sides outward of the via holes are connected to the portion of the second route left between the via holes. The route updating unit updates the constraint graph data between each of the segment numbers 31 of these routes and a surrounding segment number 31 adjacent thereto in the direction X or Y. Next, the route updating unit executes the step S506 upon the first route to remove the loop of the route (step S508).

[0214] In case where the first constraint graph number of the second route array is recorded in the first route array and the last. constraint graph number of the first route array is recorded in the second route array, the second and the first routes partly run in parallel to each other as illustrated in FIG. 29A. In this case, the route updating unit changes the order of the second and the first routes as illustrated in FIG. 29B, in the manner which will hereafter be described.

[0215] Specifically, the route updating unit removes a part of the second route that is coupled to the designated via hole to divide the route configuration of the second route. The route updating unit removes a part of the first route that is coupled to the terminating via hole on the right side to divide the route configuration. The route updating unit removes parts of the first and the second routes which are adjacent to both of the via holes in the direction Y to divide the route configurations. The route updating unit connects the left end of a part of the first route between both via holes to the designated via hole, and connects the right end to a separated part of the second route on the right side of the via hole at the terminating end. The route updating unit couples the left end of a separated part of the second route between the both via holes to a separated part of the first route on the left side of the designated via hole, and connects the right end of the part of the second route to the via hole at the terminating end. The route updating unit prepares new constraint graph data between each of the segment numbers 31 of these routes and a surrounding segment number 31 adjacent thereto in the direction X or Y. Next, the route updating unit executes the step S506 upon the first route to remove the loop of the route (step S509).

[0216] In the above-mentioned manner, the first and the second routes are changed in the order of arrangement.

[0217] Then, the terminal constraint graph generator 104 prepares the component constraint graph data via the processing similar to the steps S1031 through S1036 (FIG. 5) described in conjunction with the second embodiment.

[0218] Next, in the manner similar to the steps S204 through S216 (FIGS. 15 through 17) described in conjunction with the second embodiment, the component compactor 107 executes the compaction in the direction Y on the basis of the component constraint graph data. Then, in the step S217, the compaction in the direction Y is carried out.

[0219] The route compactor 108 and the rewiring unit 109 calculate the wiring limit position data and rearranges the route in a flexible configuration including diagonal lines, in the manner similar to the steps S111 and S112 described in conjunction with the first embodiment.

[0220] Thus, the layout illustrated in FIG. 28A is compacted in the directions Y and X to obtain the layout in FIG. 28B in which the gaps between the routes satisfy the design rule.

[0221] The above-mentioned step S1031 and subsequent steps may be performed in the following manner. Specifically, in the manner similar to the steps S101 through S1036 in the first embodiment, the terminal constraint graph generator prepares the component constraint graph data. In the manner similar to the step S104 and S105, the component compactor 107 compacts the component layout on the basis of the component constraint graph data. Then, in the manner similar to the steps S111 and S112 in the first embodiment, the route compactor 108 calculates the route limit position data and the rewiring unit 109 rearranges the route into a flexible configuration including diagonal lines.

[0222] Thus, the layout illustrated in FIG. 28A is compacted in the direction Y. Furthermore, the processing from the step S101 is repeated to carry out the compaction in the direction X to obtain the layout in which gaps between the routes satisfy the design rule.

[0223] A main effect of the graphic layout compaction system according to the sixth embodiment is as follows.

[0224] In the sixth embodiment, the layout is modified so that the routes are arranged to surround the component terminal and the relationship (order) between the routes is changed. Then, the modified layout is compacted. It is thus possible to obtain the layout in which the routes are shaped and the design rule is met.

[0225] It will readily be understood that this invention is not restricted to the foregoing embodiments and various modifications can be made within the scope of this invention. For example, the program for achieving various functions of the computer 100 may be recorded in a recording medium 115 depicted by a broken line in FIG. 3. Herein, the term “recording medium” means a medium recording the program which can be read by the computer. Specifically, the recording medium includes a CD-ROM, a magnetic disk such as a flexible disk, and a semiconductor memory. The recording medium 115 may be a magnetic tape, a paper tape, or even a paper recording the program. In case where the recording medium 115 is a paper, the computer further comprises a reading device such as an OCR (optical character reader) and a compiler for converting characters (codes) read by the reading device into a machine language recognizable by the computer.

[0226] As described above, according to this invention, compaction of a pattern of at least one layer having routes, terminals, via holes, and polygonal conductor configurations is performed in the following manner. Supplied with the layout data, the component terminals and the via holes are divided into the segment data per each layer. the routes and the polygonal conductor configurations are divided into the segment data separated by the bending points and the branching points. The segment data coupled to each other are assigned with the common component number. The individual via holes are assigned with the individual component numbers. Per each layer plane, the terminal constraint graph data and the component constraint graph data are prepared to record the limit distance within which the component terminals adjacent in the longitudinal or the lateral direction can move towards each other with the wiring zone comprising the routes and the necessary gap interposed therebetween. The components are compacted on the basis of the component constraint graph data Thereafter, the routes are shaped and rearranged. Thus, in order to avoid the interference upon compaction of the components in the second compaction direction perpendicular to the first compaction direction, the arrangement of the component causing such interference is modified to thereby reduce the layout area.