JPH06290230A - Logical simulation device - Google Patents

Abstract

(57) [Summary] [Object] The present invention provides a logic simulation apparatus capable of simulating a logic circuit including a loop in a logic simulation using a level sorting method. [Structure] A loop circuit of a plurality of primitives A, B, and P is extracted from a combinational circuit section separated from a logic circuit to be simulated, and the output of the primitive P in this circuit is removed to generate a first circuit. At the same time, a primitive PO that stores the previous output signal value of the primitive P is prepared, and the primitives A ′ and B that duplicate the first circuit are prepared.
The second circuit of 'and P'is used to form a cascade connection circuit of the second and first circuits and the primitive PO, and further, for each primitive of the second circuit, as an input to each primitive of the first circuit. Connect the same inputs.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a simulation system for verifying a logic circuit using programmable elements.

[0002]

2. Description of the Related Art With the improvement in the degree of integration of LSIs, there has been a remarkable increase in the scale and complexity of computers in recent years. Therefore, when developing such a large-scale computer, it is becoming more and more important to keep the development period and cost low. For this reason, it is important to verify the system function and system performance by simulation. It is increasing.

Therefore, when designing a system using a logic circuit, it is necessary to model the logic circuit and verify the design by performing a logic simulation to shorten the development period of the system, and also the degree of completion of the design. It is used as a necessary process to increase the

In the case of logic simulation of a logic circuit by software, the simulation time inevitably increases because the description amount of the model increases as the circuit scale increases.

Therefore, various efforts have been made to speed up the simulation, one of which is the level sorting method.

In this level sorting method, the evaluation order of gates is determined in advance, and the evaluation is performed according to this static order when the simulation is executed. The evaluation order in the level sorting method is determined under the rule that "the evaluation of the gate g is performed after the evaluation of the gate on the input side of g is completed". The purpose is to calculate the final value when the circuit is stable.

On the other hand, Japanese Patent Laid-Open No. 4-243755 proposes a time-division emulator. However, in such a time-division emulator, the logical operation assigned to each time slice needs to be level-sorted. is there.

However, according to such a level sorting method, the combinational circuit section is usually designed so as not to include a loop, and the model of the combinational circuit section does not include a loop. In most cases, there is no problem in simulating with the level sorting method that decides, but in practice, a logic circuit that includes a loop in the combinational circuit part may be designed. Since the evaluation order along the line cannot be determined, it cannot be handled by the level sorting method.

On the other hand, one of the systems for simulating a logic circuit is a hardware emulator. The hardware emulator is composed of a plurality of interconnected logic blocks, and each logic block performs the same operation as the operation of the circuit to be verified, thereby performing a logic simulation of the circuit at high speed. As a logical block, for example, F
PGA (Field Programmable Ga)
There are programmable gate arrays called te Arrays. FPGAs consist of a number of programmable elements, each programmable element simulating the operation of one or more circuit elements.

The compiler determines the allocation (mapping) of the circuit to be simulated to the programmable elements and the connection between the programmable elements. The program information obtained as a result of the mapping by the compiler is usually loaded into the memory in the emulator before the simulation and used by the emulator during the simulation to determine the behavior of the programmable device.

One of the drawbacks of hardware emulators is the huge compilation time. This is for the following reason. The conventional emulator architecture uses a FP as represented by a mesh structure that connects only adjacent persons.
The flexibility of wiring between GAs is small. Moreover, since most FPGAs are for embedded use, the degree of freedom in wiring is also low. Therefore, in order to increase the circuit filling rate of the FPGA, it is important to realize the mapping of the target circuit with the wiring means having a small degree of freedom.

As a solution to such a problem, no efficient one is known other than the stochastic algorithm. Usually, a stochastic method such as a simulated annealing method is used in which optimization is repeated until a desired mapping is achieved. However, in such a method, as the circuit scale becomes large, it takes a huge amount of time for mapping, and when the circuit is as large as 1M gate, it may take several days to complete the compilation.
Since the increase of compile time leads to the increase of turnaround of system verification, the speedup of mapping algorithm is extremely important.

As described above, it is not easy to implement an efficient mapping method with an emulator having a low degree of wiring freedom. Therefore, the above-mentioned JP-A-4-243755.
The publication discloses an emulator architecture represented by a perfect crossbar, which has a large degree of freedom in wiring.
In this architecture, the programmable elements have a structure in which they are connected in multiple stages, and the programmable elements can be used for time division. Also, back-tracking is almost unnecessary by preliminarily level-sorting the circuit to be simulated and mapping the circuit elements in order from the smallest to the largest level counted from the input to the programmable elements in the emulator. It has been shown that fast mapping is possible.

However, in such a simple algorithm, since the mapping is simple, the "circuit filling factor of the programmable element" (the average number of circuit elements allocated per programmable element) becomes insufficient. Tends to.

In an emulator having the same number of programmable elements, the circuit size that can be simulated is proportional to the circuit filling rate. Therefore, a low circuit filling rate means that the circuit size that can be simulated is small.
Therefore, it is important to improve the circuit filling rate by devising the mapping method in the emulator of multi-stage connection architecture.

[0016]

