System architecture for distribution of discrete-event simulations

• US 6,278,963 B1
• Filed: 07/01/1998
• Issued: 08/21/2001
• Est. Priority Date: 07/01/1997
• Status: Expired due to Fees

• Current Assignee: Riverbed Technology Incorporated
• Original Assignee: OPNET Technologies Incorporated (Riverbed Technology Incorporated)
• Inventors: Cohen, Alain
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): Broda, Samuel
• Application Number:
  US09/108,503
• Time in Patent Office: 1,147 Days
• Field of Search: 703/4, 703/14, 703/15, 703/16, 703/17
• US Class Current: 703/17
• CPC Class Codes: G06F 30/20 Design optimisation, verification or simulation optimisation, verification or simulation of circuit designs G06F30/30

Abstract

A method, an apparatus, and a computer-readable medium for performing a discrete-event simulation employs an event list comprising events. In the event list, one event is indicated as a head event, and each event is indicated as uncomputed, pre-computed, or in-computation. An uncomputed event is selected and transferred to one of at least one event pre-computation processes, which computes a computation for the selected uncomputed event. An uncomputed head event is executed, and a pre-computed head event is verified.

Claims

1. A method for increasing the event throughput of a discrete-event simulation comprising the steps of:

maintaining an event list for the discrete-event simulation, the event list comprising a head event; and

determining whether the head event is uncomputed, in-computation, or pre-computed;

if the head event is determined to be uncomputed, executing the head event;

if the head event is determined to be in-computation, indicating the head event as pre-computed upon completion of a computation for the head event without affecting a system state of said discrete-event simulation; and

if the head event is determined to be pre-computed, further determining whether the computation of the head event is valid or invalid;

if the computation of the head event is determined to be valid, applying the computation of the head event; and

if the computation of the head event is determined to be invalid, executing the head event.

2. A method according to claim 1, wherein the discrete-event simulation has a current system state, and the step of applying the computation of the head event if the computation of the head event is valid comprises changing the current system state based on the computation of the head event.

3. A method according to claim 1, wherein the step of determining whether the computation of the head event is valid or invalid uses input invariance.

4. A method according to claim 1, wherein the event list is an ordered collection of events.

5. A method according to claim 1, wherein the event list further comprises a plurality of events and at least one event indicated as uncomputed, the method further comprising the steps of:

selecting one of the uncomputed events from the event list; and

computing a computation for the selected uncomputed event.

6. A method according to claim 1, further comprising the steps of:

indicating a plurality of events in the event list as head events; and

determining concurrently whether each head event is uncomputed, in-computation, or pre-computed.

7. A method according to claim 6, further comprising prior to the step of indicating a plurality of events in the event list as head events, the step of:

determining whether a plurality of events in the event list are sufficiently independent to be indicated as head events.

23. A computer system having at least one processor and code segments for performing the method of claim 1.

24. A computer-readable medium having code segments executable by a computer for performing the method of claim 1.

8. A method for increasing the event throughput of a discrete-event simulation comprising the steps of:

maintaining an event list for the discrete-event simulation, the event list comprising a plurality of events and at least one event indicated as uncomputed;

selecting an event indicated as uncomputed from the event list;

transferring the selected event to an event pre-computation process;

indicating the selected event in the event list as in-computation;

computing a computation for the selected event using the event pre-computation process without affecting a system state of said discrete-event simulation;

receiving the computation from the event pre-computation process; and

indicating the selected event in the event list as pre-computed.

9. A method according to claim 8, wherein selecting an event indicated as uncomputed from the event list comprises scanning the event list for an event indicated as uncomputed.

10. A method according to claim 8, wherein the event pre-computation process selects the event from the event list.

11. A method according to claim 8, wherein transferring the selected event to an event pre-computation process comprises assigning the selected event to an event pre-computation process.

12. A method according to claim 8, further comprising the steps of:

indicating a plurality of pre-computed events as pre-computed head events for the event list; and

