Method and apparatus for logic simulation

• US 5,053,980 A
• Filed: 03/06/1989
• Issued: 10/01/1991
• Est. Priority Date: 03/10/1988
• Status: Expired due to Term

• Current Assignee: Matsushita Electric Industrial Company Limited 1006 OAZA Kadoma-Shi Osaka Japan
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Kanazawa, Kiyoshi
• Primary Examiner(s): Lall, Parshotam S.
• Assistant Examiner(s): Ramirez, Ellis B.
• Application Number:
  US07/319,430
• Time in Patent Office: 939 Days
• Field of Search: 364/526, 364/488, 364/490, 364/578, 364/300, 364/200, 364/900, 371/23, 371/17, 371/27, 340/705
• US Class Current: 703/16
• CPC Class Codes: G06F 30/33 Design verification, e.g. functional simulation or model checking

Abstract

Determination of an operation of a logic circuit is usually called logic simulation. The logic simulation in which changes in signal status at input terminals and output terminals of an element in the logic circuit to be simulated are represented by events and the signal status at the output terminal is calculated only for the element in which the event has occurred at the input terminal thereof, is called an event driven logic simulation. In the event driven logic simulation, a current time is used to decide and extract the event to be processed. In the prior art apparatus, the decision and extraction are interrupted when the current time is updated. In the present invention, identifiers (colors) are imparted to the events to group the events. The current time is updated when the event having a special color is not present. Thus, a simulation speed in the event driven logic simulation method and apparatus is improved.

Claims

1. A logic simulation method of a parallel processing type for calculating an operation of a logic circuit to be simulated by using an algorithm of an event driven type, wherein a value calculated as a current simulation time, denominated as current time, is used, and a change of a signal state occurring at an input terminal and an output terminal of an element included in said logic circuit is represented by data denominated as events, said events including

a value, denominated as an event time, representing a time when the change of the signal state has occurred,

a value representing to what state the signal state has changed, and

a value representing the input terminal or the output terminal of the element where the signal state has changed, and

in which algorithm,

an event having an event time equal to the current time is decided to be processible,

the signal state of the output terminal of the element is calculated anew only with respect to the element which is represented by the processible event and the signal state of whose input terminal has changed, and

only when the signal state of the output terminal has changed is an event representing the change of the signal state of the output terminal generated anew, and

wherein each of the events has an identifier for classifying the events into a plurality of groups,

said logic simulation method comprising the steps of:

(a) storing data representing changes of the states of signals applied to the input terminal of said logic circuit as unprocessed event groups;

(b) taking out, from the stored unprocessed event groups, an event having an event time equal to the current time and erasing the event which has been stored;

(c) setting a value to an identifier of the taken-out event;

(d) processing the event, to whose identifier a value has been set, by using the algorithm of the event driven type and storing, as a new unprocessed event, a newly calculated event by the processing using the algorithm of the event driven type;

(e) deciding whether or not an event having an event time equal to the current time is present in the stored unprocessed event groups;

(f) selecting one of values which can be assumed by the identifiers for classifying the events into a plurality of groups;

(g) deciding whether or not an event, to whose identifier a value equal to the selected value has been set, is present in the other stored unprocessed event groups; and

(h) updating the current time when it is decided that an event having the event time equal to the current time is not present in the stored unprocessed event groups, and when it is decided that an event, to whose identifier a value equal to the selected value has been set, is not present in the other stored unprocessed event groups;

said steps (a)-(h) being processible in parallel with one another.

2. A logic simulation method of a parallel processing type for calculating an operation of a logic circuit to be simulated by using an algorithm of an event driven type, wherein a value calculated as a current simulation time, denominated as current time, is used, and a change of a signal state occurring at an input terminal and an output terminal of an element including in said logic circuit is represented by data denominated as events, said events including

a value, denominated as an event time, representing a time when the change of the signal state has occurred,

a value representing to what state the signal state has changed, and

a value representing the input terminal or the output terminal of the element where the signal state has changed, and

in which algorithm,

an event having an event time equal to the current time is decided to be processible,

the signal state of the output terminal of the element is calculated anew only with respect to the element which is represented by the processible event and the signal state of whose input terminal has changed, and

only when the signal state of the output terminal has changed is an event representing the change of the signal state of the output terminal generated anew, and