As described above, according to the level sorting method applied for speeding up the conventional simulation, when a logic circuit including a loop in a combinational circuit is designed, However, there is a problem that such circuits cannot be handled because the evaluation order cannot be determined by the rule based on the level sorting method.

Further, in the conventional logic circuit simulation system composed of programmable elements connected in multiple stages, the circuit filling rate of the programmable elements in the allocation of the logic circuit is not sufficient, and it is difficult to simulate a large-scale circuit. There was a problem called.

The present invention has been made in view of the above circumstances, and it is possible to simulate a logic circuit including a loop in a logic simulation using the level sorting method, and whether the loop in the logic circuit oscillates during the simulation. It is an object of the present invention to provide a logic simulation device capable of detecting whether or not there is no.

Further, according to the present invention, in a logic circuit simulation system composed of programmable elements connected in multiple stages, the circuit filling rate of the programmable elements in the allocation of the logic circuit is improved to simulate a larger scale circuit. The purpose is to provide an enabled logic emulator.

[0020]

According to the present invention, in a logic simulation apparatus for simulating a logic circuit by using a level sort method, a means for storing a logic circuit to be simulated, a combinational circuit section for combining the logic circuits, and Means for separating into a state storage section, means for extracting a circuit A consisting of a loop composed of a plurality of logic elements from the combinational circuit section separated by this means, and one logic of the logic elements in the circuit A A circuit X is obtained by using means for creating a circuit X from which the output of the element Z is removed, means for creating a memory element U for storing the previous output signal value of the logic element Z, and a circuit Y replicating the circuit X. Y, a circuit X, and a circuit conversion means having means for forming a cascade connection circuit of the memory elements U. X is to be connected to the same input as the input for the logic elements.

Further, the present invention is, in a logic emulator in which a plurality of reprogrammable logic blocks are connected in multiple stages, a primitive graph level-sorted in the order of signal flow from the input side is counted from the input side at a constant level. A plurality of connected components are generated by partitioning into, and each connected component is assigned to a logical block.

[0022]

As a result, according to the present invention, a logic circuit model including a loop in a combinational circuit section is converted into an equivalent circuit model by connecting two disconnected loops in cascade to perform simulation by the level sorting method. It is also possible to verify the oscillation of the loop of the circuit before conversion. That is, the signal value handled in the logic circuit model is 2
Since it takes only a value (for example, “0” or “1”), the loop is evaluated for two rounds to evaluate the loop of the logic circuit model, that is, the detection of the loop oscillation and the loop depending on the case where the loop does not oscillate. An evaluation of the logic elements inside can be performed.

In addition, in a logic emulator composed of a plurality of reprogrammable logic blocks, when allocating a logic circuit to each logic block, a connected component of the circuit obtained by dividing from the input side by a certain level is obtained. By assigning as a unit, it becomes possible to assign the circuit part whose connection is internally closed to the same logic block, and as a result, the circuit filling factor of the programmable element is improved and the scale is increased. It is possible to simulate the circuit.

[0024]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of the present invention will be described below with reference to the drawings.

FIG. 1 shows a schematic configuration of the embodiment.
In this case, the simulation unit 11, the circuit model storage unit 12 that stores the circuit model, the separation unit 13 that separates the combinational circuit unit and the state storage unit, the loop circuit detection unit 14 that detects a loop circuit, and the loop circuit It is composed of a conversion unit 15 for converting into an equivalent circuit.

The apparatus thus constructed is shown in FIG.
The process proceeds according to the procedure of steps 2001 to 2006 shown in FIG.

In this case, the logic circuit input to the logic simulator is represented by a netlist. Then, this is modeled as an internal representation of the system.

The simulation section 11 has such modeling means. In this embodiment, this modeling is performed by converting the connection information between the logic elements in the netlist into a primitive graph having the wiring between them as the nodes of the primitives. Here, the primitive is one unit of simulation and corresponds to a group of one or a plurality of logic elements.
Here, it is assumed that the signal value takes only two values of "0" or "1". Although the external input signal terminal and the external output signal terminal are not logic elements, they are represented by special primitives for convenience. Hereinafter, these primitives will be referred to as input primitives and output primitives. Also, each primitive is given a different id.

The circuit model storage unit 12 stores information about the primitive graph. In this case, the primitive graph is stored in the form of an array. In this case, the array element representing the primitive is, as shown in FIG. 3, the id of the primitive, the function (AND,
OR, NOT, flip-flop, etc.), a list of ids of primitives of the output destination from the primitive, a list of ids of primitives of the input source to the primitive, other level information from the input, information necessary for loop detection, etc. Consists of a field that stores.

Then, an input primitive and an output primitive are newly created for each flip-flop in the circuit model stored in the circuit model storage unit 12 by the separation unit 13 for separating the combinational circuit and the state storage unit, and the circuit model is created. To a strongly connected component, the input branch to the flip-flop is connected to the output primitive, and the input branch from the flip-flop is connected to the input primitive.

Here, as shown in FIGS. 4 (a) and 4 (b), the strongly connected component A is a set of nodes which can come and go (reach) to each other via a directional branch in a directed graph, and its set. It is defined by a pair of directed branches that connect the nodes that are the elements of the set. However, since it is reachable by itself, there is also a strongly connected component consisting of one node, and if multiple nodes are included in the strongly connected component, it means the existence of a loop.

