Logic simulation machine - Patent Review 4656580

We claim:

1. A method for simulating logic operations comprising the steps of:

simulating one or more time sequential logic functions in each of a plurality of basic processors operating in time unison, and determining a value of a simulated logic function output in each of said plurality of basic processors as a proposed output with a fixed constant delay for the logic function being simulated; and

delaying said proposed output from a final output for a delay time specific to said logic function being simulated.

2. The method of claim 1, wherein said delay time is further specific to whether said proposed output has changed from a high to a low logic level or from a low to a high logic level.

3. The method of either of claims 1 or 2, further comprising the steps of:

detecting the presence of a glitch in said proposed output of a duration less than the corresponding delay time of said logic function being simulated; and

inhibiting said glitch from said final output.

4. A method for simulating logic operations comprising the steps of:

simulating one or more time sequential logic functions in each of a plurality of basic processors, said logic functions in each of said basic processors being simulated in successive work cycles of logic operations;

determining, in each of said basic processors in each of said work cycles, a minimum work space value as a minimum time to a next successive logic operation among all logic functions simulated by said basic processor for each said work cycle;

determining a global minimum work space value among all said basic processors for each said work cycle as a minimum one of work space values among all of said basic processors; and

advancing each of said basic processors in time sequence in each of said work cycles by said global minimum work space value.

5. The method of claim 4, wherein said step of determining a minimum time to a next successive logic operation comprises:

calculating a time to a predicted simulated logic function output transition time in accordance with a stored delay time for each logic function to be simulated during each said work cycle; and

storing a minimum calculated time to a predicted simulated function output transition time among all of said logic functions simulated during each said work cycle.

6. The method of claim 5, wherein said step of calculating a time to a predicted simulated logic function output transition time comprises:

for an initial work cycle and for a first work cycle following a transition in said simulated function output for the function simulated, subtracting said global minimum work space value from said stored delay time for each said simulated logic function and storing the difference; and

repetitively for successive work cycles, for each said simulated logic function, and until a predicted transition occurs in said simulated logic function output, subtracting said minimum work space value from said difference and replacing said difference with a new difference thus calculated.

7. The method of claim 5, wherein said delay time is one of a first delay time value corresponding to low-to-high transitions and a second delay time value corresponding to high-to-low transitions of said simulated logic function output for each said simulated logic function.

8. The method of claim 7, further comprising the step of:

selecting one of said first and second delay time values in accordance with a state of a simulated logic function output in a present work cycle and in a work cycle immediately prior to a present work cycle where a transition of a simulated logic function output occurs.

9. The method of any one of claims 4-8 further comprising the steps of:

detecting presence of a glitch having a duration less than a corresponding delay time of a logic function being simulated; and

inhibiting said glitch in a simulated logic function output.

10. A method for simulating logic operations in successive work cycles in a plurality of basic processors, comprising the steps of:

I. in each of a plurality of basic processors and for each logic function simulated in each of said basic processors:

(a) determining a value LU IN of a simulated logic function output with a fixed constant minimum delay time;

(b) reading an old data value O.sub.D (n), a saved data value S.sub.D (n), a status bit value S.sub.S (n) and a work space value WS(n) from a first signal value memory;

(c) reading at least one of a low-to-high delay time value LH and a high-to-low delay time value HL from an instruction memory;

(d) selecting one of said value WS(n), LH and HL in accordance with said values S.sub.D (n) and S.sub.S (n);

(e) if said value WS(n) is selected in step (d), subtracting a global minimum work space value GWS(n) therefrom and storing the difference value this calculated as a value WS(n+1), and if one of said values LH and HL is selected in step (d), storing the selected value as said value WS(n+1);

(f) performing a logic OR of individual bits of said value WS(n+1) to produce a signal WSO;

(g) performing logic operations:

SO=S.sub.S (n)+[(LU IN)+S.sub.D (n)],

GD=S.sub.S (n)"[(LU IN)+S.sub.D (n)],

and

S.sub.S (n+1)=WSO+SO+GD.

(h) selecting one of LU IN and O.sub.D (n) as a final simulated logic function output in accordance with a state of S.sub.S (n+1);

