System and method for increasing robustness of heterogeneous computing systems

A method for performing task pruning in a resource allocation system,

• wherein the resource allocation system comprises one or more mapping heuristics;
• wherein one or more tasks arrive into the resource allocation system;
• wherein the one or more tasks are queued upon arrival into a batch queue;
• comprising:
• establishing a dropping threshold;
• dropping one or more low quality tasks by a pruning mechanism;
• creating a mapping event;
• evaluating the oversubscription level of the computing system;
• for each task in the batch queue, the mapping event attempts to map said tasks in the batch queue to one or more machine queues, comprising:
• creating a virtual queue of one or more machine-task mappings;
• calculating a completion time distribution of one or more unmapped tasks to one or more machines;
• deferring tasks with low chances of success;
• and
• returning the tasks that have been deferred to the batch queue until a subsequent mapping event;
• calculating an impact of dropping a low quality task, wherein a pruning mechanism calculates a completion time and a probability of timely completing the task subsequent to the dropped low quality task;
• determining a best machine for each task by the mapping heuristic;
• selecting which task will be paired with which machine queue by the mapping heuristic;
• and
• mapping each task from the batch queue to a machine queue until no tasks remain in the batch queue;
• wherein calculating the impact further comprises generating one or more impulses representing a completion time of each task.