Here, a method of decomposing the primitive graph into strongly connected components will be briefly described.

First, the primitive PO in the graph is selected and the search is started from there along the directed edge. If PO
If there is something like returning to, the search path is a loop. Strongly connected components can be obtained by putting together such loops. If there is no path to return to PO, PO itself becomes a strongly connected component. Primitive PO to start searching
Selects from primitives that are not included in any strongly connected components obtained so far. Then, if the above operation is performed until there are no more selectable primitives, a primitive graph decomposed into strongly connected components is finally obtained.

Such a method is an example of decomposing a graph into strongly connected components, and a more efficient procedure and its details are described in, for example, “Algorithm Design and Analysis I, II (Science Co., 1977) p. 170. ~ P. 177 ".

If there are no loops in the primitive graph, each strongly connected component contains only one primitive. If the primitive graph contains a loop, the loop is equivalent to the existence of a strongly connected component consisting of two or more primitives.

Therefore, if only one primitive is included in each strongly connected component, the primitive graph does not include a loop, and the primitive graphs do not need to be exchanged as they are.

The problem is that a strongly connected component contains multiple primitives. In this case, since the graph includes a loop, the conversion unit 5 that converts a circuit including the loop into an equivalent circuit is used.

Here, the conversion operation in the conversion unit 15 is as follows.

First, as a simple example, consider a single loop consisting of primitives A, B, and P as shown in FIG.
At this time, the loop L in the circuit model storage unit 2 is as shown in FIG.
It is expressed as shown in.

From this state, (1) one primitive in the loop L is selected as shown in FIG. The method of selection is arbitrary, but here P is selected. In this case, although it is A that receives the output from P in the loop, the branch from the primitive P to A is removed from the branches forming the loop L.

Next, an input primitive PI that gives an output from the PF is added to the state storage unit with a primitive PF that outputs the value at the previous clock of the primitive P.
Then, an output primitive PO that gives an input to the PF is newly added to the primitive graph. FIG. 8 shows the primitive graph shown in FIG. 7 stored in the circuit model storage unit 12 that stores the circuit model, in the data structure shown in FIG. The id of A is removed from the list of the output destination primitives of the array element representing the primitive P, and the id of P is removed from the list of the input source primitives of the array element representing A to A. Further, array elements representing PI and PO are added to the array.

(2) Next, as shown in FIG. 9, a subgraph that does not include a loop obtained from L by (1) is L
1 and a subgraph L1 ′ having the same structure as the subgraph L1
make. A'and P'are similarly defined.

FIG. 10 shows the primitive graph shown in FIG. 9 in the data structure shown in FIG. A new copy of the array element representing the primitive in L1 is added. The id is added to the input / output list of the array element created so as to save the connection relation in L1.

(3) As an input branch to L1 ', an input branch corresponding to the input branch to L1 is attached. (In FIG. 11, 11
2101 to 2104 corresponding to 01 to 1104 are attached. ) Also, add a branch from P'to A of L1 ', a branch from PI to A', and a branch from P to PO to the primitive graph.

