Synchronous parallel system for emulation and discrete event simulation

• US 6,324,495 B1
• Filed: 06/09/1998
• Issued: 11/27/2001
• Est. Priority Date: 01/21/1992
• Status: Expired due to Fees

• Current Assignee: United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration
• Original Assignee: United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration
• Inventors: Steinman, Jeffrey S.
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): Sergent, Douglas W.
• Application Number:
  US09/094,386
• Time in Patent Office: 1,267 Days
• Field of Search: 703/16, 703/17, 703/20, 703/21, 703/6, 703/13, 709/400, 709/315, 713/502
• 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 synchronous parallel system for emulation and discrete event simulation having parallel nodes responds to received messages at each node by generating event objects having individual time stamps, stores only the changes to the state variables of the simulation object attributable to the event object and produces corresponding messages. The system refrains from transmitting the messages and changing the state variables while it determines whether the changes are superseded, and then stores the unchanged state variables in the event object for later restoral to the simulation object if called for. This determination preferably includes sensing the time stamp of each new event object and determining which the new event object has the earliest time stamp as the local event horizon, determining the earliest local event horizon of the nodes as the global event horizon, and ignoring events whose time stamps are less than the global event horizon. Host processing between the system and external terminals enables such a terminal to query, monitor, command or participate with a simulation object during the simulation process.

Claims

1. A method of performing object-oriented simulation in a system of interconnected processor nodes operating in parallel, said object-oriented simulation being performed at each one of said nodes and comprising:

simulating mutual interactions of a set of discrete simulation objects distributed among said nodes as a sequence of discrete events changing state variables of respective simulation objects so as to generate new event-defining messages addressed to respective ones of said nodes;

assigning self-contained simulation objects to each one of said nodes and responding to messages received at one node by generating corresponding event objects having individual time stamps and corresponding to respective events affecting one of said a simulation objects of said one node; and

storing only changes to said state variables of a one simulation object corresponding to a next one of said event objects and producing corresponding messages specifying events resulting therefrom;

transmitting said corresponding messages to respective nodes;

determining whether said changes to said state variables are superseded by another event object affecting said one simulation object;

rolling back said simulation object by returning the unchanged state variables stored in the corresponding event object to said simulation object, if said changes to said state variable are determined to be superseded by another event object affecting the simulation object; and

transmitting an antimessage to a node where a message has been sent if said message corresponds to changes to a state variable superseded by another event object, said antimessage comprising a notification to nullify said message.

2. The method of claim 1 wherein said storing step stores in said next one of said event objects changes to said state variables of said one simulation object which are attributable to said next one of said event objects, said method further comprising:

at each node sensing the time stamp of each new event object generated by said generating step during each one of said succession of cycles and determining which said new event object has the earliest time stamp and defining the value of said earliest time stamp as the local event horizon of the corresponding node;

determining the earliest local event horizon from among all of said nodes and defining the value thereof as the global event horizon of said one cycle for said system; and

first transmitting a first set of said messages to respective nodes of which not more than N1 correspond to events beyond said global event horizon.

3. The method of claim 1 further comprising:

determining whether said changes to said state variables are superseded by another event object affecting said one simulation object while refraining from effecting corresponding changes to the state variables of said one object and from transmitting said corresponding messages to others of said nodes;

transmitting said corresponding messages and effecting said changes to said state variables of said simulation object while storing the unchanged state variables thereof in the corresponding event object of said changes to said state variables are not superseded; and

wherein said storing, determining and transmitting steps comprise a single one of a succession of cycles of said node, and wherein said determining step comprises one of a plurality of protocols which is user-selected.

4. The method of claim 3 wherein said plurality of protocols comprise at least one of a time warp protocol, a time bucket protocol and a sequential protocol.

5. The method of claim 3 wherein said one protocol is a breathing time bucket protocol comprising the following steps:

at each node sensing the time stamp of each new event object generated by said generating step during each one of said succession of cycles and determining which said new event object has the earliest time stamp and defining the value of said earliest time stamp as the local event horizon of the corresponding node;

determining the earliest local event horizon from among all of said nodes and defining the value thereof as the global event horizon of said one cycle for said system;

wherein said method comprises carrying out said transmitting and effecting steps only for those messages whose time stamps are less than said global event horizon.