wherein each of the events has an identifier for classifying the events into a plurality of groups,

said logic simulation method comprising the steps of:

(a) storing data representing changes of the states of signals applied to the input terminal of said logic circuit as unprocessed event groups;

(b) taking out, from the stored unprocessed event groups, an event having an event time equal to the current time and erasing the event which has been stored;

(c) setting a value to an identifier of the taken-out event;

(d) processing the event, to whose identifier a value has been set, by using the algorithm of the event driven type, and setting a value equal to the value set to the identifier of the taken-out event to an identifier of a newly calculated event obtained by the processing using the algorithm of the event driven type, when an event time of the newly calculated event is equal to the event time of the taken-out event which has been taken out from the stored unprocessed event groups and which has been used to calculate the newly calculated event, while, setting a value different from the value set to the identifier of the taken-out event to an identifier of a newly calculated event, when an event time of the newly calculated event is different from the event time of the taken-out event;

(e) storing the newly calculated event as a new unprocessed event;

(f) deciding whether or not an event having an event time equal to the current time is present in the stored unprocessed event groups;

(g) deciding whether or not an event whose identifier has a set value equal to the value set to the identifier of a taken-out event, which has been taken out from the stored unprocessed event groups, is present in the other stored unprocessed event groups;

(h) updating the current time when it is decided that an event having the event time equal to the current time is not present in the stored unprocessed event groups, and when it is decided that an event whose identifier has a set value equal to the value set to the identifier of the taken-out event, which has been taken out from the stored unprocessed event groups, is not present in the other stored unprocessed event groups;

(i) changing a value to be set to the identifier of the taken-out event, which has been taken out from the stored unprocessed event groups, when the current time has been updated;

said steps (a)-(i) being processible in parallel with one another.

3. A logic simulation method of a parallel processing type for calculating an operation of a logic circuit to be simulated by using an algorithm of an event driven type, wherein a value calculated as a current simulation time, denominated as current time, is used, and a change of a signal state occurring at an input terminal and an output terminal of an element included in said logic circuit is represented by data denominated as events, said events including

a value, denominated as an event time, representing a time when the change of the signal state has occurred,

a value representing to what state the signal state has changed, and

a value representing the input terminal or the output terminal of the element where the signal state has changed, and

in which algorithm,

an event having an event time equal to the current time is decided to be processible,

the signal state of the output terminal of the element is calculated anew only with respect the element which is represented by the processible event and the signal state of whose input terminal has changed, and

only when the signal state of the output terminal has changed in an event representing the change of the signal state of the output terminal generated anew, and

wherein each of the events has an identifier for classifying the events into a plurality of groups,

said logic simulation method comprising the steps of:

(a) storing data representing changes of the states of signals applied to the input terminal of said logic circuit as unprocessed event groups;

(b) taking out, from the stored unprocessed event groups, an event having an event time equal to the current time and erasing the event which has been stored;

(c) setting a value to an identifier of the taken-out event;

(d) processing the event, to whose identifier a value has been set, by using the algorithm of the event driven type, and setting a value equal to the value set to the identifier of the taken-out event to an identifier or a newly calculated event obtained by the processing using the algorithm of the event driven type, when an event time of the newly calculated event is equal to the event time of the taken-out even which has been taken out from the stored unprocessed event groups and which has been used to calculate the newly calculated event, while, setting a value different from the value set to the identifier of the taken-out event to an identifier of a newly calculated event, when an event time of the newly calculated event is different from the event time of the taken-out event;

(e) storing the newly calculated event as a new unprocessed event;

(f) storing a minimum value of event times of newly calculated event groups;

(g) deciding whether or not an event having an event time equal to the current time is present in the stored unprocessed event groups;

(h) deciding whether or not an event whose identifier has a set value equal to the value set to the identifier of a taken-out event, which has been taken out from the stored unprocessed event groups, is present in the other stored unprocessed event groups;

(i) updating the current time successively within a range in which an event having an even time equal to the current time is not present in the stored unprocessed event groups and the current time does not exceed a value stored as a minimum value of the event times of the events which have been newly calculated by using the algorithm of the event driven type, when it is decided that an event having the event time equal to the current time is not present in the stored unprocessed event groups and when it is decided that an event whose identifier has a set value equal to the value set to the identifier of the taken-out event, which has been taken out from the stored unprocessed event groups, is not present in the other stored unprocessed event groups;