FIG. 10 shows the primitive graph shown in FIG. 9 in the data structure shown in FIG. S in the input list of the array element A'B'P '(id, that is, the array element indicating the primitive in L1') created in (2),
T and U ids are added. Although not shown in the figure, the output lists of S, T, and U have A ′, B ′, P.
'Id is added. Next, P in the input list of A '
Id of A'is added to the output list of PI (that is, the input branch from PI to A'is added), the id of P'is added to the input list of A, and the output list of P'is A. Id of each is added (ie,
The input branch from P'to A is added). In addition, the PO output list has a PO id, and the PO input list has a P id.
Is added. That is, a branch from P to PO is added.

The fact that the primitive graph thus obtained is logically equivalent to the original primitive graph and that the oscillation of the loop can be detected will be described with reference to FIGS. 5 and 11. . The oscillation referred to here means that the signal value is inverted an odd number of times in the loop, and the signal value cannot be determined.

In FIG. 11, the part E where the loop is expanded
L has inputs from PI and four primitives S, T, and U. After the primitives S, T and U have been evaluated, the primitives in EL are evaluated. Figure 1
The values of P ′ and P in 1 correspond to the values of P on the first and second rounds of the loop in FIG. 5, respectively.

Now, it is assumed that the signal value of the primitive in EL at a certain clock is evaluated. Then, when the signal value of P'is equal to the signal value of PI as a result of the evaluation, the signal value of P does not change when the same input is given to the pre-conversion primitive graph.

Next, when the signal value of P'is different from the signal value of PI but the signal values of P'and P are the same, if the same input is given to the loop before conversion, the signal value of P changes only once. And confirm. This can be easily understood by evaluating the loop several times in order in FIG.

In the first round, the value of P changes depending on its own value held as an internal state and the inputs from S, T, and U. The value of P on the second lap depends on the signal value of P and the signal values of S, T, and U obtained on the first lap, but if the value of P on the second lap is equal to the value of P on the first lap, In this case (if the signal values of P'and P in FIG. 11 are equal), the value of P does not change in the loop evaluation after the second round. This is because after the second round, the input for evaluating P, that is, the signal value of P and S, T, and U in the previous round do not change. Therefore, the loop does not oscillate.

The signal value of P'is different from the signal value of PF, and P'is different.
It can be seen from the same explanation that when the signal values of P and P are different, the value of P cannot be determined by giving the same input to the loop before conversion. That is, since each signal takes only two values, P and PF
Note that the value of P is the same as the value of P on the third cycle, and the signal value of P on the odd cycles is different from that on the even cycles, so the loop oscillates. To do.

From the above, it can be seen that the oscillation of the loop is seen by checking whether P and P'are equal, and if not oscillating, the simulation result of the circuit after conversion is logically correct.

Model conversion for detecting oscillation is performed as follows. That is, as shown in FIG. 13, a model is made of a primitive Xo (for example, a primitive that takes an XOR of two inputs) Xo that receives and compares the output signals of the two primitives P and P ', and an output primitive that receives the output from Xo. Add to. FIG. 14 shows the data of the circuit model storage unit 12 changed in this step. To detect oscillation, the output value may be monitored by, for example, a host computer. The above is the circuit model conversion method when the loop is simple.

When this is applied to a concrete circuit, FIG.
As shown in (a) and (b). In this case, the same figure (a)
When the values of S, T, and U are 1, the circuit N shown in FIG. 1 oscillates because the logic is inverted when it makes one round along the loop. However, if any one of the S, T, and U values is 0, the signal value is inverted at an even number of times, so that oscillation does not occur.

The circuit N shown in FIG.
When the respective logic elements of the circuit N ′ are evaluated when they are equivalently converted into ′, the following is obtained.

PI is a primitive for inputting the signal value of P in the previous clock, and is indeterminate X at clock 0.

Xo is a primitive that takes the XOR of the outputs of P and P '. When the outputs of P and P'are equal, the output of Xo is 0, but when the outputs of P and P'are different, Xo is
Has an output of 1. A ', B', P ', A, B, P, X are evaluated for the signal value at each clock according to the level sorting method.
The results obtained in the order of o are as follows.

First, if the inputs of PI, S, T, and U at clock 0 are X, 1, 1, and 0, the output signal values of the respective elements are X, 0, 1, 1, 0, 1 respectively. , 0,
Inputs S, T, and U at clock 1 are 1, 1, and 1, respectively.
Then, since the value of PI is 1, the output signal values of the respective elements are 1, 1, 0, 0, 0, 1, 1. As a result, when the oscillation does not occur, a correct simulation result is obtained, and when the oscillation occurs, the oscillation can be detected by the output of Xo.

In general, a strongly connected component composed of a plurality of primitives may be composed of a plurality of loops (see FIG. 1).
6) Also, the number of strongly connected components composed of a plurality of primitives is not limited to one in the entire circuit. In this case, the following processing, which is an extension of the above method, may be repeatedly used.

(1) One strongly connected component including two or more primitives is selected as SPG. Also, one primitive in the SPG is selected and designated as P (FIG. 17).

(2) A flip-flop PF corresponding to the primitive P is newly added to the state storage unit, and an input primitive PI that gives an output of the PF and an output primitive PO that gives an input to the PF are newly stored in the circuit model. Add to the primitive graph in the circuit model storage unit 12. Next, the branch output from P to the subgraph SPG is removed to create the subgraph SPG1. By this operation, the loop containing P does not exist in SPG1 (FIG. 18).

(3) Obtain the strongly connected component of SPG1, and if there is a strongly connected component including two or more primitives, this processing is recursively performed on such strongly connected component and it is not included in the loop. A partial graph SPG2 is created (FIG. 19).

(4) Since the loop is not already included in SPG2 at this point, a subgraph SPG2 'having the same structure as the subgraph SPG2 is created, and a corresponding input branch from G to SPG2' is attached. At this time, the output of the flip-flop PF (that is, the input from PI) is assigned to the input to the primitive that has received the output from P. Also,
The output from P included in the duplicated subgraph SPG2 'is used as the input to the primitive that has received the output from P in the primitive included in SPG2 (FIG. 20). Furthermore, the output from P is connected to PO as the output to PF.

In step 2, since the number of primitives included in the strongly connected component is reduced by at least one, even if there is a loop (that is, a strongly connected component including a plurality of primitives) in the remaining graph, that loop The number of primitives inside is one or more less than the original strongly connected components. Therefore, in the graph finally obtained by repeating this procedure, one primitive is included in all strongly connected components. That is, it can be converted into a circuit that does not include a loop.

In order to detect the oscillation, for example, to the pair of P and P'in the above procedure, a primitive for inputting and comparing the signal values of P and P'is added and output to the outside of the circuit (that is, output). Performed by monitoring with a host computer etc.) (as input of primitive).

The conversion unit 15 for converting a circuit composed of a loop into an equivalent circuit stores the primitive graph in which the equivalent conversion is performed by the above method to eliminate the loop and the oscillation can be detected in the storage device. Simulation part 1
Will be handed over to.