(i) storing said WS(n+1), S.sub.S (n+1), S.sub.D (n+1)=LU IN and O.sub.D (n+1) in a second signal value memory for a next successive work cycle;

(j) repeating said steps (a) through (i) for each simulated logic function for each said work cycle alternating reading and storing in said first and second signal value memories;

II. for each said work cycle for each said basic processor, determining a minimum value of WS(n+1); and

III. for each said work cycle determining a global minimum work space value GWS(n+1) for a next successive work cycle as a minimum value of WS(n+1) among all of said basic processors.

11. The method of claim 10, wherein said step II comprises, in each of said basic processors:

initializing a register with a maximum value;

comparing each value of WS(n+1) for each logic function simulated with the content of said register; and

if said value of WS(n+1) is less than said content of said register, replacing said content of said register with WS(n+1), and otherwise retaining said content of said register.

12. The method of claim 11, wherein said step III comprises:

initializing a counter to a minimum count value;

incrementing said counter;

while incrementing said counter, comparing a count value of said counter with values remaining in each of said registers of each of said basic processors; and

when said count value first becomes equal to one of said values remaining in said registers, employing said count value than present as said global minimum work space value GWS(n+1).

13. A logic function simulator comprising a plurality of basic processors, a control processor, and an interprocessor switch interconnecting said basic processors and said control processor, each of said basic processors comprising:

means for storing delay times for each logic function simulated by that basic processor;

means operating in response to said storing means for determining a time to a next successive logic operation for each said simulated logic function in accordance with a corresponding delay time;

means operating in response to said time determining means for determining a minimum work space value as a minimum time to a next successive logic operation among all said simulated logic functions; and

means for advancing said basic processor in time sequence by a global minimum work space value, said global minimum work space value being a minimum one of minimum work space values among all said basic processors.

14. The logic function simulator of claim 13, wherein said means for determining a time to a next successive logic operation for each said simulated logic function comprises means for subtracting said global minimum work space value from a delay time for each said simulated logic function.

15. The logic functions simulator of claim 14, wherein said subtracting means subtracts said global minimum work space value from said delay time for said simulated logic function for an initial cycle related to a predetermined logic operation and thereafter for successive cycles subtracts said global minimum work space value from a difference thus calculated and replaces said difference with a new difference determined by subtracting said global minimum work space value from the previous difference.

16. The logic function simulator of claim 15, further comprising means for calculating a new value of said global minimum work space value for each said cycle.

17. The logic function simulator of any one of claims 13-16 further comprising:

means for detecting the presence of a glitch in a simulated output for each said simulated logic function of a duration less than the corresponding delay time of said simulated logic function; and

means for inhibiting said glitch.

18. A logic function simulator comprising a plurality of basic processors, a control processor, and an interprocessor switch interconnecting said basic processors and said control processor, said basic processors and said control processor comprising means for simultaneously advancing said basic processors and said control processor through logic operations to be simulated in each work cycle, at a time interval equivalent to a minimum time to a next successive logic operation, among all said basic processors, said minimum time being determined in each said work cycle.

19. The logic function simulator of claim 18, wherein said advancing means comprises means in each of said basic processors for storing delay times for each logic function being simulated, said delay times including delay times for each of a low-to-high and high-to-low transition of each simulated output of each simulated logic function; means for selecting one of said delay times corresponding to a low-to-high transition or a high-to-low transition in accordance with a type of transition predicted for each said simulated logic function; and means for accumulatively subtracting a global minimum work space value from the selected delay time for each said simulated logic function, said global minimum work space value being a minimum work space value among all of said basic processors.

20. The logic function simulator of either one of claims 18 or 19 further comprising:

means for detecting the presence of a glitch in each simulated output of each said simulated logic function having a duration less than a corresponding delay time for a corresponding simulated logic function; and

means for inhibiting said glitch.

21. A logic function simulator comprising:

I. a plurality of basic processors, each of said processors comprising:

(a) means for determining a value of a simulated logic function output as a proposed output LU IN with a fixed constant delay for the logic function being simulated;

(b) first and second signal value memories;

