Task partitioning and scheduling on arbitrary parallel processing systems

Parallel programming is the major stumbling block preventing the parallel processing industry from quickly satisfying the demand for parallel computer software. This research is aimed at solving some of the problems of software development for parallel computers.; ELGDF is a graphical language for designing parallel programs. The goal of ELGDF is two-fold: (1) to provide a program design notation and computer-aided software engineering tool, and (2) to provide a software description notation for use by automated schedulers and performance analyzers. ELGDF is implemented as a graphical editor called Parallax.; We extend previous results for optimally scheduling parallel program tasks on a finite number of parallel processors. We introduce a new scheduling heuristic (MH) that schedules program modules represented as nodes in a precedence task graph with communication onto arbitrary machine topology taking contention into consideration.; We present results for scheduling simulated task graphs on ring, star, mesh, hypercube, and fully connected networks using MH.; We also present Task Grapher, a tool for studying optimal parallel program task scheduling on arbitrarily interconnected parallel processors. Given a parallel program represented as a precedence-constrained task graph, and an interconnect topology of a target machine, Task Grapher produces the following displays: (1) Gantt Chart Schedule, (2) Speed-up Line Graph, (3) Critical Path In Task Graph, (4) Processor Utilization Chart, (5) Processor Efficiency Chart, (6) Dynamic Activity Display. Task Grapher currently incorporates seven scheduling heuristics.; Finally, we introduce a new loop unrolling method for scheduling nested loops onto arbitrary target machines. We use local neighborhood search and simulated annealing methods to find: (1) the best unrolling vector, and (2) a Gantt chart that indicates the allocation and the order of the tasks in the post-unrolled loop on the available processing elements.