(j) changing a value to be set to the identifier of the taken-out event, which has been taken out from the stored unprocessed event groups, when the updating of the current time has been completed; and

(k) re-initializing a value stored as a minimum value of the event times of the event groups which have been calculated by using the algorithm of the event driven type;

said steps (a)-(k) being processible in parallel with one another.

4. A logic simulation method of a parallel processing type for calculating an operation of a logic circuit to be simulated by using an algorithm of an event driven type, wherein a value calculated as a current simulation time, denominated as current time, is used, and a change of a signal state occurring at an input terminal and an output terminal of an element included in said logic circuit is represented by data denominated as events, said events including

a value, denominated as an event time, representing a time when the change of the signal state has occurred,

a value representing to what state the signal state has changed, and

a value representing the input terminal or the output terminal of the element where the signal state has changed, and

in which algorithm,

an event having an event time equal to said current time is decided to be processible,

the signal state of the output terminal of the element is calculated anew only with respect to the element which is representing by the processible event and the signal state of whose input terminal has changed, and

only when the signal state of the output terminal has changed is an event representing the change of the signal state of the output terminal generated anew, and

wherein each of the events has an identifier for classifying the events into a plurality of groups,

said logic simulation method comprising the steps of:

(a) storing data representing changes of the states of signals applied to the input terminal of said logic circuit as unprocessed event groups;

(b) performing first take-out processing by taking out, from the stored unprocessed event groups, an event having an event time equal to the current time and erasing the event which has been stored;

(c) performing second take-out processing when the first take-out processing is not performed, wherein an unprocessed event representing the change of the signal state of the input terminal of each element is processed independently of any other elements, and, when unprocessed events representing the changes of the signal states of the input terminals are present at all input terminals of the elements, then an event having a minimum event time among the unprocessed events is taken out and the event which has been stored is erased;

(d) storing a minimum one of the event times of the events taken out in the first take-out processing or the second take-out processing;

(e) setting a value to an identifier of the taken-out event which is taken-out in the first take-out processing or the second take-out processing;

(f) processing the event, to whose identifier a value has been set, by using the algorithm of the event driven type, and setting a value equal to the set value of the identifier of an event, which has been taken-out from the stored unprocessed event groups so as to be used to process the event, to the identifier of a newly calculated event obtained by the processing using the algorithm of the event driven type;

(g) storing the newly calculated event, to whose identifier the value has been set, as a new unprocessed event;

(h) deciding whether or not an event having an event time equal to the current time is present in the stored unprocessed event groups;

(i) selecting one of values which can be assumed by the identifiers for classifying the events into a plurality of groups;

(j) deciding whether or not an event, to whose identifier a value equal to the above-selected value has been set, is present in the other stored unprocessed event groups;

(k) updating the current time successively within a range in which an event having an event time equal to the current time is not present in the stored unprocessed event groups and the current time does not exceed a value stored as a minimum value of the event times of the events which have been taken out by the first take-out processing or the second take-out processing, when it is decided that an event having the event time equal to the current time is not present in the stored unprocessed event groups and that an event whose identifier has a set value equal to the above-selected value is not present in the other stored unprocessed event groups;

(l) changing, at the time of starting the second take-out processing, a value to be set to the identifier of an event which has been taken out from the stored unprocessed event groups,

(m) changing, at the time of starting the second take-out processing, a value to be selected as one of the values, which values can be assumed by an identifier for classifying the events into a plurality of groups, to a value which has been set to an event taken out from the stored unprocessed event groups, until immediately before the time of starting the second take-out processing; and

(n) re-initializing, at the time of completion of updating the event time, the value stored as a minimum value of the event times of the events taken out by the first take-out processing or the second take-out processing;

said steps (a)-(n) being processible in parallel with one another.

5. A logic simulation apparatus of a parallel processing type for calculating an operation of a logic circuit to be simulated by using an algorithm of an event driven type, wherein a value calculated as a current simulation time, denominated as current time, us used, and a change of a signal state occurring at an input terminal and an output terminal of an element included in said logic circuit is represented by data denominated as events, said events including

a value, denominated as an event time, representing a time when the change of the signal state has occurred,

