Skip to content
Tutorials Center
My learning

Topics

Lesson 27 of 31 ยท Projects

Project: N-Body Simulation

Simulate gravity on the GPU: all-pairs forces, shared-memory tiling of bodies, leapfrog integration and an energy check, with runnable NumPy stand-ins.

An N-body simulation follows many bodies (stars, particles, atoms) that pull on each other. The simplest method, all pairs, computes the force between every body and every other body. For N bodies that is about N^2 interactions per time step. It is a perfect GPU workload: every body's acceleration can be computed independently, the arithmetic per interaction is large compared with the data it needs, and the same data is read again and again by many threads. This is why the N-body kernel appears in the GPU Gems book series and in many CUDA samples.

In this project you write the force kernel, speed it up with shared-memory tiling, advance the bodies in time with a stable integrator, and check the physics with an energy test. As usual, the CUDA is read-only and the runnable code is a stand-in: NumPy for the physics and a counting model for the tiling.

No GPU runs on this site. The Python examples are real programs, but they run on the CPU through NumPy. The load counts come from a model of tiling, the energy numbers from a real (CPU) simulation. No CUDA timing is claimed.

The physics in one paragraph

With unit gravitational constant, body j pulls on body i with an acceleration of

a_i = sum over j of m_j * (p_j - p_i) / (|p_j - p_i|^2 + eps^2)^(3/2)

where p is position, m is mass and eps is a small softening length. Without softening, two bodies that happen to pass very close produce an enormous force and ruin the simulation, and the term for j = i would be 0 / 0. With softening the denominator is never zero, and a body's pull on itself is exactly zero because p_j - p_i is the zero vector. That detail lets the kernel skip an if (i != j) branch.

Step 1: one thread per body

Each thread owns one body i, loops over all N bodies j, adds up their pulls and writes the total. Store each body as a float4 (x, y, z, mass): a 16-byte aligned load fetches the whole body in one transaction.

C++
__global__ void forcesNaive(const float4* bodies, float3* acc, int n, float eps2) {
    int i = blockIdx.x * blockDim.x + threadIdx.x;
    if (i >= n) return;

    float4 me = bodies[i];
    float ax = 0.0f, ay = 0.0f, az = 0.0f;

    for (int j = 0; j < n; ++j) {
        float4 other = bodies[j];                  // every thread reads the same bodies[j]
        float dx = other.x - me.x;
        float dy = other.y - me.y;
        float dz = other.z - me.z;
        float r2 = dx * dx + dy * dy + dz * dz + eps2;
        float inv = rsqrtf(r2);                    // fast reciprocal square root
        float s = other.w * inv * inv * inv;       // m / r^3
        ax += dx * s;  ay += dy * s;  az += dz * s;
    }
    acc[i] = make_float3(ax, ay, az);
}

Within a warp every thread reads the same bodies[j] at the same time, which the hardware serves as a broadcast, so this kernel is not terrible. But it still sends N loads from each of N threads through the cache hierarchy, and each interaction costs about 20 floating-point operations, so memory traffic is a real fraction of the cost. Tiling removes most of it.

Step 2: tile the bodies through shared memory

Instead of every thread reading body j on its own, the whole block cooperates. In each round, every thread loads one body into a shared array, the block waits at a barrier, and then every thread uses all the bodies in the tile. After that the block moves to the next tile of bodies.

flowchart LR
    G["Global memory<br/>N bodies"] -->|"round t: each thread<br/>loads one body"| S["Shared tile<br/>P bodies"]
    S -->|"__syncthreads()"| U["All P threads loop<br/>over the P tile bodies"]
    U -->|"__syncthreads()"| G
    U --> A["Accumulate in<br/>registers ax, ay, az"]

A block of P threads reads each body from global memory once, not P times.

C++
__global__ void forcesTiled(const float4* bodies, float3* acc, int n, float eps2) {
    extern __shared__ float4 tile[];               // blockDim.x * sizeof(float4) bytes

    int i = blockIdx.x * blockDim.x + threadIdx.x;
    float4 me = (i < n) ? bodies[i] : make_float4(0, 0, 0, 0);
    float ax = 0.0f, ay = 0.0f, az = 0.0f;

    for (int t0 = 0; t0 < n; t0 += blockDim.x) {
        int j = t0 + threadIdx.x;
        // padding bodies have mass 0, so they add nothing to the sum
        tile[threadIdx.x] = (j < n) ? bodies[j] : make_float4(0, 0, 0, 0);
        __syncthreads();                           // the tile is complete

        for (int k = 0; k < blockDim.x; ++k) {
            float4 o = tile[k];
            float dx = o.x - me.x, dy = o.y - me.y, dz = o.z - me.z;
            float r2 = dx * dx + dy * dy + dz * dz + eps2;
            float inv = rsqrtf(r2);
            float s = o.w * inv * inv * inv;
            ax += dx * s;  ay += dy * s;  az += dz * s;
        }
        __syncthreads();                           // done reading before the next load
    }
    if (i < n) acc[i] = make_float3(ax, ay, az);
}
// forcesTiled<<<(n + 255) / 256, 256, 256 * sizeof(float4)>>>(d_bodies, d_acc, n, eps2);

The pattern should look familiar from Shared Memory and Tiling, with two differences. Because the tail of the last tile can run past N, the kernel pads with zero-mass bodies instead of using an early return, so every thread still reaches both barriers. And tile[k] is read by all threads at the same index, a broadcast with no bank conflict.

The stand-in below does both algorithms on 64 random bodies. accel_loop is what one naive thread does. accel_tiled walks through the tiles exactly as a block would, counting how many bodies are loaded from "global memory".

