JP2932792B2 - Circuit splitting device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

The present invention is used for designing an electronic circuit of a large-scale LSI. In particular, it relates to a circuit division technique for parallel circuit simulation.

[0002]

2. Description of the Related Art As a circuit dividing technique for a parallel circuit simulation of a large-scale LSI, a circuit having a hierarchy is maintained in the original hierarchical structure and a nest disassembly method is performed from a subgroup referred to by a top parent circuit. Apply the process of dividing into two using the simulation with the largest simulation prediction time from the partial circuits until the number of generated partial circuits reaches the number of processors in the parallel simulation or until the parallel simulation processing time is saturated This is repeated (see JP-A-2-87279).

As a technique for equally dividing a circuit having no hierarchical structure into two, surrounding elements are fetched one after another from one node, and the size of the fetched element and that of the other elements are distorted. Incidentally, there is a nest disassembly method for performing division (refer to Japanese Patent Application Laid-Open No. 1-250173).

[0004]

In this method, in the case of a circuit having a hierarchical structure, the circuit is divided while maintaining the hierarchical structure. The size of the partial circuit group that determines the time depends on the size of the partial circuit of the original circuit, and may be uneven.

[0005] In addition, nodes extending between a plurality of partial circuits also remain unchanged as the nodes extending between the partial circuits of the original circuit are not reduced, so that the communication time between the processors in the parallel simulation may increase. .

As described above, equalization of partial circuits necessary for effectively performing parallel circuit simulation and minimization of the number of nodes over a plurality of partial circuits greatly depend on the properties of the original circuit. I will.

In addition, according to the nest disassembly method, when a partial circuit is divided into two, while surrounding elements are being taken in, they are surrounded by nodes spanning other partial circuits. May not be divided. This is the most basic technique for the circuit division technique that repeats the process of dividing the largest partial circuit into two until the number of processors and the number of partial circuits become equal. Cause.

The present invention has been made in view of such a background, and an object of the present invention is to provide an apparatus for effectively performing a parallel circuit simulation of a large-scale LSI in a short time.

[0009]

The present invention provides a large scale LSI.
A circuit diagram input terminal for inputting a circuit diagram of the circuit diagram, a circuit connection data creation unit for creating circuit connection data based on the circuit diagram input from the circuit diagram input terminal, and a circuit for dividing a circuit by data from the circuit connection data In the circuit dividing device including the division control unit, one parent circuit having a power supply element regardless of the original circuit configuration in the circuit division control unit, the hierarchy level is reduced to one layer so as to refer to one partial circuit. An initial clustering means for dividing a partial circuit obtained by the aligning means into a cluster, which is a group of elements having substantially the same size, and creating a target number of clusters; and an initial clustering means. Form a set of clusters that combine a certain number of clusters formed by the above from those with a high degree of connection, and use that as the first level, and then connect the set The next level in which a certain number of the clusters are combined from the highest one is formed, and this processing is repeated until a level at which a set of two clusters can be formed. Means for searching for a combination and performing a cluster exchange process if there is an effective combination.

[0010]

In order to perform a parallel circuit simulation of a large-scale LSI, a circuit diagram is examined, divided into partial circuits having a similar configuration, and each of them is input to a parallel circuit simulation control unit. For this classification, the circuit division control unit first arranges the hierarchy levels in one hierarchy so that one parent circuit having a power supply element refers to one partial circuit regardless of the original circuit configuration.

[0011] Initial clustering refers to dividing the partial circuit obtained by the means for arranging one layer into clusters, which are collections of elements having substantially the same size, and creating the clusters according to the target number.

A set of clusters is formed by grouping a certain number of clusters formed by the initial clustering from those having a high degree of connection, and this is set as the first level, and a certain number of clusters are grouped from those having a high degree of connection. Forming the next level and repeating this process up to the level at which a set of two clusters is formed is called hierarchical clustering.

For the set of clusters formed by the hierarchical clustering means, a more effective combination is searched, and if there is an effective combination, cluster exchange processing is performed, and finally the division is performed up to the number of simulation processors in the parallel circuit simulation controller. Do.

This partial circuit is simulated in parallel, and the result is output.

[0015]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS The configuration of an embodiment of the present invention will be described with reference to FIG. FIG. 1 is a block diagram showing the configuration of the apparatus according to the embodiment of the present invention.

