The recent development of distributed processing platforms, such as clusters of workstations, makes the use of distributed applications more extensive. A fundamental issue affecting performance in distributed systems is the scheduling of tasks to processors. The problem of solving the scheduling of parallel programs modelled with a task precedence graph (TPG) has been extensively studied. Scheduling algorithms of TPGs can be solved by a one-step method when a fixed number of processors is considered or through a two-step method by first creating an unbounded number of groups of tasks (clusters) and subsequently assigning these clusters to a bounded number of processors. The goal of this work is to present a new mapping algorithm called TASC (Task ASsignment exploiting Concurrency) to solve this second step of assigning clusters to processors. The effectiveness of TASC is established through simulation for a set of synthetic graphs that model real applications. © 2004, Sage Publications. All rights reserved.
- Static mapping
- cluster-mapping heuristics
- message-passing computation model
- modelling parallel programs
- scheduling algorithms