TY - GEN
T1 - Communication-aware Parallel Domain Decomposition using Space Filling Curves
AU - Seal, Sudip
AU - Aluru, Srinivas
N1 - Publisher Copyright:
© 19th International Conference on Parallel and Distributed Computing Systems 2006, PDCS 2006. All rights reserved.
PY - 2006
Y1 - 2006
N2 - Space filling curves (SFCs) are proximity preserving linearizations of multidimensional data. They are frequently used for parallel domain decomposition in scientific computing applications where interactions occur between elements with physical proximity. The conventional way to affect SFC-based parallel domain decomposition is to take the SFC-linearization and map it to processors in a block distributed fashion. In this paper, we derive closed form formulas for the average nearest neighbor distance along a Z-space filling curve and use this result to show that such a mapping may not be communication efficient. We introduce topology-aware mapping of SFC data to parallel computers and show that SFC data can be partitioned on hypercubes such that communication is restricted to nearest neighbors.
AB - Space filling curves (SFCs) are proximity preserving linearizations of multidimensional data. They are frequently used for parallel domain decomposition in scientific computing applications where interactions occur between elements with physical proximity. The conventional way to affect SFC-based parallel domain decomposition is to take the SFC-linearization and map it to processors in a block distributed fashion. In this paper, we derive closed form formulas for the average nearest neighbor distance along a Z-space filling curve and use this result to show that such a mapping may not be communication efficient. We introduce topology-aware mapping of SFC data to parallel computers and show that SFC data can be partitioned on hypercubes such that communication is restricted to nearest neighbors.
KW - domain decomposition
KW - parallel algorithms
KW - parallel communication
KW - space filling curves
KW - topology aware mapping
UR - http://www.scopus.com/inward/record.url?scp=85056041871&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85056041871
T3 - 19th International Conference on Parallel and Distributed Computing Systems 2006, PDCS 2006
SP - 159
EP - 164
BT - 19th International Conference on Parallel and Distributed Computing Systems 2006, PDCS 2006
PB - International Society for Computers and Their Applications (ISCA)
T2 - 19th International Conference on Parallel and Distributed Computing Systems, PDCS 2006
Y2 - 20 September 2006 through 22 September 2006
ER -