Physical Sciences and Mathematics Commons^™

Efficient Gpu Tree Walks For Effective Distributed N-Body Simulations, Jianqiao Liu, Michael Robson, Thomas Quinn, Milind Kulkarni

Computer Science: Faculty Publications

N-body problems, such as simulating the motion of stars in a galaxy, are popularly solved using tree codes like Barnes-Hut. ChaNGa is a best-of-breed n-body platform that uses an asymptotically-efficient tree traversal strategy known as a dual-tree walk to quickly determine which bodies need to interact with each other to provide an accurate simulation result. However, this strategy does not work well on GPUs, due to the highly-irregular nature of the dual-tree algorithm. On GPUs, ChaNGa uses a hybrid strategy where the CPU performs the tree walk to determine which bodies interact while the GPU performs the force computation. In …