Backfill scheduling of applications based on data of the applications

• US 7,331,048 B2
• Filed: 04/04/2003
• Issued: 02/12/2008
• Est. Priority Date: 04/04/2003
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Skovira, Joseph F.
• Primary Examiner(s): Thomson; William
• Assistant Examiner(s): Anya; Charles E
• Application Number:
  US10/406,985
• Publication Number:
  US 20040199918A1
• Time in Patent Office: 1,775 Days
• Field of Search: 709201-207, 709216-219, 709/226, 709/229, 709/233, 709/235, 719/311, 718100-108, 707/10, 707201-206
• US Class Current: 718/102
• CPC Class Codes: G06F 2209/506 Constraint
• CPC Class Codes: G06F 2209/509 Offload
• 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
• CPC Class Codes: H04L 67/62 Establishing a time schedule for servicing the requests

Abstract

Backfill scheduling techniques are used to schedule execution of applications, either on a local computing unit or a remote unit. In determining whether a particular application is to be scheduled to execute on a local unit or a remote unit, the data associated with that application is considered. As examples, an amount of data to be moved, availability of communication channels, and/or availability of remote data storage resources are considered.

Claims

1. A method of facilitating backfill scheduling of applications of a computing environment, said method comprising:

determining on which computing unit of a plurality of computing units of the computing environment an application is to be scheduled to execute, the application having an amount of data associated therewith, said determining being based, at least in part, on the amount of data of associated with the application;

backfill scheduling the application for execution, in response to the determining;

wherein the plurality of computing units comprise a local unit and a remote unit;

wherein the determining comprises considering an estimated amount of time it would take to transfer the data to the remote unit and determining whether the application is to be scheduled on the local unit or the remote unit; and

applying an adjustment to the estimated amount of time considered to provide an adjusted amount of time, and wherein the determining comprises considering the adjusted amount of time, wherein the adjust amount of time is the estimated amount of time plus a percentage of the estimated amount of time.

2. The method of claim 1, wherein the determining comprises considering availability of one or more communication channels between at least a portion of the computing units of the plurality of computing units.

3. The method of claim 1, wherein determining comprises considering availability of one or more storage resources of the remote unit in determining whether the application is to be scheduled on the local unit or the remote unit.

4. The method of claim 1, further comprising applying an adjustment to the amount of time considered to provide an adjusted amount of time, and wherein the determining comprises considering the adjusted amount of time, wherein the adjusted amount of time is a shadow time on the remote unit when the shadow time is greater than the estimated amount of time it would take to transfer the data to the remote unit, the shadow time indicating how long the application will need to wait for reQuired resources to execute on the remote unit.

5. The method of claim 1, wherein said determining comprises:

determining a remote completion time of the application, the remote completion time being the sum of a remote shadow time for execution of the application on the remote unit, an estimated time for executing the application on the remote unit, and a resultant transfer time required to return application execution results from the remote unit to the local unit, wherein the remote shadow time is the greater of a shadow time on the remote unit and the estimated amount of time it would take to transfer the data associated with the application from the local unit to the remote unit;

determining a local completion time of the application on the local unit, the local completion time being the sum of a local shadow time and an estimated time for execution of the application on the local unit;

comparing the remote completion time and the local completion time; and

selecting the computing unit in which the application is to be scheduled to execute, in response to the comparing, wherein the selected computing unit is one of the local unit and the remote unit.

6. The method of claim 5, further comprising determining whether remote storage is available, and wherein the selecting is further in response to the determining of the remote storage.

7. A system of facilitating backfill scheduling of applications of a computing environment, said system comprising:

means for determining on which computing unit of a plurality of computing units of the computing environment an application is to be scheduled to execute, the application having an amount of data associated therewith, said determining being based, at least in part, on the amount of data of associated with the application;

means for backfill scheduling the application for execution, in response to the determining;

wherein the plurality of computing units comprise a local unit and a remote unit;

wherein the means for determining comprises means for considering an estimated amount of time it would take to transfer the data to the remote unit and determining whether the application is to be scheduled on the local unit or the remote unit; and

means for applying an adjustment to the estimated amount of time considered to provide an adjusted amount of time, and wherein the means for determining comprises means for considering the adjusted amount of time, wherein the adjusted amount of time is the estimated amount of time plus a percentage of the estimated amount of time.

8. The system of claim 7, wherein the means for determining comprises means for considering availability of one or more communication channels between at least a portion of the computing units of the plurality of computing units.

9. The system of claim 7, wherein the determining comprises considering availability of one or more storage resources of the remote unit in determining whether the application is to be scheduled on the local unit or the remote unit.

10. The system of claim 7, further comprising means for applying an adjustment to the amount of time considered to provide an adjusted amount of time, and wherein the means for determining comprises means for considering the adjusted amount of time, wherein the adjusted amount of time is a shadow time on the remote unit when the shadow time is greater than the estimated amount of time it would take to transfer the data to the remote unit, the shadow time indicating how long the application will need to wait for required resources to execute on the remote unit.

11. The system of claim 7, wherein said means for determining comprises:

means for determining a remote completion time of the application, the remote completion time being the sum of a remote shadow time for execution of the application on the remote unit, an estimated time for executing the application on the remote unit, and a resultant transfer time required to return application execution results from the remote unit to the local unit, wherein the remote shadow time is the greater of a shadow time on the remote unit and the estimated amount of time it would take to transfer the data associated with the application from the local unit to the remote unit;

means for determining a local completion time of the application on the local unit, the local completion time being the sum of a local shadow time and an estimated time for execution of the application on the local unit;

means for comparing the remote completion time and the local completion time; and

means for selecting the computing unit in which the application is to be scheduled to execute, in response to the comparing, wherein the selected computing unit is one of the local unit and the remote unit.

12. The system of claim 11, further comprising means for determining whether remote storage is available, and wherein the means for selecting is further in response to the determining of the remote storage.

13. At least one program storage device readable by a machine, tangibly embodying at least one program of instructions executable by the machine to perform a method of facilitating backfill scheduling of applications of a computing environment, said method comprising:

determining on which computing unit of a plurality of computing units of the computing environment an application is to be scheduled to execute, the application having an amount of data associated therewith, said determining being based, at least in part, on the amount of data of associated with the application;

backfill scheduling the application for execution, in response to the determining;

wherein the plurality of computing units comprise a local unit and a remote unit;

wherein the determining comprises considering an estimated amount of time it would take to transfer the data to the remote unit and determining whether the application is to be scheduled on the local unit or the remote unit and

applying an adjustment to the estimated amount of time considered to provide an adjusted amount of time, and wherein the determining comprises considering the adjusted amount of time, wherein the adjust amount of time is the estimated amount of time plus a percentage of the estimated amount of time.

14. The at least one program storage device of claim 13, wherein the determining comprises considering availability of one or more communication channels between at least a portion of the computing units of the plurality of computing units.

15. The at least one program storage device of claim 13, further comprising applying an adjustment to the estimated amount of time considered to provide an adjusted amount of time, and wherein the determining comprises considering the adjusted amount of time, wherein the adjusted amount of time is a shadow time on the remote unit when the shadow time is greater than the estimated amount of time it would take to transfer the date to the remote unit, the shadow time indicating how long the application will need to wait for reciuired resources to execute on the remote unit.