[[PageOutline(1)]]

= 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^2^) 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 ==
[[Image(bare.png)]] 

== preprint ==
http://jp.arxiv.org/abs/0904.3659

== Recent test results with RV870 ==
I've created a [wiki:"Tests_With_RV870" new page] dedicated to Radeon 5870.

= Demo Program =
A demo program of our many-body simulation code.
To control the program, see a message printed on the command window.
It will takes 15-20 seconds to finish one simulation then it will print the sustained perfromance of the simulation. 
I attach five different initial models with different N. 
Press 1-5 to change the model. Larger N, the better performance. 

 * Download
   * [attachment:R700demo.zip]

 * System Requirement
   * Windows XP/Vista (both 32 and 64 bit version works)
   * Catalyst version 9.4 or later
   * A supported GPU board (both R600 and R700 GPU works)

 * Premilinary Benchmark Results
   [http://spreadsheets.google.com/pub?key=r3oiL9QyqtnbBj6EuzguCUw&single=true&gid=0&output=html "link to google doc"]
   * Note the benchmark results compiled here were obtained with the "figure eight N = 10k" model.

Have a fun! 

R700demo was originally developed by K.Fujiwara. N.Nakasato has modifed it
to support our latest code with minior enhancements.

[[Image(screenshot.png)]] 


= 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
is reduced from O(N^2^) 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^6^ particles
took 5.79 hours and executed 1.2 x 10^13^ 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 == 
[[Image(time.png)]] 

== preprint == 
http://arxiv.org/abs/0909.0541