US 10,503,548 B2Granted

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

AssigneeMicrosoft Technology Licensing, LLC

InventorsShravan Matthur Narayanamurthy, Yan Li, Sathiya K. Selvaraj

Life of this patent

Estimating the term…

Loading patent…

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.

Claims20

Dependent claims

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.

6 more elements

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.

3 more elements

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.

3 more elements

Dependencies are inferred from the claim text.