The oscillation detection method described above is not limited to the level sorting method. The fact that oscillation can be detected by evaluating the loop only twice can be applied to simulation algorithms other than the level sorting method.

For example, in a software simulator or the like, the following simulation method can be considered without making a copy of the model. That is, as shown in FIG. 21, with respect to the primitive graph, first, L ′ at a certain clock is evaluated and the signal value of P is stored in the storage device PM. Next, if the value of PM is equal to the value of PF, the circuit does not oscillate and the evaluation result of P is correct. If the value of PM is different from the value of PF, the value of PM is used instead of PF and L '
, That is, P is evaluated. And the value of P and P
If the value of M is the same, the circuit does not oscillate, and if the value of P and the value of PM are different, the circuit oscillates.

Further, in the above description, only the case where the signal value is binary is described, but it is possible to extend to the case where it is multi-valued.

Therefore, in this way, a logic circuit including a loop in the combinational circuit portion, which could not be simulated in principle by the conventional level sorting method, is simulated by the level sorting method by converting it into an equivalent circuit model. Will be able to. It also becomes possible to verify the oscillation of the circuit loop before conversion.

Next, as another embodiment of the present invention, an example of a hardware emulator will be described with reference to FIGS.

FIG. 22 is a block diagram of the hardware emulator. In this case, the emulator 221 is realized by the FPGA 222 having a dedicated logic block. And FP
The GA 222 is connected in multiple stages via the complete crossbar switch 223, and the signal flows in one direction from the input side to the output side. Note that the coupling between the FPGAs 222 may be composed of partial crossbar switches.

FIG. 23 is a block diagram of the FPGA 222.
The programmable element here consists of a 4-input 1-output universal element 222a. Generally, it may be a universal device of M input N output type (M and N are positive integers). And the universal element 222a is a complete crossbar switch 222b.
Are connected in multiple stages via, and the signal flows in one direction from the input side to the output side. The coupling between the universal elements 222a may be a partial crossbar.

The universal element 222a in the FPGA is in charge of simulating a plurality of circuit elements, which are grouped in units of 4 inputs and 1 output (when there are circuit elements having more than 4 inputs, those are input 4 inputs 1 Disassemble until the output constraints are met and treat them as multiple circuit elements). Hereinafter, the circuit element set put together in units of 4 inputs and 1 output will be referred to as a primitive.

FIGS. 24 to 26 show examples of conversion of circuit primitives. FIG. 24 shows an example of a circuit to be simulated. Here, a 9-bit parity generator (SN74ALS280) manufactured by Texas Instruments is shown as a 9-input 2-output circuit. 25 is an example in which the circuits in FIG. 24 are grouped into primitives that satisfy the constraint of 4 inputs and 1 output, and FIG. 26 is a primitive graph obtained as a result of the grouping in FIG.

24 to 26, A to I are input signals, X and Y are output signals, and 1 to 37 are primitives. Then, each primitive 1 to 37
Are level-sorted in order of the length of the longest path counted from the input side to the output.

The level sort can be easily realized on a computer by the procedure shown in p80 and p320 of "Operational Graph Theory (Corona Corp.)", for example. Further, according to this procedure, the level sorting can be performed at high speed with the labor of calculation proportional to the number of branches of the graph.

Here, since the universal element is coupled only to the adjacent levels, the signal value transfer between the primitives separated by two levels or more is realized by storing the signal value in the universal element on the way. . Therefore, a dummy primitive for passing signals is inserted in the primitive graph shown in FIG. The primitive graph converted in this way is shown in FIG. In FIG. 27, 38-4
4 are output signals 10, 11, 12, 22, 23, 24,
28 is a dummy primitive that holds 28. These dummy primitives 38 to 44 are represented by shading in the drawing.

Next, an example of a data structure expressing a primitive graph for executing such a procedure will be described.

Here, the primitive graph is represented by an array, and each array element contains information on one primitive. Each array element is shown in FIG.
As shown in FIG. 8, (1) primitive id, (2) input primitive id list, (3) output destination primitive id list, (4) dummy bit, (5) original primitive id, (6) level, ( 7) Connected component id
It consists of

In this case, the above (1) to (3) are graph connection information, (4) to (5) are dummy primitive information, and (6) to (7) are information related to mapping.
In the above example, all of these pieces of information are collectively realized as one array, but they may be realized as separate arrays. The dummy bit is 1 when the primitive is a dummy and 0 otherwise. The original primitive id stores the original primitive id when the primitive is a dummy. It has no meaning if the primitive is not a dummy.

Hereinafter, the logic circuit will be expressed as a primitive graph including dummy primitives.

Next, the circuit shown in FIG.
FPG in which three primitives are lined up in the direction of the number of stages
Consider the case of mapping to a multistage emulator composed of A.

The mapping here is executed according to the processing from step 2901 to step 2908 shown in FIG.

In this case, first, the primitive graph is divided from the input side by three stages which is the number of FPGA stages. Reference numerals 101 to 104 shown in FIG. 30 represent the connected components thus obtained.

