Method and system for predicting communication delays of detailed application workloads

• US 6,925,431 B1
• Filed: 08/04/2000
• Issued: 08/02/2005
• Est. Priority Date: 06/06/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Papaefstathiou, Efstathios
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): SHARON, AYAL I
• Application Number:
  US09/632,522
• Time in Patent Office: 1,824 Days
• Field of Search: 703/22, 703/17, 703/21, 718/100, 718/102, 709/223
• US Class Current: 703/17
• CPC Class Codes: G06F 11/3447 Performance evaluation by modeling
• CPC Class Codes: G06F 2201/86 Event-based monitoring
• CPC Class Codes: G06F 30/33 Design verification, e.g. functional simulation or model checking

Abstract

A method and system for generating a communication model are disclosed. The communication model is used to provide performance information on the use of communication networks by application code. The expected utilization of resources is important to when high performance is to be achieved in both cluster computing environments and information power GRIDs.

The disclosed method and system is designed to generate a model of an underlying network topology using detailed workload information, which encapsulates the expected computation/communication requirements of an application. Such workload information may be obtained from a number of different sources. Furthermore, the disclosed method provides detailed information of the expected use of a network system unlike traditional communication models that rely on statistical information and provide general performance information.

The disclosed method is a hybrid model containing statistical model information as well as steps for simulating the main stages that change the state of the communication network traffic. As such, the evaluation time is orders of magnitude quicker than traditional methods, while providing predictions, which are of reasonable accuracy. The characteristics of different networks can be easily incorporated into the model, and thus the model can be used in a variety of situations. The output of the model is the expected delay of a set of communications, which can be further, expanded into a suitable trace format and visualized for further investigation. In evaluation tests, the disclosed method and system provides predictions which are more accurate than simple regression models while requiring seconds of CPU processing time.

Claims

1. A method for generating a delay model in a networked system under a defined workload, the method comprising:

generating, for a first active message, a routing structure based upon a network configuration and a source network node and destination network node of the active message;

creating a contention structure created by summing together routing structure elements for active message events;

first calculating, for the first active message, an available bandwidth for use by the message at a path between network nodes utilized by the active message, the available bandwidth being a function of a level of contention between the first active message and at least a second active message on the path, the level of contention being determined in accordance with the contention structure and the routing structure for the first active message; and

second calculating, for the first active message, based upon the available bandwidth, a modeled communication delay to communicate at least a portion of the first active message.

2. The method of claim 1 further comprising:

rendering a set of delay values corresponding to a set of active events; and

identifying an event horizon corresponding to a simulated time duration before an event state change.

3. The method of claim 2 further comprising:

advancing a simulation clock based upon the event horizon; and

third calculating completed portions of each one of the set of active events based upon the event horizon.

4. The method of claim 3 wherein the event state change corresponds to a message event state change, and further comprising the steps of:

fourth calculating an updated contention structure in accordance with the message event state change and a present set of active message events after the advancing step;

rendering a new set of delay values corresponding to the present set of active events in accordance with the updated contention structure and remaining portions of the present set of active events; and

determining a next event horizon in accordance with the new set of delay values.

5. The method of claim 2 wherein the event state change corresponds to a completed active event, and further comprising the step of recording within an output trace record an entry corresponding to the completed active event.

6. The method of claim 1 wherein the routing structure comprises an array.

7. The method of claim 1 wherein the contention structure comprises an array.

8. The method of claim 1 further comprising generating a statistical summary of completed events based upon simulated time durations.

9. The method of claim 1 further comprising the step of processing an input trace sequence to render a set of events including the first active message.

10. The method of claim 9 wherein the input trace sequence is rendered by a translator of a workload definition.

11. A computer system including executable program code for generating a delay model in a networked system under a defined workload, the computer system comprising:

an input stage that receives a workload description and renders event sequences corresponding to the workload description; and

an evaluation stage that receives the event sequences and renders timing information representing execution of the event sequences in a distributed processing network configuration, the evaluation stage comprising executable program instructions for;

generating for a first active message, a routing structure based upon a network configuration and a source network node and destination network node of the first active message;

creating a contention structure created by summing together routing structure elements for active message events;

first calculating, for the first active message, an available bandwidth for use by the message at a path between network nodes utilized by the first active message, the available bandwidth being a function of a level of contention between the first active message and at least a second active message on the path, the level of contention being determined in accordance with the contention structure and the routing structure for the first active message; and

second calculating, for the first active message, based upon the available bandwidth, a modeled communication delay to communicate at least a portion of the first active message.

12. The computer system of claim 11 wherein the evaluation stage further comprises executable program instructions for:

rendering a set of delay values corresponding to a set of active events; and

identifying an event horizon corresponding to a simulated time duration before an event state change.

13. The computer system of claim 12 wherein the evaluation stage further comprises executable program instructions for:

advancing a simulation clock based upon the event horizon; and

third calculating completed portions of each one of the set of active events based upon the event horizon.

14. The computer system of claim 13 wherein the event state change corresponds to a message event state change, and the evaluation stage further comprises executable program instructions for:

fourth calculating an updated contention structure in accordance with the message event state change and a present set of active message events after the advancing step;

rendering a new set of delay values corresponding to the present set of active events in accordance with the updated contention structure and remaining portions of the present set of active events; and

determining a next event horizon in accordance with the new set of delay values.

15. The computer system of claim 12 wherein the event state change corresponds to a completed active event, and the evaluation stage further comprises executable program instructions for recording within an output trace record an entry corresponding to the completed active event.

16. The computer system of claim 11 wherein the routing structure comprises an array.

17. The computer system of claim 11 wherein the contention structure comprises an array.

18. The computer system of claim 11 further comprising a post output stage for receiving data corresponding to the timing information rendered by the evaluation stage, and generating a statistical summary of completed events based upon simulated time durations.

19. The computer system of claim 11 wherein the input stage comprises executable code facilitating processing an input trace sequence to render a set of events including the first active message.

20. The computer system of claim 19 wherein the input trace sequence is rendered by a translator of a workload definition.

21. A computer-readable medium having computer executable instructions for performing a set of steps to generate a delay model in a networked system under a defined workload, the steps including:

generating, for a first active message, a routing structure based upon a network configuration and a source network node and destination network node of the first active message;

creating a contention structure created by summing together routing structure elements for active message events;

first calculating, for the first active message, an available bandwidth for use by the message at a path between network nodes utilized by the first active message, the available bandwidth being a function of a level of contention between the first active message and at least a second active message on the path, the level of contention being determined in accordance with the contention structure and the routing structure for the first active message; and

second calculating, for the first active message, based upon the available bandwidth, a modeled communication delay to communicate at least a portion of the first active message.

22. The computer-readable medium of claim 21 further comprising computer executable instructions for performing the steps of:

rendering a set of delay values corresponding to a set of active events; and

identifying an event horizon corresponding to a simulated time duration before an event state change.

23. The computer-readable medium of claim 22 further comprising computer executable instructions for performing the steps of:

advancing a simulation clock based upon the event horizon; and

third calculating completed portions of each one of the set of active events based upon the event horizon.

24. The computer-readable medium of claim 23 further comprising computer executable instructions for performing the steps of:

fourth calculating an updated contention structure in accordance with the message event state change and a present set of active message events after the advancing step;

rendering a new set of delay values corresponding to the present set of active events in accordance with the updated contention structure and remaining portions of the present set of active events; and

determining a next event horizon in accordance with the new set of delay values.

25. The computer-readable medium of claim 22 wherein the event state change corresponds to a completed active event, and further comprising executable instructions for performing the step of recording within an output trace record an entry corresponding to the completed active event.

26. The computer-readable medium of claim 21 wherein the routing structure comprises an array.

27. The computer-readable medium of claim 21 wherein the contention structure comprises an array.

28. The computer-readable medium of claim 21 further comprising executable instructions for performing the step of generating a statistical summary of completed events based upon simulated time durations.

29. The computer-readable medium of claim 21 further comprising computer executable instructions for performing the step of processing an input trace sequence to render a set of events including the first active message.

30. The computer-readable medium of claim 29 wherein the input trace sequence is rendered by a translator of a workload definition.

31. A computer system including executable program code for generating a delay model in a networked system under a defined workload, the computer system comprising:

an input stage that receives a workload description and renders event sequences corresponding to the workload description; and

an evaluation stage that receives the event sequences and renders timing information representing execution of the event sequences in a distributed processing network configuration, the evaluation stage comprising;

a routing structure generator for generating, for a first active message, a routing structure based upon a network configuration and a source network node and destination network node of the first active message;

a contention structure generator for creating a contention structure by summing together routing structure elements for active message events;

a bandwidth availability calculator for first calculating, for the first active message, an available bandwidth for use by the message at a path between network nodes utilized by the first active message, the available bandwidth being a function of a level of contention between the first active message and at least a second active message on the path, the level of contention being determined in accordance with the contention structure and the routing structure for the first active message; and

a delay calculator for second calculating, for the first active message, based upon the available bandwidth, a modeled communication delay to communicate at least a portion of the first active message.