JPH02218148A - Decision of terminal position of block in vlsi - Google Patents

Abstract

PURPOSE:To minimize the length of wirings by incorporating the initial wiring step based on an evaluation function only for the length of the wiring and the wiring improving step for rewiring, and deciding the positions of terminal based on the general wiring for deciding the wiring paths for all the signals. CONSTITUTION:In wiring sequence of terminals for every network, at first, the shortest distance between the terminals among the terminals in already designed blocks 11-14 is wired. The wiring is performed sequentially. Finally, the terminals in blocks 21 and 22 wherein designs are not yet finished are wired. In graph formation, three kinds of the graphs, i.e. a floor plan graph, a path seeking graph and a channel position graph, are formed. In the initial wiring, the path seeking whose cost is only for the wiring length is performed. Then, the path seeking and the wiring improvement for adding the costs in consideration of the congestion degree are performed. Rewiring is performed for the network which passes through the congested wiring channel. As a result of the path seeking, the optimum terminal positions are sequentially determined from the networks having the long wiring length in correspondence with the wiring paths. In this way, the wiring length can be minimized, and the terminal position suitable for an actual layout can be determined.

Description

[Detailed description of the invention]

[Industrial Application Field 1] The present invention relates to a method for determining the terminal position of an undesigned block in floor planning of a large-scale LSI. [Prior Art] In the layout design of large-scale LSIs, it is common to divide the layout into multiple functional blocks, and floor planning for optimizing the entire chip has become an important issue. . What is floor planning?
The purpose of this is to estimate how to arrange multiple functional blocks constituting a chip on a chip in order to optimize layout conditions such as chip area, wiring length, timing, etc., and to obtain the chip layout. At this time, if there is an undesigned block, the chip area and wiring length can be optimized by determining the terminal position of that block in consideration of wiring requirements, and this terminal position determination is an important design item. It has become. The general method for determining the terminal position of an undesigned block is to use rough wiring to determine the approximate path of each signal, and then determine the terminal position each time.
Inter-block schematic wiring block for hierarchical 1/i-aud of LSN ['J Gram J (Information Processing Society of Japan, Set δ1 Child 1 Dynamics Study Group, DA36-8.19B?-2), and r V]
[A method for optimizing block-shaped bin arrangement in SI L/IAU l-design] (IEICE technical report, VLSI design technology study group, VT, D88-4.1988-4), etc. (Problem to be solved by the invention) In the conventional determination of the terminal position of an undesigned block, the general route is determined by rough wiring, and the terminal position is determined each time, so the order of the signals to be roughly wired is It is difficult to determine the position of the terminal at t:, which affects the position determination and minimizes the wiring length. The present invention was devised in view of the following two points, and it is an object of the present invention to provide a method for determining the terminal position of a Glock in a large-scale LSI, which minimizes the wiring length independent of the order of the signals to be roughly wired. The purpose is

[Means to solve the problem]

In order to achieve the above object, the method of determining the terminal position of a block in a large-scale T, SI according to the present invention performs a route search based on the evaluation interval of only the wiring length, and does not depend on the order of the signals to be roughly routed. Initial wiring processing process to obtain wiring results,
1', using the results of the initial wiring processing described above, to reroute the wiring that passes through the wiring area that governs the chip size. A terminal position determination step consisting of a general wiring step for determining the wiring route, a two-step processing step for determining the approximate position of the terminal in order of the wiring length as a result of the above-mentioned general wiring, and then determining the detailed position. It is configured to have.

[Effect]

In the present invention, the rough wiring consists of an initial wiring process and a wiring improvement process, and in the initial wiring process, a route search is performed using an evaluation function based only on the wiring length. Thereby, it is possible to obtain a wiring result that does not depend on the order of the signals to be roughly routed. Next, wiring improvement processing is performed using this result. In the wiring improvement process, the wiring that passes through the wiring area where the zip size is controlled is rerouted. Once the wiring paths for all signals are determined by this rough wiring, terminal positions are determined next. In terminal position determination, as a result of the rough wiring, the terminal positions are determined in order from the signal with the longest wiring length. The terminal position determination is performed in a two-step process of first determining the approximate position and then determining the detailed position. [Example 1] First, a VLSI layout model to which the present invention is applied and a graph model used in the present invention will be explained,
Examples of the present invention will be described. Layout model The layout model of VT and SI to which the present invention is applied will be defined using FIG. The chip is rectangular and functional.
TJO placed on four sides with cock 11-14.21.22
It is assumed that the buffer array is composed of buffer rows 31 to 34, and the positions of the individual I10 buffers are given. In addition, the shape of functional blocks 11 to 14, 21, and 22 is rectangular,
We deal with the following two types. 1゜Pre-designed Block I Cock (ii = 14) Functional block 1. The shape is fixed and its 9 items are fixedly arranged on the four sides of the block. 2. Undesigned block (2), 22) A functional block whose shape can be changed, and whose terminal can be freely repositioned as long as it is on all four sides of the block. Graph Model The graph model used in the present invention will be explained. (A) Floor plan graph (FIG. 2-(a)) A graph showing the relative arrangement between functional blocks and wiring channels. The node S1 of the floor plan graph has its position coordinates from the given block arrangement, and the branch L1 has information about the distance between the nodes. (B) Route search graph (Fig. 2-(b)) A graph obtained by adding node S2 and branch L2 for route search to the floor plan graph. The nodes to be added include those corresponding to terminals of already designed blocks, and intra-block subgraphs used for terminal position determination and intra-block wiring of undesigned blocks. Also, like the floor plan graph, each node has its position coordinates, and each school has the distance between nodes! (branch length) as information. (C) Channel position graph (FIG. 2-(C)) A graph showing the relative positions of functional blocks and wiring channels. Node S3 corresponds to a functional block, and branch L3 corresponds to a wiring channel. There are two types: horizontal channel position graphs and vertical channel position graphs. Processing Processing An outline of the processing according to the embodiment of the present invention is shown below. [1] With terminal ordering, the wiring order of the terminals for each net is such that the terminals of the already designed block are wired in order from the one with the smallest distance between the terminals, and then the terminals of the undesigned block are wired last. It can be decided. [21 Graph Generation In graph generation, the three types of graphs described above are generated. [3] Perform route search using only the initial wiring length as cost. In the initial wiring, only the wiring length is considered as a cost, so there is no need to order the nets. [4] Wiring improvement: Search for a route by adding costs that take into account the degree of wiring congestion. In wiring improvement, nets that pass through congested wiring channels are rerouted. [51 Terminal Position Determination In terminal position determination, as a result of the route search, the optimum terminal position is determined according to the wiring route in order from the net with the longest wiring length. The route search method used for initial wiring and wiring improvement is as follows:
It uses the minimum cost maze method on the path search graph. The maze method is suitable for finding the minimum cost route between two terminals, and in order to apply it to route searching for multi-terminal signals, it must be broken down into two-terminal wiring problems. In this method, the route search between the terminal and the search/cleaning path is performed according to the wiring order of the terminal. In addition, the starting point and ending point in the maze method may be set as a terminal or a searched route, and are set as follows. (1) When using the terminal of an already designed block as the starting point or end point The node of the route search graph corresponding to the terminal of the already designed block is set as the starting point or end point of the route search. (2) When using the terminal of an undesigned block as the starting point or end point, use all nodes on the four sides of the undesigned block (not including the four corners) as the starting point or end point of the path search. When using a route that has been previously determined as the end point, all nodes on the route that has already been found are used as the end point of the route search. In the initial wiring of the virtual distribution process, the above route search is performed for all nets. At this time, , the cost of each school in the path search graph is calculated by the following formula: ERFC" ELEN ERVC: CL Length a Weighting is constant Also, regarding the cost of the edges of the intra-block subgraph,
Each time an intra-block passing wiring occurs in route search, its cost is updated using the following equation. ERVC=ERVC+D X ELENp Weighting is a constant wiring improvement process The wiring improvement process is performed by the following process. As a result of the route search, the width of each wiring channel is estimated, costs are attached to the branches of the channel position graph, and critical buses in both horizontal and vertical directions are determined. The cost of the branch of the channel position graph is calculated by the following formula. ECC==BWI/2-1- BW2/2-
1- CWEcc Cost of branch BWI Horizontal or vertical width of the left or lower block of the branch BWZ Horizontal or vertical width of the right or upper block of the branch ew Wiring channel width Also wiring channel width C Since the required number of main lines for each wiring channel is estimated based on the route search results, %J/ is calculated using the following equation based on the estimate. cw = D Appendix 1? ). Two branches of the path search graph that correspond to channels on the critical bus, and one cost EI of the other branches, such as Ertep? , C are calculated by multiplying J by the following formula. Eaep-γX ELEN ERC= ELEN / (Lep-I4a)XDE
LEN Length of the branch to which the cost is attached LCP Length of the critical bus T, P Length of the nearest bus including the cost and the branch to be attached D Wiring center-to-center design rule γ Weight I = J-key constant, from the cost assignment of 2 , the wiring channel that dominates the chip size is difficult to pass through, and other wiring channels become easy to pass depending on the wiring margin. As for the branches of the intra-block subgraph, when an intra-block passing wiring occurs in the route search, its cost is updated, similar to the initial wiring process. All nets passing through the channels on the horizontal and vertical critical buses will be stripped and rewired. Repeat Step 1 to Step 3 a specified number of times to obtain a rough wiring result that takes into account the degree of wiring congestion and chip size. Terminal position determination Considering the rough wiring results for the terminals of undesigned blocks 1. to determine the optimal terminal position. Instead of finding the wiring route for each net and determining the terminal position each time, the method is to temporarily assign the wiring route to the node of the route search graph at the wiring stage, and after the routes of all nets have been determined, the terminal position is determined. Determine. The processing flow is shown below. Step 5: Sort all nets in descending order of wiring length based on the 1 wiring result. Step 5: Allocate the positions of the non-movable terminals in 2-sort order. 5 steps, 3 In sort order, 6 movable terminals are used and positions are allocated. Here, an immovable terminal is a terminal that is constrained by other terminals on the same net. ", refers to a terminal whose optimal terminal position is uniquely determined, and a movable terminal refers to a terminal for which there are several candidates for the optimal terminal position even under the constraints of other terminals in the same net. To tell. In Figure 3(a),
It is best to determine the terminal position of terminal a of undesigned block A at the bottom of the right side of the block, but for undesigned block B
The terminals can be anywhere on the path around the block. Terminal position determination is performed in two steps: rough position allocation to the nodes of the route search graph, and detailed position allocation to the actual terminal positions. (1) Position of non-movable terminals In initial rough position allocation, nodes of the route search graph corresponding to the wiring results are allocated, and then absolute positions are determined in detailed position allocation. Each node has several candidates for its corresponding absolute position, and the optimal position is selected from among them. In FIG. 3(b), undesigned block A
Terminal a is placed at the lowest vacant terminal position among the candidate positions. If all candidates for absolute positions of nodes in the wiring result are assigned to terminals of other nets, the node corresponding to the terminal is made the next candidate and the same process is repeated. (2) For the position allocation of movable terminals, select the node with the least number of already allocated terminals within the set of nodes in the route search graph that can be allocated in the rough position allocation, and for detailed position allocation, select the node with the least number of already allocated terminals. Perform similar processing. The method of the invention described above was applied to two types of data. Information regarding the applied data is shown in Table 1, and experimental results are shown in Table 2. The wiring length in the experimental results is the approximate length of the wiring path, and the chip size is an estimate after estimating the wiring area. For comparison, there is a case (A) where all the functional blocks are existing needle blocks and the terminal positions cannot be moved, and a case where all the functional blocks are undesigned blocks and the terminal position is determined by a straight line connecting the centers of the functional blocks. The results are shown in the case (B) in which the terminal positions are determined by the method of the present invention with all functional blocks being undesigned blocks (B) and in the case (C) in which the terminal positions are determined by the method of the present invention. Furthermore, regarding terminal position determination using the method of the present invention, there are cases in which the terminal position is determined immediately after initial wiring (C-1) and cases in which the terminal position is determined after several improvements (C-2). ) are also shown. From the experimental results, it can be said that terminal position determination using the method of the present invention is highly likely to generate a layout with a small chip size and short wiring length. Table 1. Experimental data 4゜