a value representing to what state the signal state has changed, and

a value representing the input terminal or the output terminal of the element where the signal state has changed, and

in which algorithm,

an event having an event time equal to the current time is decided to be processible,

the signal state of the output terminal of the element is calculated anew only with respect to the element which is represented by the processible event and the signal state of whose input terminal has changed, and

only when the signal state of the output terminal has changed is an event representing the change of the signal state of the output terminal generated anew,

said logic simulation apparatus comprising:

(a) a current time outputting unit for outputting a current time;

(b) an event memory unit for storing unprocessed events;

(c) an event take-out unit for taking out from said event memory unit an event having an event time equal to the current time and erasing from said event memory unit the taken-out event;

(d) a coloring unit for assigning one of a plurality of identifiers, which classify the events into a plurality of groups, to a taken-out event which has been taken out from said event memory unit;

(e) a circuit operation calculation unit for inputting an event, to which one of said identifiers has been assigned, as input data, calculating a change of a signal state of the logic circuit to be simulated by using the algorithm of the event driven type, and outputting an event representing a result of the calculation as a new unprocessed event having the one of the identifiers;

(f) a special color designation unit for selecting one value from among a plurality of values, which can be assumed by the identifiers assigned to the events by said coloring unit, and outputting t he selected one value as a special color; and

(g) a special color presence deciding unit for deciding whether or not an event having an identifier, whose value is equal to the value of the special color, is present in said event take-out unit and said circuit operation calculation unit, wherein,

said event memory unit comprises;

storage means for storing the event outputted from said circuit operation calculation unit, but with the identifier being removed therefrom; and

means for deciding whether or not an event having an event time equal to the current time is present in said event memory unit, and

said current time outputting unit comprises means for updating the current time when said event memory unit has decided that an event having an event time equal to the current time is not present in said event memory unit and simultaneously when said special color presence deciding unit has decided that an event, whose identifier has a set value equal to the special color, is not present in both said event take-out unit and said circuit operation calculation unit;

said units (a)-(g) comprising hardware independent of one another and being operable in parallel with one another.

6. A logic simulation apparatus of a parallel processing type for calculating an operation of a logic circuit to be simulated by using an algorithm of an event driven type wherein a value calculated as a current simulation time, denominated as current time, is used, and a change of a signal state occurring at an input terminal and an output terminal of an element included in said logic circuit is represented by data denominated as events, said events including

a value, denominated an event time, representing a time when the change of the signal state has occurred,

a value representing to what state the signal state has changed, and

a value representing the input terminal or the output terminal of the element where the signal state has changed, and

in which algorithm,

an event having an event time equal to the current time is decided to be processible,

the signal state of the output terminal of the element is calculated anew only with respect to the element which is represented by the processible event and the signal state of whose input terminal has changed, and

only when the signal state of the output terminal has changed is an event representing the change of the signal state of the output terminal generated anew,

said logic simulation apparatus comprising:

(a) a current time outputting unit for outputting a current time;

(b) an event memory unit for storing unprocessed events;

(c) an event take-out unit for taking out from said event memory unit an event having an event time equal to the current time and for erasing from said event memory unit the taken-out event;

(d) a coloring unit for assigning one of a plurality of identifiers, which classify the events into a plurality of groups, to a taken-out event which has been taken out from said event memory unit;

(e) a circuit operation calculation unit for inputting an event, to which one of the identifiers has been assigned, as input data, calculating a change of a signal state of the logic circuit to be simulate by using the algorithm of the event driven type, and outputting an event representing a result of the calculation;

(f) a special color designation unit for outputting, as a special color, a value which is the same as the value of an identifier which has been assigned to an event by said coloring unit; and

(g) a special color presence deciding unit for deciding whether or not an event having an identifier, whose value is equal to the value of the special color, is present in said event take-out unit and said circuit operation calculation unit, wherein,

said circuit operation calculation unit comprises;

means for processing the event, which has been taken out from said event memory unit and to which the identifier has been assigned, by using the algorithm of the event driven type, thereby calculating and outputting a new event;

means for setting a value which is the same as the special color to an identifier of the new event when an event time of the new event is equal to the event time of the taken-out event which has been taken out from said event memory unit and used in the calculation to obtain the new event, while, said means setting a value different from the special color to the identifier of the new event when the event time of the new event is different from the event time of the taken-out event which has been taken out from said event memory unit and used in the calculation to obtain the new event; and

