Title: Efficient process mapping for cartesian topologies
Language: English
Authors: Lehr, Markus 
Qualification level: Diploma
Advisor: Träff, Jesper Larsson  
Issue Date: 2019
Number of Pages: 90
Qualification level: Diploma
In this thesis we introduce different algorithms for mapping physical processes to Cartesian grids. We assume that processes within this grid communicate with certain neighboring processes as defined by a given stencil. We show that this mapping problem is already NP-complete for two dimensional grids and a very simple isomorphic neighborhood. We compare the current state of solutions in the field of High Performance Computing, specifically the Message Passing Interface (MPI). With his algorithm from 2018, W. D. Gropp showed promising performance, which is why we compare our approaches to his work, as well as MPI's standard behaviour. For qualitatively comparing concrete mappings, we define fitting optimality criteria, based on the core concept of minimizing inter-computation-node communication. We benchmarked using MPI_Irecv and MPI_Isend and show that our algorithms can find mappings, where Gropp cannot and that we could match or improve upon his resulting mappings in terms of quality and runtime. The first algorithm, which we present is similar to other graph partitioning approaches, since it utilizes recursive splitting in order to guarantee a logarithmic runtime wrt. the number of vertices in the Cartesian grid. We also guarantee a quality bound for this algorithm, which becomes better with increasing number of dimensions. In another implementation-variant, we adapted this algorithm for accommodating differently shaped stencils by weighting dimensions before the recursive splitting depending on how much communication happens across them. The third approach attempts to find hyperrectangular strips within the Cartesian grid, which are then filled similar to MPI's default row-major rank assignment. Although the theoretical bound of this approach is not as good as the first, this assignment strategy yielded the most compact mappings most of the time. Its main shortcoming, however, is its inability to adapt these strips, depending on different stencils.
Keywords: Parallel, distributed memory computing; High-Performance computing; Process mapping; Communication patterns; Grids; Stencils; MPI
Parallel, distributed memory computing; High-Performance computing; Process mapping; Communication patterns; Grids; Stencils; MPI
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-134088
Library ID: AC15563558
Organisation: E191 - Institut für Computer Engineering 
Publication Type: Thesis
Appears in Collections:Thesis

Files in this item:

Page view(s)

checked on Jul 15, 2021


checked on Jul 15, 2021

Google ScholarTM


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.