Depending on the graph, it may be desirable to divide the number of stages into the number of stages of the FPGA or less (for example, two stages in this case), which may be appropriately used. Also,
The operation of dividing by level is not limited to the first division of the entire circuit. It is also possible to dynamically calculate the level again from the wavefront of the circuit each time the mapping of one stage of the FPGA is completed, and re-divide the level-sorted circuit by the level.

As for the numbering (id) of the connected components, the higher the level, the higher the number.
The connected components corresponding to the same level, such as 1, 102, and 103, may be numbered in any order. Here, it is assumed that connected component numbers 1, 2, 3, and 4 are numbered in order of 101, 102, 103, and 104, respectively. FIG. 28 is a data structure expressing the primitive 15 in the connected component 101, where the level of the primitive 15 is 3 and the connected component number is 1.

Mapping is performed in order from the connected component with the smallest number. Taking the mapping of the circuit in FIG. 30 as an example,
The connected components 101, 102, and 103 fit within the size of the FPGA, and mapping is applied to each FPGA. Here, the fact that a circuit is larger than the size of the FPGA means that when the circuit is sorted in order of level, it exceeds the width of the FPGA.

In FIG. 31, 111 to 113 are 1 respectively.
FP to which the mapping of connected components from 01 to 103 is applied
The GA is shown. In this way, the first level FP
Mapping to the GA (111, 112, 113) can be efficiently performed by using the connected component information separated by level.

Next, consider the mapping of the connected component 104. 104 is larger than the size of the FPGA,
It doesn't fit in one. In this case, one of the following mapping methods is applied to 104.

(1) Mapping the connected primitives in order (2) Mapping in the order of primitive numbers (3) Mapping in the order of lower level primitives (4) Creating a duplicate of the primitive and dividing the connected component into a plurality of connected components Mapping for each obtained connected component In the mapping method of (1), an appropriate primitive is selected from the primitives in the component 104 as a starting point,
Start mapping to FPGA 114. The starting point primitive can be any of the minimum levels. In this example, the primitive 25 having the smallest number is selected. Next, one primitive 29, which is the output destination of the primitive 25, is selected, and the primitives 42 and 43 that are this input are mapped. Since the primitives to which the primitives 25, 42, and 43 are output include those that have not been mapped yet, it is necessary to connect these to the pins as dummy primitives. Therefore, because of the pin count constraint, the primitives cannot be mapped anymore and the FPG
The mapping to A114 ends. Same operation as FP
It applies to GA115 and 116. When the mapping to the FPGA 116 is completed, the mapping to the next FPGA is performed. In this case as well, a mapping result as shown in FIG. 31 is obtained by the same operation.

In the mapping method of (2), the component 1
Among the primitives that have not been mapped yet in 04, the one with the smallest number is selected. In this example, FP
The mapping to GA124 is from primitive 25 to 2
Map 8 and end. The primitive 29 is mapped to the next FPGA 125. For that 2
The primitives 25, 42 and 43 which are the inputs to 9 are mapped to the preceding stage. At this time, the primitives 30, 3
1, 32, and 33 cannot be mapped because they do not satisfy the constraints of universal elements and pins, but primitive 3
Since 4 satisfies the constraint, 34 is mapped and the process ends. By the same operation, the mapping result as shown in FIG. 32 is obtained.

By the way, in order to improve the filling rate of the circuit, it is desirable to map the primitives in ascending order of level. This is because the circuit elements that form the critical path in the signal flow from the input to the output are mapped at the earliest possible time as compared with simply following the connection of the primitives. The mapping method of (3) realizes this.

Steps 3301 to 33 in FIG. 33
The algorithm indicated by 06 is the mapping method of (3). This shows the mapping of the connected component i in FIG. 29 in more detail, and the primitives in the constituent component 104 are mapped in ascending order of level. FPGA
The primitives 25 to 28 are mapped to 134, and the process ends. The primitives 41 to 43 are mapped on the FPGA 135. Further, since there is a margin in the universal element, the primitive 29 is mapped and the process is completed. Here, since all the minimum-level primitives in 104 can be mapped, the primitives 30 which are not yet mapped among the primitives in the next stage are mapped to the FPGA 136. By the same operation, the primitive 33 is mapped and the process is completed. This result is shown in Figure 3.
4 shows.

Primitive 3 to FPGA 136
The mapping of 0 and 33 is essentially unnecessary when looking at the mapping result to the FPGA in the next stage. Therefore, 3
In the mapping method of F, the circuit of FIG.
It means that the mapping is completed with 7 PGAs, and it is understood that the packing rate of the FPGA is improved as compared with the mapping method of (1) or (2).

As described above, it is desirable that the connected components that exceed the size of the FPGA are simply mapped in order of increasing level. Since this method has almost no calculation time overhead, high speed mapping is also maintained.

On the other hand, when the size of the connected component exceeds the size of the FPGA, it is effective to make a copy of the primitive that has many connections with other primitives and to make the original connected component the size of the FPGA. This is a method of dividing into the following partial circuits. This is the mapping method of (4).

Next, the FP in which the number of stages of the circuit shown in FIG. 35 is four in the width direction and two primitives in the number of stages direction are arranged in the FP.
Consider the case of mapping to an emulator composed of GA.

