EFFICIENT DUPLICATION-BASED SCHEDULING ALGORITHMS FOR DISTRIBUTED MEMORY MULTIPROCESSOR SYSTEMS

Abstract

Parallel processing systems have witnessed an incredible growth over the last decade with increasingly complex and challenging scientific and engineering applications coming to their realm. Task scheduling is one of the key issues for the success of parallel computing systems, and development of efficient scheduling algorithms plays a crucial role in achieving this goal. Due to NP-completeness of the scheduling problem, research efforts are mainly directed towards exploring heuristic-based approaches that generate nearoptimal schedules within reasonable time and resource constraints. However, we find that most of the available heuristics ignore the practical aspect and/or compromise too much on complexity or performance fronts. Further, over the passage of time due to the advances in technology, new dimensions and constraints get added to the scheduling problem that demand new approaches and techniques to be explored and developed in the concerned fields. This thesis attempts to improve upon these frontages by contributing three efficient algorithms for scheduling DAG structured applications in the traditional Homogeneous, and the imminent Heterogeneous and Mixed-Parallel computing environments. Interprocessor communication overheads, an unavoidable facet of the most versatile distributed memory multiprocessor systems, can be handled more effectively by the duplication-based heuristics in comparison to list or clustering-based heuristics, and is one of our main concerns in this work. High performance duplication-based algorithms, so far reported in literature, are quite complex and consume too many processors to be practical, for large problem sizes, as observed during the course of this work. In addition, most of the algorithms do not take into iv account the interconnection constraints of networks, and work with restricted precedence constraints and predefined computation and/or communication costs in task graphs. An improved duplication strategy has been developed for arbitrary task graphs and network topologies, which consumes lesser number of processors and performs reasonably well. The proposed Selective-Duplication (SD) algorithm attempts to improve upon the complexityfront by limiting the number of duplications to the few critical ones, and on the performance front by avoiding redundant duplications and judiciously exploiting the scheduling holes. The selective-duplication approach has been extended for scheduling task graphs on heterogeneous platforms, which has been paid relatively lesser attention in the literature. A low-complexity Heterogeneous Limited Duplication (HLD) algorithm is suggested and its performance is evaluated by using an A-cube (A3) performance model, which has been suggested in this work to study the behavior of an Algorithm, Application, and Architecture in the presence of heterogeneity, in a more comprehensive and exhaustive manner. Other major stream attended in this work is the mixed-parallel computing environment that deals with simultaneous exploitation of task and data parallelism in application programs; a thought that is steadily taking shapes for high performance parallel computing. A Modified Critical Path and Area-based (MCPA) scheduling algorithm is proposed that targets at modifying the processor allocation phase of an existing two-step algorithm in this field. Strength of the algorithm lies in exploiting data parallelism without sacrificing the crucial task parallelism available in the task graph, resulting in a more balanced processor allocation especially in a resource constrained set-up. Extensive simulations of the proposed algorithms, for the benchmark task graphs with widely varying precedence, cost, and size constraints, indicate their goodness and effectiveness over the existing state-of-the-art scheduling algorithms, which further justify the rationale behind the proposed heuristics.