6. The method of claim 5 wherein the time length of the current one of said succession of cycles for each node corresponds to the local event horizon of that node.

7. The method of claim 5 wherein the time length of the current one of said succession of cycles for each node corresponds the amount of time required for all nodes to cross said global event horizon, wherein a node crosses an event horizon by generating an event object having a time stamp beyond said event horizon.

8. The method of claim 5 further comprising broadcasting from each node to all nodes when the local even horizon has been crossed and ending said cycle at each node upon sensing said broadcast from another node, wherein the time length of the current one of said succession of cycles for each node does not go beyond the first node to exceeds its local event horizon.

9. The method of claim 1 further comprising:

at each node listing each event object generated for any simulation object in said node in a secondary list in the order in which it was generated;

at the conclusion of the current cycle in said node, sorting said secondary list in accordance with the time stamps of said event objects and merging said secondary list into a primary list listing all of the event objects to be performed in said node in chronological order;

during the next cycle, performing said event objects in the order of said primary list.

10. The method of claim 1 further comprising:

determining whether said changes to said state variables are superseded by another event object affecting said one simulation object while refraining from effecting corresponding changes to the state variables of said one object and from transmitting said corresponding messages to others of said nodes;

transmitting said corresponding messages and effecting said changes to said state variables of said simulation object while storing the unchanged state variables thereof in the corresponding event object of said changes to said state variables are not superseded; and

performing host processing between said system and plural external human interaction means, whereby to communicate between each external human interaction means and a respective one of said nodes.

11. The method of claim 1 further comprising:

determining whether said changes to said state variables are superseded by another event object affecting said one simulation object while refraining from effecting corresponding changes to the state variables of said one object and from transmitting said corresponding messages to others of said nodes;

transmitting said corresponding messages and effecting said changes to said state variables of said simulation object while storing the unchanged state variables thereof in the corresponding event object of said changes to said state variables are not superseded; and

wherein said storing, determining and transmitting steps comprise a single one of a succession of cycles of said node and wherein said transmitting step is followed by a blocking step wherein the beginning of the next cycle is delayed pending a communication from one of said external human interaction means.

12. The method of claim 11 wherein each of said external human interaction means is permitted to interact with an event occurring in one cycle during the next succeeding cycle.

13. The method of claim 3 wherein the step of interacting comprises one of:

a. interrogating the state variables of a selected simulation object at a selected point in time;

b. continuously monitoring the state variables of a selected simulation object over a selected period of time;

c. commanding changes to the state variables of a selected simulation object;

d. being a simulation object controlled by the simulation performed by said system.

22. A method of performing object-oriented simulation in a system of interconnected processor nodes operating in parallel, said object-oriented simulation being performed at each one of said nodes and comprising:

simulating mutual interactions of a set of discrete simulation objects distributed among said nodes as a sequence of discrete events changing state variables of respective simulation objects so as to generate new event-defining messages addressed to respective ones of said nodes;

responding to messages received at one node by generating corresponding event objects having individual time stamps and corresponding to respective events affecting one of said simulation objects of said one node and producing therefrom changes to said state variables of said one object corresponding to a next one of said event objects and producing corresponding messages specifying events resulting therefrom;

determining whether said changes to said state variables are superseded by another event object affecting said simulation object while refraining from effecting corresponding changes to the state variables of said one object and from transmitting said corresponding messages to others of said nodes;

transmitting said corresponding messages and effecting said changes to said state variables of said simulation object while storing the unchanged state variables thereof in the corresponding event object if said changes to said state corresponds to the local event horizon of that node.

23. The method of claim 22 wherein the step of assigning simulation objects to each one of said nodes is accompanied by the step of specifying a set of initial events affecting said simulation objects and is user-specified.

24. The method of claim 23 wherein said responding, determining and transmitting steps comprise a single one of a succession of repetitive cycles of said node, and wherein said determining step comprises one of a plurality of protocols which is user-selected.

25. The method of claim 24 wherein said plurality of protocols comprise at least one of a time warp protocol, a time bucket protocol and a sequential protocol.

26. The method of claim 22 wherein said determining step comprises a breathing time bucket protocol comprising the following steps:

at each node sensing the time stamp of each new event object generated by said generating step during each one of said succession of cycles and determining which said new event object has the earliest time stamp and defining the value of said earliest time stamp as the local event horizon of the corresponding node;

determining the earliest local event horizon from among all of said nodes and defining the value thereof as the global event horizon of said one cycle for said system;

wherein said method comprises carrying out said transmitting and effecting steps only for those messages whose time stamps are less than said global event horizon.

27. The method of claim 26 wherein the time length of the current one of said succession of cycles for each node corresponds to the local event horizon of that node.

28. The method of claim 26 wherein the time length of the current one of said succession of cycles for each node corresponds the amount of time required for all nodes to cross said global event horizon, wherein crossing an event horizon is performed by generating an event object having a time stamp beyond said event horizon.

29. The method of claim 26 further comprising broadcasting from each node to all nodes when the local even horizon has been crossed and ending said cycle at each node upon sensing said broadcast from another node, wherein the time length of the current one of said succession of cycles for each node does not go beyond the first node to exceeds its local event horizon.

30. A method of performing object-oriented simulation in a system of interconnected processor nodes operating in parallel, said object-oriented simulation being performed at each one of said nodes and comprising:

simulating mutual interactions of a set of discrete simulation objects distributed among said nodes as a sequence of discrete events changing state variables of respective simulation objects so as to generate new event-defining messages addressed to respective ones of said nodes;

assigning simulation objects to each one of said nodes;

responding to a message received at one node by generating a corresponding event object having a time-stamp corresponding to the time of receipt of said message and corresponding to an event affecting one of said simulation objects of said one node, said responding and generating steps being repeated until the end of a current repetitive cycle;

at each node listing each event object generated for any simulation object in said node in a secondary list in the order in which it was generated;

at the conclusion of the current cycle in said node, sorting said secondary list in accordance with the time stamps of said event objects and merging said secondary list into a primary list listing all of the event objects to be performed in said node in chronological order;

during the next cycle, implementing changes to simulation object state variables in accordance with event objects in the order of said primary list.

31. A method of performing object-oriented simulation in a system of interconnected processor nodes operating in parallel, said object-oriented simulation being performed at each one of said nodes and comprising:

simulating mutual interactions of a set of discrete simulation objects distributed among said nodes as a sequence of discrete events changing state variables of respective simulation objects so as to generate new event-defining messages addressed to respective ones of said nodes;

assigning simulation objects to each one of said nodes;

responding to a message received at one node by generating a corresponding event object having a time-stamp corresponding to the time of receipt of said message and corresponding to an event affecting one of said simulation objects of said one node;

performing host processing between said system and plural external human interaction means, whereby to communicate between each external human interaction means and a respective one of said nodes.

14. The method of claim 35 further comprising:

providing in each node an antimessage hash object;

storing a pointer in the hash object designating a destination in said node for each message received in the node and sent to the destination;

guiding a received antimessage with said pointer to the destination of a message corresponding to said received antimessage.

32. The method of claim 31 further comprising:

storing changes to said state variables of said one object corresponding to a next one of said event objects and generating corresponding messages specifying events resulting therefrom;

determining whether said changes to said state variables are superseded by another event object affecting said simulation object while refraining from effecting corresponding changes to the state variables of said one object and from transmitting said corresponding messages to others of said nodes;

transmitting said corresponding messages and effecting said changes to said state variables of said simulation object while storing the unchanged state variables thereof in the corresponding event object if said changes to said state variables are not superseded;

wherein said storing, determining and transmitting steps comprise a single one of a succession of cycles of said node and wherein said transmitting step is followed by a blocking step wherein the beginning of the next cycle is delayed pending a communication from one of said external human interaction means.

33. The method of claim 32 wherein each of said external human interaction means is permitted to interact with an event occurring in one cycle during the next succeeding cycle.

34. The method of claim 33 wherein the step of interacting comprises one of:

a. interrogating the state variables of a selected simulation object at a selected point in time;

b. continuously monitoring the state variables of a selected simulation object over a selected period of time;

c. commanding changes to the state variables of a selected simulation object;

d. being a simulation object controlled by the simulation performed by said system.

35. The method of claim 34 wherein each of said external human interaction means is permitted to interact with an event occurring in one cycle during the next succeeding cycle.