When this circuit is divided into two stages which is the number of FPGA stages, it is divided into connected components 201 to 204 as shown in FIG. Here, pay attention to the connected component 203 that exceeds the size of the FPGA. FIG. 36 shows the result of mapping the connected components 203 in the order of the numbers or in the order of lower levels. Four FPGAs 213 to 216 were used. Here, among the lowest level primitives in the connected component 203, the one having the largest number of primitives at the output destination is selected, and a duplicate thereof is created. In this example, candidates for such primitives are primitives 15, 16,
Primitive 1 with the smallest number
Choose 5. FIG. 37 (a) is a primitive graph forming the connected component 203. FIG. 37B shows a result of the connected component 203 being decomposed into three new connected components 221, 222, and 223 by creating a copy of the primitive 15. Here, the primitives 151 and 152 in FIG. 37B both represent a copy of the primitive 15.

Here, since the size of the FPGA is still exceeded even after making 15 copies, the connected component 2
Again apply the decomposition by duplication of the primitive to 21. As a result, FIG. 37C shows the decomposition obtained by creating a copy of the primitives 16 and 17 in this order. In this way, the connected component 203 has the F of 231 to 237.
It was decomposed into a total of 7 connected components below the size of PGA.
Connected components Nos. 3 to 237 are connected components 231 to 237, respectively.
If 9 is added and the connected component number 10 is added to the connected component 204, it means that the primitive graph in FIG. 35 is divided into 10 connected components each having a size equal to or smaller than the FPGA.

At the time of creating the above duplication, primitive 1
38 and 39 show how the information regarding 5 changes. FIG. 38 shows the primitive information before the copy creation, and FIG. 39 shows the primitive information after the copy creation. In FIG. 39, the output destination of the primitive 15 is divided into three primitives 15, 151, 152.
Here, the same id as the original primitive 15 is attached to the primitive output to the dummy primitive.

Next, the plurality of newly obtained connected components are appropriately combined and assembled while satisfying the condition that the size is equal to or smaller than the size of FPGA. For example, the following procedure is available as a method of summarizing.

Step 1 C and T are an empty set, and U is a set whose connected components obtained by the above procedure are elements.

Step 2 If U is empty, end.

Step 3 Select the largest size A from U.

Step 4 Let S be a graph formed by merging T and A.

Step 5 If U is less than or equal to the size of the FPGA, replace T with S, remove A from U, otherwise register T with C.

Step 6 Go to step 2.

When the above procedure is completed as a result of the merging in step 4, C contains the connected components grouped up to the size of the FPGA as an element. In this process, if the original primitive id for a dummy primitive and the id of another primitive match, the primitives can be put together.

For a plurality of connected components in FIG. 37 (c),
Apply the above procedure. As the A in step 3, the largest size is selected (when the sizes are the same, the smallest number is selected). At the end of the procedure, the connected components 241, 242, 24 as shown in FIG.
It is summarized in 3. The rewriting of the primitive information in this grouping may be performed in the same manner as in the case of decomposing the connected components. If necessary, the primitive information corresponding to the generated copy is deleted.

Based on the connected components obtained above, FIG.
FIG. 41 shows a graph reconstructed by making a duplicate of a primitive of the circuit of FIG. The connected component 203 in FIG.
In FIG. 41, they are connected components 311, 312, 313.

The result of mapping the graph of FIG. 41 is shown in FIG. The number of FPGAs required for mapping the connected components 311, 312, 313 is three, which is improved compared to the case where four FPGAs are required when the mapping method of (3) is used as shown in FIG. I understand.

Therefore, by using the mapping method of (4), the filling rate of the FPGA can be improved in the logic emulator composed of a plurality of reprogrammable logic blocks with almost no loss of high speed. Also,
The division and grouping procedure of the connected components of the graph by copying the primitives is easy to mechanize, and the calculation time required for this is almost the same as the time required for searching the graph. In other words, the grouping of connected components is also mechanical, and backtracking is rarely performed, so that it can be similarly executed in a short time. This results in step 420 of FIG.
In the procedure of allocating connected components by duplicating primitives as shown in 1 to step 4205, the filling rate of FPGA can be improved without losing the high-speed mapping in the emulator of multistage connection.

The algorithm of the present invention can be applied to an emulator in which the programmable elements are connected by a connection other than the multistage connection method.

[0115]

According to the present invention, a logic circuit including a loop in a combinational circuit section could not be simulated in principle by the level sorting method, but such a logic circuit model is converted into an equivalent circuit model. As a result, it becomes possible to perform simulation by the level sorting method. Also, the oscillation of the loop of the circuit before conversion can be verified.

Further, according to the present invention, in a logic emulator composed of a plurality of reprogrammable logic blocks, it is possible to realize a mapping method for improving the filling rate of FPGA with almost no loss of high speed, and at the same time, Since it is easy to mechanize these dividing procedures, it can be implemented as a program on a computer.

[Brief description of drawings]

FIG. 1 is a diagram showing a schematic configuration of an embodiment of the present invention.

FIG. 2 is a diagram showing a model conversion procedure according to an embodiment.

FIG. 3 is a diagram showing a configuration of array elements.

FIG. 4 is a diagram for explaining decomposition of strongly connected components.

