PARALLEL SCHEDULING OF PRECEDENCE CONSTRAINT TASKS IN MULTIPROCESSOR SYSTEMS

Abstract

Existing heuristics for scheduling a node and edge weighted directed task graph to multiple processors can produce satisfactory solutions but incur high time complexities, which tend to exacerbate in more realistic environments with relaxed assumptions. Consequently, these heuristics do not scale well and cannot handle problems of moderate sizes. A natural approach to reducing complexity, while aiming for a smaller or potentially better solution, is to parallelize the scheduling algorithm. This can he done by partitioning the task graphs and concurrently generating partial schedule for the partitioned parts, which are then concatenated to obtain the filial schedule. The problem, however, is nontrivial as there exist dependencies among the nodes of a task graph, which must be preserved for generating a valid schedule. Moreover, the time clock , for scheduling is global for all the processors (that are executing the parallel scheduling algorithm), making the inherent parallelism invisible. In this thesis, a parallel algorithm is simulated that is guided by a systematic partitioning of the task graph to per form scheduling using multiple processors. The algorithm schedules both the tasks and messages, and is suitable for graphs with arbitrary computation crud communication costs, and is applicable to systems with arbitrary network topologies using homogeneous or heterogeneous processors. The algorithm exhibits an interesting trade-off between the solution quality and speedup while scaling well with the problem size.....