The Development of Grav-Sim

Grav-Sim uses an evolution of the “Art of Computer Science” ACS code base provided on www.artcompsci.org by Piet Hut and Jun Makino, two of the leading authorities on n-body simulations.


Porting from Ruby to C++

Grav-Sim was ported from Ruby to C++ to make it practical for home users to run simulations. Although home computers are vastly more powerful than they were even 10 years ago, gravity simulation can be so intensive that we need every drop of performance we can get. A compiled language like C++ is a good choice with a significant performance improvement compared to an interpreted language like Ruby.


Simulators

Instead of a single Ruby script "world6.rb", Grav-Sim provides 3 compiled command-line simulators:

  • Fast-Sim
  • Grav-Sim
  • Fine-Sim

Floating Point Data Types

The pre-compiled choices of Grav-Sim data-type are:

  • Fast-Sim: “float” for up to 7-digit precision
  • Grav-Sim: “double” for up to 15-digit precision
  • Fine-Sim: “dd_real” for up to 30-digit precision

High Precision Libraries

Fine-Sim is compiled with the high precision QD library and can also be compiled with the multi-precision ARPREC library.

The following data types are available to those compiling the source code:

QD Library

  • dd_real (double-double-real, uses 2 doubles, accurate to roughly 30 decimal digits)
  • qd_real (quad-double-real, uses 4 doubles, accurate to roughly 60 decimal digits)

ARPREC Library

  • mp_real (multi-precision-real, uses an arbitrary-length sting, 90 decimal digits or beyond)

The extra precision does come at a price in terms of performance (particularly with mp_real).


Brute-Force Accelerator

All simulators include the brute-force direct calculation method advocated by Hut and Makino on the ACS website. This gives the maximum possible accuracy, but at a cost of “order n-squared performance”. This means that a 10,000-body simulation takes 100 times longer than a 1,000-body simulation, even though the problem size is only 10 times as big.


Tree-Based Accelerators

Also included is a range of tree-based accelerators developed by Mark Ridler, the author. They range from “Barnes-Hut Tree” as published by Joshua Barnes and Piet Hut in 1986, to the "Walter Dehnen" method as used in the GyrfalcON code

Monopole and Quadrupole Terms

The tree-based gravity calculation uses a multipole expansion with monopole and quadrupole terms (note that gravity dipole terms are always zero if you calculate relative to the centre-of-mass).


Batch Processing

All Grav-Sim integration, gravity and collision time-scale calculations have been adapted to calculate with many bodies at a time. This has the effect of improving locality-of-reference in terms of computer memory (RAM) accesses. The technique is particulary effective with modern processors that use several levels of caching, each one smaller than the last, right down to the CPU registers.

There are 2 configurable parameters that control the batch processing:

  • Maximum batch size (too big and the batch itself won't fit in the cache
  • Minimum batch size (below which the tree-based accelerator reverts to brute-force)

Batch processing is one of the fundamental changes introduced by Grav-Sim that affects almost every part of the ACS code as ported from Ruby.


Integrators

The following list of integrators provided by Hut and Makino are available.

  • Hermite-8 (GravSim and FineSim only)
  • Hermite-6 (the default)
  • Hermite
  • Chin-Chen (or Optimised)
  • Runge-Kutta (2n, 2n_fsal, 3, 4, 4n)
  • Leap-Frog
  • Proto-Hermite
  • Forward-Plus
  • Forward-Euler

The Multi-Step integrator was available for those compiling early versions of the Grav-Sim source code. This is no longer maintained.


Individual Time-steps

In keeping with the spirit of ACS, Grav-Sim caters for:

  • Individual time-steps (the default)
  • Shared time-steps
  • Constant time-steps

The constant time-steps option causes simulations to take a predictable length of time and can be useful for debugging purposes. However it can suffer from inaccuracy with close encounters and binaries.

The shared time-steps option is faster than constant, not as fast as individual but tends to be the most accurate.

The individual time-steps option is the most efficient overall for a given level of accuracy.


Block Time-Steps

Grav-Sim supports time-steps at discrete times. This helps to keep the performance high in conjunction with the batch-processing feature and is the default.

Furthermore, Grav-Sim supports time-steps on a logarithmic scale based on the sqare root of 2 (compared to ACS which only supports factors of 2). This allows the block time-steps to get closer to the target time-step and yields a slight gain in efficiency.


Transactional Time-Steps

Transactional time-steps ensure that the corrected position of one body is not used in the same calculation as the predicted position of another. This helps to reduce systematic errors.


Softening

Grav-Sim currently does not cater for collisions. In the event of a near miss (which can happen repeatedly with a close binary) the gravity calculation can generate errors if used in its raw Newtonian form. A way of avoiding this is to use a modified gravity calculation that avoids getting too close by systematically adding a small separation. This is known as "softening" and is available in Grav-Sim as an option.


Performance Profiler

For those experimenting with the source code and tweaking the various compile-time options, Grav-Sim is compatible with the Shiny Profiler.


Compilers

Grav-Sim tests have been performed with several compilers. On a Windows PC, Intel C++ produces the best results, several times quicker than either Microsoft Visual C++ or GNU gcc.