Fast Simulations of Gravitational Many-body Problem on RV770 GPU

by K.Fujiwara and N.Nakasato (Based on Fujiwara's undergraduate thesis 2008 University of Aizu)

abstract

The gravitational many-body problem is a problem concerning the movement of bodies, which are interacting through gravity. However, solving the gravitational many-body problem with a CPU takes a lot of time due to O(N²) computational complexity. In this paper, we report our technique to speed-up the exact force-calculation on RV770 GPU from AMD/ATi. Our implementation on RV770 GPU running at 750 MHz shows performance of ~ 1 Tflops thanks to efficient cache architecture of RV770 GPU. This significant performance result is fastest ever as far as we know. Our optimized result is realized by a loop-unrolling technique that is highly effective for RV770 GPU.

Result

preprint

​http://jp.arxiv.org/abs/0904.3659

Oct-tree Method on GPU: $42/Gflops Cosmological Simulation

by N.Nakasato (submitted April 14 2009)

abstract

The kd-tree is a fundamental tool in computer science. Among others, an application of the kd-tree search (oct-tree method) to fast evaluation of particle interactions and neighbor search is highly important since computational complexity of these problems are reduced from O(N²) with a brute force method to O(N log N) with the tree method where N is a number of particles. In this paper, we present a parallel implementation of the tree method running on a graphic processor unit (GPU). We successfully run a simulation of structure formation in the universe very efficiently. On our system, which costs roughly $900, the run with N ~ 2.87 x 10⁶ particles took 5.79 hours and executed 1.2 x 10¹³ force evaluations in total. We obtained the sustained computing speed of 21.8 Gflops and the cost per Gflops of $41.6/Gflops that is two and half times better than the previous record in 2006.

Result

preprint

to be posted

Demo programs

to be posted