Parallel tree building on a range of shared address space multiprocessors: Algorithms and application performance

Hongzhang Shan; Jaswinder Pal Singh

doi:10.1109/IPPS.1998.669959

Parallel tree building on a range of shared address space multiprocessors: Algorithms and application performance

Hongzhang Shan, Jaswinder Pal Singh

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

9 Scopus citations

Abstract

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.

Original language	English (US)
Title of host publication	Proceedings of the International Parallel Processing Symposium, IPPS
Editors	Anon
Pages	475-484
Number of pages	10
DOIs	https://doi.org/10.1109/IPPS.1998.669959
State	Published - Jan 1 1998
Event	Proceedings of the 1998 12th International Parallel Processing Symposium and 9th Symposium on Parallel and Distributed Processing - Orlando, FL, USA Duration: Mar 30 1998 → Apr 3 1998

Publication series

Name	Proceedings of the International Parallel Processing Symposium, IPPS
ISSN (Print)	1063-7133

Other

Other	Proceedings of the 1998 12th International Parallel Processing Symposium and 9th Symposium on Parallel and Distributed Processing
City	Orlando, FL, USA
Period	3/30/98 → 4/3/98

All Science Journal Classification (ASJC) codes

Hardware and Architecture

Access to Document

10.1109/IPPS.1998.669959

Fingerprint Dive into the research topics of 'Parallel tree building on a range of shared address space multiprocessors: Algorithms and application performance'. Together they form a unique fingerprint.

Cite this

@inproceedings{5e1d0964b55e423ca28b9aa4d85ff099,

title = "Parallel tree building on a range of shared address space multiprocessors: Algorithms and application performance",

abstract = "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.",

author = "Hongzhang Shan and Singh, {Jaswinder Pal}",

year = "1998",

month = jan,

day = "1",

doi = "10.1109/IPPS.1998.669959",

language = "English (US)",

isbn = "0818684046",

series = "Proceedings of the International Parallel Processing Symposium, IPPS",

pages = "475--484",

editor = "Anon",

booktitle = "Proceedings of the International Parallel Processing Symposium, IPPS",

note = "Proceedings of the 1998 12th International Parallel Processing Symposium and 9th Symposium on Parallel and Distributed Processing ; Conference date: 30-03-1998 Through 03-04-1998",

}

Shan, H & Singh, JP 1998, Parallel tree building on a range of shared address space multiprocessors: Algorithms and application performance. in Anon (ed.), Proceedings of the International Parallel Processing Symposium, IPPS. Proceedings of the International Parallel Processing Symposium, IPPS, pp. 475-484, Proceedings of the 1998 12th International Parallel Processing Symposium and 9th Symposium on Parallel and Distributed Processing, Orlando, FL, USA, 3/30/98. https://doi.org/10.1109/IPPS.1998.669959

Parallel tree building on a range of shared address space multiprocessors : Algorithms and application performance. / Shan, Hongzhang; Singh, Jaswinder Pal.

Proceedings of the International Parallel Processing Symposium, IPPS. ed. / Anon. 1998. p. 475-484 (Proceedings of the International Parallel Processing Symposium, IPPS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 -