Apparatus and method for checkpointing simulation data in a simulator

This application is a Continuation of application Ser. No. 07/530,716, filed May 29, 1990 now abandoned.

This invention relates generally to logic simulators and more particularly to apparatus and method for storing and retrieving signal values in a logic simulator.

Logic simulators have been used by designers to test the integrity of design without actually building the hardware. The logic simulator simulates the functions performed by the circuit and provides the designer an opportunity to examine the signals generated by the design. From these signals, the designer may uncover errors in the design.

In the event that a design error is found, the logic simulator allows the designer to modify the design and rerun the logic simulation, thereby decreasing the edit-debug cycle time and greatly reducing the overall circuit design time. Therefore, designers have come to rely on logic simulators as an essential design tool.

During the course of a logic simulation, certain signal values, such as those signals generated by the design, are stored for examination at the end of the simulation run. The availability of these signal values enable the user to determine whether errors have been uncovered by the simulation run. However, for simulations of more complex circuits that may run for hours or days, the number of signals that can be stored is greatly limited by the amount of available memory. Therefore, although the designer would like to examine most of the signal values to more accurately and expediently determine the errors, it may not be possible to specify all desirable signals. Consequently, the designer may be required to run a simulation multiple times to obtain all necessary information to diagnose the logic design error.

Once the designer has determined the problem and modified the design to eliminate the uncovered error, more simulation runs are required to ascertain the correctness of the correction and of the remainder of the design. It is likely more errors will be uncovered and corrected, and more simulations are run to further determine the accuracy of the design.

It is obvious from the foregoing that although logic simulators are invaluable design aides, they are not without problems. For example, they do not provide a designer access to all signal values for the duration of simulation time due to the large number of signals and the unavailability of memory. Certainly, to add memory capacity large enough for all the signal values would be impractical and expensive.

Additionally, logic simulators require an entire simulation to be rerun after the design has been modified to determine the correctness of the fix. To rerun an entire simulation may require days and weeks. Both aforementioned problems add considerably to the edit-debug time a designer must spend to ensure the correctness of the design.

The present invention is directed to overcoming one or more of the problems as set forth above.

In accordance with the present invention, apparatus and method for checkpointing signal and memory values in logic simulations are provided which substantially eliminate or reduce disadvantages and problems associated with prior logic simulators.

In one aspect of the present invention, apparatus for storing all simulation signal values generated by a simulator during a simulation run is provided. The apparatus includes a runtime array for storing a plurality of signal values for each time instance in a predetermined time period, and a checkpoint cache for selectively storing the plurality of signal values stored in the runtime array at selected time instances.

In another aspect of the present invention, a hyper-checkpoint array is further provided to checkpoint the signal values in the checkpoint cache. In addition, the time instances and values of memory writes are also checkpointed.

In yet another aspect of the present invention, a user may retrieve the value of any signal value generated during the simulation run and may additionally rewind the simulator to a user-specified time in the simulation run.

An important technical advantage of the present invention is to make available all signal values generated in a simulation run, regardless of the length and complexity of the simulation.

Another important technical advantage of the present invention provides for rewinding the state of the simulator to a prior state so that the starting point of a simulation run may be set arbitrarily.

For a better understanding of the present invention, reference may be made to the accompanying drawings, in which:

FIG. 1 is a diagram illustrating the data structures for storing the simulation register signal values;

FIG. 2 is a flowchart of the register value checkpoint algorithm;

FIG. 3 is a diagram illustrating the data structures for storing the simulation memory values;

FIG. 4 is a flowchart of the memory value checkpoint algorithm;

FIG. 5 is a flowchart illustrating how a checkpointed register value may be retrieved in the present invention;

FIG. 6 is a flowchart illustrating how to write to a memory location;

FIG. 7 is a flowchart illustrating how to read a checkpointed memory value; and

FIG. 8 is a flowchart illustrating how the simulator may be rewound back to a predetermined time using the present invention.

Referring to FIG. 1 , a first data structure 10 , preferably implemented by an array or a list, for storing signal values during a logic simulation run is shown. In particular, a predetermined number of register signal values are stored in data structure 10 , also known as the runtime array.

A user definable time parameter indicates the time interval encompassed by the runtime array 10 , which acts like a circular buffer and only maintains the latest predetermined number of signal values. The exemplary runtime array 10 is shown encompassing 200 (0 to 199) clock cycles of the simulation clock, which actually represent clock cycle time 42,800 to 42,999. For each clock cycle, (n+1) signal values may be stored in runtime array 10 . n may also be defined by the user.