means for outputting, as a new unprocessed event, the new event which has been calculated anew and to whose identifier the new value has been assigned,

said event memory unit comprises;

storage means for storing the event outputting from said circuit operation calculation unit, but with the identifier being removed therefrom; and

means for deciding whether or not an event having an event time equal to the current time is present in said event memory unit,

said current time outputting unit comprises means for updating the current time when said event memory unit has decided that an event having an event time equal to the current time is not present in said event memory unit and simultaneously when said special color presence deciding unit has decided that an event, whose identifier has a set value equal to the special color, is not present in both said event take-out unit and said circuit operation calculation unit, and

said coloring unit comprises means for changing a value of an identifier to be assigned to a taken-out event which has been taken out from said event memory unit when the current time has been updated,

said units (a)-(g) comprising hardware independent of one another and being operable in parallel with one another.

7. A logic simulation apparatus of a parallel processing type for calculating an operation of a logic circuit to be simulated by using an algorithm of an event driven type, wherein a value calculated as a current simulation time, denominated as current time, is used, and a change of a signal state occurring at a input terminal and an output terminal of an element included in said logic circuit is represented by data denominated as events, said events including

a value, denominated an event time, representing a time when the change of the signal state has occurred,

a value representing to what state the signal state has changed, and

a value representing the input terminal or the output terminal of the element where the signal state has changed, and

in which algorithm,

an event having an event time equal to the current time is decided to be processible,

the signal state of the output terminal of the element is calculated anew only with respect to the element which is represented by the processible event and the signal state of whose input terminal has changed, and

only when the signal state of the output terminal has changed is an event representing the change of the signal state of the output terminal generated anew,

said logic simulation apparatus comprising:

(a) a current time outputting unit for outputting a current time;

(b) an event memory unit for storing unprocessed events;

(c) an event take-out unit for taking out from said event memory unit an event having an event time equal to the current time and for erasing from said event memory unit the taken-out event;

(d) a coloring unit for assigning one of a plurality of identifiers, which classify the events into a plurality of groups, to a taken-out event which has been taken out from said event memory unit;

(e) a circuit operation calculating unit for inputting an event, to which one of the identifiers has been assigned, as input data, calculating a change of a signal state of the logic circuit to be simulated by using the algorithm of the event driven type, and outputting an event representing a result of the calculation;

(f) a minimum event time memory unit for storing a minimum value of event times of the events outputted from said circuit operation calculating unit;

(g) a special color designation unit for outputting, as a special color, a value which is the same as the value of an identifier which has been assigned to an event by said coloring unit; and

(h) a special color presence deciding unit for deciding whether or not an event having an identifier, whose value is equal to the value of the special color, is present in said event take-out unit and said circuit operation calculation unit, wherein

said circuit operation calculation unit comprises;

means for processing the event, which has been taken out from said event memory unit and to which the identifier has been assigned, by using the algorithm of the event driven type, thereby calculating and outputting a new event;

means for setting a value which is the same as the special color to an identifier of the new event when an event time of the new event is equal to the event time of the taken-out event which has been taken out from said event memory unit and used in the calculation to obtain the new event, while, said means setting a value different from the special color to the identifier of the new event when the event time of the new event is different from the event time of the taken-out event which has been taken out from said event memory unit and used in the calculation to obtain the new event; and

means for outputting, as a new unprocessed event, the new event which has been calculated anew and to whose identifier the new value has been set,

said event memory unit comprises;

storage means for storing the event outputted from said circuit operation calculation unit, but with the identifier being removed therefrom; and

means for deciding whether or not an event having an event time equal to the current time is present in said event memory unit,

said current time outputting unit comprises means for updating the current time successively within a range in which an event having an event time equal to the current time is not present in said event memory unit and the current time does not exceed values stored in said minimum event time memory unit, when it is decided by said event memory unit that an event having the event time equal to the current time is not present in said event memory unit and when it is decided by said special color presence deciding unit that an event, whose identifier has a set value equal to the special color, is not present in both said event take-out unit and said circuit operation calculation unit,

