Abstract:
The invention is directed to a method and apparatus for simulating a digital logic circuit simulator. In particular, a block object, representing a component of the digital logic circuit, is instantiated. An event object having a queue is also instantiated. The queue holds an ordered list of destinations, which are representative of the block objects that the event object initiates an action with. When the event object interacts with the block object, this initiates behavior in the block object indicative of behavior of the component in the digital system. The digital logic circuit simulator components, namely the block object and the event object, can be instantiated in a run-time object oriented language, such as the JAVA® language promulgated by Sun Microsystems. The block object can initiate a dynamic addition to the destination queue. Additionally the destination can be another event object. When the destination is another event object, another event object is initiated. The new event object may be dynamically created within the instructions of adding to the destination queue, and may based upon test for the existence of a particular condition. The event object can alter a condition of the block object, and vice versa. As such, a system and method for simulating event behavior in a complex digital system is envisioned. Other objects, advantages and novel features of the present invention will be apparent to those skilled in the art from the following detailed description of the invention, the appended claims, and in conjunction with the accompanying drawings.

Description:
FIELD OF THE INVENTION  
         [0001]    This invention relates to simulation and design of digital circuitry. More particularly, it relates to a system and method of simulating digital systems in a software environment.  
         DESCRIPTION OF THE PRIOR ART  
         [0002]    Digital circuitries typically exhibit more degrees of complex behavior as the complexity of the system grows. All the same, timing considerations, event flow, and system resource allocation in this arena all are important considerations.  
           [0003]    Current microprocessors contain vast numbers of more highly defined logical, or block level, systems. On a less macroscopic level, these complex systems contain hundreds of millions of elements making up these block level components. These block and smaller level systems are all responsive to events. Many different types of events are serviced, and generated by these components.  
           [0004]    For example, a floating point unit may pipeline many macro level instructions. In this sense, the instructions may be serviced with different timing considerations, based on the state of the machine, and the type of request.  
           [0005]    The same floating point unit may also contain different queues within itself, each queue responsible for the performance of one low level operation. These different queues may be all interlinked to perform the higher order instruction, but the output of the queues may be dependent upon different things, including the availability of system resources, the result of another queue, or if the larger component had to respond to some external request.  
           [0006]    The functionality of the unit, as a queue may be altered during runtime in light of some pre-engineered behavior. Additional individual sub-components exhibiting queue-like behavior may also be similarly altered. This behavior can include such designs as “look-ahead” type instruction behavior, prefetch behavior, or the like.  
           [0007]    System resources can impact seriously on the queue behaviors as well. For example, a multilevel cache may be present. In this case, the queue behavior is dependent on the contents of the different order caches, and whether the data needs to be pulled in from slower but more persistent data storage systems.  
           [0008]    In the case of many processors, these behaviors are duplicated many times. This is due to the sheer number of logical components that the typical microprocessor must use or employ. However, many computer systems use multiple processor systems. Thus, the interaction between the processors themselves leads to many event processing scenarios just to take into account the interactions between the processors. This is above and beyond the requirements for the processors themselves.  
           [0009]    Additionally, many systems have many multi-processor boards coupled through multiple interconnecting busses in various configurations. In this manner, the interactions grow even larger. Especially so in the event that each processor may maintain a cache, or several caches. When other processors attempt to access data, the data may be in another cache under the control of a different processor, and subject to varying levels of control. In this manner, the interactive requests between the processors regarding data control and coherency involve increasingly complex behavior.  
           [0010]    Accordingly, the simulators that model these highly complex systems are themselves highly complex. As can be seen, the numbers of components, interactions, external events, and internal events is quite high.  
         SUMMARY OF THE INVENTION  
         [0011]    The invention is directed to a method and apparatus for simulating a digital logic circuit simulator. In particular, a block object, representing a component of the digital logic circuit, is instantiated. An event object having a queue is also instantiated. The queue holds an ordered list of destinations, which are representative of the block objects that the event object initiates an action with. When the event object interacts with the block object, this initiates behavior in the block object indicative of behavior of the component in the digital system. The digital logic circuit simulator components, namely the block object and the event object, can be instantiated in a run-time object oriented language, such as the JAVA® language promulgated by Sun Microsystems. The block object can initiate a dynamic addition to the destination queue. Additionally the destination can be another event object. When the destination is another event object, another event object is initiated. The new event object may be dynamically created within the instructions of adding to the destination queue, and may based upon test for the existence of a particular condition. The event object can alter a condition of the block object, and vice versa. As such, a system and method for simulating event behavior in a complex digital system is envisioned. Other objects, advantages and novel features of the present invention will be apparent to those skilled in the art from the following detailed description of the invention, the appended claims, and in conjunction with the accompanying drawings.  
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0012]    The accompanying drawings, which are incorporated into and constitute a part of this specification, illustrate one or more embodiments of the present invention and, together with the detailed description, serve to explain the principles and implementations of the invention.  
         [0013]    In the drawings:  
         [0014]    [0014]FIG. 1 is a block diagram of a computing device operating a digital logic simulator according to the invention.  
         [0015]    FIGS.  2 - 4  depict an embodiment of the simulator of FIG. 1. In this case, the simulator initiates the event objects  202  and  204 .  
         [0016]    [0016]FIGS. 5 and 6 are block object oriented diagrams detailing the timing characteristics of various block diagrams.  
         [0017]    [0017]FIG. 7 is a block diagram detailing the interactions that event objects, block objects, and system wide values may have on one another.  
         [0018]    FIGS.  8 - 10  are a block level diagram of another embodiment of the system of FIG. 1.  
         [0019]    [0019]FIGS. 11 through 15 are block diagrams indicating another aspect of the invention of FIG. 1.  
         [0020]    [0020]FIG. 15 is an exemplary implementation of a high level simulation of a multi processor, multi-bus system that can be simulated with the present invention.  
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT  
       [0021]    Embodiments of the present invention are described herein in the context of a SYSTEM AND METHOD FOR MODELING DIGITAL SYSTEMS HAVING QUEUE-LIKE OPERATING CHARACTERISTICS. Those of ordinary skill in the art will realize that the following detailed description of the present invention is illustrative only and is not intended to be in any way limiting. Other embodiments of the present invention will readily suggest themselves to such skilled persons having the benefit of this disclosure. Reference will now be made in detail to implementations of the present invention as illustrated in the accompanying drawings. The same reference indicators will be used throughout the drawings and the following detailed description to refer to the same or like parts.  
         [0022]    In the interest of clarity, not all of the routine features of the implementations described herein are shown and described. It will, of course, be appreciated that in the development of any such actual implementation, numerous implementation-specific decisions must be made in order to achieve the developer&#39;s specific goals, such as compliance with application- and business-related constraints, and that these specific goals will vary from one implementation to another and from one developer to another. Moreover, it will be appreciated that such a development effort might be complex and time-consuming, but would nevertheless be a routine undertaking of engineering for those of ordinary skill in the art having the benefit of this disclosure.  
         [0023]    In accordance with the present invention, the components, process steps, and/or data structures may be implemented using various types of operating systems, computing platforms, computer programs, and/or general purpose machines. In addition, those of ordinary skill in the art will recognize that devices of a less general purpose nature, such as hardwired devices, field programmable gate arrays (FPGAs), application specific integrated circuits (ASICs), or the like, may also be used without departing from the scope and spirit of the inventive concepts disclosed herein.} 
         [0024]    [0024]FIG. 1 is a block diagram of a computing device operating a digital logic simulator according to the invention. In particular, the computing device  100  contains a software based digital logic simulator  102 . The digital logic simulator  102  incorporates an event object  104 , and the block objects  106  and  108 .  
         [0025]    The block objects are modules that model components of the digital system. For example the block object  106  may represent a bus, a core, a queue, an external interrupt mechanism, or any user defined component or activity of the digital system. The block object can contain internal logic activity. In this manner, the block object can alter system variables or parameters, initiate events, alter the settings of other block objects, to name just a few. The block object may be defined with delays. In this manner, the characteristics of low level or high level components can be simulated.  
         [0026]    The event object  104  is a software module that is dynamically interactive with the block objects depicted. In this manner the event object may “spark” any functionality of the associated block object. In this manner, a digital system can be modeled.  
         [0027]    In particular the event object  102  contains a queue. This queue contains an indication of the specific blocks that it is to interact with. As pictured, the event object  102  is targeted to interact with the block object A first, then the block object b. Thus, the interaction of the block objects with the event simulates the full digital system.  
         [0028]    FIGS.  2 - 4  depict an embodiment of the simulator of FIG. 1. In this case, the simulator initiates the event objects  202  and  204 . The event object  202  contains in its block queue an indication to interact with a block object  206  and a block object  208 , respectively. Correspondingly, the event object  204  contains in its block queue an indication to interact with a block object  208  and a block object  210 , respectively. At the initiation of the simulation, the block objects  206 ,  208 , and  210  are initialized. Thus, the block object  206  contains an indication that the event object  202  is being responded to, and the block object  208  contains an indication that the event object  204  is being responded to.  
         [0029]    In FIG. 3, the block object  206  has performed the logical operation required, and all delays associated with the block object  206  have been met. The event object  202  has been released from the consideration of the next operation step to the block object  206 . Additionally, the event object  202  has indicated itself that the block object  206  is not relevant to its continued journey. The event object  202  then determines that the next relevant interaction that it has is with the block object  208 .  
         [0030]    However, the event object  204  has not finished it interaction with the block object  208 . Thus, the block object  208  is altered to show that the next action it responds to is the event object  202 .  
         [0031]    In FIG. 4, the block object  208  has finished its interaction with the event object  204 . In the same manner as described above, the event object  204  is released from consideration by the block object  208 , and correspondingly, the event object  204  is altered to indicate that it need not interact with the block object  208 . In this manner, the block object  208  will initiate actions in response to the event object  202 , and the block object  210  will initiate action with the event object  204  at the next clock cycle.  
         [0032]    [0032]FIG. 5 is a block object oriented diagrams detailing the timing characteristics of various block diagrams. In this case, assume that 5 different block objects are present. Specifically, a block object V, a block object W, a block object X, a block object Y, and a block object Z have been defined in the system.  
         [0033]    The block object Y has been defined as having a process time of 2 cycles, a release delay of 1 cycle, and a delay of 1 cycle in responding to any new request. Of course, many other characteristics of the component may be defined. The block object W has been defined as having a process time of 1 cycles, no release delay, and a delay of 1 cycle in responding to any new request. The block object X has been defined as having a process time of 2 cycles, no release delay, and a delay of 1 cycle in responding to any new request. The block object Y has been defined as having a process time of 1 cycles, a release delay of 1 cycle, no delay in responding to any new request. The block object Z has been defined as having a process time of 2 cycles, no release delay, and no delay in responding to any new request. Each block has multiple events defined to be processed, and the initial events are all assumed to have the start of the event at the same time for purposes of this diagram.  
                                                                 TABLE A                                   Object V   Object W   Object X   Object Y   Object Z                                    Cycle 1   V0   W1   X0   Y0   Z0           (PR = 1)   (NE = 1)   (PR = 1)   (RD = 1)   (PR = 1)       Cycle 2   V0   W1   X1   Y1   Z1           (RD = 1)   (PR = 1)   (NE = 1)   (PR = 1)   (PR = 2)       Cycle 3   V1   W2   X1   Y1   Z1           (NE = 1)   (NE = 1)   (PR = 2)   (RD = 1)   (PR = 1)       Cycle 4   V1   W2   X1   Y2   Z2           (PR = 2)   (PR = 1)   (PR = 1)   (PR = 1)   (PR = 2)       Cycle 5   V1       X2   Y2   Z2           (PR = 1)       (NE = 1)   (RD = 1)   (PR = 1)       Cycle 6   V1       X2           (RD = 1)       (PR = 2)       Cycle 7   V2       X2           (NE = 1)       (PR = 1)                  
 
         [0034]    Table A, above, shows the timing characteristics of the system of block objects processing the respective event objects as described in FIG. 5. In this table, PR=Processing, RD=Release Delay, NE=New Event Delay. At the first cycle, the block object V processes the event. However, at time 2 the block V cannot release the event due to the presence of a release delay. On the third cycle, the block object V releases its first event, and prepares the new event to be processed.  
         [0035]    However, the block object V has another response delay of one cycle, in which time the new event simply waits the proper delay to be serviced. On the fourth and fifth cycles, the second event present in the block object V is serviced. On the sixth cycle, the event has been serviced, but like the first event, must wait to be released.  
         [0036]    The block object W has a different operational characteristic, based on different delay characteristics. On the first cycle, the first event in the block object W is processed, and since there is no release delay, the first event serviced by the block object W is released. The second event processed by the block object W is set to await the interaction with the block object W. However, the block object W has a delay before it can service the second event. On the second cycle, the second event for the block object W is serviced. Succeeding new event objects are serviced in this manner based on the characteristics of the block object.  
         [0037]    The block object X, the block object Y, and the block object Z, are all diagrammed in a similar manner. The block objects X, Y, and Z each show different timing interactions based on characteristics defined at the block.  
         [0038]    Of course other timing characteristics may be defined, based on the specific component. Some components may allow for immediate interrupts and rescheduling. Other components may allow for interrupts, but may only service such interrupts in predefined windows. As such, many different schemes for component characteristics may be envisioned.  
         [0039]    [0039]FIG. 6 is a block diagram detailing the interactions that event objects, block objects, and system wide values may have on one another. In this case an event object  602  is specified to interact with the block objects  604 ,  606 , and  608 , in order. In this case, assume that a particular variable in the event object  602  has a value of 2, and a state variable has a value of 11. In the first interaction, that with the block object  604 , the block object alters the data associated with the event object  602  in some fashion. In particular, the block object increments the data field by 1. When the block object  604  releases the event object, the data field should reflect the change associated with the interaction.  
         [0040]    Next, the event block will interact with the block object  606 . In this case, the associated logic affects a state variable. In other cases, interactions can affect data associated with the block object, rather than the event object or state variable. Or, logical tests may be performed on inherent data, state variables, types of interactions, types of block objects, or types of event objects, such as that depicted with the block object  608 . Of course, the functionality could reside either in the event object or block object, or some combination.  
         [0041]    In particular, the event object may be predefined with a specific destination order. In this case, the event object would be instantiated, and the specific destinations would be added to the queue. Thus, the particular event path could be completely defined prior to the execution of the event. Or, the interactions can be used to dynamically vary the path.  
         [0042]    [0042]FIGS. 7 through 9 are a block level diagrams of another embodiment of the system of FIG. 1. The event object  702  is a specific list of destinations. In particular, the destinations could be indicative of a specific path that the event should take through the particular digital system. The destinations could include units for prefetching data, instruction pipeline, and cache determination units, to name but a few. Assume that the destination of the block object  704  is, in actuality, some type of branching block. For example, the block object  704  may be indicative of a component that sends instructions to one of several parallel functional units. In this case, the block object  704  could insert alternative destinations into the event object  702 . In this case assume that the algorithm calls for straight alternate branching.  
         [0043]    In processing the event object  702 , the block object  704  then directs the event object  702  to the first branch block object  706 . This is accomplished by inserting a new destination in the event object queue. This is diagrammed in FIG. 9.  
         [0044]    The event object  702  then goes to the appropriate block object. In this case, the block object can dynamically alter the destination of the event. In this manner, the dynamic nature of the component can be translated into the simulation without a great deal of recoding. As such, the events may be modeled as accurately in the dynamic propagation as possible or necessary. In this manner, highly complex behavior in the system can be obtained without the same complexity as normal.  
         [0045]    Continuing with the example, the next event object, specifically another event object  710 , is then redirected to the other parallel unit. This is diagramed in FIG. 9. One should note that the specific logical redirection might be obtained for any digital behavior. For example, the redirection is not necessarily obtained through simple algorithms, but highly complex look-ahead and prefetch behavior can be modeled through this dynamic redirection.  
         [0046]    Additionally, the redirection need not be additive in nature. This means destinations may be selectively or dynamically removed. Assume that an event is specified by the queue to have a certain action taken. Assume that the action is comparable to the instruction awaiting data from a slow memory, and after the appropriate information has been sent to the cache and, in parallel, to the main memory or readable medium for a prefetch. If the cache returns a hit, which could be modeled as the arrival of another event, or the change of a variable, the event may be flushed from the current block object. Or, other contingent block objects representing a predicted behavior can be remodeled. In this manner, highly complex interactions between components and events may be modeled on the most complex scales.  
         [0047]    [0047]FIGS. 10 through 14 are block diagrams indicating another aspect of the invention of FIG. 1. In this case, the destinations of the event objects need not be solely block objects. In FIG. 10, assume that the event object  1002  is propagated to the block object  1004 . The block object  1004  is indicative of the front end of a parallel component; that is, the component can send the same event to multiple destinations for a response. In operation, this is much like a cache request among a parallel microprocessor system, where each other processor needs to know of the request.  
         [0048]    Assume that the alternative paths are represented by the block objects  1006 ,  1008 , and  1010 . In this case, the path of the event object  1002  may contain, or be altered, to contain several other event objects to be sent out. Thus, before the virtual execution of the event object  1002 , the path for the event object  1002  could contain other indications of other event objects. In this case, the propagation is to be among three different paths, so two other event objects are specified in the destination queue. This is diagrammed in FIG. 12.  
         [0049]    In FIG. 12, the path of the event object  1002  has been found to have another event object. Thus the event object  1012  is initiated with a path indicative of one of the alternative paths.  
         [0050]    In FIG. 14, the next destination of the event object  1002  is yet another event object. Again, an event object  1014  is initiated with yet another path. Typically, these “spawn events” can be modeled so that no “virtual cycles” have ticked off—they are zero time events. Or, depending on the components involved, they may be modeled as positive time events.  
         [0051]    In FIG. 15, the three different events are headed to its particular block object destination. Communication between the various block objects or other events can be used to “kill” these fan-out events. Or, if necessary, specific “zero-time” block objects may be implemented to determine when some threshold regarding the fanned out events has occurred.  
         [0052]    The same fan-out behavior may be used to model a single event that initiates several other events, but not in the parallel sense. For example, such fan-out events may be the receipt of an instruction, with simultaneous events sent to both the cache and main memory. Or, assume that a certain event will cause simultaneous repercussions in several components. This may occur due to an interrupt or some other event.  
         [0053]    [0053]FIG. 16 is an exemplary implementation of a high level simulation of a multi processor, multi-bus system that can be simulated with the present invention. In particular the specific computing system may be modeled as several block objects. In the lower portion of FIG. 16, a high level implementation of a single processor is modeled. The implementation may be with the block object, with the appropriate logical connections and delays.  
         [0054]    At the next level, a board containing multiple processors can also be modeled. Additionally multiple boards may be modeled in the same way.  
         [0055]    Further, a multi-bus global address bus system (Gab) is modeled through the use of the block objects, each representing on of the buses. Further, a global data bus is modeled through the use of a block object. In this manner, the highly complex interactions of the microprocessor system can be easily simulated.  
         [0056]    The following code segment is a specific encoding of the Snoop invalidate functionality of the microprocessor depicted in FIG. 15.  
                                                                                           public Block snoopInval = new Block() {                {setString (“Snoop Invalidate”); }           public void program (InvokeEvent e) {                e.add (Queue.delay(1)); // cpu thinks           e.add (12Dir); // read           e.add(12Dir); // write                }                }                      
 
         [0057]    In this case, the event has specific delays placed into the queue, as well as specific functional specifications.  
         [0058]    The following code segments show specific testing situations that enables the specific testing sequence. Notice in the case of the second code segment, in that the system changes the timing of the sequence in the manner in which the event is added to the queue.  
                                                                                                                                               Path   =     {       q1   ,   q2   ,     q4                 if                 test                 is                 true     ,       q1   ,   q3   ,     q4                 otherwise                                                 Queue q1 = new Queue (1, “Queue One”);       Queue q2 = new Queue (1, 2, “Queue Two”);       Queue q3 = new Queue (1, 3, “Queue Three”);       Queue q4 = new Queue (2, “Queue Four”)’       public class MyBlock extends Block {                public void program (InvokeEvent e) {                e.add (q1);           if (test( )) e.add(q2);           else e.add (q3);           e.add (q4);                              Path   =     {   q1   }       ,     {         q2                 if                 test                 is                 true     ,       q3                   otherwise   .         }     ,     {   q4   }                                           Queue q1 = new Queue (1, “Queue One”);       Queue q2 = new Queue (1, 2, “Queue Two”);       Queue q3 = new Queue (1, 3, “Queue Three”);       Queue q4 = new Queue (2, “Queue Four”);       Public class MyBlock extends Block {                Public void program (InvokeEvent e) {                e.add (q1);           e.add (new Block( ) {                public void program (InvokeEvent e) {                if (test( )) e.add(q2);           else e.add(q3);                }                {);           e.add(q4);             }       }                  
 
         [0059]    The following code segment details the simulating the spawning of parallel events. This occurs in the context of a background store, where the store can take place at the same time that other events can occur that are relevant to the system being depicted.  
                                                                                           case 1;                12hit(e);           break;                default: // background store                CacheEvent store = new CacheEvent(e);           12hit (store);           e.add(store);                }                      
 
         [0060]    In particular, the event objects and the block objects as described are implemented in an object oriented environment. This environment may be monolithic in nature or each specific event object or block object may exist as independent persistent objects which interact, rather than run as part of a program. Additionally, the objects can take the form of an object implemented in a run time system, such as Java®. In this case, the execution of the object takes place automatically without specific invocation. Additionally, the single computing system depicted in FIG. 1 need not be a single system, but may take the form of several interconnected systems, each containing one or more of the objects.  
         [0061]    Of course, the specific simulation need not take place at such a highly defined level. Any particular the simulation scope can be increased or decreased to any desired level with relatively little impact on the building blocks, namely the event objects and the block objects, and their interactivity with themselves and each other.  
         [0062]    The invention may be embodied on any computing device or software that runs on a computer. It may be embodied in any combination of software or hardware, including running instructions from any computer readable medium.  
         [0063]    Thus, a method and apparatus for modeling digital systems is described and illustrated. Those skilled in the art will recognize that many modifications and variations of the present invention are possible without departing from the invention. Of course, the various features depicted in each of the Figures and the accompanying text may be combined together. Accordingly, it should be clearly understood that the present invention is not intended to be limited by the particular features specifically described and illustrated in the drawings, but the concept of the present invention is to be measured by the scope of the appended claims. It should be understood that various changes, substitutions, and alterations could be made hereto without departing from the spirit and scope of the invention as described by the appended claims that follow.