(c) means for storing data received from said first and second signal value memories, said data received from said signal value memories including an old data value O.sub.D (n), a saved data value S.sub.D (n), a status bit value S.sub.S (n) and a work space value WS(n);

(d) an instruction memory for storing a low-to-high delay time value LH and a high-to-low delay time value HL for each logic function simulated by the basic processor;

(e) multiplexer means for selecting one of WS(n), LH and HL in accordance with S.sub.S (n) and S.sub.D (n);

(f) subtractor means for subtracting a minimum work space value from WS(n) to obtain a value WS(n+1) if said WS(n) is selected and passing the selected of said LH and HL if one of said LH and HL is selected;

(g) logic circuit means operating in response to an output of said subtracting means, said signals LU IN, O.sub.D (n), S.sub.D (n) and S.sub.S (n) for determining a next successive value S.sub.S (n+1) of S.sub.S (n) indicative of whether or not a change in said LU IN has occurred but is not yet to be propagated;

(h) means for selecting as an output O.sub.D (n+1) one of LU IN and O.sub.D (n+1) in accordance with an output of said logic circuit means; and

(i) switch means for loading into a selected one of said first and second signal value memories said S.sub.S (n+1), LU IN=S.sub.D (n+1), O.sub.D (n+1) and WS(n+1) to become O.sub.D (n), S.sub.S (n) and WS(n), respectively, for a next successive work cycle for a corresponding logic function;

II. a control processor for providing primary signal inputs to said basic processors; and

III. an inter-processor switch for interconnecting said basic processor and said control processor.

Description Submit all comments and votes

BACKGROUND OF THE INVENTION

The present invention relates to a logic simulation machine, which is a special purpose, highly parallel computer for the gate level simulation of logic. The logic simulation machine may operate in combination with a host computer and a local computer which are used to provide loading functions and to analyze the results of the simulation. The logic simulation machine includes a plurality of separate basic processors and a control processor interconnected by a switch.

Logic technologies such as very large scale integrated circuits and Josephson technology provide significant improvements in cost/performance and reliability. However, they have disadvantages in that fault diagnosis thereof is more difficult than previous technologies and engineering rework cycles needed to correct faults in logic design are greatly lengthened. These disadvantages exact great economic penalties for design errors and omissions and place a greater emphasis on the goal of completely verifying design in advance of engineering models.

One technique for providing design verification is simulation; however, this approach has certain disadvantages. It lacks the absoluteness of static verification or any other technique actually proving correctness. The presence of errors, not their absence, is all testing can show, and it is expensive in computer resources and time consuming. Even with high-level software simulation, it is not feasible to run even short hardware diagnostic programs.

However, if the cost of simulation is decreased drastically and the speed and capacity are increased by orders of magnitude, the situation is altered radically. Since an entire processor can be simulated, far more stringent verification is possible through execution of substantial software tests. Also, logic can be tested while embedded in a standard processor design, simplifying test sequence creation and effectively providing personal engineering models. Other advantages also arise. Thus, simulation of faults can be used to derive and verify manufacturing and field tests much more economically.

U.S. Pat. No. 4,306,286, issued Dec. 15, 1981, to Cocke et al. and assigned in common with the present application, describes a logic simulation machine composed of a plurality of parallel processors and a control processor which is capable of simulating a large variety of logic functions. The present invention is an improvement upon the logic simulation machine described in the Cocke et al. patent. As such, the logic simulation machine of Cocke et al. will hereinafter be described in detail.

The logic simulation machine of the Cocke et al. patent is a special purpose, highly parallel computer for the gate level simulation of logic. It provides logic simulation speeds far beyond those of earlier software logic simulators. The embodiment thereof to be described includes thirty-one processors which simulate one gate delay for 31K gates.

Since that logic simulation machine is not a general purpose computer, it must be used as a device attached to a computer which can perform for it functions such as compilation, input/output control, etc. The system in which the logic simulation machine is used may for instance, contain two computers in addition to the logic simulation machine.