Python Tiled forces match the all-pairs loop, with far fewer loads

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The tiled results match the plain loop for every tile width. The loads fall from N^2 = 4,096 to N^2 / P: 512, 256 and 128 for P = 8, 16, 32. As with matrix multiplication, the saving equals the tile width. In practice tile widths of 128 to 256 threads are common. A block of 256 threads uses only 256 x 16 = 4 KB of shared memory, so shared memory is not a limiting factor here, and the kernel is mostly limited by raw floating-point throughput, which is the best place to be.

Step 3: advance time with the leapfrog method

Knowing the acceleration, you update the velocities and positions. The obvious Euler method (p += v*dt, v += a*dt) is easy but unstable for orbits: energy creeps upward and orbits spiral outward. A far better choice at the same cost is leapfrog (also called kick-drift-kick):

  1. Half-kick: v += a * dt/2
  2. Drift: p += v * dt
  3. Recompute the accelerations a at the new positions (the expensive kernel)
  4. Half-kick: v += a * dt/2

The acceleration from step 3 is reused as the first half-kick of the next step, so there is still just one force evaluation per step. On the GPU the host code looks like this, with two tiny kernels and one big one:

C++
// a (d_acc) is valid for the current positions
for (int step = 0; step < steps; ++step) {
    kick<<<blocks, 256>>>(d_vel, d_acc, 0.5f * dt, n);    // half-kick
    drift<<<blocks, 256>>>(d_bodies, d_vel, dt, n);       // p += v * dt
    forcesTiled<<<blocks, 256, 256 * sizeof(float4)>>>(d_bodies, d_acc, n, eps2);
    kick<<<blocks, 256>>>(d_vel, d_acc, 0.5f * dt, n);    // half-kick
}

All the launches go into the same stream, so they run in order and no explicit synchronization is needed between them (see Streams and Events). Only when you copy results to the host do you need to synchronize.

Let us compare the two integrators on the simplest orbit there is: one light body circling a heavy mass at distance 1, with speed 1, which is an exact circle. The correct answer is that the radius stays 1 and the energy stays constant.

Python Euler versus leapfrog on a circular orbit

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Euler lets the body drift outward: the radius grows past 1.1 even with the smallest step shown, and the energy error is of order 10 to 30 percent. Leapfrog keeps the radius at 1.000 and the energy error below 1e-7 with the same step sizes. Halving dt shrinks Euler's error only slowly (here by about a third), while leapfrog's error falls about 16 times. In a GPU simulation that runs for millions of steps, only a symplectic scheme like leapfrog stays believable.

Step 4: check the physics with energy and momentum

A simulation can run without crashing and still be wrong. Physics gives free tests: in a closed system, the total energy (kinetic plus potential) and the total momentum are conserved. The potential energy of all pairs uses the same softening as the force, otherwise the test would fail for the wrong reason:

PE = - sum over pairs i<j of m_i * m_j / sqrt(|p_i - p_j|^2 + eps^2)

The next stand-in simulates 128 bodies for 500 steps with leapfrog, using the vectorized all-pairs formula (this is what the GPU kernel computes, as one NumPy expression) and prints the relative energy drift.

Python 128 bodies: energy and momentum stay put

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The total energy stays at -0.15291 to five digits at every checkpoint, and momentum stays at zero up to rounding. Momentum is conserved because the force between two bodies is equal and opposite by construction. If you introduce a bug, for example a wrong sign or forgetting the mass of body j, the energy test is the first thing to fail. On the GPU, single precision gives noticeably larger drift than float64 over long runs; scientific codes either use double precision or accept and monitor the error.

Going further

  • Switch to structure-of-arrays storage (x[], y[], z[], m[]) and compare with float4 (see Global Memory and Coalescing).
  • Unroll the inner loop (#pragma unroll 8) and try a block size of 128, 256 or 512.
  • For millions of bodies, N^2 is too slow. Tree codes (Barnes-Hut) and fast multipole methods bring the cost to roughly N log N; their irregular memory access is much harder on a GPU, and all-pairs tiling is still used for the nearby interactions.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is softening added to the distance in the force formula?

    The denominator becomes (r^2 + eps^2)^(3/2), never zero. A body's pull on itself is the zero vector, so no i != j branch is needed.
  2. 2. A block of 256 threads tiles N bodies through shared memory. Compared with no sharing, how many global body loads per block are needed?

    Each thread loads one body per round and the whole block reuses the tile, so global traffic per block is N bodies instead of 256 x N.
  3. 3. Why does the tiled kernel pad the last tile with zero-mass bodies instead of returning early for threads with i >= n?

    A thread that left the kernel would skip the barrier and its share of the tile load. Padding keeps the block uniform without changing the physics.
  4. 4. Which integrator keeps an orbit's energy nearly constant at one force evaluation per step?

    Leapfrog is symplectic: it keeps the energy error bounded and small, while Euler's error grows steadily.
  5. 5. What does a growing relative energy drift in a closed N-body simulation usually tell you?

    Conservation laws are free correctness tests. A drift that keeps growing points to a bug, a large dt or precision problems.

Summary

  • All-pairs N-body does about N^2 independent interactions per step: one thread per body, a loop over all other bodies, and a softened force so nothing divides by zero.
  • Tiling through shared memory lets a block read each body once instead of once per thread, so global loads fall by the block size; pad the last tile with zero-mass bodies so all threads reach the barriers.
  • Leapfrog costs one force evaluation per step and conserves energy far better than Euler.
  • Use conservation of energy and momentum as correctness tests, with a potential energy that uses the same softening as the force.
  • For huge N, switch to tree methods; keep all-pairs tiling for the near field.

Continue with Project: Monte Carlo Pi and Option Pricing.