Distributed system simulation: slow message relaxation

• US 7,590,519 B2
• Filed: 11/08/2005
• Issued: 09/15/2009
• Est. Priority Date: 11/08/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Pan, Aimin, Zhang, Zheng, Lin, Shiding, Guo, Rui
• Primary Examiner(s): Rodriguez; Paul L
• Assistant Examiner(s): Thangavelu; Kandasamy
• Application Number:
  US11/269,133
• Publication Number:
  US 20070129928A1
• Time in Patent Office: 1,407 Days
• Field of Search: 703/17, 703/14, 703/13, 703/16, 703/20, 703/22, 709/248, 709/217, 709/224, 707/104.1, 707/202, 370/351, 719/318, 712/36, 716/5, 717/104
• 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

Distributed system simulation is enhanced by extending the simulation window. In a described implementation, the simulation window extension is facilitated with a slow message relaxation scheme. For example, especially when the simulation window is extended, slow unscheduled events can arrive at a logical process with a timestamp that is prior to (e.g., less than) the local time of a receiving logical process that is participating in a simulation. To ameliorate issues created by a slow unscheduled message and its corresponding slow unscheduled event, a current logical time of the receiving logical process is substituted for the original timestamp of the slow unscheduled event to transform it into a punctual unscheduled event.

Claims

1. A method to perform on a plurality of computing devices a simulation of a distributed system, the simulation occurring round by round, the method comprising:

receiving, by a logical process operated by one of the computing devices, an event having a timestamp;

determining, by the one of the computing devices, if the timestamp of the event is less than a local time of the logical process;

if the timestamp of the event is determined to be less than the local time of the logical process, substituting, by the one of the computing devices, the local time of the logical process for the timestamp of the event;

determining by the one of the computing devices that all logical processes operating on the computing devices have finished processing all events for a given round;

after the determining that all the logical processes have finished processing all the events, calculating by the one of the computing devices a new relaxation width of a simulation window, the new relaxation width being responsive to at least one runtime simulation parameter, the value of the relaxation width exceeding a global lookahead value for the distributed system being simulated, wherein the calculating comprises ensuring that the relaxation width does not exceed one-half of a timeout interval that is related to maintaining nodal knowledge of the distributed system being simulated; and

sending the new relaxation width to other computing devices.

2. The method as recited in claim 1, further comprising:

adding, by the one of the computing devices, the event having the local time to an event queue of the logical process; and

processing the event having the local time.

3. The method as recited in claim 2 wherein adding the event having the local time comprises inserting the event having the local time at a head position of the event queue of the logical process.

4. The method as recited in claim 1, wherein the logical process is executing at least part of the simulation of the distributed system, and the local time of the logical process comprises a current logical time of the simulation.

5. The method as recited in claim 1, further comprising:

if the timestamp of the event is not determined to be less than the local time of the logical process, inserting the event into an event queue of the logical process at a chronological position based on the timestamp of the event.

6. The method as recited in claim 1, further comprising:

prior to receiving any events, receiving by the one of the computing devices, a message from another computing device, the message comprising a list of scheduled events for a current round for the logical process;

determining, by the one of the computing devices, if the received event is a scheduled event by determining whether the event is found in the list of scheduled events for the current round for the logical process;

if the event is determined to be a scheduled event, adding, by the one of the computing devices, the scheduled event to an event queue of the logical process.

7. One or more processor-accessible storage media comprising processor-executable instructions that, when executed by a processor, implement a method to perform a simulation of a distributed system synchronously, the method comprising:

determining by a master computing device a relaxation width of a simulation window for a round of execution that exceeds a global lookahead value of the distributed system;

adjusting the relaxation width of the simulation window responsive to at least one runtime parameter, the at least one runtime parameter including a timeout interval that is related to maintaining nodal knowledge of the distributed system being simulated, the adjusting comprising ensuring that the relaxation width does not exceed one-half of the timeout interval; and

sending the relaxation width from the master computing device to one or more slave computing devices.

8. The one or more processor-accessible storage media as recited in claim 7, wherein the method further comprises handling slow unscheduled messages that are behind a local clock of a logical process by increasing a respective latency of each respective slow unscheduled message of the slow unscheduled messages.

9. The one or more processor-accessible storage media as recited in claim 7, wherein the method further comprises handling a slow unscheduled message having a timestamp that is less than a current local time of a logical process by replacing the timestamp with the current local time of the logical process.

10. The one or more processor-accessible storage media as recited in claim 7, wherein the at least one runtime parameter also comprises one or more of a current speed of the simulation, a previous speed of the simulation, a directional change coefficient, or a previous relaxation width.

11. The one or more processor-accessible storage media as recited in claim 7, wherein the simulation is performed in rounds, the method further comprising:

determining a duration responsive to the relaxation width of the simulation window;

sending by the master computing device a global time to a logical process to which local time of the logical process is to be advanced in a given round and a listing of safe events that are scheduled for execution in the given round by the logical process.

12. An apparatus to perform a simulation of a distributed system, the apparatus comprising:

a master computing device that adapts a relaxation width of a simulation window of the simulation of the distributed system responsive to at least one runtime parameter, the at least one runtime parameter including a timeout interval that is related to maintaining nodal knowledge of the distributed system being simulated, and the adapting comprising ensuring that the relaxation width does not exceed one-half of the timeout interval;

wherein the master computing device comprises;

one or more processors;

a global time ascertainer that ascertains a globally lowest clock; and

a determiner of safe scheduled events for each logical process in the simulation; and

wherein the master computing device sends the ascertained globally lowest clock and those safe scheduled events corresponding to each logical process to the corresponding logical process; and

a plurality of slave computing devices communicatively coupled to the master computing device, each slave computing device having a logical process that replaces a timestamp of an event with a local time of the logical process if the timestamp is less than the local time,

wherein each slave computing device comprises an event queue having multiple events that are chronologically ordered, a head event of the multiple events located at a head of the event queue, and wherein the local time of the logical process is established by a timestamp of the head event, and

wherein the logical process processes events in the event queue in chronological order.

13. The apparatus as recited in claim 12, further comprising:

another slave computing device having another logical process;

wherein the logical process is associated with a first set of nodes, and the another logical process is associated with a second set of nodes, each node of the first and second sets of nodes forming a node of the distributed system; and

wherein the logical process sends to the master computing device at the conclusion of a current simulation round a concluding local time and a list of scheduled events, along with their associated timestamps, that were sent to the another logical process during the current simulation round.