A Comparison Study of Heuristics for Mapping Parallel Algorithms to Message-Passing Multiprocessors

Abstract:

This paper presents a comparison study of popular clustering and mapping
heuristics which are used to map task-flow graphs to message-passing
multiprocessors. To this end, we use task-graphs which are representative
of important scientific algorithms running on data-sets of practical
interest. The annotation which assigns weights to nodes and edges of the
task-graphs is realistic. It reflects current trends in processor,
communication channel, and message-passing interface technology and takes
into consideration hardware characteristics of state-of-the-art
multiprocessors. Our experiments show that applying realistic models for
task-graph annotation affects the effectiveness and functionality of
clustering and mapping techniques. Therefore, new heuristics are necessary
that will take into account more practical models of communication costs.
We present modifications to existing clustering and mapping algorithms
which improve their efficiency and running-time for the practical models
adopted.

This technical report has been published as

A Comparison Study of Heuristics for Mapping Parallel Algorithms
to Message-Passing Multiprocessors. Kenneth
Steiglitz, Anne Rogers and Marios D. Dikaiakos,
Parallel Algorithms and Applications,
10(3-4), 1995.