36. A method of performing object-oriented simulation in a system of interconnected processor nodes operating in parallel, said object-oriented simulation being performed at each one of said nodes and comprising:

simulating mutual interactions of a set of discrete simulation objects distributed among said nodes as a sequence of discrete events changing state variables of respective simulation objects so as to generate new event-defining messages addressed to respective ones of said nodes;

responding to each message received at one node by generating a corresponding event having a time-stamp and affecting one of said simulation objects of said one node and producing therefrom corresponding changes to said state variables of said one simulation object and corresponding messages specifying other events resulting therefrom;

at each node sensing the time stamp of each new event object generated by said generating step during each one of said succession of cycles and determining which said new event has the earliest time stamp and defining the value of said earliest time stamp as the local event horizon of the corresponding node;

determining the earliest local event horizon from among all of said nodes and defining the value thereof as the global event horizon of said one cycle for said system;

transmitting said corresponding messages and effecting said changes to said state variables of said simulation object only for those events whose time stamps are within said global event horizon.

15. The method of claim 36 wherein said first set is further limited in that the number messages beyond said global event horizon transmitted by all of said nodes is not more than N2.

16. The method of claim 15 wherein N1 and N2 are integers and N2 exceeds N1.

17. The method of claim 16 wherein N1 and N2 correspond to an optimum number of messages least likely to result in creation of events which are superseded.

18. The method of claim 36 wherein said first transmitting step is followed by:

second transmitting a second set of messages consisting of only messages corresponding to changes to said state variables which have not been superseded by another event object affecting the same simulation object.

19. The method of claim 36 further comprising:

during said first transmitting step, determining whether said changes to said state variables are superseded by another event object affecting said one simulation object and transmitting antimessages to respective nodes to cancel messages corresponding to the changes which have been so superseded.

20. The method of claim 18 wherein said second transmitting step comprises a breathing time bucket protocol comprising:

transmitting only those messages whose time stamps are less than said global event horizon;

determining whether said changes to said state variable are superseded by another event object; and

rolling back said simulation object by returning the unchanged state variables stored in the corresponding event object to said simulation object, if said changes to said state variable are determined to be superseded by another event object affecting the simulation object.

21. The method of claim 18 wherein said second transmitting step comprises a time bucket protocol comprising:

determining a minimum time T within which a message can produce a new event superseding said changes;

transmitting only those messages having time stamps within T of said global event horizon.

37. The method of claim 36 wherein the time length of the current one of said succession of cycles for each node corresponds to the local event horizon of that node.

38. The method of claim 36 wherein the time length of the current one of said succession of cycles for each node corresponds the amount of time required for all nodes to cross said global event horizon, wherein crossing an event horizon is performed by generating an event having a time stamp beyond said event horizon.

39. The method of claim 36 further comprising broadcasting from each node to all nodes when the local even horizon has been crossed and ending said cycle at each node upon sensing said broadcast from another node, wherein the time length of the current one of said succession of cycles for each node does not go beyond the first node to exceeds its local event horizon.

40. A method of performing object-oriented simulation in a system of interconnected processor nodes operating in parallel, said object-oriented simulation being performed at each one of said nodes and comprising:

simulating mutual interactions of a set of discrete simulation objects distributed among said nodes as a sequence of discrete events changing state variables of respective simulation objects so as to generate new event-defining messages addressed to respective ones of said nodes;

responding to messages received at one node by generating corresponding event objects having individual time stamps and corresponding to respective events affecting one of said simulation objects of said one node and producing therefrom changes to said state variables of said one simulation object corresponding to a next one of said event objects and producing corresponding messages specifying events resulting therefrom;

effecting corresponding changes to the state variables of said one simulation object;

determining whether said changes to said state variables are superseded by another event object affecting said simulation object, and, if superseded, undoing the superseded changes in said one simulation object;

at each node sensing the time stamp of each new event object generated by said generating step during each one of said succession of cycles and determining which said new event object has the earliest time stamp and defining the value of said earliest time stamp as the local event horizon of the corresponding node;

determining the earliest local event horizon from among all of said nodes and defining the value thereof as the global event horizon of said one cycle for said system;

