Methods and apparatus to perform process placement for distributed applications

• US 7,644,142 B2
• Filed: 05/04/2006
• Issued: 01/05/2010
• Est. Priority Date: 05/04/2006
• Status: Expired due to Fees

• Current Assignee: Intel Limited (Intel Corporation)
• Original Assignee: Intel Corporation
• Inventors: Huang, Eric, Kuhn, Bob, Chen, Wenguang, Chen, Hu
• Primary Examiner(s): SALAD, ABDULLAHI ELMI
• Application Number:
  US11/418,311
• Publication Number:
  US 20070260668A1
• Time in Patent Office: 1,342 Days
• Field of Search: 709220-224, 717121-133
• US Class Current: 709/220
• CPC Class Codes: H04L 41/5009 Determining service level performance parameters or violations of service level contracts, e.g. violations of agreed response time or mean time between failures [MTBF]
• CPC Class Codes: H04L 41/5096 wherein the managed service relates to distributed or central networked applications
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/60 Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources admission control or resource allocation H04L47/70

Abstract

Methods and apparatus to perform process placement for distributed applications are disclosed. An example method comprises determining a mapping between a communication graph representative of communications of a distributed application and a topology graph representative of communication costs associated with a computing network, and executing the distributed application with the processes of the distributed application assigned to the processing entities of the computing network based upon the mapping.

Claims

1. A computer implemented method comprising:

determining a mapping between a communication graph representative of communications of a distributed application and a topology graph representative of communication costs associated with a computing network;

determining a size of the communication graph;

determining a size of the topology graph;

inserting a dummy vertex into the communication graph if the size of the communication graph is smaller than the size of the topology graph;

inserting a dummy vertex into the topology graph if the size of the topology graph is smaller than the size of the communication graph; and

executing the distributed application with processes of the distributed application assigned to computing nodes of the computing network based upon the mapping.

2. A method as defined in claim 1, wherein the communications represent at least one of a number of bytes transmitted, a number of messages transmitted, a message delay, or a message latency between pairs of processes of the distributed application.

3. A method as defined in claim 1, further comprising profiling the distributed application to determine the communication graph.

4. A method as defined in claim 3, wherein the profiling is done while the distributed application is executing.

5. A method as defined in claim 3, further comprising using at least one of a trace collector or a messaging passing interface (MPI) library to profile the distributed application.

6. A method as defined in claim 1, wherein the communication costs represent at least one of a bandwidth or a latency between pairs of processing entities of the computing network.

7. A method as defined in claim 6, further comprising using at least one of a messaging passing interface (MPI) parallel ping-pong tool, a trace collector, or an MPI library to measure the at least one of the bandwidth or the latency.

8. A method as defined in claim 1, further comprising:

creating an initial mapping of the communication graph to the topology graph;

calculating a cost associated with the initial mapping; and

changing a component of the initial mapping if the change results in a lower cost associated with the changed mapping.

9. A method as defined in claim 8, further comprising changing a component of the changed mapping if the change results in a lower cost.

10. A method as defined in claim 8, wherein changing a component of the initial mapping switches a mapping of a first process and a second process.

11. A method as defined in claim 8, wherein a cost associating with a particular mapping of the communication graph to the topology graph is a function of costs associating a plurality of mappings of two processes of the distributed application to two processing entities of the computing network that form the mapping.

12. A method as defined in claim 11, wherein a cost associated with a mapping of two processes of the distributed application to two processing entities of the computing network is computed by multiplying a first number representative of an amount of communications between the two processes with a second number representative of a communication cost between the two processing entities.

13. An apparatus comprising:

a memory to store a communication graph representative of communication requirements for a distributed application, and to store a topology graph representative of communication costs associated with a computing network; and

a graph mapper to;

assign processes of the distributed application to processing entities of the computing network by mapping the communication graph to the topology graph to minimize a cost associated with the mapping;

determine a size of the communication graph;

determine a size of the topology graph;

insert a dummy vertex into the communication graph if the size of the communication graph is smaller than the size of the topology graph; and

insert a dummy vertex into the topology graph if the size of the topology graph is smaller than the size of the communication graph.

14. An apparatus as defined in claim 13, further comprising:

a communication profiler to determine the communication graph; and

a network profiler to determine the topology graph.

15. An apparatus as defined in claim 13, further comprising a performance profiler to measure the performance of the distributed application.

16. An apparatus as defined in claim 13, wherein the communications requirements represent at least one of a number of bytes or a number of messages transmitted between pairs of processes of the distributed application.

17. An apparatus as defined in claim 13, wherein the communication profiler uses at least one of a trace collector or a messaging passing interface (MPI) library to profile the distributed application, and the distributed application is profiled while the distributed application is executing.

18. An apparatus as defined in claim 13, wherein the communication costs represent at least one of a bandwidth or a latency between pairs of processing entities of the computing network.

19. An apparatus as defined in claim 18, wherein the network profiler uses a messaging passing interface (MPI) parallel ping-pong tool to measure the at least one of the bandwidth or the latency.

20. An apparatus as defined in claim 13, wherein the graph mapper is configured to:

create an initial mapping of the communication graph to the topology graph;

calculate a cost associated with the initial mapping; and

change a component of the initial mapping if the change results in a lower cost associated with the changed mapping.

21. An apparatus as defined in claim 20, wherein changing a component of the initial mapping switches a mapping of a first process and a second process.

22. An apparatus as defined in claim 20, wherein a cost associating with a particular mapping of the communication graph to the topology graph is a sum of costs associated with a plurality of mappings of two processes of the distributed application to two processing entities of the computing network that form the mapping, and a cost associated with a mapping of two processes of the distributed application to two processing entities of the computing network is computed by multiplying a first number representative of an amount of a communication requirement between the two processes with a second number representative of a communication cost between the two processing entities.

23. An article of manufacture storing machine accessible instructions which, when executed, cause a machine to:

obtain a communication graph for a distributed application;

obtain a topology graph for a computing network;

determine a size of the communication graph;

determine a size of the topology graph;

insert a dummy vertex into the communication graph if the size of the communication graph is smaller than the size of the topology graph;

insert a dummy vertex into the topology graph if the size of the topology graph is smaller than the size of the communication graph; and

iteratively and randomly map the communication graph to the topology graph to select a process-to-node map to reduce an overall communication cost of the distributed application when executed on the computing network, wherein randomly mapping increases the likelihood of an overall communication cost minimum.

24. An article of manufacture as defined in claim 23, wherein the machine accessible instructions, when executed, cause the machine to execute the distributed application on the computing network based on the selected process-to-node map.

25. An article of manufacture as defined in claim 23, wherein the machine accessible instructions, when executed, cause the machine to profile the distributed application to determine the communication graph.

26. An article of manufacture as defined in claim 25, wherein the profiling is done while the distributed application is executing.

27. An article of manufacture as defined in claim 23, wherein the machine accessible instructions, when executed, cause the machine to iteratively map the communication graph to the topology graph to select a process-to-node map by:

creating an initial mapping of the communication graph to the topology graph;

calculating a cost associated with the initial mapping; and

changing a component of the initial mapping if the change results in a lower cost associated with the changed mapping.