A second data structure 12 , also referred to as the checkpoint cache, is for storing or checkpointing selected signal values at a user definable checkpoint time interval. Checkpoint cache 12 may be viewed as an archive of selected signal values at predetermined clock cycles (checkpoints). The exemplary checkpoint cache 12 shown in FIG. 1 stores (n+1) signal values into a checkpoint for every 100 clock cycles, where 20 such checkpoints are grouped into a checkpoint group 14 a - c . Therefore, the first checkpoint group 14 a in checkpoint cache 12 contains clock cycle time 42,000 and the signal values for clock cycle time 42,000 through 43,900 at 100 clock cycle increments, the second checkpoint group 14 b contains clock cycle time 40,000 and the signal values for clock cycle time 40,000 through 41,900, etc.

Checkpoint cache 12 also functions like a circular buffer where the least used or oldest signal values are purged to accommodate the latest generated signal values. For example, checkpoint cache 12 shown in FIG. 1 contains 100 clock cycle intervals, and signal values for clock cycle time prior to 4,000 are not available. Implemented in this fashion, checkpoint cache 12 will always contain the latest 20 groups of checkpointed signal values.

A third data structure 16 is used to further checkpoint the checkpointed signal values of checkpoint cache 12 . Third data structure 16 , also known as hyper-checkpoint array, contains the signal values at 2,000 clock cycle hyper-checkpoint intervals and includes signal values from the beginning of the simulation run. Exemplary hyper checkpoint array 16 contains a first and latest entry of clock cycle time 42,000 and its respective (n+1) signal values, and subsequent entries of signal values at every 2,000 clock cycle decrements until time zero.

From the foregoing discussion, it may be seen that the present invention has two underlying principles. First, all signal values at time X may be derived from the values of the same signals at a time Y prior to time X. Since not all signal values for all time instances are stored, the signal values for a time Y closest to time X is retrieved and the signal values at time X may be obtained by simulating from time Y to time X. Therefore, if the desired signal values at time X are not present in runtime array 10 , checkpoint cache 12 and hyper-checkpoint array 16 are searched to determine Y and its respective signal values.

Second, similar to a computer cache memory, there is more likelihood that the desired signal values at time X will be one of the latest signal values currently stored in runtime array 10 . Therefore, even if the simulator is required to rerun 100 cycles (if time Y is found in checkpoint cache 12 ) or 2,000 clock cycles (if time Y is found in hyper-checkpoint array 16 ), considerably little time will be spent regenerating the signal values at time X. To avoid thrashing, it is preferable that runtime array 10 encompasses at least two checkpoint time instances and that the maximum number of checkpoint groups in checkpoint cache 12 is at least 10.

Referring to FIG. 2 , the process of checkpointing the signal values are shown. In particular, flowchart 20 illustrates how register signal values are checkpointed. In block 22 , the register signal values at time X are stored in runtime array 10 . Time X is then checked in decision block 24 to determine whether it is one of the predetermined checkpoint times, such as clock cycle time 100 , 200 , 300 , . . . 1000 , 1100 , etc. if the checkpoint time interval is defined as 100, for example. As described above, the checkpoint time interval may be set by the user or a default value may be used.

If time X is one of the predetermined checkpoint times, then determine the checkpoint group for the checkpoint, block 25 A. If the checkpoint group already exists, just add the checkpoint to the group, block 25 B. If the checkpoint group does not exist, execution proceeds to decision block 26 where the number of checkpoint groups currently in checkpoint cache 12 is compared with a predetermined maximum number. In the example shown in FIG. 1 , the predetermined maximum number of checkpoint groups is 20. If it is determined that the number of checkpoint groups is equal to the predetermined maximum, then execution proceeds to block 28 .

The procedure beginning in block 28 performs the function of purging the last checkpoint group in checkpoint cache 12 and adding the current signal values at time X to a new checkpoint group in checkpoint cache 12 . In block 28 the last checkpoint group is deleted. In the preferred embodiment of the instant invention, the checkpoint groups in checkpoint cache 12 are chronologically arranged, where the most recently used checkpoint group occupies the first location in the array and the least recently used checkpoint group occupies the last location in the array. Therefore, the least used checkpoint may be readily located and deleted. Subsequently in block 30 , a new checkpoint group is created. Additionally, a new entry is created for hyper-checkpoint array 16 in block 32 , as the signal values for the first time instance in a checkpoint group is also hyper-checkpointed. The signal values are then stored in the newly created hyper-checkpoint entry, as shown in block 34 , and are also stored in the newly created checkpoint group in checkpoint cache 12 , as shown in block 36 .

