Resource and latency estimation-based scheduling in a distributed computing environment

Patent metadata

Field	Value
Publication number	US-10503548-B2
Application number	US-201615290983-A
Country	US
Kind code	B2
Filing date	Oct 11, 2016
Priority date	Oct 11, 2016
Publication date	Dec 10, 2019
Grant date	Dec 10, 2019

Abstract

A time series of metric values indicative of a cost of executing a job may be acquired. The acquired time series may be normalized to form a skyline indicative of costs incurred, over time, during an instance of executing the job. A modelled skyline may be formed by a best-fit analysis of a plurality of metric-based skylines, constrained by penalties for over-allocation and under-allocation. Based on the modelled skyline, the modelled skyline may be aligned with one or more additional modelled skylines to identify execution times for the job. The identified execution times may be selected to minimize risk of exceeding a time-to-complete parameter and avoid under-utilization of resources.

First claim

What is claimed:

1. A system for scheduling a set of tasks over a plurality of computing devices, the system comprising:
one or more processors; and
one or more memories having stored thereon computer readable instructions that, when executed by the one or more processors, cause the system to at least:
for each task of the set of tasks,
receive at least two time series in which each time series thereof is indicative of resource utilization costs associated with execution of an instance of that task by a computing device of the plurality of computing devices, and
identify a resource utilization model for that task based at least in part on a best-fit analysis of the at least two time series, to obtain a set of resource utilization models for the set of tasks;

for a workload of the set of tasks, identify a schedule for executing the set of tasks based on the resource utilization models and a selected one or more of an over-utilization constraint and an under-utilization constraint, wherein the schedule for executing the set of tasks maintains a resource utilization efficiency of executing the set of tasks of the workload within the selected one or more of the over-utilization constraint and the under-utilization constraint; and
configure one or more computing devices of the plurality of computing devices to execute the set of tasks in accordance with the schedule for the workload.

2. The system of claim 1 , wherein identifying the schedule further comprises: determining that the schedule further reduces a risk of violating a time-to-finish constraint compared to a second schedule.

3. The system of claim 1 , further comprising instructions executable to:
calculating a penalty for over-allocating the total resource utilization costs during a portion of time represented by the schedule.

4. The system of claim 1 , further comprising instructions executable to:
for a first time series of the at least two time series, split the first time series into a first portion of the first time series and a second portion of the first time series; and
schedule a first portion of the workload based at least in part on an alignment of the first portion of the first time series with the resource utilization models.

5. The system of claim 4 , wherein scheduling the first portion of the workload further comprises: reducing a risk of exceeding at least one of a time-to-finish constraint or the under-utilization constraint, compared to a second schedule.

6. The system of claim 1 , further comprising instructions executable to: determine a step function fitting a first time series of the at least two time series, based at least in part on assigning penalties for at least one of over-allocation or under-allocation.

7. The system of claim 1 , further comprising instructions executable to: determine a period of time for reevaluating the at least two time series, the period of time based at least in part on a rate of change of a cost of executing the schedule for the workload on the computing device of the plurality of computing devices.

8. A method of scheduling a set of tasks over a plurality of computing devices, the method comprising:
for each task of the set of tasks,
receiving at least two time series in which each time series thereof is indicative of resource utilization costs associated with execution of an instance of that task by a computing device of the plurality of computing devices, and
identifying a resource utilization model for that task based on a best-fit analysis of the at least two time series to obtain a set of resource utilization models for the set of tasks;

for a workload of the set of tasks, identifying a schedule for executing the set of tasks based on the resource utilization models and a selected one or more of an over-utilization constraint and an under-utilization constraint, wherein the schedule for executing the set of tasks maintains a resource utilization efficiency of executing the set of tasks of the workload within the selected one or more of the over-utilization constraint and the under-utilization constraint; and
configuring one or more computing devices of the plurality of computing devices to execute the set of tasks in accordance with the schedule for the workload.

9. The method of claim 8 , wherein identifying the schedule further comprises:
determining that the schedule further reduces a risk of violating a time-to-finish constraint compared to a second schedule.

10. The method of claim 8 , further comprising:
for a first time series of the at least two time series, splitting the first time series into a first portion of the first time series and a second portion of the first time series; and
aligning the first portion of the first time series with the resource utilization models.

11. The method of claim 8 , further comprising: determining a step function fitting a first time series of the at least two the time series, based at least in part on assigning penalties for at least one of over-allocation or under-allocation.

12. The method of claim 8 , further comprising: forming the at least two time series based at least in part on a solution to a linear programming problem governed by the selected one or more of the over-utilization constraint and the under-utilization constraint.

13. The method of claim 8 , further comprising: receiving information indicative of at least one of a permitted level of risk of exceeding a time-to-finish constraint and a permitted level of risk of under-utilization.

14. The method of claim 8 , further comprising: receiving information indicative of a maximum cost of executing the workload.

15. The method of claim 8 , wherein the resource utilization models are based at least in part on a prediction of the resource utilization models of executing the workload.

16. A non-volatile computer-readable storage medium having stored thereon computer-executable instructions that, when executed by a computing device, cause the computing device to schedule a set of tasks over a plurality of computing devices by:
for each task of the set of tasks,
receive at least two time series in which each time series thereof is indicative of resource utilization costs associated with execution of an instance of that task by a computing device of the plurality of computing devices, and
identify a resource utilization model for that task based on a best-fit analysis of the at least two time series, to obtain a set of resource utilization models for the set of tasks;

for a workload of the set of tasks, identify a schedule for executing the set of tasks based on the resource utilization models and a selected one or more of an over-utilization constraint and an under-utilization constraint, wherein the schedule for executing the set of tasks maintains a resource utilization efficiency of executing the set of tasks of the workload within the selected one or more of the over-utilization constraint and the under-utilization constraint; and
configure one or more computing devices of the plurality of computing devices to execute the set of tasks in accordance with the schedule for the workload.

17. The non-volatile computer-readable storage medium of claim 16 , wherein identifying the schedule further comprises: determining that the schedule reduces a risk of violating a time-to-finish constraint compared to a second schedule.

18. The non-volatile computer-readable storage medium of claim 16 , further comprising executable to: determine a step function fitting a first time series of the at least two time series, based at le

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Narayanamurthy Shravan Matthur
• Li Yan
• Selvaraj Sathiya K

Classifications

• G06F9/4887 Primary

  involving deadlines, e.g. rate based, periodic · CPC title