System and Method for Hardware Based Dynamic Load Balancing of Message Passing Interface Tasks

• US 20090064166A1
• Filed: 08/28/2007
• Published: 03/05/2009
• Est. Priority Date: 08/28/2007
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Arimilli, Ravi K., Rajamony, Ramakrishnan, Arimilli, Lakshminarayana B., Speight, William E.
• Application Number:
  US11/846,141
• Publication Number:
  US 20090064166A1
• Time in Patent Office: Days
• US Class Current: 718/105
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: G06F 9/522 Barrier synchronisation

Abstract

A system and method for providing hardware based dynamic load balancing of message passing interface (MPI) tasks are provided. Mechanisms for adjusting the balance of processing workloads of the processors executing tasks of an MPI job are provided so as to minimize wait periods for waiting for all of the processors to call a synchronization operation. Each processor has an associated hardware implemented MPI load balancing controller. The MPI load balancing controller maintains a history that provides a profile of the tasks with regard to their calls to synchronization operations. From this information, it can be determined which processors should have their processing loads lightened and which processors are able to handle additional processing loads without significantly negatively affecting the overall operation of the parallel execution system. As a result, operations may be performed to shift workloads from the slowest processor to one or more of the faster processors.

Claims

1. A method, in a multiple processor system, for balancing a Message Passing Interface (MPI) workload across a plurality of processors, comprising:

receiving one or more MPI synchronization operation calls from one or more processors of the plurality of processors;

identifying a first processor, in the plurality of processors, having a fastest time of completion of a computation phase of a first associated MPI task based on the received one or more MPI synchronization operation calls;

identifying a second processor, in the plurality of processors, having a slowest time of completion of a computation phase of a second associated MPI task based on the received one or more MPI synchronization operation calls; and

modifying a first amount of data to be processed by the first processor in executing the first associated MPI task in a next computation cycle to thereby increase the amount of data.

2. The method of claim 1, further comprising:

modifying a second amount of data to be processed by the second processor in executing the second associated MPI task in the next computation cycle to thereby decrease the amount of data.

3. The method of claim 1, wherein the MPI job is a set of tasks to be performed in parallel on the plurality of processors, and wherein each processor of the plurality of processors executes a corresponding task of the MPI job in parallel on a corresponding set of data allocated to the processor from a superset of data.

4. The method of claim 2, further comprising:

determining if a difference in the fastest time of completion and the slowest time of completion exceeds a threshold, wherein modifying the first amount of data and modifying the second amount of data are performed in response to the difference exceeding the threshold.

5. The method of claim 2, wherein at least one of modifying the first amount of data or modifying the second amount of data comprises:

determining an offset to at least an ending address of a portion of data to be processed, wherein when the offset modifies the ending address of the portion of data to either increase or decrease a size of the portion of data to be processed.

6. The method of claim 5, wherein the offset is determined based on a relationship between an amount of data and a difference in timestamps associated with entries in a history data structure corresponding to the first processor in the plurality of processors and the second processor in the plurality of processors.

7. The method of claim 1, further comprising:

performing one or more setup operations in the first processor of the plurality of processors for preparing to process a larger portion of data in a subsequent computation cycle than a current computation cycle, wherein the one or more setup operations are performed while other processors of the plurality of processors are executing their respective tasks of the MPI job.

8. The method of claim 7, wherein the one or more setup operations comprise at least one of allocating a larger portion of cache memory for use by the first processor, setting up buffer space to receive an additional amount of data, or acquiring a host fabric interface window or windows for communication.

9. The method of claim 2, wherein each processor of the plurality of processors comprises a MPI load balancing controller, wherein each MPI load balancing controller implements the receiving and identifying operations, an MPI load balancing controller associated with the first processor implements the operation of modifying the first amount of data, and an MPI load balancing controller associated with the second processor implements the operation of modifying the second amount of data.

