Efficient Tree-based Parallel Algorithms for N-Body Simulations Using C++ Standard Parallelism

Thomas Lane Cassell; Tom Deakin; Aksel Alpay; Vincent Heuveline; Gonzalo Brito Gadeschi

doi:10.1109/SCW63240.2024.00099

Efficient Tree-based Parallel Algorithms for N-Body Simulations Using C++ Standard Parallelism

Thomas Lane Cassell, Tom Deakin, Aksel Alpay, Vincent Heuveline, Gonzalo Brito Gadeschi

School of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

291 Downloads (Pure)

Abstract

The Barnes-Hut approximation for N-body simula tions reduces the time complexity of the naive all-pairs approach from O(N 2 ) to O(N log N) by hierarchically aggregating nearby particles into single entities using a tree data structure. This inherently irregular algorithm poses substantial challenges for performance portable implementations on multi-core CPUs and GPUs. We introduce two portable fully-parallel Barnes-Hut implementation strategies that trade-off different levels of GPU support for performance: an unbalanced concurrent octree, and a balanced bounding volume hierarchy sorted by a Hilbert space filling curve. We implemente these algorithms in portable ISO C++ using parallel algorithms and concurrency primitives like atomics. The results demonstrate competitive performance on a range of CPUs and GPUs. Additionally, they highlight the effectiveness of the par execution policy for highly concurrent irregular algorithms, outperforming par_unseq on CPUs and GPUs with Independent Forward Progress.

Original language	English
Title of host publication	14th Workshop on Irregular Applications
Subtitle of host publication	Architectures and Algorithms co-located with IEEE/ACM Supercomputing
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	708-717
ISBN (Print)	979-8-3503-5554-3
DOIs	https://doi.org/10.1109/SCW63240.2024.00099
Publication status	E-pub ahead of print - 26 Nov 2024
Event	Workshop on Irregular Applications: Architecture and Algorithms - Atlanta, United States Duration: 17 Nov 2024 → 17 Nov 2024 https://hpc.pnl.gov/IA3/

Publication series

Name	SC24-W: Workshops of the International Conference for High Performance Computing, Networking, Storage and Analysis
Publisher	IEEE

Conference

Conference	Workshop on Irregular Applications
Abbreviated title	IA3
Country/Territory	United States
City	Atlanta
Period	17/11/24 → 17/11/24
Internet address	https://hpc.pnl.gov/IA3/

Access to Document

10.1109/SCW63240.2024.00099

Full-text PDF (accepted manuscript)
This is the accepted author manuscript (AAM) of the article which has been made Open Access under the University of Bristol's Scholarly Works Policy. The final published version (Version of Record) can be found on the publisher's website. The copyright of any third-party content, such as images, remains with the copyright holder.
Accepted author manuscript, 367 KBLicence: CC BY

Handle.net

Persistent link

Cite this

Lane Cassell, T., Deakin, T., Alpay, A., Heuveline, V., & Brito Gadeschi, G. (2024). Efficient Tree-based Parallel Algorithms for N-Body Simulations Using C++ Standard Parallelism. In 14th Workshop on Irregular Applications: Architectures and Algorithms co-located with IEEE/ACM Supercomputing (pp. 708-717). (SC24-W: Workshops of the International Conference for High Performance Computing, Networking, Storage and Analysis). Institute of Electrical and Electronics Engineers (IEEE). Advance online publication. https://doi.org/10.1109/SCW63240.2024.00099

Lane Cassell, Thomas ; Deakin, Tom ; Alpay, Aksel et al. / Efficient Tree-based Parallel Algorithms for N-Body Simulations Using C++ Standard Parallelism. 14th Workshop on Irregular Applications: Architectures and Algorithms co-located with IEEE/ACM Supercomputing. Institute of Electrical and Electronics Engineers (IEEE), 2024. pp. 708-717 (SC24-W: Workshops of the International Conference for High Performance Computing, Networking, Storage and Analysis).

@inproceedings{a61da15d738e4c23afd790dcea70f3a2,

title = "Efficient Tree-based Parallel Algorithms for N-Body Simulations Using C++ Standard Parallelism",

abstract = "The Barnes-Hut approximation for N-body simula tions reduces the time complexity of the naive all-pairs approach from O(N 2 ) to O(N log N) by hierarchically aggregating nearby particles into single entities using a tree data structure. This inherently irregular algorithm poses substantial challenges for performance portable implementations on multi-core CPUs and GPUs. We introduce two portable fully-parallel Barnes-Hut implementation strategies that trade-off different levels of GPU support for performance: an unbalanced concurrent octree, and a balanced bounding volume hierarchy sorted by a Hilbert space filling curve. We implemente these algorithms in portable ISO C++ using parallel algorithms and concurrency primitives like atomics. The results demonstrate competitive performance on a range of CPUs and GPUs. Additionally, they highlight the effectiveness of the par execution policy for highly concurrent irregular algorithms, outperforming par\_unseq on CPUs and GPUs with Independent Forward Progress.",

author = "\{Lane Cassell\}, Thomas and Tom Deakin and Aksel Alpay and Vincent Heuveline and \{Brito Gadeschi\}, Gonzalo",

year = "2024",

month = nov,

day = "26",

doi = "10.1109/SCW63240.2024.00099",

language = "English",

isbn = "979-8-3503-5554-3",

series = "SC24-W: Workshops of the International Conference for High Performance Computing, Networking, Storage and Analysis",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

pages = "708--717",

booktitle = "14th Workshop on Irregular Applications",

address = "United States",

note = "Workshop on Irregular Applications : Architecture and Algorithms, IA3 ; Conference date: 17-11-2024 Through 17-11-2024",

url = "https://hpc.pnl.gov/IA3/",

}

