Multiple loop parallel pipelined logic simulation system

The present invention is capable of registering and reading out a logical element for which the state of the output pin changes. The system includes an input side reading out circuit for reading out the kind of logical element and the states of all the input pins thereof, a decision circuit for deciding the presence of the output pin that the status change is produced on when a logical operation is carried out according to the kind of logical element, an output side reading out circuit for reading out the information related to the logical element of the output pin producing the status change, and an exchange sending circuit for sending each information read out from the output side reading out circuit to the desired registering and reading out circuit for precise high speed logic simulation of a large scale logic circuit containing MOS-type logical elements.

BACKGROUND OF THE INVENTION 
1. Field of the Invention 
The present invention relates to a logic circuit simulator, particularly, 
to a special purpose processor suitable for high speed simulation of a 
large scale gate level circuit. 
2. Background of the Invention 
Documents describing special purpose processors for logic simulation of one 
gate level (G. F. Pfister: The Yorktown Simulation engine, 19th Design 
Automation Conference) and one functional level [Sasaki: Summary of the 
High Speed Simulator (HAL), The 26th National Conference of Information 
Processing] have been published. A well-known example of the former which 
is similar to the present invention has the disadvantage of being unable 
to precisely effect logic simulation of a MOS element circuit, because 
only unit delay or three-value (0, 1, indefinite) simulation can be 
carried out thereby. 
SUMMARY OF THE INVENTION 
The purpose of the present invention is to provide a special purpose 
processor for high speed and precise simulation of a large scale logic 
circuit containing MOS elements. 
Logic simulation is divided into four processes, (1) registration and read 
out of activated logical elements, (2) read out of the type of elements 
(AND, OR, etc) and the state the input pins, (3) logical operation of the 
elements and decision of output status change, (4) read out of the output 
side elements and of a delay time. These are effected by special purpose 
hardware, and data or operating instructions are circulated according to 
the sequence of (1).fwdarw.(2).fwdarw.(3).fwdarw.(4).fwdarw.(1)--for high 
speed logic simulation.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
In an embodiment shown in FIG. 1, an overall operating processor is 
composed of a triple loop. 
The first (or the second or the third, read the numbers in this order in 
parentheses hereinafter) loop 17 (18, 19) is composed of a registration 
and read out CKT 1 (2, 3) for registering and reading out the activated 
element; an element input side read out CKT 4 (5, 6) for reading out the 
kind of the element and the state of the input pin; a decision CKT 7 (8, 
9) for a logical operation of the element and for deciding the presence of 
output status change; a FIFO data buffer 10 (11, 12); an element output 
side read out CKT 13 (14, 15) for reading out the element to be output and 
the delay time; and an exchange network 16. 
It is assummed that a logic simulation circuit is divided into as many 
sub-circuits as the number of loops. The data for the kind of element, the 
connecting structure, and the delay time are divided corresponding to the 
subgraph, assigned to each one of the loops, and stored in the processor 
of the corresponding loop. 
Next, the structure of each one of the circuits is described. Each of the 
circuits 1 to 3 is composed of an event processor 20 and an event memory 
21, as shown in FIG. 2. The event memory 21 comprises a time wheel 22 
which is individually accessible and an event list 23. In the time wheel 
22, a head pointer H and a tail pointer T of the event list is stored, 
corresponding to each time. In the event list 23, the number of the 
activated element G, the input pin number N showing the status change of 
the element, and a status value S of the input pin are connected by a 
pointer P to be stored. If the four values [Driving, Resistive, High 
Impedance, X (indefinite)] are considered as a strength besides the level 
0, 1, and X (indefinite) to provide 3.times.4=12 values-for the status 
value S, a sufficient precision for processing MOS can be obtained. 
The circuits 4 to 6 are composed of a fan in processor 30 and an element 
memory 31, as shown in FIG. 3. The element memory 31 is composed of an 
activated element list 32, which is individually accessible, an element 
kind table 33, and an input value table 34. The element number G is stored 
in the activated element list, the element kind OP and the pointer P of 
the input table are stored in the element kind table, and the status of 
the input pins of all the element S.sub.1, S.sub.2, . . . are stored in 
the input value table. 
The circuits 7 to 9 are composed of an evaluation unit 40 and a status 
memory 44, as shown in FIG. 4. The evaluation unit 40 is composed of a 
data compression CKT for compressing the data of the input signal, a 
memory 42 for storing a true value for each element, and a decision 
circuit 43 for deciding the presence of the status change of output. The 
data compression CKT is provided for excluding a combination of a 
redundancy or meaningless input and for decreasing the memory capacity 
required for the true value table. The status of the output pin of the 
element is stored in the status memory 44, corresponding to the element 
number. 
The circuits 13 to 15 are composed of a fan-out processor 50 and a 
connecting structure memory 51, as shown in FIG. 5. The connecting 
structure memory 51 is composed of a pointer table 52, which is 
individually accessible, and a table to be output 53. The pointer P of the 
table to be outputted is stored in the pointer table and the number of 
elements to be output, the input pin number of the element, and the delay 
time d are stored in the table to be output. Furthermore, propagation 
delay time is also considered as the delay time to provide a value such 
that the propagation delay time is added to the delay time of the element 
to be output. The output is complicated, and termination of the reading 
out of the table to be output is decided by an END flag in the stored 
data. 
The exchange network 16 distributes the input data according to the address 
in a header part, and is composed of a multiple step network or a crossbar 
switch. 
The operation of each one of the above-described parts is divided into two 
phases, as shown in FIG. 6. In phase I, only the event processor and the 
fan-in processor are operated and the evaluation unit and the fan-out 
processor are in an idling state. In phase II, all the processors operate 
at the same time. 
The operations in phase I will be described according to FIGS. 2 and 3. 
First, the event processor 20 in FIG. 2 reads out the number of element G 
activated at the current time t, the input pin number N, and the input pin 
state S and feeds out the combination of (G,. N, S) to the fan-in 
processor. The fan-in processor 30 receives the combination of (G, N, S) 
and writes G in the activated element list 32 and S in the input value 
table 34. When this operation terminates for all the input pins of the 
activated element, phase I is complete. 
Next, the operations in the phase II will be described according to FIGS. 2 
to 5. The fan-in processor 30 reads out the element number G for the 
element registered in the activated element list, the kind OP, and the 
status of all the input pins of the element S.sub.1, S.sub.2, . . . from 
the element memory 31 and feeds out the combination of (G, OP, S.sub.1, 
S.sub.2, . . .). When there are many input points, it is preferable to 
provide a function that enables sending them separately. The evaluation 
unit 40 receives the combination of (G, OP, S.sub.1, S.sub.2, . . . ) and 
inputs them to the data compression circuit 41. The values read out from 
the status memory 44 are simultaneously inputted when the internal states 
are required for logical operations such as a flip-flop. The output of the 
data compression circuit 41 becomes the address of the true value table 
memory 42 and the value read out from the memory 42 becomes a new output 
of the element. Accordance or discordance of the present output and the 
previous output is checked by the decision circuit 43, and if there is a 
change, a new output value S is stored in the status memory 44, while the 
combination of (G, S) is sent to the data buffer. The fan-out processor 50 
of FIG. 5 fetches the combination of (G, S) then reads out the number of 
the element to be output G, the pin number N, and the delay time d from 
the connection structure memory 51, and sends out the combination of (G, 
N, S, d) to the exchange network 16. When all data has been outputted, the 
next combination of (G, S) is fetched from the data buffer. 
The exchange network 16 decodes the element number G and sends out the 
combination of (G, N, S, d) to any one of the three event processors. That 
is to say, the data is sent out to the event processor connected to the 
event memory which stores the information related to G. The event 
processor 20 of FIG. 2 receives the combination of (G, N, S, d), 
calculates the estimated time of activation t+d from the present time t 
and the delay time d, and then registers (G, N, S) with the event list of 
this time. 
The above-described operations are effected by a pipe-line method along a 
loop. That is to say, in phase I, the event processor and the fan-in 
processor, and in phase II, the event processor, the fan-in processor, the 
evaluation unit, the fan-out processor, and the exchange network 
simultaneously conduct the operation for the different elements. 
The above operations are described with regard to one loop, but 
calculations proceed in parallel with the exchange of data through the 
exchange network. If more parallel processing is desired, the number of 
loops can be increased without a major modification of the structure. 
Not shown in FIG. 1, the calculation device is connected to a host 
computer, for example, (a micro-computer) which loads data into memory, 
reads out results, and controls exchanges between phases I and II. 
The present invention can resolve the problems inherent in parallel 
processing to effect maximum calculation so that it can effect high speed 
logic simulation. For example, a large computer corresponding to the 
M200-H class effects simulation at 5.times.10.sub.4 elements/ second. In 
contrast, the present invention can effect simulation at 
1.2.times.10.sub.7 element/second four loops and at 4.8.times.10.sub.7 
element/second 16 loops, provided that the machine cycle is 100 ns. 
As compared with the well-known special purpose processor of logic 
simulation (G. F. Pfister: The Yorktown Simulation Engine, described 
before), the well-known example can process only a unit delay, whereas the 
present invention can process a standard delay containing a propagation 
delay. Furthermore, precise simulation becomes possible because the 
present invention can process many statuses. 
According to the present invention, less hardware is required due to its 
limited purpose, and the degree of parallel processing is easily improved.