According to the present invention, there is provided a circuit diagram input terminal 1 for inputting a circuit diagram of a large-scale LSI, a circuit connection data creation unit 2 for creating circuit connection data based on the circuit diagram input from the circuit diagram input terminal 1, In a circuit dividing device including a circuit dividing control unit 3 for dividing a circuit according to data from circuit connection data, one parent circuit having a power element in the circuit dividing control unit 3 is connected to one parent circuit regardless of the original circuit configuration. Means for aligning the hierarchical level to one level so as to refer to the partial circuit, and dividing the partial circuit obtained by the means for aligning to one level into clusters, which are collections of elements having approximately the same size,
An initial clustering means for creating the target number of clusters, and a set of clusters obtained by grouping a certain number of clusters formed by the initial clustering means from those having a high degree of connection, as a first level, and further setting the set A hierarchical clustering unit that forms the next level in which a certain number of connected clusters are collected and repeats this processing until a level at which a set of two clusters can be formed, and a set of clusters formed by the hierarchical clustering unit. Means for searching for a valid combination and performing a cluster exchange process if there is a valid combination.

Next, the operation of the apparatus according to the embodiment of the present invention will be described with reference to FIGS. FIG. 2 is a flowchart for explaining the operation of the circuit division control unit 3 of the apparatus according to the embodiment of the present invention.

First, the circuit diagram data input from the circuit diagram input device 9 is detected by the circuit connection data generator 2 to determine the load of each partial circuit and a node (hereinafter referred to as a node), and the circuit division controller 3 To enter.

The operation of the circuit division control unit 3 will be described with reference to FIG.

First, as a pre-processing 19, a flat circuit having no hierarchical structure raises a power supply element to a parent circuit, and forms a partial circuit with other elements. While holding the partial circuit, the hierarchy is raised so as to be referred to by one parent circuit, and the one-layering 12 is performed to align the hierarchy. Here, a circuit portion other than the created parent circuit is named a leaf circuit. In the initial clustering 13 of the preprocessing 19, clusters having the same load are formed. In the update processing 14, a leaf circuit having the largest load is selected and set as a division target. The selected leaf circuit forms two sets of clusters having an equal load while forming a set of the same level of clusters by the hierarchical clustering 15 of the division processing 20. The cluster exchange processing 16 is performed so as to reduce the nodes common to the two sets of divided clusters while breaking the level created at this time, and the two divisions are performed by the set of clusters at the end of the first level cluster exchange. Do. The two circuits created by the dividing process 20 are newly set as leaf circuits. In the end determination processing 17, if the number of leaf circuits is equal to the number of simulation processors, each leaf circuit is set as a partial circuit, and the result output 18 is performed in a form referred to by the parent circuit. Otherwise, the process returns to the updating process 14.

The operation of each part of the apparatus according to the embodiment of the present invention will be described with reference to FIG. FIG. 3 is a view in which the configuration of the apparatus of the embodiment of the present invention shown in FIG. 1 is developed vertically.

First, a circuit diagram input 21 is input from the circuit diagram input device 9 via the circuit diagram input terminal 1, and circuit connection data 22 is created by the circuit connection data creation unit 2. Next, the circuit division 23 is performed in the circuit division control circuit 3 by the processing shown in FIG.
Generate In the parallel compiling section 5, parallel compiling 25 is performed, object data is generated, the object data is applied to the parallel circuit simulation control section 6, parallel circuit simulation 26 is performed, and the result file 27 is output to the result output terminal 8.
Is displayed on the result display device 10 through the process.

The operation will be described more specifically with reference to FIGS. FIG. 4 is a diagram showing a state of a circuit before circuit division. FIG. 5 is a diagram showing how the circuit of FIG. 4 is divided.

The parent circuit 30 is configured to store one of the partial circuits 31 to 34 or the like.
Reference is made to 92 nodes, and there are 346 nodes excluding the nodes shared by the respective partial circuits, that is, the nodes connected to the power supply in the parent circuit 30.

First, the initial number of clusters in the initial clustering is set to 6974 ÷ 256 = about 27. In addition, assuming that the number of transistors in the initial cluster is within ± 40% of the target of 27, the initial clustering was performed. As a result, 249 initial clusters were generated. The minimum number of transistors in the cluster was 18 and the maximum was 38.