Lane Cassell, T, Deakin, T, Alpay, A, Heuveline, V & Brito Gadeschi, G 2024, Efficient Tree-based Parallel Algorithms for N-Body Simulations Using C++ Standard Parallelism. in 14th Workshop on Irregular Applications: Architectures and Algorithms co-located with IEEE/ACM Supercomputing. SC24-W: Workshops of the International Conference for High Performance Computing, Networking, Storage and Analysis, Institute of Electrical and Electronics Engineers (IEEE), pp. 708-717, Workshop on Irregular Applications, Atlanta, Georgia, United States, 17/11/24. https://doi.org/10.1109/SCW63240.2024.00099

Efficient Tree-based Parallel Algorithms for N-Body Simulations Using C++ Standard Parallelism. / Lane Cassell, Thomas; Deakin, Tom; Alpay, Aksel et al.
14th Workshop on Irregular Applications: Architectures and Algorithms co-located with IEEE/ACM Supercomputing. Institute of Electrical and Electronics Engineers (IEEE), 2024. p. 708-717 (SC24-W: Workshops of the International Conference for High Performance Computing, Networking, Storage and Analysis).

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

TY - GEN

T1 - Efficient Tree-based Parallel Algorithms for N-Body Simulations Using C++ Standard Parallelism

AU - Lane Cassell, Thomas

AU - Deakin, Tom

AU - Alpay, Aksel

AU - Heuveline, Vincent

AU - Brito Gadeschi, Gonzalo

PY - 2024/11/26

Y1 - 2024/11/26

N2 - The Barnes-Hut approximation for N-body simula tions reduces the time complexity of the naive all-pairs approach from O(N 2 ) to O(N log N) by hierarchically aggregating nearby particles into single entities using a tree data structure. This inherently irregular algorithm poses substantial challenges for performance portable implementations on multi-core CPUs and GPUs. We introduce two portable fully-parallel Barnes-Hut implementation strategies that trade-off different levels of GPU support for performance: an unbalanced concurrent octree, and a balanced bounding volume hierarchy sorted by a Hilbert space filling curve. We implemente these algorithms in portable ISO C++ using parallel algorithms and concurrency primitives like atomics. The results demonstrate competitive performance on a range of CPUs and GPUs. Additionally, they highlight the effectiveness of the par execution policy for highly concurrent irregular algorithms, outperforming par_unseq on CPUs and GPUs with Independent Forward Progress.

AB - The Barnes-Hut approximation for N-body simula tions reduces the time complexity of the naive all-pairs approach from O(N 2 ) to O(N log N) by hierarchically aggregating nearby particles into single entities using a tree data structure. This inherently irregular algorithm poses substantial challenges for performance portable implementations on multi-core CPUs and GPUs. We introduce two portable fully-parallel Barnes-Hut implementation strategies that trade-off different levels of GPU support for performance: an unbalanced concurrent octree, and a balanced bounding volume hierarchy sorted by a Hilbert space filling curve. We implemente these algorithms in portable ISO C++ using parallel algorithms and concurrency primitives like atomics. The results demonstrate competitive performance on a range of CPUs and GPUs. Additionally, they highlight the effectiveness of the par execution policy for highly concurrent irregular algorithms, outperforming par_unseq on CPUs and GPUs with Independent Forward Progress.

UR - https://conferences.computer.org/sc-wpub/#!/toc/0

UR - https://hpc.pnl.gov/IA3/

UR - https://sc24.supercomputing.org/proceedings/workshops/workshop_pages/ws_ia108.html

U2 - 10.1109/SCW63240.2024.00099

DO - 10.1109/SCW63240.2024.00099

M3 - Conference Contribution (Conference Proceeding)

SN - 979-8-3503-5554-3

T3 - SC24-W: Workshops of the International Conference for High Performance Computing, Networking, Storage and Analysis

SP - 708

EP - 717

BT - 14th Workshop on Irregular Applications

PB - Institute of Electrical and Electronics Engineers (IEEE)

T2 - Workshop on Irregular Applications

Y2 - 17 November 2024 through 17 November 2024

ER -

Lane Cassell T, Deakin T, Alpay A, Heuveline V, Brito Gadeschi G. Efficient Tree-based Parallel Algorithms for N-Body Simulations Using C++ Standard Parallelism. In 14th Workshop on Irregular Applications: Architectures and Algorithms co-located with IEEE/ACM Supercomputing. Institute of Electrical and Electronics Engineers (IEEE). 2024. p. 708-717. (SC24-W: Workshops of the International Conference for High Performance Computing, Networking, Storage and Analysis). Epub 2024 Nov 26. doi: 10.1109/SCW63240.2024.00099

Efficient Tree-based Parallel Algorithms for N-Body Simulations Using C++ Standard Parallelism

Abstract

Publication series

Conference

Access to Document

Handle.net

Other files and links

Fingerprint

Cite this