Dissertation/Thesis Abstract

Robust Resource Allocation of Independent Tasks in Heterogeneous Computing Systems via Probabilistic Task Pruning
by Gentry, James A. S., M.S., University of Louisiana at Lafayette, 2018, 88; 10843501
Abstract (Summary)

In heterogeneous distributed computing system, diversity can be present both in the computational resources and in the types of arriving tasks. In an inconsistently Heterogeneous Computing (HC) system, different task types can have different performance characteristics (i.e., execution times) on heterogeneous machines. A mapping method is required to match arriving tasks with machines based on both machine availability and performance to maximize the number of tasks meeting their deadlines (known as robustness). In particular, for tasks with hard individual deadlines ( e.g., live video streaming tasks), those that have missed their deadlines are dropped, as there is no value in executing them. The problem investigated in this research is how to maximize robustness of an HC system, specifically, when it is oversubscribed. The proposal is to prune (i.e., defer or drop) tasks with low probability of meeting their deadlines. Pruning low-chance tasks increases the probability of other tasks meeting their deadlines. To that end, first a model is provided to estimate the probability of meeting deadline for each task in the presence of task dropping. Second, a pruning mechanism is proposed to predictively defer or drop tasks in an effort to maximize the overall robustness of the HC system. Third, a mapping method is proposed that functions based on the pruning mechanism and improves robustness of the HC system. Fourth, to show a broad application, the pruning mechanism is applied to other mapping heuristics. Fifth, further development of the pruning mechanism is made from multiple fronts to improve robustness, engender fairness amongst completed task types, and examine the cost ramifications of using a pruning mechanism. Simulation results, harnessing a selection of mapping heuristics, show the efficacy of the proposed pruning mechanism can improve robustness of some oversubscribed HC system by more than 40%.

Indexing (document details)
Advisor: Salehi, Mohsen A.
Commitee: Chen, Sheng, Jin, Miao, Tzeng, Nian-Feng
School: University of Louisiana at Lafayette
Department: Computer Science
School Location: United States -- Louisiana
Source: MAI 58/05M(E), Masters Abstracts International
Subjects: Computer science
Keywords: Distributed computing, Heterogeneous computing, Mapping heuristic, Robustness, Scheduling
Publication Number: 10843501
ISBN: 9781392041710
Copyright © 2019 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy