it framerate:fps
Drag mouse to rotate model. Hold shift key or use mouse wheel to zoom it (canvas is matched to the browser window). N = 4096. The script makes 2×it = 20 iterations per frame. Framerate is calculated after every 20 iterations. Be careful with overclocking, this script overheats my videocard quickly.

N-Body toy

N-Body dynamics
    d 2ri / dt 2 = Fi = G m ∑ k (rk - ri ) / |rk - ri|3
for N = 4096 are simulated. We put G m = 1 by the time scaling. Explicit scheme
    r t+2 = 2 r t+1 - r t + F t+1 Δt2
with constant time step Δt is used.
As bodies approach each other, the force between them grows without bound, which is an undesirable situation for numerical integration. To preclude collisions softening factor ε = 0.1 is added [1], this is reasonable if the bodies represent galaxies that may pass right through each other. The denominator is rewritten as follows:
    Fi = ∑ k (rk - ri ) / (|rk - ri|2 + ε2)3/2.
So this simulation is not absolutely accurate but funny. You can see clasters formation from a slowly rotating random ring.

See also N = 8K simulation. I can't make a spiral galaxy (I'm not an expert :)

Performance results. 400 Gflops in your home PC!

I've got 2×1010 interactions per second, i.e. 20-times speedup after I've replaces 1D textures by 2D ones. Thanks to Lars Nyland (NVIDIA) private message:
"From what I know of textures, the 1d textures are very slow compared to 2d. In 2004, when we did our Cg version of n-body, we converted the index i of a body into a pair (ix,iy) and used a 2d texture to look up the important attributes of the body. For something like 4096 bodies, we used a 64*64 texture. This was much faster than you would have expected."
It is similar to the CAL based simulations without loop-unrolling [2]. N-Body is an amazing but a little special application.
N =   4096     16K     32K
HD 4870   1200=20×60  
20
80=4×20
21.5
21=2.1×10
22.5
HD 4650   420=21×20
7
28=14×2  
7.5
5=2.5×2
5.4
You see above:
    integration time steps per second = fps × iterations per frame   and
    integration time steps per second × N 2 / 10 9   i.e.   interactions per second / 10 9
Multiply interactions per second by (about) 20 floating point operations to get Flops.

HD 4870   800 shaders, 790gpu/1100mem MHz, 256 bit bus width, GDDR5 memory
HD 4650   320 shaders, 712gpu/550mem MHz, 128 bit bus width, GDDR3 memory

Numbers: shaders power ratio is 800×790 / 320×712 = 2.8 and performance ratio is 20/7 = 2.9 so GDDR3 memory bandwidth is not a bottleneck in this simulation!

The algorithm outline

For N = 64×64 = 4096 bodies 3D coordinates are stored in two 64×64 RGB float texture2D. The main computations are made in this shader. The for cycle sums up all forces.
<script id="shader-fs" type="x-shader/x-fragment"> 
#ifdef GL_ES
precision highp float;
#endif
  uniform sampler2D samp;
  uniform sampler2D samp1;
  varying vec2 vTexCoord;
  const float d = 1./64., e2 = .01,  dt2 = .00001;
void main(void) {
   vec3 r = texture2D(samp, vTexCoord).xyz;
   vec3 r1  = texture2D(samp1, vTexCoord).xyz;
   vec3 f = vec3( 0. );
   for(float y = 0.; y < 1.; y += d ){
    for(float x = 0.; x < 1.; x += d ){
     vec3 v = texture2D(samp1, vTexCoord + vec2(x, y)).xyz - r1;
     float a = dot(v, v) + e2;
     f += v/(a*sqrt(a));
    }
   }
   r = 2.*r1 - r + f*dt2;
   gl_FragColor = vec4(r, 0. );
}
</script> 
This vertex script renders the 2×2 square into FBO to make computations for every pixel in textures.
<script id="shader-vs" type="x-shader/x-vertex"> 
  attribute vec2 aPos;
  attribute vec2 aTexCoord;
  varying   vec2 vTexCoord;
void main(void) {
   gl_Position = vec4(aPos, 0., 1.);
   vTexCoord = aTexCoord;
}
</script> 
N points square lattice is used to show the bodies in the shader below
<script id="shader-vs-show" type="x-shader/x-vertex"> 
  attribute vec2 aPoints;
  uniform mat4 mvMatrix;
  uniform mat4 prMatrix;
  uniform sampler2D uTexSamp;
  varying vec4 color;
void main(void) {
   gl_Position = prMatrix * mvMatrix * texture2D(uTexSamp, aPoints );
   color = vec4( 1.);
}
</script> 
Computations are organized by the function
function draw(){
   gl.viewport(0, 0, 64, 64);
   gl.useProgram(prog);
   for(var i = 0; i < it; i++){
     gl.uniform1i(sampLoc, 0);
     gl.uniform1i(samp1Loc, 1);
     gl.bindFramebuffer(gl.FRAMEBUFFER, FBO2);
     gl.drawArrays(gl.TRIANGLE_STRIP, 0, 4);

     gl.uniform1i(sampLoc, 1);
     gl.uniform1i(samp1Loc, 2);
     gl.bindFramebuffer(gl.FRAMEBUFFER, FBO);
     gl.drawArrays(gl.TRIANGLE_STRIP, 0, 4);

     gl.uniform1i(sampLoc, 2);
     gl.uniform1i(samp1Loc, 0);
     gl.bindFramebuffer(gl.FRAMEBUFFER, FBO1);
     gl.drawArrays(gl.TRIANGLE_STRIP, 0, 4);
   }
   drawScene();
   frames++;
}
at last drawScene() prepares transformations and executes
  gl.drawArrays(gl.POINTS, 0, 64*64);
to show scene.

[1] GPU Gems 3. Chapter 31. Fast N-Body Simulation with CUDA L.Nyland, M.Harris, J.Prins
[2] Kazuki Fujiwara, Naohito Nakasato Fast Simulations of Gravitational Many-body Problem on RV770 GPU arXiv:0904.3659v1
[3] S.F.P.Zwart, R.G.Belleman, P.M.Geldof   High-performance direct gravitational N-body simulations on graphics processing units. New Astronomy 12 (2007) 641-650
[4] Vanderbei's N-Body Page 1000 "Star Clusters" Java simulation
[5] WebGL Orrery by Ilmari Heikkinen


Simulations on GPU
updated 23 Jan 2011