Unboundedly parallel simulations

• US 5,375,074 A
• Filed: 01/23/1990
• Issued: 12/20/1994
• Est. Priority Date: 01/23/1990
• Status: Expired due to Term

• Current Assignee: American Telephone & Telegraph Company (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Mitrani, Israel, Greenberg, Albert G., Lubachevsky, Boris D.
• Primary Examiner(s): Ramirez, Ellis B.
• Application Number:
  US07/468,524
• Time in Patent Office: 1,792 Days
• Field of Search: 364/578, 364/976.5, 364/916.3, 364/931.41, 371/23, 340/286 M, 340/515
• 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

Efficient simulation is achieved by employing a highly efficient ordering of the events to be simulated. Specifically, the events to be simulated are grouped into layers and the layers are simulated in order. Each of the layers consists of events that are either strictly independent of the other events in the layer or are dependent of other events in the layer but possess a particular attribute. That attribute is one that permits the use of an associative operator. This operator allows the simulation of N events in O(log N) computation iterations.

Claims

1. A method for simulating on a computer events of a system comprising the steps of:

selecting a cluster of events of said system that includes primarily events that are related to each other through an associative operator, an operator being associative when the same result is reached whether the operator is applied to a first intermediate result and event C, or to event A and a second intermediate result--where the first intermediate result is obtained by applying the operator to events A and B, and the second intermediate result is obtained by applying the operator to events B and C;

simulating the events of said cluster of events; and

returning to said step of selecting when at least some of said events of said system have not been simulated.

2. The method of claim 1 wherein said step of selecting excludes events that belong to another cluster.

3. The method of claim 1 wherein said step of simulating, when simulation information about events in other clusters is required, utilizes the simulation information of said events in other clusters developed by preceding steps of simulating, and makes assumptions about the simulation information of said events in other clusters to which said step of simulating was not applied.

4. The method of claim 3 wherein said steps of selecting, simulating and returning form a sequence of cluster simulations, and at least a portion of said sequence is repeated until the simulation information for all of the events in repetition k of said sequence, where k is an integer, is the same as the simulation information for all of the events in repetition k-1 of said sequence.

28. The method of claim 1 wherein said step of selecting selected the events of a cluster based on said associative operator.

29. The method of claim 1 wherein said step of simulating simulates the events with the aid of said associative operator.

30. The method of claim 1 wherein said step of selecting selected the events of a cluster based on said associative operator, and said step of simulating simulates the events with the aid of said associative operator.

5. A method for simulating on a computer events of a system comprising the steps of:

selecting a layer of events of said system that includes mostly event groups that are related to each other through an associative operator, an operator being associative when the same result is reached whether the operator is applied to a first intermediate result and event C, or to event A and a second intermediate result--where the first intermediate result is obtained by applying the operator to events A and B, and the second intermediate result is obtained by applying the operator to events B and C;

simulating said layer of events; and

returning to said step of selecting when at least some of said system events have not been simulated.

6. The method of claim 5 wherein said step of selecting excludes events that belong to another layer.

7. The method of claim 5 wherein said step of simulating, when simulation information about events in other clusters is required, utilizes the simulation information of said events in other clusters developed by preceding steps of simulating, and makes assumptions about the simulation information of said events in other clusters to which said step of simulating was not applied.

8. The method of claim 5 wherein said steps of selecting, simulating and returning form a sequence of cluster simulations, and at least a portion of said sequence is repeated until the simulation information for all of the events in repetition k of said sequence, where k is an integer, is the same as the simulation information for all of the events in repetition k-1 of said sequence.

9. The method of claim 5 wherein the event groups that are related to each other through an associative operator are such that the groups can be ordered and the events of a group can be simulated from the events of some previous groups with the aid of said associative operator.

10. The method of claim 5 wherein said system comprises a plurality of interacting nodes and each of said layers comprises primarily the events of one of said nodes.

11. The method of claim 5 wherein said system comprises a plurality of interacting nodes and each of said layers consists the events of one of said nodes.

12. The method of claim 5 wherein said step of simulating a layer includes a step of merging the events of other layers that affect said layer.

13. The method of claim 5 wherein said step of simulating a layer includes the steps of

merging the simulated events of layers that affect said layer and that have been previously simulated;

and

merging assumed events of layers that affect said layer but which have not been previously simulated.

14. The method of claim 13 wherein said steps of selecting, simulating and returning from a sequence of cluster simulations, and at least a portion of said sequence is repeated until the simulation information for all of the events in repetition k of said sequence, where k is an integer, is the same as the simulation information for all of the events in repetition k-1 of said sequence.

24. The method of claim 5 wherein said step of simulating develops an order of simulating the events in said layer.

25. The method of claim 24 wherein said order is related to priority of the events being simulated.

26. The method of claim 24 wherein said order is related to constraints of hardware in which said method of simulating is carried out.

27. The method of claim 24 wherein said order is related to memory constraints of hardware in which said method of simulating is carried out.

15. A method for discrete event simulation on a computer of system events occurring in a plurality of nodes in a multi-node system, where events in one node correspond to a time interval having more than one time sample and affect events in another node, comprising the steps of:

selecting the events of a node;

simulating events of the selected node; and

returning to said step of selecting until the last node in said order has been simulated and all events have been simulated.

16. The method of claim 15 wherein said simulating comprises simulating departure times of jobs.

17. The method of claim 15 wherein said simulating is carried out with the aid of an associative operator.

18. The method of claim 17 wherein said associative operator includes a "max" function which selects the larger of said two inputs.

19. The method of claim 15 wherein said step of selecting includes a step of formulating a simulations order of said nodes.

20. The method of claim 19 wherein said step of formulating a simulations order is based on an acyclic directed graph representation of said system, which graph comprises at least one node from the set of nodes that includes strongly connected component nodes and non-strongly connected component nodes.

21. A method for discrete event simulation on a computer of system events occurring in a plurality of nodes in a multi-node system, where events in one node correspond to a time interval having more than one time sample and affect events in another node, comprising the steps of:

formulating a simulations order for simulating said nodes;

designating said the first node in said order as the simulation node;

simulating events scheduled for said simulation node;

designating a new simulation node by selecting the node that follows, in said order, the current simulation node; and

returning to said step of simulating until the last node in said order has been simulated and all events have been simulated.

22. The method of claim 21 wherein said step of formulating a simulations order comprises:

attaining a directed parent graph to represent the interaction of said plurality of nodes;

creating an acyclic directed graph from said directed parent graph by representing each strongly connected component in said parent graph by node;

selecting a node in said acyclic directed graph that is dependent on the fewest number of other nodes in said acyclic directed graph;

assigning the selected node to a list when the selected node is nonstrongly connected component node;

developing a sublist when the selected node is a strongly connected component node and appending said sublist to said list; and

returning to said step of selecting until the last node in said acyclic directed graph has been selected.

23. A method for discrete event simulation on a computer of system events occurring in a plurality of nodes in a multi-node system, where events in one node correspond to a time interval having more than one time sample and affect events in another node and where the termination of the appearance on independent events at one or more of the system nodes is not known, comprising the steps of:

selecting a super-group of events;

for events within the selected super-group, executing a simulation procedure including

selecting a cluster of events from among the events within the selected super-group, which cluster includes primarily events that are related to each other through an associative operator;

simulating the events of said cluster of events; and

returning to said step of selecting when at least some of said events of said system have not been simulated;

selecting another super-group of events; and

returning to said step of executing a simulation procedure.

31. A method for simulating events of a system with an available number of processors comprising the steps of:

dividing the events to be simulated into layers having defined interface borders between the layers where at least in some of the layers one of the events in a layer is causally related to at least one other event in the layer;

selecting an order of simulation for simulating said layers; and

simulating the layers in a seriatim manner, where each step of simulating a layer completely simulates the layer by employing essentially all of the available number of processors.

32. The method of claim 31 wherein said step of dividing the events to be simulated creates clusters of events where each cluster of events of said system includes primarily events that are related to each other through an associative operator.

33. The method of claim 31 wherein said step of dividing the events to be simulated creates clusters of events where each cluster of events of said system includes events within a lower border and an upper border of the simulated time where the lower border and the upper border encompass events of more than one particular time.