It is well known that parallel task graphs (PTG) are modeled with Directed Acyclic graphs (DAG tasks). DAG tasks are scheduled in Heterogeneous Distributed Computing Systems (HDCS) for execution with different techniq...
详细信息
ISBN:
(纸本)9783030337490;9783030337483
It is well known that parallel task graphs (PTG) are modeled with Directed Acyclic graphs (DAG tasks). DAG tasks are scheduled in Heterogeneous Distributed Computing Systems (HDCS) for execution with different techniques which seek to reduce completion of each PTG. Proposed planning techniques generally only make use of the critical path in planning as an internal characteristic of the DAG task, helping to optimize scheduling. In this study it is shown that analyzing other internal characteristics, such as layering and graph density aside from the critical path of DAG workflow tasks, before being scheduled in execution locations, can improve computer system performance, as well as optimize the use of their resources. For the above, the internal characteristics considered in this study of each DAG task are: the critical path, layering as well as graph density. The analyzed DAG tasks are synthetic loads produced with a graph generation algorithm as well as real application graphs. The findings obtained with the experiments performed show that the distribution estimation algorithm obtains better response times than the genetic algorithm.
Many scientific applications can be structured as parallel task graphs (PTGs) that is graphs of data-paralleltasks Adding data parallelism to a task-parallel application provides opportunities for higher performance ...
详细信息
Many scientific applications can be structured as parallel task graphs (PTGs) that is graphs of data-paralleltasks Adding data parallelism to a task-parallel application provides opportunities for higher performance and scaliability but poses additional scheduling challenges In this paper we study the off-line scheduling of multiple PTGs on a single homogeneous cluster The objective is to optimize performance without compromising fairness among the PTGs We consider the range of previously proposed scheduling algorithms applicable to this problem from both the applied and the theoretical literature and we propose minor improvements when possible Our main contribution is an extensive evaluation of these algorithms in simulation using both synthetic and real-world application configurations using two different metrics for performance and one metric for fairness We identify a handful of algorithms that provide good trade-offs when considering all these metrics The best algorithm overall is one that structures the schedule as a sequence of phases of increasing duration based on a makespan guarantee produced by an approximation algorithm (C) 2010 Elsevier Inc All rights reserved
An n-parallel-task graph consists of an input node nu(0) (the source), an output node nu(n+1) (the sink), and n intermediate task nodes nu(1), nu(2),...,nu(i), with each nu(i), i = 1,...,n having a (directed) inlink f...
详细信息
An n-parallel-task graph consists of an input node nu(0) (the source), an output node nu(n+1) (the sink), and n intermediate task nodes nu(1), nu(2),...,nu(i), with each nu(i), i = 1,...,n having a (directed) inlink from nu(0) and a (directed) outlink to nu(n+1). The source sends each task node exactly one of n distinct inputs, which are then processed and forwarded to the sink. The system is said to work if the output node correctly receives the results for all processed inputs. Nodes and links may fail however. We introduce a replicated version of the n-parallel-task graph in which node nu(i) is replicated r(i) times, i = 0, 1,...,n + 1, with each copy of a task node possessing an inlink from each of the r(0) copies of the source, as well as an outlink to each of the r(n+1) copies of the sink. The replicated n-parallel-task graph works if and only if there exists an output node which correctly receives the results for all processed inputs. We give an O(2(4rn+1) r(0)n + 2(rn+1) r(0) Sigma(i=1)(n) r(i)) algorithm to compute the reliability of replicated n-parallel-taskgraphs, for arbitrary replication indices r(i), generalizing a previous result of Liang and Jan for the uniformly replicated case i.e. r(i) = r, i = 0,...,n + 1. We also give conditions under which the uniformly replicated case may be solved in O(2(4)' log n) time. For constant r(i) and r, the nonuniform case requires linear time, while the uniform case logarithmic time.
暂无评论