الفهرس Only 14 pages are availabe for public view
 |  | from | 186 |  |  |
| | | from | 186 | | |
Abstract
During the past few years, a pectacular growth of parallel computing hardware
platforms 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 Polynomial
time)-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 for
compile-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 outperforms
the previous reported algorithm and enhances it with task duplication technique to
reduce 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 graphs
used 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 implemented
program. The proposed scheduling algorithms were compared with one of the most popular and recent algorithms which is called Modified Critical Path (MCP) scheduling
algorithm, and belongs to list scheduling algorithms techniques.