Mapping Unstructured Applications into Nested Parallelism
Arturo González-Escribano - Universidad de Valladolid -Spain
Arjan J.C. van Gemund - Delft University of Technology - The Netherlands
Valentín Cardeñoso-Payo - Universidad de Valladolid - Spain
Nested parallel programming models, where the task graph associated to a
computation is series-parallel are easy to program and show good analysis
properties. These can be exploited for efficient scheduling, accurate cost
estimation or automatic mapping to different architectures.
Restricting synchronization structures to nested series-parallelism
may bring performance losses due to a less parallel solution, as compared
to more generic ones based in unstructured models (e.g. message passing).

A new algorithmic technique is presented which allows automatic
transformation of the task graph of any unstructured application
to a series-parallel form (nested-parallelism). The tool is applied to
random and irregular application task graphs to investigate
the potential performance degradation when conveying them
into series-parallel form. Results show that a wide range of irregular
applications can be expressed using a structured
coordination model with a small loss of parallelism.

Last update: Wed Jun 12 14:26:53 2002 WEST