performing a time warp phase comprising transmitting a first set of not more than N1 of said corresponding messages having time stamps beyond said global event horizon to others of said nodes and not more than N2 of said corresponding messages having time stamps beyond said global event horizon from all of said nodes and transmitting antimessages to cancel messages corresponding to superseded ones of said changes; and

thereafter performing a time bucket phase comprising transmitting other corresponding messages not included in said first set of messages and effecting changes to said state variables of said one simulation object corresponding to said other messages only if said changes to said state variables corresponding to said other messages are not superseded.

41. The method of claim 40 wherein said time bucket phase comprises a breathing time bucket protocol comprising:

transmitting only those messages whose time stamps are less than said global event horizon.

42. The method of claim 40 wherein said time bucket phase comprises a time bucket protocol comprising:

determining a minimum time T within which a message can produce a new event superseding said changes;

transmitting only those messages having time stamps within T of said global event horizon.

43. A method of performing object-oriented simulation in a system of interconnected processor nodes operating in parallel, said object-oriented simulation being performed at each one of said nodes and comprising:

simulating mutual interactions of a set of discrete simulation objects distributed among said nodes as a sequence of discrete events changing state variables of respective simulation objects so as to generate new event-defining messages addressed to respective ones of said nodes;

responding to messages received at one node by generating corresponding event objects having individual time stamps and corresponding to respective events affecting one of said simulation objects of said one node and producing therefrom changes to said state variables of said one simulation object corresponding to a next one of said event objects and producing corresponding messages specifying events resulting therefrom;

effecting corresponding changes to the state variables of said one simulation object;

determining whether said changes to said state variables are superseded by another event object affecting said simulation object, and, if superseded, undoing the superseded changes in said one simulation object;

determining an event horizon from the events specified by said messages;

performing a time warp phase comprising transmitting a first set of not more than N1 of said corresponding messages having time stamps beyond said global event horizon to others of said nodes and transmitting antimessages to cancel messages corresponding to superseded ones of said changes.

44. The method of claim 43 further comprising, after performing said time warp phase:

performing a time bucket phase comprising transmitting other corresponding messages not included in said first set of messages and effecting changes to said state variables of said one simulation object corresponding to said other messages, provided that said changes to said state variables corresponding to said other messages are not superseded.

45. The method of claim 43 wherein the number of messages beyond said global event horizon which are transmitted is further limited in that the number of such messages transmitted from all of said nodes in a given cycle does not exceed N2.

46. The method of claim 45 wherein N1 and N2 are integers and N2 exceeds N1.

47. The method of claim 46 wherein N1 and N2 correspond to an optimum number of messages least likely to result in creation of events which are superseded.

48. The method of claim 44 wherein said time bucket phase comprises a breathing time bucket protocol comprising:

transmitting only those messages whose time stamps are less than said global event horizon.

49. The method of claim 44 wherein said time bucket phase comprises a time bucket protocol comprising:

determining a minimum time T within which a message can produce a new event superseding said changes;

transmitting only those messages having time stamps within T of said global event horizon.

50. The method of claim 43 wherein said event horizon is a global event horizon.

51. The method of claim 50 where the step of determining said event horizon comprises:

at each node sensing the time stamp of each new event object generated by said generating step during each one of said succession of cycles and determining which said new event object has the earliest time stamp and defining the value of said earliest time stamp as the local event horizon of the corresponding node;

determining the earliest local event horizon from among all of said nodes and defining the value thereof as the global event horizon of said one cycle for said system.

52. A system of interconnected processor nodes operating in parallel comprising:

a set of discrete simulation objects distributed among said nodes;

a computer program operating on said system for simulating mutual interactions of a set of discrete simulation objects as a sequence of discrete events changing state variables of respective simulation objects so as to generate new event-defining messages addressed to respective ones of said nodes;

wherein said computer program performs object-oriented simulation at each one of said nodes and comprises,

self-contained simulation objects assigned to each one of said nodes, and

corresponding active event objects generated in response to messages received at one node, said active event objects having user-defined inherent capabilities and individual time stamps and corresponding to respective events affecting one of said self-contained simulation objects of said one node, wherein said active event objects request information and change variables within a self-contained simulation object and produce corresponding messages specifying events resulting therefrom;

