Optimizing the Gravitational Tree Algorithm for Many-Core Processors
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913188178558976 |
|---|---|
| author | Tokuue, Tomoyuki Ishiyama, Tomoaki |
| author_facet | Tokuue, Tomoyuki Ishiyama, Tomoaki |
| contents | Gravitational $N$-body simulations calculate numerous interactions between particles. The tree algorithm reduces these calculations by constructing a hierarchical oct-tree structure and approximating gravitational forces on particles. Over the last three decades, the tree algorithm has been extensively used in large-scale simulations, and its parallelization in distributed memory environments has been well studied. However, recent supercomputers are equipped with many CPU cores per node, and optimizations of the tree construction in shared memory environments are becoming crucial. We propose a novel tree construction method in contrast to the conventional top-down approach. It first creates all leaf cells without traversing the tree and then constructs the remaining cells by a bottom-up approach. We evaluated the performance of our novel method on the supercomputer Fugaku and an Intel machine. On a single thread, our method accelerates one of the most time-consuming processes of the conventional tree construction method by a factor of above 3.0 on Fugaku and 2.2 on the Intel machine. Furthermore, as the number of threads increases, our parallel tree construction time reduces considerably. Compared to the conventional sequential tree construction method, we achieve a speedup of over 45 on 48 threads of Fugaku and more than 56 on 112 threads of the Intel machine. In stark contrast to the conventional method, the tree construction with our method no longer constitutes a bottleneck in the tree algorithm, even when using many threads. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_06102 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Optimizing the Gravitational Tree Algorithm for Many-Core Processors Tokuue, Tomoyuki Ishiyama, Tomoaki Instrumentation and Methods for Astrophysics Cosmology and Nongalactic Astrophysics Astrophysics of Galaxies Gravitational $N$-body simulations calculate numerous interactions between particles. The tree algorithm reduces these calculations by constructing a hierarchical oct-tree structure and approximating gravitational forces on particles. Over the last three decades, the tree algorithm has been extensively used in large-scale simulations, and its parallelization in distributed memory environments has been well studied. However, recent supercomputers are equipped with many CPU cores per node, and optimizations of the tree construction in shared memory environments are becoming crucial. We propose a novel tree construction method in contrast to the conventional top-down approach. It first creates all leaf cells without traversing the tree and then constructs the remaining cells by a bottom-up approach. We evaluated the performance of our novel method on the supercomputer Fugaku and an Intel machine. On a single thread, our method accelerates one of the most time-consuming processes of the conventional tree construction method by a factor of above 3.0 on Fugaku and 2.2 on the Intel machine. Furthermore, as the number of threads increases, our parallel tree construction time reduces considerably. Compared to the conventional sequential tree construction method, we achieve a speedup of over 45 on 48 threads of Fugaku and more than 56 on 112 threads of the Intel machine. In stark contrast to the conventional method, the tree construction with our method no longer constitutes a bottleneck in the tree algorithm, even when using many threads. |
| title | Optimizing the Gravitational Tree Algorithm for Many-Core Processors |
| topic | Instrumentation and Methods for Astrophysics Cosmology and Nongalactic Astrophysics Astrophysics of Galaxies |
| url | https://arxiv.org/abs/2312.06102 |