Static task partitioning techniques for parallel applications on heterogeneous processors
Citation:
Aravind Vasudevan, 'Static task partitioning techniques for parallel applications on heterogeneous processors', [thesis], Trinity College (Dublin, Ireland). School of Computer Science & Statistics, 2016, pp. 195Download Item:
Abstract:
A critical factor contributing to the efficiency of execution of parallel applications on parallel computing resources is the method chosen to map and schedule the tasks of the parallel application. This problem, often referred to as the DAG scheduling problem, of statically mapping and scheduling a weighted directed acyclic graph (DAG) to a set of heterogeneous processors to minimize the completion time (makespan) has been extensively studied. It remains intractable even with severe assumptions applied to the task and machine models. This thesis tackles two challenges faced by scheduling algorithms when mapping and scheduling tasks onto heterogeneous processors: (1) the execution time of a task on heterogeneous processors is not well represented in the conventional application DAGs (2) critical-path is poorly defined in the presence of communication and such heterogeneity. We address the first challenge by adopting a better representation model for the application DAGs and the resource graphs that enable processors to be selectively faster for certain kinds of tasks. We propose, design and evaluate a simulated annealing based task mapping algorithm that exploits this representation and maps applications with task and data level parallelism onto a set of heterogeneous processors. The novelty of this algorithm lies in guiding the random search using one of the systemic parameters called temperature. We observe significant improvements, in quality of the solutions for real world benchmarks, when compared against other well established task mapping algorithms. As an additional contribution, we show that similar meta-heuristic techniques are effective for partitioning road networks for distributed simulation. In the context of the second related challenge of finding critical paths on a set of heterogeneous processors, existing solutions to calculate the critical path use mean values of computation and communication. In the presence of heterogeneity and communication costs these methods of calculating the critical path are rendered ineffective. We resolve this issue, by postulating that the critical path is inherently defined by its mapping and formulate a polynomial time algorithm (Critical Earliest Finish Time (CEFT)) to find the true critical path for a given application DAG and parallel computing resources. This algorithm runs in O(P2e), where P is the number of different classes of processors and e is the total number of edges in the application graph. Based on our experiments, we show that the critical path lengths produced by our algorithm is always at least as long as the ones produced by CPOP for the conventional workloads. Our experiments also show that when we leverage the better representation model from our earlier work, the paths found by our algorithm are shorter than CPOP’s paths in 83.99% of the experiments. We also extend our critical path finding algorithm into a DAG scheduling algorithm (CEFT-CPOP) by using the path found by our algorithm (with its corresponding partial assignment) in conjunction with the critical path on a processor (CPOP) algorithm, with a running cost of O(p2e), where p is the number of processors. We compare the efficacy of our algorithm mainly against CPOP through the use of makespan related comparison metrics like: schedule length ratio (SLR), speedup and slack. We find that our algorithm outperforms CPOP even as a scheduling algorithm, in nearly all aspects.
Sponsor
Grant Number
Irish Research Council
Author: Vasudevan, Aravind
Advisor:
Gregg, DavidQualification name:
Doctor of Philosophy (Ph.D.)Publisher:
Trinity College (Dublin, Ireland). School of Computer Science & StatisticsNote:
TARA (Trinity’s Access to Research Archive) has a robust takedown policy. Please contact us if you have any concerns: rssadmin@tcd.ieType of material:
thesisAvailability:
Full text availableMetadata
Show full item recordLicences: