TY - GEN
T1 - Parallel tree building on a range of shared address space multiprocessors
T2 - Proceedings of the 1998 12th International Parallel Processing Symposium and 9th Symposium on Parallel and Distributed Processing
AU - Shan, Hongzhang
AU - Singh, Jaswinder Pal
PY - 1998/1/1
Y1 - 1998/1/1
N2 - The performance of five parallel tree building methods in the context of a complete galaxy simulation on four very different platforms that support the coherent shared address space programming model is investigated. A proposed algorithm that uses a separate spatial partitioning of the domain for the tree building phase and eliminates locking at a significant cost in locality and load balance is found to be the best by far. By changing the tree building algorithm, improvements of more than factors of 4-40 on commodity-based systems are achieved in overall application performance even on only 16 processors. This allows commodity shared memory platforms to perform well for hierarchical N-body applications for the first time.
AB - The performance of five parallel tree building methods in the context of a complete galaxy simulation on four very different platforms that support the coherent shared address space programming model is investigated. A proposed algorithm that uses a separate spatial partitioning of the domain for the tree building phase and eliminates locking at a significant cost in locality and load balance is found to be the best by far. By changing the tree building algorithm, improvements of more than factors of 4-40 on commodity-based systems are achieved in overall application performance even on only 16 processors. This allows commodity shared memory platforms to perform well for hierarchical N-body applications for the first time.
UR - http://www.scopus.com/inward/record.url?scp=0031652121&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0031652121&partnerID=8YFLogxK
U2 - 10.1109/IPPS.1998.669959
DO - 10.1109/IPPS.1998.669959
M3 - Conference contribution
AN - SCOPUS:0031652121
SN - 0818684046
T3 - Proceedings of the International Parallel Processing Symposium, IPPS
SP - 475
EP - 484
BT - Proceedings of the International Parallel Processing Symposium, IPPS
A2 - Anon, null
Y2 - 30 March 1998 through 3 April 1998
ER -