If, in decision block 26 , it was determined that the number of checkpoint groups is not yet equal to the predetermined maximum, then the signal values are simply stored in a new checkpoint group in checkpoint cache 12 , as shown in block 30 and a new hyper-checkpoint array entry is created in 32 . The register value checkpoint procedure is repeatedly executed until the end of the simulation run, at which time it terminates in block 38 .

In addition to storing or checkpointing register signal values, the values written into memory during a logic simulation must also be checkpointed for later examination. Shown in FIG. 3 is a diagram illustrating the memory checkpointing portion of the present invention, which consists of a change management list 40 . Change management list 40 includes a plurality of memory checkpoint groups 42 a - b , each containing one or more time-address pairs 44 a - d . Each memory checkpoint group 42 a - b stores all writes to memory within a particular hyper-checkpoint interval. Time-address pairs 44 a - d indicate the time instances at which writes were performed and their respective physical memory addresses.

Change management list 40 is also arranged chronologically with the latest checkpoint group at the beginning of the list and the oldest at the end. Similarly, time-address pairs 44 a - c within checkpoint group 42 a are also arranged so that time-address pair 44 a having the latest time instance is positioned at the beginning of group 42 a.

Each time-address pair 44 a - d is associated with entries in a memory array 46 . Memory array 46 includes a plurality of entries, where each entry represents one address location and contains a memory value list 48 of checkpoint groups 50 a - c . Each checkpoint group 50 a - c in memory value list 48 in turn includes one or more time-value pairs 52 a - d . Time-value pairs 52 a - d correspond to time-address pairs 44 a - d in change management list 40 . In particular, time-value pairs 52 a - d include, additionally, the values stored in memory at addresses contained in corresponding time-address pairs 44 a - d . Configured in this manner, memory array 46 may be indexed by a memory address to retrieve the value stored at that memory address at a particular time instance.

Change management list 40 and memory array 46 not only serve as the data structures for checkpointing memory values, but also as hyper-checkpointing data structures. Recall that in register value checkpointing described in FIGS. 1 and 2 , only the latest used 20 checkpoint groups 14 a - c are maintained and earlier checkpoint groups are deleted. In memory checkpointing, only the checkpoint groups that correspond to the cache checkpoint groups of the register checkpointing contain all records of memory writes during each respective checkpoint interval. The rest of the checkpoint groups are truncated to contain only the first memory write instance in each respective checkpoint interval. Implemented in this manner, the amount of memory required to store change management list 40 and memory array 46 is reduced considerably and yet still maintain enough information to regenerate the unrecorded checkpoints if necessary.

In operation, if it is desirable to retrieve or read the value stored at a memory address location Y at time X, a check is done to see if the simulator has run up to time X or if time X has been “hyper-checkpointed,” i.e. the checkpoint cache group that X belongs to has been deleted to make room for other groups. If either case is true, the simulator is run forward to time X. Next, memory array 46 at address Y is scanned for the checkpoint group entry. Once the group is retrieved, the time-value pairs are searched for an entry having a time of X or immediately prior to X. Because time-value pairs 52 a - b within a checkpoint group 50 a are arranged from the latest to the earliest in time, the search is easily accomplished.

Referring to FIG. 4 , the process by which the data structures change management list 40 , memory array 46 and memory value list 48 are constructed is shown. Memory checkpointing, beginning in block 54 , begins by capturing the value of memory address Y at time X during simulation, as shown in block 56 . In decision block 58 , it is determined whether X belongs in an existing checkpoint group. This determination is made by comparing X to predetermined checkpoint time intervals. For example, if predetermined checkpoint time instances are every 2,000 clock cycles, and existing checkpoint groups start at time instances such as 0, 2000, 4000, . . . , 30000, 32000, and 34000, then if X is equal to 31023, it belongs to the checkpoint group starting at time instance 30000 . On the other hand, if X is equal to 36450, then it belongs in checkpoint group for the time interval (36000-38000), which is not yet in existence. If this is the case, execution proceeds to block 60 .