said coloring unit comprises means for changing a value of an identifier to be assigned to a taken-out event which has been taken out from said event memory unit when the updating of the current time has been completed, and

said minimum time memory unit comprises means for reinitializing the stored minimum value of event times of the events when the updating of the current time has been completed,

said units (a)-(h) comprising hardware independent of one another and being operable in parallel with one another.

8. A logic simulation apparatus of a parallel processing type for calculating an operation of a logic circuit to be simulated by using an algorithm of an event driven type, wherein a value calculated as a current simulation time, denominated as current time, is used, and a change of a signal state occurring at an input terminal and an output terminal of an element included in said logic circuit is represented by data denominated as events, said events including

a value, denominated an event time, representing a time when the change of the signal state has occurred,

a value representing to what state the signal state has changed, and

a value representing the input terminal or the output terminal of the element where the signal state has changed, and

in which algorithm,

an event having an event time equal to the current time is decided to be processible,

the signal state of the output terminal of the element is calculated anew only with respect to the element which is represented by the processible event and the signal state of whose input terminal has changed, and

only when the signal state of the output terminal has changed is an event representing the change of the signal state of the output terminal generated anew,

said logic simulation apparatus comprising:

(a) a current time outputting unit for outputting a current time;

(b) an event memory unit for storing unprocessed events;

(c) a first event take-out unit for taking out form said event memory unit an event having an event tim equal to the current time and erasing from said event memory unit the taken-out event;

(d) a second event take-out unit wherein, when said first take-out unit does not take out an event from said event memory unit, unprocessed events representing the change of the signal state of input terminals of the elements respectively are processed independently of one another among the elements, and when the unprocessed events representing the change of the signal state of the input terminals are present at all the input terminals of the elements, said second event take-out unit takes out an event having a minimum event time among the unprocessed events and erases the events which have been stored;

(e) a minimum event time memory unit for storing a minimum value of events times of the events which have been taken out from said event memory unit by said first event take-out unit or said second event take-out unit;

(f) a coloring unit for assigning one of a plurality of identifiers, which classify the events into a plurality of groups, to a taken-out event which has been taken out from said event memory unit by said first event take-out unit or said second event take-out unit;

(g) a circuit operation calculation unit for inputting an event, to which one of the identifiers has been assigned, as input data, calculating a change of a signal state of the logic circuit to be simulated by using the algorithm of the event driven type, setting, to an identifier of an event representing a result of the calculation, a value which is the same as the set value of the identifier or an event used as input data to calculate the event representing the result of the calculation, and outputting, as a new unprocessed event, the resultant event representing the result of the calculation;

(h) a special color designation unit for selecting one value from among plural values, which can be assumed by the identifiers assigned to the events by said coloring unit, and outputting the selected one value as a special color;

(i) a special color presence deciding unit for deciding whether or not an event having an identifier, whose value is equal to the value of the special color, is present said first and second event take-out units and said circuit operation calculation unit;

wherein,

said event memory unit comprises;

storage means for storing the event outputted from said circuit operation calculating unit, but with the identifier being removed therefrom; and

means for deciding whether or not an event having an event time equal to the current time is present in said event memory unit,

said current time outputting unit comprises means for updating the current time successively within a range in which an event having an event time equal to the current time is not present in said event memory unit and the current time does not exceed values stored in said minimum event time memory unit, when it is decided by said event memory unit that an event having the event time equal to the current time is not present in said event memory unit, and when it is decided by said special color presence deciding unit that an event, whose identifier has a set value equal to the special color, is not present in said first and second event take-out units and said circuit operation calculation unit,

said coloring unit comprises means for changing a value of an identifier to be assigned to a taken-out event, which has been taken out from said event memory unit, at the time when said second event take-out unit starts to take out an event from said event memory unit,

said special color designating unit comprises means for changing a value, which is outputted as one of plural values assumable by an identifier to be assigned to an event by said coloring unit, at the time when said second event take-out unit starts to take out an event from said event memory unit, to a value, which has been set to an event taken out from a said event memory unit by said coloring unit until immediately before the time when said second event take-out unit starts to take out an event from said event memory unit, and

said minimum time memory unit comprises means for reinitializing the stored minimum value of event times of the events when the updating of the current time has been completed,

said unit comprising hardware independent of one another and being operable in parallel with one another.