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
Publisher	IEEE Comp Soc
Pages	475-484
Number of pages	10
ISBN (Print)	0818684046
DOIs	https://doi.org/10.1109/IPPS.1998.669959
State	Published - 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

Conference

Conference	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

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}",

note = "Publisher Copyright: {\textcopyright} 1998 IEEE.; 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",

year = "1998",

doi = "10.1109/IPPS.1998.669959",

language = "English (US)",

isbn = "0818684046",

pages = "475--484",

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

publisher = "IEEE Comp Soc",

}

Shan, H & Singh, JP 1998, Parallel tree building on a range of shared address space multiprocessors: Algorithms and application performance. in Proceedings of the International Parallel Processing Symposium, IPPS. IEEE Comp Soc, 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

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

Y1 - 1998

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

SP - 475

EP - 484

BT - Proceedings of the International Parallel Processing Symposium, IPPS

PB - IEEE Comp Soc

Y2 - 30 March 1998 through 3 April 1998

ER -

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

Abstract

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this