DocumentCode :
125486
Title :
On Partitioning Two Dimensional Finite Difference Meshes for Distributed Memory Parallel Computers
Author :
Grandjean, Anael ; Ucar, Bora
Author_Institution :
LIP, UCBL, Lyon, France
fYear :
2014
fDate :
12-14 Feb. 2014
Firstpage :
9
Lastpage :
16
Abstract :
We investigate the problem of partitioning finite difference meshes in two dimensions among the processors of a parallel computer. The objective is to achieve a perfect load balance while minimizing the communication cost. There are well-known graph, hypergraph, and geometry-based partitioning algorithms for this problem. The known geometric algorithms have linear running time and obtain the best results for very special mesh sizes and processor numbers. We propose another geometric algorithm. The proposed algorithm is linear, is applicable to much more cases than some well-known alternatives, obtains better results than the graph partitioning algorithms, obtains better results than the hypergraph partitioning algorithms almost always. Our algorithm also obtains better results than a known asymptotically-optimal algorithm for some small number of processors. We also catalog related theoretical results.
Keywords :
distributed processing; finite difference methods; graph theory; mesh generation; resource allocation; distributed memory parallel computers; geometry-based partitioning algorithms; graph partitioning algorithms; hypergraph partitioning algorithms; linear running time; perfect load balance; two dimensional finite difference meshes; Approximation algorithms; Diamonds; Measurement; Partitioning algorithms; Program processors; Shape; Standards;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel, Distributed and Network-Based Processing (PDP), 2014 22nd Euromicro International Conference on
Conference_Location :
Torino
ISSN :
1066-6192
Type :
conf
DOI :
10.1109/PDP.2014.10
Filename :
6787247
Link To Document :
بازگشت