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

• US 8,589,944 B2
• Filed: 03/16/2005
• Issued: 11/19/2013
• Est. Priority Date: 03/16/2005
• Status: Expired due to Fees

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Productions Print Solutions LLC
• Inventors: Haller, Michael, Mitchell, Joan L., Rijavec, Nenad, Smith, James T. II
• Primary Examiner(s): Truong, Lechi
• Application Number:
  US11/083,384
• Publication Number:
  US 20060212875A1
• Time in Patent Office: 3,170 Days
• Field of Search: 718/105, 718/100, 719/310, 710/100, 710/105
• US Class Current: 719/310
• 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 improving performance of computing a task comprised of a plurality of sub-tasks in a heterogeneous computing (HC) system comprising a plurality of machines, the method comprising:

assigning each of the sub-tasks to one of the machines for processing;

estimating a time period for each of the machines to process the assigned sub-tasks;

identifying a first machine having a longest estimated time period to process the assigned sub-tasks;

selecting at least one of the assigned sub-tasks for the first machine for re-assignment;

identifying a second machine capable of processing the selected sub-task and previously assigned sub-tasks in less time than the longest estimated time period for the first machine;

re-assigning the selected sub-task from the first machine to the second machine for processing;

determining if the first machine still has the longest estimated time period after re-assigning the selected sub-task;

identifying another machine as having a longest estimated time period when the first machine no longer has the longest estimated time period; and

repetitively performing the steps of estimating the time period, identifying a first machine, selecting an assigned sub-task, identifying a second machine, and re-assigning the selected sub-task until no machine is identified that is capable of processing the selected sub-task and previously assigned sub-tasks in less time than the longest estimated time period for the first machine.

2. A system for improving performance of computing a task comprised of a plurality of sub-tasks in a heterogeneous computing (HC) environment, the system comprising:

a network of heterogeneous computing systems comprising a plurality of machines operable to process the sub-tasks; and

a processing system operable to assign each of the sub-tasks to one of the machines for processing, to estimate a time period for each of the machines to process the assigned sub-tasks, to identify a first machine having a longest estimated time period to process the assigned sub-tasks, to select at least one of the assigned sub-tasks for the first machine for re-assignment, to identify a second machine capable of processing the selected sub-task and previously assigned sub-tasks in less time than the longest estimated time period for the first machine, to re-assign the selected sub-task from the first machine to the second machine for processing, to determine if the first machine still has the longest estimated time period after the re-assignment of the selected sub-task, to identify another machine as a having a longest estimated time period when the first machine no longer has the longest estimated time period, and to repetitively estimate a time period, identify a first machine, select an assigned sub-task, identify a second machine, and re-assign the selected sub-task until no machine is identified that is capable of processing the selected sub-task and previously assigned sub-tasks in less time than the longest estimated time period for the first machine.

3. A non-transitory computer readable medium tangibly embodying programmed instructions which, when executed by a computing system, are operable for performing a method of improving performance of computing a task comprised of a plurality of sub-tasks in a heterogeneous computing (HC) system comprising a plurality of machines, the method comprising:

assigning each of the sub-tasks to one of the machines for processing;

estimating a time period for each of the machines to process the assigned sub-tasks;

identifying a first machine having a longest estimated time period to process the assigned sub-tasks;

selecting at least one of the assigned sub-task for the first machine for re-assignment;

identifying a second machine capable of processing the selected sub-task and previously assigned sub-tasks in less time than the longest estimated time period for the first machine;

re-assigning the selected sub-task from the first machine to the second machine for processing;

determining if the first machine still has the longest estimated time period after re-assigning the selected sub-task;

identifying another machine as a having a longest estimated time period when the first machine no longer has the longest estimated time period; and

repetitively performing the steps of estimating a time period, identifying a first machine, selecting an assigned sub-task, identifying a second machine, and re-assigning the selected sub-task until no machine is identified that is capable of processing the selected sub-task and previously assigned sub-tasks in less time than the longest estimated time period for the first machine.