In block 60 , the number of checkpoint groups 42 a - b in change management list 40 is compared with a predetermined maximum which is the same as the number of cache groups in register checkpointing. If the number of checkpoint groups 42 a - b is equal to the maximum, then all time-address pairs in the oldest used checkpoint group in change management list 40 are deleted except for the latest pair at each address. The corresponding time-value pairs in memory array 46 of deleted time-address pairs are also deleted, so that a one-to-one correspondence between change management list 40 and memory array 46 is maintained. Subsequently in block 64 , new checkpoint groups are created at the front of change management list 40 and memory value lists 48 . If, in decision block 60 , it is determined that the number of memory checkpoint groups does not yet equal the predetermined maximum, then execution simply proceeds to block 64 , where new checkpoint groups are created to accommodate the new checkpoint.

Proceeding to block 66 , the memory value of memory address Y at time X captured in block 56 is added as a time-address pair (X,Y) to the first checkpoint group in change management list 40 . In addition, a time-value pair (X,VALUE) is added to the front of corresponding memory value list 48 as indexed by address Y in memory array 46 , as shown in block 68 . The memory checkpointing algorithm is repeatedly executed until the end of simulation, at which time it terminates in block 70 .

A logic simulator must serve several functions. It captures a logic design to simulate an actual working design; it captures and stores signal values generated during the simulation run; and it provides the captured signals so that a logic designer may derive therefrom whether the design functioned properly or failed in some respect. A typical design generates three types of signals: register, memory and combinational. The present invention provides the means for checkpointing the register and memory signal values, as described above, so that every signal generated during simulation is available for examination. The preferred embodiment of the present invention only checkpoint register and memory signals since combinational signal values may be easily derived from register and/or memory signal values.

Referring to FIG. 5 , the process 72 by which the value of a register A generated at time X may be retrieved for examination after a simulation run is shown. The particular register value and time X may be specified by a user. The method of specifying these values may encompass any implementation, such as selecting the desired register by name from a list of register names, etc. as known in the art. First it is determined whether time X is a valid value, i.e. a positive number, as shown in block 74 . If X is invalid, then a nil value is simply returned and execution terminates, as shown in block 76 . Otherwise, execution proceeds to block 78 where it is determined whether time X is currently encompassed in the time instances in runtime array 10 . If so, then the value of register A may simply be retrieved from runtime array 10 and returned, as shown in blocks 80 and 82 .

If X is not encompassed in runtime array 10 , then it is determined whether time X is greater than the maximum simulation time in decision block 84 . If X is not greater than the maximum simulation time, then the duration of the latest simulation run includes the specified time X, which indicates that either a checkpoint group in checkpoint cache 12 or hyper-checkpoint array may yield the desired value, as shown in block 86 . Preferably, checkpoint cache 12 is searched for a checkpoint group that encompasses time X. If not found, hyper-checkpoint array 16 is searched. It is likely that neither checkpoint cache 12 nor hyper-checkpoint array 16 contains precisely time X and its register values, unless time X is one of the checkpoint time instances, in which case the value is simply retrieved and returned. Otherwise, a time instance Z that is immediately prior to time X and in either checkpoint cache 12 or hyper-checkpoint array 16 is determined. The simulator is made to simulate forward from time Z to time X, and the value of register A is retrieved and returned, as shown in blocks 88 and 90 . If, on the other hand, time X is greater than the maximum simulation time, then the register signal values stored in checkpoint array 12 and the memory values stored in memory array 46 closest and prior to the maximum simulation time are used as a starting point to simulate forward to time X, which is the new maximum simulation time, as shown in blocks 92 and 94 . Register and memory checkpointing as described above are performed to store the additional signal values generated during this time. When time X is reached, the value of register A is retrieved from runtime array 10 and returned, as shown in block 90 .

FIG. 6 illustrates how memory values may be retrieved or read from the memory checkpointing data structures 40 and 46 . A memory address B and a time instance X of interest are specified, as shown in block 100 . In block 102 , X is compared with the maximum simulation time and it is also determined whether the signal values at time X have been checkpointed. If X is either greater than the maximum simulation time or the signal values at time X belong in a truncated checkpoint group in change management list 40 , then the memory value is probably not readily available and the maximum simulation time or the closest earlier checkpointed time is used to simulate forward to time X, as shown in block 104 . The exception would be when X happens to equal to one of the checkpointed time instances where a memory write had occurred, for which the value of memory is readily available.