wherein said respective self-contained simulation objects are restricted to only providing and receiving information from said respective active event objects; and

wherein a generic object event queue is defined for said one simulation object, said generic object event queue being indicative of the order of the event objects produced by said generating step affecting said one simulation object, whereby said next event object is specified by said generic object event queue.

53. The system of claim 52 further comprising:

a determine module for determining whether said changes to said state variables are superseded by another event object affecting said one simulation object while refraining from effecting corresponding changes to the state variables of said one object and from transmitting said corresponding messages to others of said nodes;

a transmit module for transmitting said corresponding messages and effecting said changes to said state variables of said simulation object while storing the unchanged state variables thereof in the corresponding event object if said changes to said state variables are not superseded.

54. The system of claim 53 wherein storing, determining and transmitting comprise a single one of a succession of cycles of said node, and wherein determining comprises one of a plurality of protocols which is user-selected.

55. The system of claim 54 wherein said plurality of protocols comprise at least one of a time warp protocol, a time bucket protocol and a sequential protocol.

56. The system of claim 54 wherein said one protocol is a breathing time bucket protocol comprising:

at each node a sensor for sensing the time stamp of each new event object generated by said generating step during each one of said succession of cycles and determining which said new event object has the earliest time stamp and defining the value of said earliest time stamp as the local event horizon of the corresponding node;

a device for determining the earliest local event horizon from among all of said nodes and defining the value thereof as the global event horizon of said one cycle for said system;

wherein said system transmits and effects only for those messages whose time stamps are less than said global event horizon.

57. The system of claim 56 wherein the time length of the current one of said succession of cycles for each node corresponds to the local event horizon of that node.

58. The system of claim 56 wherein the time length of the current one of said succession of cycles for each node corresponds the amount of time required for all nodes to cross said global event horizon, wherein a node crosses an event horizon by generating an event object having a time stamp beyond said event horizon.

59. The system of claim 56 further comprising a broadcast module for broadcasting from each node to all nodes when the local even horizon has been crossed and ending said cycle at each node upon sensing said broadcast from another node, wherein the time length of the current one of said succession of cycles for each node does not go beyond the first node to exceeds its local event horizon.

60. The system of claim 52 further comprising:

a list module for, at each node, listing each event object generated for any simulation object in said node in a secondary list in the order in which it was generated;

a sort module for, at the conclusion of the current cycle in said node, sorting said secondary list in accordance with the time stamps of said event objects and merging said secondary list into a primary list listing all of the event objects to be performed in said node in chronological order;

during the next cycle, a device for performing said event objects in the order of said primary list.

61. The system of claim 52 further comprising:

a transmit module for transmitting said corresponding messages to respective nodes;

a determine module for determining whether said changes to said state variables are superseded by another event object affecting said one simulation object;

a roll back module for rolling back said simulation object by returning the unchanged state variables stored in the corresponding event object to said simulation object, if said changes to said state variable are determined to be superseded by another event object affecting the simulation object.

62. The system of claim 61 further comprising a module for transmitting an antimessage to a node where a message has been sent if said message corresponds to changes to a state variable superseded by another event object, said antimessage comprising a notification to nullify said message.

63. The system of claim 62 further comprising a device for:

providing in each node an antimessage hash object;

storing a pointer in the hash object designating a destination in said node for each message received in the node and sent to the destination;

guiding a received antimessage with said pointer to the destination of a message corresponding to said received antimessage.

64. The system of claim 52 further comprising:

an event module for, at each node;

sensing the time stamp of each new event object generated by said generating step during each one of said succession of cycles and determining which said new event object has the earliest time stamp and defining the value of said earliest time stamp as the local event horizon of the corresponding node;

determining the earliest local event horizon from among all of said nodes and defining the value thereof as the global event horizon of said one cycle for said system;

first transmitting a first set of said messages to respective nodes of which not more than N1 correspond to events beyond said global event horizon.

65. The system of claim 64 wherein said first set is further limited in that the number messages beyond said global event horizon transmitted by all of said nodes is not more than N2.

66. The system of claim 65 wherein N1 and N2 are integers and N2 exceeds N1.

67. The system of claim 66 wherein N1 and N2 correspond to an optimum number of messages least likely to result in creation of events which are superseded.