Resource aware scheduling in a distributed computing environment

• US 9,201,690 B2
• Filed: 10/21/2011
• Issued: 12/01/2015
• Est. Priority Date: 10/21/2011
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Meng, Xiaoqiao, Tan, Jian, Zhang, Li
• Primary Examiner(s): KESSLER, GREGORY AARON
• Application Number:
  US13/278,383
• Publication Number:
  US 20130104140A1
• Time in Patent Office: 1,502 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

Systems and methods for resource aware scheduling of processes in a distributed computing environment are described herein. One aspect provides for accessing at least one job and at least one resource on a distributed parallel computing system; generating a current reward value based on the at least one job and a current value associated with the at least one resource; generating a prospective reward value based on the at least one job and a prospective value associated with the at least one resource at a predetermined time; and scheduling the at least one job based on a comparison of the current reward value and the prospective reward value. Other embodiments and aspects are also described herein.

Claims

1. A computer program product comprising:

a computer-readable storage medium having computer-readable program code embodied therewith, the computer-readable program code comprising;

computer-readable program code configured to access at least one multi-stage job and at least one resource on a distributed parallel computing system;

computer-readable program code configured to generate a current reward value based on the at least one job and a current value associated with the at least one resource;

computer-readable program code configured to launch a first stage of at least one job, based on the current reward value;

computer-readable program code configured to generate a prospective reward value based on the at least one job and a prospective value associated with the at least one resource at a predetermined time; and

computer-readable program code configured to schedule a second stage of at least one job based on a comparison of the current reward value and the prospective reward value.

2. The computer program product according to claim 1, wherein the current reward value and the prospective reward value may be augmented by at least one performance characteristic.

3. The computer program product according to claim 2, wherein the at least one performance characteristic comprises fairness and promptitude.

4. The computer program product according to claim 1, wherein the at least one job comprises a signature having at least one resource requirement measurement.

5. The computer program product according to claim 4, wherein the at least one resource requirement measurement comprises CPU percentage and memory percentage.

6. The computer program product according to claim 5, further comprising:

computer-readable program code configured to generate a job fitness value for the at least one job based on the CPU percentage and memory percentage;

wherein the job fitness value augments the current reward value to characterize how the at least one job fits the at least one resource.

7. The computer program product according to claim 1, wherein scheduling the at least one job based on a comparison of the current reward value and the prospective reward value comprises immediately scheduling the at least one job responsive to the current reward value being greater than the prospective reward plus a tuning factor.

8. The computer program product according to claim 7, further comprising delaying a scheduling of the at least one job responsive to the prospective reward plus the tuning factor being greater than the current reward value.

9. The computer program product according to claim 1, wherein the distributed parallel computing system employs a MapReduce model.

10. The computer program product according to claim 9, wherein the at least one job comprises at least one map task and at least one reduce task.

11. The computer program product according to claim 10, wherein scheduling further comprises associating a progress corresponding with the at least one map task with a progress corresponding with the at least one reduce task.

12. The computer program product according to claim 11, wherein a percentage of the at least one reduce task is scheduled responsive to completion of the percentage of the at least one map task.

13. A method comprising:

accessing at least one multi-stage job and at least one resource on a distributed parallel computing system;

generating a current reward value based on the at least one job and a current value associated with the at least one resource;

launching a first stage of at least one job, based on the current reward value;

generating a prospective reward value based on the at least one job and a prospective value associated with the at least one resource at a predetermined time; and

scheduling a second stage of at least one job based on a comparison of the current reward value and the prospective reward value.

14. The method according to claim 13, wherein the current reward value and the prospective reward value may be augmented by at least one performance characteristic.

15. The method according to claim 14, wherein the at least one performance characteristic comprises fairness and promptitude.

16. The method according to claim 13, wherein the at least one job comprises a signature having at least one resource requirement measurement.

17. The method according to claim 16, wherein the at least one resource requirement measurement comprises CPU percentage and memory percentage.

18. The method according to claim 17, further comprising:

generating a job fitness value for the at least one job based on the CPU percentage and memory percentage;

wherein the job fitness value augments the current reward value to characterize how the at least one job fits the at least one resource.

19. The method according to claim 13, wherein scheduling the at least one job based on a comparison of the current reward value and the prospective reward value comprises immediately scheduling the at least one job responsive to the current reward value being greater than the prospective reward plus a tuning factor.

20. The method according to claim 19, further comprising delaying a scheduling of the at least one job responsive to the prospective reward plus the tuning factor being greater than the current reward value.

21. The method according to claim 13, wherein the distributed parallel computing system employs a MapReduce model.

22. The method according to claim 21, wherein the at least one job comprises at least one map task and at least one reduce task.

23. The method according to claim 22, wherein scheduling further comprises associating a progress corresponding with the at least one map task with a progress corresponding with the at least one reduce task.

24. The method according to claim 23, wherein a percentage of the at least one reduce task is scheduled responsive to completion of the percentage of the at least one map task.

25. A system comprising:

at least one processor; and

a memory device operatively connected to the at least one processor;

wherein, responsive to execution of program instructions accessible to the at least one processor, the at least one processor is configured to;

access at least one multi-stage job and at least one resource on a distributed parallel computing system;

generate a current reward value based on the at least one job and a current value associated with the at least one resource;

launch a first stage of at least one job, based on the current reward value;

generate a prospective reward value based on the at least one job and a prospective value associated with the at least one resource at a predetermined time; and

schedule a second stage of at least one job based on a comparison of the current reward value and the prospective reward value.