Abstract:
Scheduling programs represented by task graphs (dags) onto multiprocessors represented by processor graphs (undirected graphs) is tackled in this project. A new linear time heuristic (MMH) is proposed for task scheduling. MMH is a simplified version of the Mapping Heuristic. Execution times of programs scheduled by MMH onto different multiprocessors are compared. Finally, a simple way of estimating a quality of a topology is proposed.