Cornerstone: Octree Construction Algorithms for Scalable Particle Simulations

This paper presents an octree construction method, called Cornerstone, that\nfacilitates global domain decomposition and interactions between particles in\nmesh-free numerical simulations. Our method is based on algorithms developed\nfor 3D computer graphics, which we extend to distributed high performance\ncomputing (HPC) systems. Cornerstone yields global and locally essential\noctrees and is able to operate on all levels of tree hierarchies in parallel.\nThe resulting octrees are suitable for supporting the computation of various\nkinds of short and long range interactions in N-body methods, such as\nBarnes-Hut and the Fast Multipole Method (FMM). While we provide a CPU\nimplementation, Cornerstone may run entirely on GPUs. This results in\nsignificantly faster tree construction compared to execution on CPUs and serves\nas a powerful building block for the design of simulation codes that move\nbeyond an offloading approach, where only numerically intensive tasks are\ndispatched to GPUs. With data residing exclusively in GPU memory, Cornerstone\neliminates data movements between CPUs and GPUs. As an example, we employ\nCornerstone to generate locally essential octrees for a Barnes-Hut treecode\nrunning on almost the full LUMI-G system with up to 8 trillion particles.\n