The objective of this effort is to explore the concept of dominant edges and dominant tasks for scheduling parallel programs on a distributed memory processing system. A dominant edge will play a crucial role in generating a task schedule because of the associated communication cost. A dominant task is a coarse grained task with low run time overhead such that they can be rescheduled on a different processor to achieve a load balance. Thus all remaining (non-dominant) tasks will be allocated statically to processors. This project will build on the earlier work on Threshold Scheduling, where the degree of parallelism is treaded off for the schedule length. In this project, the goal is to investigate the threshold scheduling to enhance unified data and code partitioning for a family of distributed memory architectures including Touchstone Delta and Paragon. This will involve the formalization of feasibility conditions and optimality conditions. A feasibility condition guarantees that the schedule delay of a task from its earliest start time is below the threshold and an optimality condition used a merit function to decide the best task-processor match for a set of tasks competing for a given processor.