10. The method of claim 2, wherein modifying the first amount of data and modifying the second amount of data comprises changing an amount of data processed by the first processor and changing an amount of data processed by the second processor in a subsequent computation cycle such that time periods for completion of MPI tasks executing on the first and second processors are brought within a tolerance of each other.

11. The method of claim 2, further comprising:

identifying at least one third processor, in the plurality of processors, having an intermediate time of completion of a computation phase of associated MPI tasks based on the received one or more MPI synchronization operation calls;

selecting one or more of the at least one third processor based on the intermediate time of completion associated with each of the one or more third processor, for receiving an increased amount of data in a subsequent computation cycle; and

modifying an amount of data to be processed by the one or more third processors in a subsequent computation cycle.

12. A computer program product comprising a computer useable medium having a computer readable program, wherein the computer readable program, when executed on a data processing system, causes the data processing system to:

receive one or more Message Passing Interface (MPI) synchronization operation calls from one or more processors of a plurality of processors;

identify a first processor, in the plurality of processors, having a fastest time of completion of a computation phase of a first associated MPI task based on the received one or more MPI synchronization operation calls;

identify a second processor, in the plurality of processors, having a slowest time of completion of a computation phase of a second associated MPI task based on the received one or more MPI synchronization operation calls; and

modify a first amount of data to be processed by the first processor in executing the first associated MPI task in a next computation cycle to thereby increase the amount of data.

13. The computer program product of claim 12, wherein the computer readable program further causes the data processing system to:

modify a second amount of data to be processed by the second processor in executing the second associated MPI task in the next computation cycle to thereby decrease the amount of data.

14. The computer program product of claim 12, wherein the MPI job is a set of tasks to be performed in parallel on the plurality of processors, and wherein each processor of the plurality of processors executes a corresponding task of the MPI job in parallel on a corresponding set of data allocated to the processor from a superset of data.

15. The computer program product of claim 13, wherein the computer readable program further causes the data processing system to:

determine if a difference in the fastest time of completion and the slowest time of completion exceeds a threshold, wherein modifying the first amount of data and modifying the second amount of data are performed in response to the difference exceeding the threshold.

16. The computer program product of claim 13, wherein the computer readable program causes the data processing system to at least one of modify the first amount of data or modify the second amount of data by:

determining an offset to at least an ending address of a portion of data to be processed, wherein when the offset modifies the ending address of the portion of data to either increase or decrease a size of the portion of data to be processed.

17. The computer program product of claim 16, wherein the offset is determined based on a relationship between an amount of data and a difference in timestamps associated with entries in a history data structure corresponding to the first processor in the plurality of processors and the second processor in the plurality of processors.

18. The computer program product of claim 13, wherein each processor of the plurality of processors comprises a MPI load balancing controller, wherein each MPI load balancing controller performs the receive and identify operations, an MPI load balancing controller associated with the first processor performs the modify operation with regard to the first amount of data, and an MPI load balancing controller associated with the second processor performs the modify operation with regard to the second amount of data.

19. The computer program product of claim 13, wherein the computer readable program causes the data processing system to modify the first amount of data and modify the second amount of data by changing an amount of data processed by the first processor and changing an amount of data processed by the second processor in a subsequent computation cycle such that time periods for completion of MPI tasks executing on the first and second processors are brought within a tolerance of each other.

20. A data processing system, comprising:

a plurality of processors; and

at least one load balancing controller associated with the plurality of processors, wherein the at least one load balancing controller balances a Message Passing Interface (MPI) workload across the plurality of processors by;

receiving one or more MPI synchronization operation calls from one or more processors of the plurality of processors;

identifying a first processor, in the plurality of processors, having a fastest time of completion of a computation phase of a first associated MPI task based on the received one or more MPI synchronization operation calls;

identifying a second processor, in the plurality of processors, having a slowest time of completion of a computation phase of a second associated MPI task based on the received one or more MPI synchronization operation calls; and

modifying a first amount of data to be processed by the first processor in executing the first associated MPI task in a next computation cycle to thereby increase the amount of data.