Optimized Real Time N-Body Simulation - Part 2: SIMD and OpenMP

In Part 1 I built the naive brute-force N-body simulation and watched it fall apart past a few thousand bodies - almost 7 seconds per frame at 50,000 bodies. This time we're going to squeeze every last cycle out of that algorithm without changing the physics.

Spoiler: at N=20,000 the simulation goes from 477 seconds per frame to 1.2 seconds - roughly a 400x speedup.

Profiling First

Guessing where the bottleneck is rarely works. I built a custom in-simulation profiler that exports per-step force time, render time, and FPS to CSV, and ran the Visual Studio Performance Analyzer to see exactly where the CPU was burning cycles.

The culprit was obvious: the square root in the force calculation. A square root costs about 29 clock cycles versus 1 for an addition. At N=20,000 that's 400 million force calculations and 400 million square roots per frame - 11.6 billion clock cycles just for sqrt.

Even accounting for the rest of the math, the absolute best single-core runtime was over 3 seconds per frame. Real-time simulation on one thread was physically impossible, so the plan became: optimize single-core performance first, then throw threads at it, then use SIMD.

Compiler Optimizations

The first optimizations were embarrassingly cheap - no algorithm changes, just telling the compiler what it was allowed to do:

• Inlining via LTCG (Link-Time Code Generation): eliminates 400 million function-call jump-and-return cycles by laying computeAcceleration inline with the loop.
• O2: aggressive loop vectorization, code restructuring, and inline expansion.
• FastMath: treats division as multiplication by the reciprocal, and lets the compiler reorder floating-point operations.

These alone took N=20,000 from 477.85s to 51.04s - a 9.4x speedup.

Multithreading with OpenMP

The force loop has a beautiful property: each particle's acceleration depends only on the others, so the outer loop is embarrassingly parallel. One #pragma omp parallel for and the work splits across all 16 logical threads of the AMD 5800H.

Bodies	Optimized (s)	Parallel (s)	Compiler speedup	Parallel speedup	Total
1,000	0.22	0.30	4.7x	0.7x	3.4x
5,000	3.36	1.00	7.6x	3.4x	25.7x
20,000	51.04	7.41	9.4x	6.9x	64.5x
100,000	1303.52	144.89	-	9.0x	-

Note the 9x instead of the theoretical 16x - the 5800H has 8 physical cores with SMT, so 8x is the realistic ceiling. And for small N the thread-management overhead eats the gains.

SIMD with AVX2

Now the fun part. AVX2 registers are 256 bits wide - four doubles or eight floats at once. I restructured the algorithm to compute the attractions between two target particles (I) and four source particles (J) simultaneously, packing them into __m256 registers and driving the whole force kernel with AVX2 intrinsics.

A few tricks made the SIMD kernel fast:

• Mixed precision: positions load as doubles (preserving memory bandwidth), but get converted to floats for the arithmetic, so 8 interactions compute per instruction instead of 4.
• Hardware reciprocal square root (_mm256_rsqrt_ps): replaces the 29-cycle sqrt + division with a single fast intrinsic.
• ID masking to zero out self-interactions instead of branching.

The result at N=20,000: 1.21s per frame, a 6.1x gain over the parallel version and roughly 395x faster than the baseline.

Bodies	SIMD time (s)	Speedup vs parallel
2,000	0.118	3.9x
10,000	0.408	6.0x
20,000	1.210	6.1x
100,000	25.44	5.7x

10 steps of N=100,000 ran in 25 seconds, down from 149 seconds for the parallel-only build.

What's Next

A 400x speedup sounds great until you realize the brute-force algorithm still scales O(N²). My next project ditches the double loop entirely for a Barnes-Hut tree with spatial partitioning, parallel tree construction, and Morton ordering - check it out. The full write-up for this project is available as a PDF report.