Parallel Task Graphs Scheduling Based on the Internal Structure

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.