Method and system for task mapping to iteratively improve task assignment in a heterogeneous computing system

• US 20060212875A1
• Filed: 03/16/2005
• Published: 09/21/2006
• Est. Priority Date: 03/16/2005
• Status: Active Grant

• Current Assignee: Ricoh Company Limited
• Original Assignee: International Business Machines Corporation
• Inventors: Rijavec, Nenad, Mitchell, Joan L., Smith, James T. II, Haller, Michael
• Granted Patent: US 8,589,944 B2
• Time in Patent Office: Days
• US Class Current: 718/107
• CPC Class Codes: G06F 2209/506 Constraint
• CPC Class Codes: G06F 9/4856 resumption being on a different machine, e.g. task migration, virtual machine migration G06F9/5088 takes precedence
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups

Abstract

Method and system aspects for mapping tasks to iteratively improve task assignment in a heterogeneous computing (HC) system include identifying a current machine that defines a makespan in the HC system. Further included is the reassigning of at least one task from the current machine to at least one alternate machine in the HC system according to a predefined reassignment constraint. Reassigning also includes reassigning the at least one task when the at least one alternate machine can perform the at least one task in addition to previously assigned work while finishing in less time than the time of the makespan reduced by time required for the task being reassigned.

Claims

1. A method for mapping tasks to iteratively improve task assignment in a heterogeneous computing (HC) system, the method comprising:

identifying a current machine that defines a makespan in the HC system; and

reassigning at least one task from the current machine to at least one alternate machine in the HC system according to a predefined reassignment constraint.

2. The method of claim 1 wherein reassigning further comprises reassigning the at least one task when the at least one alternate machine can perform the at least one task in addition to previously assigned work while finishing in less time than the time of the makespan reduced by time required for the task being reassigned.

3. The method of claim 2 further comprising determining if the current machine still defines the makespan after the reassigning.

4. The method of claim 3 further comprising identifying another machine as a makespan machine when the current machine no longer defines the makespan.

5. The method of claim 4 further comprising continuing the reassigning until no more reassignments can be made that meet the predefined reassignment constraint.

6. A system for mapping tasks to iteratively improve task assignment in a heterogeneous computing (HC) environment, the system comprising:

a network of heterogeneous computing systems; and

a processing system for identifying a current machine that defines a makespan in the network, and reassigning at least one task from the current machine to at least one alternate machine in the network according to a predefined reassignment constraint.

7. The system of claim 6 wherein the processing system further reassigns the at least one task when the at least one alternate machine can perform the at least one task in addition to previously assigned work while finishing in less time than the time of the makespan reduced by time required for the task being reassigned.

8. The system of claim 7 wherein the processing system further determines if the current machine still defines the makespan after the reassigning.

9. The system of claim 8 wherein the processing system further identifies another machine as a makespan machine when the current machine no longer defines the makespan.

10. The system of claim 9 wherein the processing system further continues the reassigning until no more reassignments can be made that meet the predefined reassignment constraint.

11. A computer readable medium containing program instructions for mapping tasks to iteratively improve task assignment in a heterogeneous computing (HC) system, the program instructions comprising:

identifying a current machine that defines a makespan in the HC system; and

reassigning at least one task from the current machine to at least one alternate machine in the HC system according to a predefined reassignment constraint.

12. The computer readable medium of claim 11 wherein reassigning further comprises reassigning the at least one task when the at least one alternate machine can perform the at least one task in addition to previously assigned work while finishing in less time than the time of the makespan reduced by time required for the task being reassigned.

13. The computer readable medium of claim 12 further comprising determining if the current machine still defines the makespan after the reassigning.

14. The computer readable medium of claim 13 further comprising identifying another machine as a makespan machine when the current machine no longer defines the makespan.

15. The computer readable medium of claim 14 further comprising continuing the reassigning until no more reassignments can be made that meet the predefined reassignment constraint.