Scheduling techniques for parallel computers

During the past few years, a pectacular growth of parallel computing hardwareplatforms has been witnessed. As the hardware of parallel processing systems evolves towards achieving the goal of a teraflop performance, the software designers of these systems face increasingly difficult challenges. These include designing new algorithms,programming models, languages, automated programming aids and performance assessment tools. Perhaps, the most crucial component of efficient parallel processing software is the scheduling.Since the scheduling problem is known to be NP (Non-deterministic Polynomialtime)-complete in many variants, most of the previous solutions are based on heuristics.However, these approaches make simplified assumptions about the parallel program and the target machine architecture. This thesis proposes similar heuristic algorithms forcompile-time scheduling of parallel programs onto parallel processing systems. The first algorithm, called the Least Communication Time (LCT) algorithm which is designed for scheduling arbitrary task graphs on unlimited and fully connected processors, is based on new principles. The LCT algorithm evolved to produce the second algorithm,which is called the Least Communication Time Task Duplication (LCTTD) algorithm,is designed to exploit task duplication in scheduling. Using task duplication the communication overhead can drastically reduced. The LCTTD algorithm outperformsthe previous reported algorithm and enhances it with task duplication technique toreduce the schedule length (SL).The proposed algorithms are evaluated using a number of suites of task graphs. These include randomly generated graphs of various different structures, as well as task graphsused in various published papers. Also task graphs for a number of practical parallel algorithms such as Gaussian-elirnination, and Gauss-Jordan elimination methods are also considered. Such evaluation was performed using a software implementedprogram. The proposed scheduling algorithms were compared with one of the most popular and recent algorithms which is called Modified Critical Path (MCP) schedulingalgorithm, and belongs to list scheduling algorithms techniques.