【Effect of the invention】

As described above, the terminal position determination according to the present invention can reduce both the chip size and the wiring length, and since the terminal position determination is performed in consideration of the rough wiring results, the terminal position can be determined more suitable for the actual layout. can be determined.

[Brief explanation of the drawing]

Figure 1 is a diagram for explaining the layout model, Figure 2 (a) is a diagram showing a floor plan graph, Figure 2 (b) is a diagram showing a route search graph, and Figure 2 (c) is a diagram showing the channel position. The graphs shown in FIGS. 3(a) and 3(b) are diagrams for explaining the terminal position determination processing steps, respectively. 11-14... Existing needle blocks 21, 22.
...Existing needle blocks 31 to 34...Existing needle block sl...Node LII of floor plan graph...・・・・・・
・・Branch S2 of the floor plan graph・・・・・・・・・・
...Node L2 of route search graph...
・・・・・・Branch S3 of route search graph・・・・・・・
・・・・・・Node L3 of channel position graph
・・・・・・・・・・・・・・・Channel Position Graph Branch Representative Patent Attorney Takeshi Sugiyama (1 other person)

Claims (1)

[Scope of Claims] 1. An initial wiring processing step for performing a route search using an evaluation function of only the wiring length to obtain a wiring result that does not depend on the order of signals to be roughly routed, and using the results of the initial wiring processing, A wiring improvement process for rerouting the wiring passing through the wiring area that controls the chip size; a rough wiring process for determining the wiring paths of all signals; and a result of the rough wiring described above. A terminal of a block in a large-scale LSI, characterized by having a terminal positioning step consisting of a two-step processing step of determining the approximate position of the terminal in order of the longest wiring length and then determining the detailed position. Positioning method.