verifying each head event concurrently to determine if the head event is valid or invalid;

if the head event is valid, applying the computation of the head event; and

if the head event is invalid, executing the head event.

13. A method according to claim 8, wherein the discrete-event simulation has a current system state that is updated and wherein the step of computing a computation for the selected event using the event pre-computation process comprises the steps of:

providing the event pre-computation process with event inputs; and

determining a change to the system state based on the selected event and the event inputs;

wherein the step of receiving the computation from the event pre-computation process comprises receiving the event inputs and the change to the system state from the event pre-computation process; and

wherein the step of indicating the selected event in the event list as pre-computed comprises associating the event inputs and the change to the system state with the selected event.

14. A method according to claim 13, further comprising the steps of:

indicating the selected pre-computed event as a pre-computed head event for the event list;

verifying the head event to determine if the head event is valid or invalid;

if the head event is valid, applying the computation of the head event; and

if the head event is invalid, executing the head event.

15. A method according to claim 14, wherein the step of verifying the head event comprises comparing the current system state with the event inputs associated with the head event;

and

wherein the step of applying the computation of the head event comprises updating the current system state using the change to the system state associated with the head event.

16. A method according to claim 14, wherein the step of verifying the head event to determine if the head event is valid or invalid uses input invariance.

25. A computer system having at least one processor and code segments for performing the method of claim 8.

26. A computer-readable medium having code segments executable by a computer for performing the method of claim 8.

17. A method for increasing the event throughput of a discrete-event simulation comprising:

maintaining an event list for the discrete-event simulation, the event list having a plurality of events indicated as pre-computed;

selecting an event indicated as pre-computed from the event list; and

determining whether the selected event is valid or invalid, said determination being carried out as follows;

if the selected event is invalid;

assigning the selected event to an event pre-computation process;

indicating the selected event in the event list as in-computation;

computing a computation for the selected event using the event pre-computation process without affecting a system state of said discrete-event simulation;

receiving the computation from the event pre-computation process; and

indicating the selected event in the event list as pre-computed.

18. A method according to claim 17, wherein the event list has a head event indicated as pre-computed with an associated computation, the method further comprising the steps of:

verifying the head event to determine if the head event is valid or invalid;

if the head event is valid, applying the associated computation of the head event; and

if the head event is invalid, executing the head event.

27. A computer system having at least one processor and code segments for performing the method of claim 17.

28. A computer-readable medium having code segments executable by a computer for performing the method of claim 17.

19. A computer system having at least one processor and code segments for performing a discrete-event simulation comprising:

means for maintaining an event list comprising a plurality of events, one event being indicated as a head event, each event being indicated as uncomputed, in-computation, or pre-computed;

means for carrying out at least one event pre-computation process for computing a computation for an uncomputed event without affecting a system state of said discrete-event simulation;

means for selecting an uncomputed event and transferring the uncomputed event to one of the event pre-computation processes; and

means for executing an uncomputed head event and verifying a pre-computed head event.

20. The computer system of claim 19, wherein at least one processor implements the means for maintaining an event list, the means for selecting an uncomputed event and transferring the uncomputed event, and the means for executing an uncomputed head event and verifying a pre-computed head event.

21. The computer system of claim 19, wherein a plurality of processors implements the means for computing a computation for an uncomputed event.

22. A computer-readable medium embodying code segments executable by a computer for performing a discrete-event simulation, the code segments comprising:

a code segment for maintaining an event list comprising a plurality of events, one event indicated as a head event, each event indicated as uncomputed, in-computation, or pre-computed;

a code segment for each of at least one event pre-computation process for computing a computation for an uncomputed event without affecting a system state of said discrete-event simulation;

a code segment for selecting an uncomputed event and transferring the uncomputed event to one of the event pre-computation processes to have a computation computed according to the event pre-computation process; and

a code segment for executing an uncomputed head event and verifying a pre-computed head event.