The two other computers used in the logic simulation machine may be on an IBM System/370 "host" computer and a local computer connected as an interface between the logic simulation machine and the 370 host computer. The local computer may be IBM Series/1 Model 5 minicomputer. Although two general purpose computers are shown in the following description in alternative embodiments their functions may be performed by one general purpose computer such as the IBM 801. The functions performed by the two general purpose computers are to load the logic simulation machine with data and instructions and to analyze the results that the logic simulation machine has obtained in a manner known in the data processing art.

More particularly, the System/370 host computer provides large computation and file support functions such as user interface control, command parsing, EXEC execution, result display, etc., compilation of logic simulation machine code and input test sequences, file storage and management, and communication with the local computer. The local computer provides fast turn-around functions, such as control of logic simulation machine execution, e.g., single-cycle execution, communication with the host computer, simulation of large storage arrays (control store, main memory, etc.), application of test input sequences, capture of test output results and insertion/removal of logic faults in the fault simulation mode.

Information passed between the logic simulation machine and the host computer is not interpreted by the local computer. The host computer compilation generates information in a form which is directly usable by the logic simulation machine and which can be transmitted through the local computer with no change.

The local computer and the host computer are standard machines and are controlled by programs, therefore, their contribution to the system is conventional. Also, it is possible for the logical simulation machine to have its instructions and data loaded by manual means and its results analyzed by manual means.

Referring to FIG. 1, the logic simulation machine of the Cocke et al. patent is shown in block diagram form. The machine includes a plurality of basic processors, the number of which may vary although thirty-one processors are shown as an example. The thirty-one basic processors are connected to a thirty second processor referred to as a control processor through an inter-processor switch. The plurality (thirty-one) of basic processors are the computing engines of the logic simulation machine; they simulate the individual gates of the design. All the basic processors run in parallel, each simulating a portion of the logic and each basic processor can simulate up to 1024 single output functions. Because the basic processors run in parallel, increasing their number does not decrease the simulation rate, but may, in alternative embodiments, be used to increase it.

There is one control processor (processor 32 in FIG. 1) provided in a logic simulation machine. It provides overall control and input/output facilities. Responding to I/O commands from the Series/1, the control processor performs the functions of starting and stopping the basic processor, loading the basic processor switch instructions and data and transferring input and output data between the basic processors and the local computer, re-ordering the data for simpler processing by the local computer. In addition the control processor interrupts the local computer in response to events occurring during the simulation. Such events include the end of the simulation, requests for array simulation within the local computer, and the occurrence of user-defined break-points.

There is one inter-processor switch 33 in the logic simulation machine. It provides communication among the thirty-one basic processors and between them and the control processor 32. Its primary purpose is to communicate simulated logic signals from the basic processor generating them to the basic processor using them. In addition, it provides communication between the basic processors 1-31 and the control processor 32 for loading the basic processors, transferring inputs and outputs to the local computer, etc.

In the next section of this description the basic processors 1-31, inter-processor switch 33 and control processor 32 of the logic simulation machine are described on a block diagram level with reference to FIG. 1, then a more detailed description is presented with reference to the schematic drawings of FIGS. 2 through 8.

Basic processors (1 through 31 in FIG. 1) are the computing engines of the logic simulation machine: each simulates the individual gates of a portion of the logic. The simulation results are also communicated among the various processors.

The data on which a basic processor operates represent logic signal values. Each datum can represent three values: logical 0, logical 1, and undefined. "Undefined" indicates that the represented signal could be either logical 0 or logical 1. The three values are coded using two bits per datum as follows:

______________________________________ BIT 0 BIT 1 VALUE ______________________________________ 0 0 logical 0 1 0 logical 1 0 1 undefined 1 1 undefined ______________________________________

Either of the two "undefined" combinations may be initially loaded into a basic processor, and a basic processor may produce either as a result during simulation.

Since bit 1 distinguishes the undefined combinations, it is referred to as "the undefined bit." Since bit 0 distinguishes logical 0 from logical 1, it is referred to as "the value bit."

The use of 00 as logical 0 and 10 as logical 1 is a convention; the reverse could be used. However, the use of combinations 01 and 11 to represent undefined values is not a convention; it is built into the basic processor hardware.