As shown in FIG. 5, a leaf circuit 39 composed of 249 clusters is replaced with a leaf circuit 40 composed of 125 clusters.
Are divided into two into 124 leaf circuits 41. Among the leaf circuits 40 and 41, the leaf circuit 40 having a large load is divided first, and is divided into a leaf circuit 42 having 64 clusters and a leaf circuit 43 having 61 clusters. The leaf circuit 41 having the largest load among the leaf circuits 41, 42, 43
Is divided into a leaf circuit 44 having 63 clusters and a leaf circuit 45 having 61 clusters. Since the number of processors was set to four, the division was completed.

As a result, the maximum number of transistors of the generated four partial circuits is 1890, and the number of internal nodes of the parent circuit is 125.

[0028]

According to the present invention, since the division processing is executed irrespective of the original circuit, even if the original partial circuits are uneven in size, the division results will not be uneven in size. Also, since the original circuit configuration is not retained, if the original circuit has many partial circuits and the parent circuit has many nodes, the nodes of the parent circuit are reduced.

Since the hierarchical clustering method and the cluster exchange for each level were performed without using the nest disassembly method for the dividing process,
An extreme size imbalance does not occur in the two divisions, and the division can be performed with few common nodes between the partial circuits that are the nodes of the parent circuit.

In the parallel circuit simulation, the simulation execution time is reduced because the sizes of the partial circuits are averaged and reduced, and the simulation execution time of the parent circuit is also reduced by reducing the number of nodes of the parent circuit. . As a result, the execution time of the entire parallel circuit simulation is reduced.

[Brief description of the drawings]

FIG. 1 is a block diagram of an apparatus according to an embodiment of the present invention.

FIG. 2 is a flowchart showing an operation of a division control unit of the embodiment device of the present invention.

FIG. 3 is a diagram showing the operation of each unit of the apparatus according to the embodiment of the present invention.

FIG. 4 is a diagram showing a circuit before division.

FIG. 5 is a diagram showing a divided state of a circuit.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 Circuit diagram input terminal 2 Circuit connection data creation part 3 Circuit division control part 4 Circuit division file part 5 Parallel compile part 6 Parallel circuit simulation control part 7 Result file part 8 Result output terminal 9 Circuit diagram input device 10 Result display device 11 Circuit Connection data input 12 One layering 13 Initial clustering 14 Update processing 15 Layer clustering 16 Cluster exchange processing 17 End judgment processing 18 Result output 19 Preprocessing 20 Division processing 21 Circuit diagram input 22 Circuit connection data 23 Circuit division 24 Circuit division file 25 Parallel Compilation 26 Parallel circuit simulation 27 Result file 28 Display 30 Parent circuit 31-34 partial circuit 39-45 leaf circuit

──────────────────────────────────────────────────続 き Continuation of the front page (56) References JP-A-63-25778 (JP, A) JP-A-3-186971 (JP, A) JP-A-2-87279 (JP, A) Masato Edahiro, Outside 1 Name, "Placement Method for Cell-Line LSI Using Hierarchical Clustering Method", IEICE Technical Report (VLD90-62), IEICE, October 1990, Vol. 90, No. 261, p. 9-16 (58) Fields surveyed (Int. Cl. ⁶ , DB name) G06F 17/50 JICST file (JOIS)

Claims (1)

(57) [Claims] 1. A circuit diagram input terminal for inputting a circuit diagram of a large-scale LSI, a circuit connection data creation unit for creating circuit connection data based on a circuit diagram input from the circuit diagram input terminal, of the circuit dividing device and a circuit dividing unit for dividing circuit by the data, the circuit division control unit to perform the pre-processing an hierarchical hierarchical level irrespective original circuit component circuit one hierarchy To
Means that aligning the partial circuit obtained by means of aligning this one level divided into clusters is a collection of elements having the same order of magnitude, the initial clustering means for creating the target number of this cluster, the initial clustering A cluster set is formed by grouping a certain number of clusters formed by the means from those with a high degree of connection, and the next level is formed by grouping the groups from a group having a high degree of connection with a high degree of connection. Hierarchical clustering means that repeats to a level at which a set of clusters can be formed, and means for searching for a more effective combination of the set of clusters formed by the hierarchical clustering means and performing a cluster exchange process if there is an effective combination. Circuit dividing device.