Traversing runtime spanning trees

• US 20070130219A1
• Filed: 11/08/2005
• Published: 06/07/2007
• Est. Priority Date: 11/08/2005
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Zheng, Lin, Shiding, Guo, Rui
• Application Number:
  US11/269,131
• Publication Number:
  US 20070130219A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 41/00 Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network

Abstract

The traversal of runtime spanning trees is facilitated in a distributed operational environment. Distributed traversal of runtime spanning trees may be implemented in different scenarios. However, by way of example only, distributed traversal of runtime spanning trees is described herein primarily in the context of a distributed system simulation scenario. Ensuring that each unscheduled event is processed within a simulation round (i.e., within a quantum barrier) in which it is created is especially challenging when executing an operation (e.g., performing a simulation) with a distributed apparatus. To address this challenge, unscheduled events are set to correspond to event nodes in a tree. Parent events that beget child events are assigned token values. The token value of a parent event is split and assigned to its child events such that a runtime spanning tree may be distributively traversed by summing the token values of leaf nodes of the spanning tree.

Claims

1. A method comprising:

creating a child event from a parent event;

halving a current token value of the parent event; and

assigning half the current token value of the parent event to the child event.

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

recording the current token value half assigned to the child event in an exponential variable format.

3. The method as recited in claim 2, wherein the exponential variable format uses an integer variable to represent a fractional token value.

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

setting a new current token value for the parent event to equal half the current token value of the parent event.

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

creating another child event from the parent event;

halving the new current token value of the parent event; and

assigning half the new current token value of the parent event to the other child event.

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

sending the child event, along with the current token value half assigned to the child event, to a destination logical process.

7. The method as recited in claim 6, wherein the destination logical process is executing on a destination slave device;

and wherein the sending is performed prior to creation of another child event.

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

creating another child event from the parent event;

determining if the other child event is a final child event for the parent event; and

if the other child event is determined to be the final child event for the parent event, assigning a remaining half of the current token value of the parent event to the other child event.

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

receiving token reports from leaf event nodes;

accumulating token values from the received token reports;

determining if a total of the accumulated token values matches a predetermined total value; and

if the total of the accumulated token values is determined to match the predetermined total value, ascertaining that all unscheduled events have been processed.

10. One or more processor-accessible media comprising processor-executable instructions that implement a logical process to perform an operation with at least part of a distributed apparatus;

the logical process capable of creating one or more child events from a parent event that is associated with a token value;

wherein the logical process is adapted to split the token value of the parent event and assign split token values to the one or more child events.

11. The one or more processor-accessible media as recited in claim 10, wherein the one or more child events comprise unscheduled events that are to be processed in a round in which the logical process creates them.

12. The one or more processor-accessible media as recited in claim 10, wherein the split token values assigned to the one or more child events are equal to each other;

and wherein each split token value is equivalent to the token value of the parent event divided by a total number of the one or more child events.

13. The one or more processor-accessible media as recited in claim 10, wherein the split token values assigned to the one or more child events are determined by halving a current amount of the token value of the parent event and by contemporaneously assigning to each child event one-half of the current value of the token value upon creation of each child event.

14. The one or more processor-accessible media as recited in claim 10, wherein the split token values assigned to the one or more child events are fractional values;

and wherein the fractional values are represented by integers using an exponential variable format.

15. The one or more processor-accessible media as recited in claim 10, wherein the operation comprises a simulation of a distributed system;

and wherein the simulation of the distributed system uses a simulation window that exceeds a global lookahead of the distributed system.

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

a slave device to create child event nodes corresponding to unscheduled events and to assign token values to the child event nodes by splitting token values of parent event nodes.

17. The apparatus as recited in claim 16, wherein the token values comprise fractions that are represented as integers that are part of an exponential variable format.

18. The apparatus as recited in claim 16, wherein the slave device assigns one-half of a token value of a parent event node to a first child event node and one-fourth of the token value of the parent event node to a second child event node.

19. The apparatus as recited in claim 18, wherein the apparatus comprises a distributed apparatus;

the apparatus further comprising;

a master; and

another slave device;

wherein the slave device sends a first child event corresponding to the first child event node and the one-half of the token value of the parent node to the other slave device; and

wherein the other slave device reports the one-half of the token value of the parent node to the master after processing the first child event.

20. The apparatus as recited in claim 19, wherein the master adds the one-half of the token value of the parent node to a token report accumulation total;

and wherein the master ascertains that all of the unscheduled events are completed when the token report accumulation total equals a predetermined total value.