System and method for increasing robustness of heterogeneous computing systems
Inventors
Gentry, James • Salehi, Mohsen Amini • Denninnart, Chavit
Assignees
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Publication Number
US-11455188-B2
Publication Date
2022-09-27
Expiration Date
Abstract
Disclosed is a method for task pruning that can be utilized in existing resource allocation systems to improve the systems' robustness without requiring changing to existing mapping heuristics. The pruning mechanism leverages a probability model, which calculates the probability of a task competing before its deadline in the presence of task dropping, and only schedules tasks that are likely to succeed. Pruning tasks whose chance of success is low improves the chance of success for other tasks. Tasks that are unlikely to succeed are either deferred from current scheduling event or are preemptively dropped from the system. The pruning method can benefit service providers by allowing them to utilize their resources more efficiently and use them only for tasks that can meet their deadlines. The pruning method further helps end users by making the system more robust in allowing more tasks to complete on time.
Core Innovation
A resource allocation system performs task pruning when one or more tasks arrive and are queued upon arrival into a batch queue. A dropping threshold is established, and low quality tasks are dropped by a pruning mechanism. A mapping event is then created, and for the tasks in the batch queue the mapping event attempts to map the tasks to one or more machine queues using one or more mapping heuristics, including creating a virtual queue of machine-task mappings.
During each mapping event, the mapping event calculates a completion time distribution of one or more unmapped tasks to one or more machines and defers tasks with low chances of success. Deferred tasks are returned to the batch queue until a subsequent mapping event. The mechanism also calculates an impact of dropping a low quality task by estimating a completion time and a probability of timely completing the task subsequent to the dropped low quality task.
The impact calculation further generates one or more impulses representing a completion time of each task. For each task, a best machine is determined by the mapping heuristic, and the mapping heuristic selects which task is paired with which machine queue. Tasks are mapped from the batch queue to a machine queue until no tasks remain in the batch queue, and the overall pruning mechanism uses the computed probability and completion time distribution in the pruning and deferring decisions.
Claims Coverage
The partial claim set includes two independent claims. Across them, the inventive coverage centers on threshold-based pruning combined with deferred remapping using probability-of-timely-completion based modeling, and a pruning mechanism architecture that measures oversubscription by missed deadlines against a Dropping Toggle and includes a fairness module to avoid bias.
Threshold-based pruning with deferred remapping using a probability of timely completion
A method for performing task pruning in a resource allocation system comprising establishing a dropping threshold; dropping one or more low quality tasks by a pruning mechanism; creating a mapping event; evaluating the oversubscription level; for each task in the batch queue, the mapping event attempts to map said tasks to one or more machine queues by creating a virtual queue of machine-task mappings, calculating a completion time distribution of unmapped tasks, deferring tasks with low chances of success, and returning deferred tasks to the batch queue until a subsequent mapping event.
Impact of dropping using completion time impulses and probability of timely completion
Calculating an impact of dropping a low quality task by a pruning mechanism wherein the pruning mechanism calculates a completion time and a probability of timely completing the task subsequent to the dropped low quality task, and generating one or more impulses representing a completion time of each task.
Pruning mechanism architecture with oversubscription measurement via missed deadlines and Dropping Toggle
A pruning mechanism for a resource allocation system comprising an accounting module, a toggle module, a pruner module, a pruning configuration, and a fairness module, wherein the accounting module gathers one or more task’s information; the toggle module measures the computing system’s oversubscription level by monitoring a total amount of tasks that have missed their deadlines since a prior mapping event and identifying the system as oversubscribed if the total exceeds a Dropping Toggle.
Bias avoidance through a fairness module
A pruning mechanism for a resource allocation system wherein the fairness module comprises functionality to avoid bias.
Taken together, the independent claims cover threshold-based pruning with a dropping threshold, mapping events, a virtual queue of machine-task mappings, completion time distribution, deferred tasks, and impact calculation using completion time, probability of timely completion, and impulses. The other independent claim covers a pruning mechanism architecture that measures oversubscription based on missed deadlines against a Dropping Toggle and incorporates a fairness module configured to avoid bias.
Stated Advantages
Not explicitly described in patent.
Documented Applications
Not explicitly described in patent.
Interested in licensing this patent?