Title: Efficient Process Mapping for Cartesian Topologies
Language: English
Authors: Lehr, Markus 
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
Advisor: Träff, Jesper Larsson  
Issue Date: 2020
Number of Pages: 90
Qualification level: Diploma
Abstract: 
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.
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-134088
http://hdl.handle.net/20.500.12708/1480
Library ID: AC15563558
Organisation: E191 - Institut für Computer Engineering 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Hochschulschrift | Thesis

Files in this item:

File Description SizeFormat
Efficient Process Mapping for Cartesian Topologies.pdf7.01 MBAdobe PDF View/Open
Show full item record

Page view(s)

2
checked on Jul 2, 2020

Google ScholarTM

Check


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