Return to search

Analysis and Adaption of Graph Mapping Algorithms for Regular Graph Topologies

The Message Passing Interface (MPI) standard defines virtual topologies that can be applied to systems
of cooperating processes. Among issues regarding a more convenient namespace this may be used to
optimize the placement of MPI processes in order to reduce communication time. That means, the
processes with their main communication paths represent a graph that has to be cost efficiently mapped
onto the graph representing the actual communication network. In this context, this work analyses
and compares state-of-the-art task mapping strategies with respect to running time and their quality
of solutions to the MPI mapping problem. In particular, the focus is on generic strategies that can
be used for arbitrary process/network topologies although, here, the topologies of interest are regular
ones, where the number of processes is greater than the number of processors in the underlying physical
network. Additionally, different measures of mapping quality are discussed and a close correspondence
between the most appropriate, the weighted edge cut, and program execution time is shown. In order
to investigate how mapping quality affects MPI program execution time, some mapping strategies have
been incorporated into Open MPI. Finally, benchmark results prove that optimized process-to-processor
mappings can improve program execution time by up to 60%, compared to the default mapping in many
MPI implementations (linear mapping). The findings in this work can serve as reference not only for MPI
implementors, but also for researchers investigating static process-to-processor mappings, in general.

Identiferoai:union.ndltd.org:DRESDEN/oai:qucosa.de:bsz:ch1-200901453
Date01 September 2009
CreatorsRinke, Sebastian
ContributorsTU Chemnitz, Fakultät für Informatik, Dipl.-Inf. Torsten Mehlan, Prof. Dr.-Ing. Wolfgang Rehm, Dipl.-Inf. Torsten Mehlan
PublisherUniversitätsbibliothek Chemnitz
Source SetsHochschulschriftenserver (HSSS) der SLUB Dresden
LanguageEnglish
Detected LanguageEnglish
Typedoc-type:masterThesis
Formatapplication/pdf, text/plain, application/zip

Page generated in 0.0021 seconds