Proceeding to block 106 , change management list 40 is searched for a time-address pair having a time instance equal to or immediately prior to time X, and its associated time-value pair is then located in a memory value list 48 in one entry in memory array 46 . The value is then readily retrievable and is returned. The above steps are shown in blocks 106 and 108 .

The mechanism 112 for writing a value C to an address location D at time X is provided by the present invention and shown in FIG. 7 . Time X is first compared with the maximum simulation time and it is further determined whether X belongs in one of the truncated checkpoint groups or hyper-checkpoint groups. If in decision block 114 it is determined that X is either greater than the maximum simulation time or X has been hyper-checkpointed, then the value C is returned, as shown in block 116 . Otherwise, X is further checked to determine whether it is less than zero in block 118 . If X is less than zero, then the memory is initialized to default values, as shown in block 120 , and execution returns in block 122 .

If X does not meet any of the conditions in decision blocks 114 and 118 , then time-address (X,D) and time-value (X,C) pairs are created for change management list 40 and memory array 46 , respectively. If, in block 126 , it is determined that time X belongs to an existing checkpoint group in change management list 40 , then the time-address and time-value pairs are added to the appropriate checkpoint group in change management list 40 and to the appropriate checkpoint group in the appropriate memory value list 48 , as shown in block 128 , and execution returns in block 122 .

If X does not belong in an existing checkpoint group, new checkpoint groups are created for both change management list 40 and appropriate memory value list 48 , as shown in block 130 . The time-address and time-value pairs are then added to the newly created checkpoint groups, as shown in block 132 . In block 134 , the number of checkpoint groups are compared with the predetermined maximum, and if it is greater, then the oldest checkpoint group in change management list 40 is purged of all except the latest time-address pair, as shown in block 136 . Additionally, the corresponding time-value pairs of the deleted time-address pairs are also purged from memory array 46 . Execution subsequently terminates in block 122 .

Generally, logic designers go through edit-debug cycles in which a simulation is run, errors are detected, a correction is made, and the simulation is rerun until the design is satisfactorily error-free. It is common for each simulation run to require days or weeks to complete, and it is also likely that the errors occur near the end of the simulation run. After determining the source of the error and applying a fix, an entire simulation has to be rerun to check the correctness of the fix, which may also be near the end of the run. Thus, time is wasted in rerunning the portion of the simulation which precedes the error. The present invention provides for a mechanism which restores the simulator to a prior state. In doing so, the simulator may be restored to a state just prior to the crucial point of the simulation, and simulation runs may begin therefrom. Implemented in this manner, the edit-debug cycle time is greatly reduced by eliminating the need to run the entire simulation.

Referring to FIG. 8 , the simulator rewind mechanism 140 which restores the state of the simulator to a prior state as specified by time X is shown. In block 142 , hyper-checkpoint array 16 is traversed and those entries having time instances greater than the hyper-checkpoint time interval encompassing time X are deleted. Checkpoint cache 12 is also searched and those checkpoint groups having time instances greater than the hyper-checkpoint time interval encompassing time X are also deleted. If X is in a particular checkpoint group in checkpoint cache 12 , as determined in decision block 146 , then those entries in the particular checkpoint group having time instances greater than time X are also deleted, as shown in block 148 .

Additionally, change management list 40 is also traversed and those checkpoint groups having time instances greater than time X are deleted, as shown in block 150 . Those time-address and time-value pairs in change management list 40 and memory value lists that have time instances greater than time X are further deleted, as shown in block 152 . Implemented in this manner, the register and memory checkpoint data structures contain only those signal values generated at times prior to time X. In block 154 , the maximum simulation time is set to X to reflect the purged data structures. Execution terminates in block 156 .

Having rewound the state of the simulator as described above, the user may simply indicate a new maximum simulation time and simulation may run forward from time X.

Although the present invention, as presented herein, is built upon a register transfer level (RTL) simulator, the present invention may be equally applicable to other simulators, such as gate level and transistor level simulators. In particular, the present invention is applicable to those situations where a large number of values are generated and stored following some prescribed and orderly fashion. By storing or checkpointing selected signal values as described herein, the amount of memory required to accommodate the signal values is greatly decreased.

Although the present invention has been described in detail, it should be understood that various changes, substitutions and alterations may be made thereto without departing from the spirit and scope of the invention as defined by the appended claims.