FIG. 5 is a diagram showing a circuit model including a loop.

FIG. 6 is a diagram showing a circuit model including a loop.

FIG. 7 is a diagram showing a circuit model including a loop in which a cut point is designated.

FIG. 8 is a diagram showing a circuit model including a loop in which a cut point is designated.

FIG. 9 is a diagram showing a circuit model in which a partial circuit in which a loop is cut is duplicated.

FIG. 10 is a diagram showing a circuit model in which a partial circuit in which a loop is cut is duplicated.

FIG. 11 is a diagram showing an equivalent circuit model to which corresponding branches are added.

FIG. 12 is a diagram showing an equivalent circuit model to which corresponding branches are added.

FIG. 13 is a diagram showing a circuit model to which a primitive for oscillation detection is added.

FIG. 14 is a diagram showing a circuit model to which a primitive for oscillation detection is added.

FIG. 15 is a diagram showing an example of circuit conversion.

FIG. 16 is a diagram showing a circuit model including a strongly connected component (a plurality of loops).

FIG. 17 is a diagram showing the circuit model 1 in which one loop is cut by designating a cut point.

FIG. 18 is a diagram showing a circuit model 2 in which one loop is cut by designating a cut point.

FIG. 19 is a diagram showing a circuit model and a strongly connected component after the loop is broken.

FIG. 20 is a diagram showing an equivalent circuit.

FIG. 21 is a diagram illustrating a simulation method in the case of a software simulator.

FIG. 22 is a diagram showing a configuration of an emulator according to another embodiment of the present invention.

FIG. 23 is a diagram showing a configuration of an FPGA.

FIG. 24 is a diagram showing an example of a simulation target circuit.

FIG. 25 is a diagram showing an example of grouping into primitives.

FIG. 26 is a diagram showing a primitive graph.

FIG. 27 is a diagram showing an example of inserting a dummy primitive.

FIG. 28 is a diagram showing a data structure expressing primitive information.

FIG. 29 is a diagram showing the flow of a circuit allocation procedure.

FIG. 30 is a diagram showing connected components when separated by level.

FIG. 31 is a diagram showing a circuit allocation result (a method of tracing a primitive connection).

FIG. 32 is a diagram showing a circuit allocation result (primitive number ordering method).

FIG. 33 is a diagram showing a connected component allocation procedure (allocated in ascending order of level).

FIG. 34 is a circuit allocation result (a method of increasing level)
FIG.

FIG. 35 is a diagram showing a primitive graph.

FIG. 36 is a circuit allocation result (smallest level order method)
FIG.

FIG. 37 is a diagram showing decomposition of connected components by copying a primitive.

FIG. 38 is a diagram showing primitive information before copy creation.

FIG. 39 is a view showing primitive information after the copy is created.

FIG. 40 is a diagram showing a summary of connected components.

FIG. 41 is a view showing a primitive graph after the primitives are put together.

FIG. 42 is a diagram showing a circuit allocation result (after grouping primitives).

FIG. 43 is a view showing a procedure for allocating connected components (division of connected components by copying a primitive).

[Explanation of symbols]

11 ... Simulation unit, 12 ... Circuit model storage unit,
13 ... Separation unit for separating the combinational circuit unit and the state storage unit, 1
4 ... Loop circuit detection unit, 15 ... Conversion unit for converting a loop circuit into an equivalent circuit, 221 ... Emulator, 2
22 ... FPGA 222a ... Universal element, 222b ... Complete crossbar switch.

Claims (4)

[Claims] 1. A logic simulation device for simulating a logic circuit using a level sorting method, means for storing a logic circuit to be simulated, and means for separating the logic circuit into a combinational circuit section and a state storage section. And a means for extracting a circuit A consisting of a loop composed of a plurality of logic elements from the combinational circuit section separated by this means, and the output of one logic element Z of the logic elements in the circuit A is removed. The circuit Y, the circuit X, and the storage element U are formed by using means for creating the circuit X, means for creating the storage element U that stores the previous output signal value of the logic element Z, and circuit Y that is a duplicate of the circuit X. Circuit conversion means having means for forming a cascade connection circuit of the circuit Y, and for each logic element of the circuit Y with respect to each logic element of the circuit X. Logic simulation apparatus characterized by connecting the same input as the input. 2. A means for comparing the output of the logic element Z of the circuit X and the output of the logic element corresponding to the logic element Z of the duplicated circuit Y, and determining whether or not the loop oscillates. The logic simulation device according to claim 1, which is made detectable. 3. A logic emulator in which a plurality of reprogrammable logic blocks are connected in multiple stages, wherein a primitive graph level-sorted in the order of signal flow from the input side is counted from the input side and divided into constant levels. A logic emulator characterized in that a plurality of connected components are generated and each connected component is allocated to a logic block. 4. When the size of the connected component allocated to the logical block exceeds the size of the logical block, the connected component is created by making a duplicate of the circuit element having the smallest level counted from the input side in the connected component. Is decomposed into a plurality of connected components having a size equal to or smaller than the size of the logical block, and these connected components are collectively assigned to the logical block under the condition that the size is smaller than the size of the logical block. The described logic emulator.