الفهرس Only 14 pages are availabe for public view
 |  | from | 163 |  |  |
| | | from | 163 | | |
Abstract
Parallel scheduling is defined as the problem of scheduling Directed Acyclic Graphs (DAGs) tasks with precedence constraints (representing certain projects) in a way that minimizes the completion time. Efficient scheduling is essential to exploit the tremendous potential of high performance systems in different fields. Parallel scheduling of DAGs with precedence constraints is a well studied problem and a number of heuristics have been proposed to solve it since it is known to be NP-hard or even NP-complete except for a few very restricted cases. Heuristics obtain near optimal schedules in a reasonable amount of computation time.
Any scheduling instance consists of a set of jobs subject to two classes of constraints: AND-only precedence constraints (presented by Graphs with AND-only nodes) and AND/OR precedence constraints (presented by Graphs with AND- and OR-nodes or by Networks with AND-nodes and waiting conditions). This dissertation shows that both implementations of the AND/OR precedence constraints are equivalent, i.e. any scheduling instance presented using one method can be transformed to the other method without loss of generality. A new algorithm AONtoAOG is introduced to transform AND/OR-Networks into AND/OR-Graphs. To examine and evaluate AONtoAOG, a random AND/OR Network Generator algorithm AONG is created to provide a wide range of random networks to be used in the simulation experiments.
Next, we address the problem of parallel scheduling of DAGs with AND/OR precedence constrained tasks on Multiple Instructions Multiple Data MIMD fully-connected machines architecture with maximum number of processors equivalent to number of DAG nodes. At first, a new heuristic algorithm – Critical Path Maximum Zeroing CPMZ – is proposed to schedule DAGs with AND-only precedence constraints. It is compared to the famous Dominant Sequence Clustering DSC heuristic that was classified as one of the best AND-only DAG scheduling heuristics in the literature. CPMZ has proved to outperform DSC in both Parallel Time and Number of Clusters. A Random AND-only Graph Generator RGG is created to provide a wide range of random AND-only graphs to be used in the experiments comparing CPMZ to DSC. Next, AND/OR precedence constraints are applied on CPMZ. A new heuristic – AND/OR Critical Path Maximum Zeroing AOCPMZ – is proposed. Up to the moment of working on this dissertation, the problem of parallel scheduling of DAGs with AND/OR precedence constraints is not tackled by any researches in the literature. AOCPMZ is a successful heuristic for problems that allow AND/OR precedence constrained DAGs.
Then, we present an efficient heuristic algorithm called Parallel AND/OR Scheduling PAOS for the parallel scheduling of DAGs with AND/OR precedence constraints. It aims to reduce the resulting Parallel Time PT– the parallel schedule length – as well as the Number of parallel Clusters used. In PAOS, we deal with OR-nodes from the beginning and some non-essential edges are removed from the AND/OR DAG in order to transform all OR-nodes to AND-nodes preceded only by their main direct AND-predecessors before starting the parallel scheduling process of the resulting AND-only DAG. A Random AND/OR Graph Generator AOGG is created to provide a wide range of random AND/OR DAGs to be used in the experiments comparing PAOS to AOCPMZ. PAOS proved to outperform AOCPMZ, consequently to outstand other heuristics when AND/OR precedence constraints among tasks is permitted in the process.