The data representation described above is uniformly used throughout the logic simulation machine to represent logic signals.

As illustrated in FIG. 1, each basic processor such as processor 1 has a plurality of internal memories with a logic unit 34 connecting them. Two of these memories are two identical logic data memories which alternately assume one of two roles; that of the current signal value memory 35 and that of the next signal value memory 36. For a clearer explanation of the logic simulation machine, the functions of the logic data memories will be described in terms of these roles.

The current and next signal value memories 35 and 36 contain logic signal representations. Both have 1024 locations, each holding one signal.

The data in current signal value memory 35 are the logic signal values that are currently present in the simulation. The logic unit updates those values, placing the results in the next signal value memory.

The process of updating all the signal values is called a major cycle. The simulation proceeds in units of major cycles, each of which corresponds to a single gate delay. At the conclusion of each major cycle, the logic simulation machine may halt; if it does not, the former next signal value memory is designated to be the current signal value memory (and vice versa) and another major cycle is performed. (It may be noted at this point that the major cycle as used in the Cocke et al. machine is later redefined for purposes of the present invention as a "work cycle", which need not correspond to a fixed time period in simulation. This will be discussed below in more detail.)

Another component of the basic processor of FIG. 1 is the instruction memory 202. The logic unit 34 uses the instruction memory 202 in computing updated logic signal values. The instruction memory has 1024 locations, each containing a single logic simulation machine instruction corresponding to a single 1-output, 5-input gate.

Each logic simulation machine instruction contains a function code field, referred to as the opcode, and five address fields. The function code specifies the logic function to be performed, e.g., AND, NOR, XOR, etc.; this is discussed in more detail hereinafter. The five address fields specify input connections to a gate.

To perform a major cycle, the logic unit 34 sequences through instruction memory 202 in address order, executing each instruction by computing the specified logic function on the five specified values from current signal memory. The result of each instruction is placed in next signal value memory 36 at the address equal to the instruction (representing a gate). For example, the instruction at address X has its result (representing the gate's output) placed at next signal value memory 36 address X; and the gate's output one gate delay earlier resides at current signal value memory 35 address X.

Each execution of an instruction by the logic unit is referred to (somewhat informally) as a minor cycle.

It is important to note that instructions can be executed in any order, i.e., their placement in the instruction memory is arbitrary. This is true because updated values are placed in a separate memory, and there are no branch, test, etc., instructions. This is true because updated values are placed in a separate memory, and there are no sequences for communication between basic processors as will be discussed later.

Instructions have fields other than the function code and 5 addresses. These fields are used to perform "dotted" logic and to simulate gates with more than 5 inputs. When these fields are used, instruction execution order is no longer completely arbitrary. These fields are discussed in later sections.

The operation of a basic processor of FIG. 1 will be described using, as an example, the circuit shown in FIG. 2, which includes four NAND gates.

In FIG. 2, the numbers on the output sides of the gates are the locations in instruction memory of the instructions representing the gate. They are also the locations in current and next signal memory holding the simulated gate outputs. Inputs are assumed to come from locations 5 and 6. (The numbers above the gates represent delay times through the gates. These will be discussed in more detail below in the Description of the Preferred Embodiments. For the present discussion, and as is universally true in the logic simulation machine of Cocke et al., a unit gate delay is assumed for both high-to-low and low-to-high signal transitions.)

The instruction memory contents required for simulation are shown (simplified) in the table of FIG. 3.

Addresses 3 through 5 of each instruction in FIG. 3 are left blank because they are unused in this example; in practice, they might be set to addresses containing constant logical 1's (because the gates are NAND gates).

The table shown in FIG. 4 lists the contents of current signal values undefined (shown as asterisks). The gradual extinction of undefined values shows how logic values propagate through the gates. It should be noted that gate 2 output is fully defined at cycle 2, since a NAND gate with a 0 input has an output of 1 independent of its other inputs.

When a simulation does not require all of the instruction memory locations, the logic unit may execute fewer than the maximum of 1024 instructions per major cycle. This shortens each major cycle, increasing the simulation speed.

The major cycle length is controlled by a minor cycle count register to be described in