N-Body Simulation

This was written to demonstrate and test the compute toolchain/implementation I'm currently working on for my master's thesis (github.com/a2f.... With this it is possible to compile the same C++17 code to CUDA/PTX, OpenCL/SPIR/SPIR-V, Metal and Vulkan/SPIR-V, thus running on a multitude of GPUs and CPUs on different platforms. To achieve this, I'm using a modified clang/llvm/libc++ 4.0 toolchain and a layer of host and device side code that makes it possible to address everything the same way. This demo in particular shows the use of local/shared memory buffers, local memory barriers, OpenGL buffer sharing, loop unrolling and that high performance computing is indeed possible with this toolchain.
The N-body simulation is largely based on http.developer.... with some additional optimizations.
More information on N-body simulations: en.wikipedia.o...
Code for this demo: github.com/a2f...
Current performance stats (in benchmark mode):
* P6000: ~8400 gflops (--count 262144 --tile-size 512)
* GP100: ~7600 gflops (--count 262144 --tile-size 512)
* GTX 970: ~2770 gflops (--count 131072 --tile-size 256)
* GTX 780: ~2350 gflops (--count 131072 --tile-size 512)
* GTX 1050 Ti: ~1675 gflops (--count 262144 --tile-size 256)
* R9 285: ~850 gflops (--count 131072 --tile-size 64)
* GTX 750: ~840 gflops (--count 65536 --tile-size 256)
* GT 650M: ~375 gflops (--count 65536 --tile-size 512)
* HD 530: ~242 gflops (--count 65536 --tile-size 128)
* HD 4600: ~235 gflops (--count 65536 --tile-size 80)
* i7-6700: ~195 gflops (--count 32768 --tile-size 1024)
* HD 4000: ~165 gflops (--count 32768 --tile-size 128)
* iPhone A10: ~131 gflops (--count 32768 --tile-size 512)
* i7-5820K: ~105 gflops (--count 32768 --tile-size 8)
* i7-4770: ~80 gflops (--count 32768 --tile-size 8)
* i7-3615QM: ~38 gflops (--count 32768 --tile-size 8)
* i7-950: ~29 gflops (--count 32768 --tile-size 4)
* iPhone A8: ~28 gflops (--count 16384 --tile-size 512)
* iPad A7: ~20 gflops (--count 16384 --tile-size 512)
Stats from this video:
* N = 131072, damping = 0.9983, softening = 0.01
* since this is an O(n^2) algorithm, this results in 131072^2 = 17179869184 body/body interactions per iteration
* the initial body setup is a hollow sphere (or on-sphere), with body velocities set to the center
* with rendering and video capturing, performance is degraded a little and one iteration of this simulation took about 175ms (w/o rendering/capturing it would be ~155ms)
* with N = 65536 this runs in realtime on a GTX 780 (~38ms per iteration with rendering)
* the 1x runtime of this video is slightly above 1 hour, the video is shown in 16x speed-up, with camera rotations at 3x (to not cause that much confusion ;))

[@taiyc3]

this looks exactly like the cosmic web! amazing!!! xP

[@oystercatcher943]

Amazing stuff. I'm doing similar on a GPU helped by much fasters GPUs since 2015. I'm also planning to use a space partitioning optimisation but it runs fairly fast with 10-20K particles right now which seems amazing when its O(N^2). I found it was easy to get particles thrown off using forces ~1/(R^2) so I used something like 1/(R^2+0.001) and got less thrown off particles. Looking at your code, it looks like this is indeed similar to your softening factor but you use 1/(R+soft_factor)^2. Its good I wasn't totally hacking it when I did this. I guess the factor needed is proportional to the magnitudes of R

[@PinkeySuavo]

It looks like galaxies superclusters, wtf. Aren't these simulations giving us a look on how the universe was created?

[@sirrcharles1869]

They do

[@rajinfootonchuriquen]

Maybe when they make a theory of quantum gravity

[@Joao-uj9km]

Yes, that's literally what they're simulating :)

[@JacobNax]

This is a useless simulation. You can see an abstract pattern that matches the galaxy superclusters due to how particles attract eachother but it doesn't simulate actual gravity.

[@PinkeySuavo]

why doesnt it?@@JacobNax

[@resbizhou1488]

Amazing work! I‘ve been doing something similar since last year......

[@asdf-mu8zi]

It just shaped heatmap of universe.. amazing

[@Geomasterthesecond]

No idea what you're talking about that's not the heat map of the universe

[@radhakrishnamohanty3807]

Seems like a super cluster of galaxies ...

[@daerhiel]

It seems it doesn't include the particle collisions, is it?

[@MrRenanwill]

Why?

[@pixelprincess9]

Very cool! Question for the creator: are you taking Dark Matter and Dark Energy into account or are you just using Newtonian physics? Thanks!

[@a2flo]

Just plain old Newtonian with some softening/damping: developer.nvidia.com/gpugems/GPUGems3/gpugems3_ch31.html

[@brucesimonson4581]

What happens in this simulation as time goes to infinity?

[@RmX.]

Same what happens in space

[@brucesimonson4581]

Asking out of curiosity: does this excellent model and graphic simulation lead to a big crunch, big chill, or big rip, by including the Hubble constant, mass density, and dark energy pressure and its density as parameters? (see en.m.wikipedia.org/wiki/Big_Rip ) It would be interesting to model each of these scenarios, and watch their simulations in this software. Again, awesome work and presentation.

[@a2flo]

This is just plain old Newtonian gravity. Anything fancier than this would not nearly run as fast (or would require much more compute resources). So, in this case, everything would eventually just coalesce into a single point. Fancier simulations: www.illustris-project.org kzbin.info/www/bejne/iGjRh2mAerJ6d9E

[@kahlzun]

As it shows in the video, everything is collapsing into the central point

[@mixer0014]

@@a2flo Have you tried giving the particles some initial velocities? When angular momentum is introduced at the beginning it will be preserved and result in a spinning structure at the end. But It won’t work when there is friction.

[@양익서-g8j]

인간의 의식은 수많은 항성과 블랙홀의 중성미자 소립자 양자들의 끊임없는 움직임과 소멸로 생긴 부분도 있겠죠.

[@ph08nyx]

Похоже на планетарную туманность, но на сколько мы их можем наблюдать, они не схлопываются в одну точку, как в этой симуляции, а продолжают расширяться и рассеиваться.

[@Rayvenor]

Потому что это не симуляция галактики.

[@MsAlfred1996]

Can I please use some part of this as an intro a series of educational videos I'm working at now ? (I'm not even gonna be paid, it's not for profit)

[@a2flo]

Yes, it's licensed under CC BY.

[@MsAlfred1996]

@@a2flo Thank you

[@jareknowak8712]

Yep, thats how it all started. Been there, done that. I should still have some pictures on my old laptop.

[@Frommerman]

I thought this was a cool 2d sim. Then you started rotating it

[@playfra5004]

Cool video! Could you tell me the code and what program are you using to run it? Thank you.

[@hamsterdam1942]

Looking at the description before asking was never an option

[@blaze-pn6fk]

Great work 👏👏

[@tanishqajk6514]

Add soothing music! Lovely simulation How should I get started here?

[@a2flo]

kzbin.info/www/bejne/rJKUoJyln9N6qKM goes well with it ;)

[@kgtc]

Oh my looks like we need to get an FPGA for this! For now get an RX 480 4GB for the 5.5 TFlops for cheap.

[@orderofchaos8680]

Any pattern emerges from chaos?

[@DiamondSane]

yes. still it's a chaotic pattern

[@pixelapse9613]

@@DiamondSane or is it

[@dielaughing73]

Many, as you see

[@boRegah]

One would think 3 bodies are plenty

[@eeronat]

This is a good metaphor for immigration reform. (Too much coffee?)

[@MartinMizner]

He is literally simulating our universe

[@laurencevanhelsuwe3052]

Pretty. I wrote something similar (with about 1000x fewer objects) on my Amiga 1000 back in.. oh.. it must have been 1986 (in 68000 assembler.. had to be for speed - the result was a smooth animation).

[@a2flo]

The only way is up :) I'm already getting ~20x the performance on a 3090 vs the 780 I made this video on + run this with a million bodies at somewhat decent speed.

[@pablouuuu]

D:

[@MisterTrayser]

Thats the proof that we are in simulation If we already have such computing power, in 100 years we will be able to make universe with all physic forces

[@the18thdoctor3]

I don’t think you know what “proof” means

[@thealbinotadpole2878]

Thats called a "hunch", not a proof.

[@MisterTrayser]

@@thealbinotadpole2878 confirmation, ok. Don't hang on every word

[@thealbinotadpole2878]

@@MisterTrayser It still doesn't confirm anything. You could call it supporting evidence, but it cannot prove anything.

[@hangyeoljung4254]

Why did my professor give me this stuff to my software assignments...

[@wolfboyft]

How is the particles-"'colliding"'-and-flying-away-at-'insane-'speeds effect mitigated in this simulation? Lovely btw, absolutely magnificient, just the kind of thing I like to see.

[@bitw1se]

I would guess using the "velocity damping" and "softening" he's written about in his stats

[@orionsuniversepart2932]

Kinda looks like a simulation of the universe.

[@vidstige]

In other videos I've seen that he describes that he uses "dampening" (where a force opposite to the velocity and proportional to the velocity is applied) and "softening" (where the distance between particles are artificially increased, avoiding the harshest accelerations).

[@phivpap8632]

Did you find a concrete solution to this? I'm kinda facing that issue in my sim :(

[@phivpap8632]

@@vidstige Wouldn't "dampening" cause orbit decay and thus more collisions?

[@genkidama7385]

would be interesting to do the inverse, starting from known body positions, and calculating their evolution backwards in time.

[@PrzemysawUznanski]

just reverse the speed vectors...

[@puddle.studios]

@@PrzemysawUznanski i dont think that would work but you could just reverse the simulation

[@vke6077]

I think this is not possible. You can get to a certain position in many ways, no?

[@TransoceanicOutreach]

Approximations make it impossible for this particular sim.

[@bronson4574]

Not possible, too much chaos on the system

Cool compute video. Would you mind telling that how did you count flops in kernel code? For example, did you count rsqrt/fma as 1 flop? Did you count only compute time or did you include drawing time too? How many flops per particle-particle? I'm just trying to compare my RX550 with OpenCL nbody to this and to know if I'm calculating right.

[@a2flo]

github.com/a2flo/floor_examples/blob/master/nbody/src/nbody.cpp#L25 Since rsqrt is executed in hardware (on all h/w afaik) it's counted as a single flop, fma is counted as 2 flops, in total you get 19 flops per particle/particle interaction. Drawing time is excluded (in the table at least), because nothing is being drawn in benchmark mode. What is included in the time however is any kind of synchronization and global/local memory transfers (since we obviously need that to do anything). Note that AMD is doing particularly bad with nbody (you get about 25% the theoretical #flops that is possible on that hardware, at least on GCN 1.2, I haven't tested this with Polaris/Vega yet). On all other hardware you get about 50% the theoretical #flops (NVIDIA pre-Pascal, Intel GPUs, Apple/PowerVR since A9/A10), or 70% since Pascal.

Thank you. I think amd has put less sqrt or special function core density than nvidia and intel. I just tried a mad only kernel which is unrolled for pipelining could use 90 percent but when sqrt is included it drops badly as if there is only 1 sqrt unit per 32 arithmetic logic units

Also you can see same thing in userbenchmark site too. In pure shader performance(or mad mul add) rx550 is faster than gt1030 but in its nbody part its slower by a large margin. Certainly sqrt density of amd is much less than nvidia but has more cores to tolerate to some degree which is useful only when implementing own sqrt functions.

[@a2flo]

rsqrt throughtput on GCN is the same as on NVIDIA since Maxwell (1/4 "speed"). So that shouldn't be the issue (even if it was much slower, it still wouldn't be the significant part). As far as I can tell, the performance issues originate from less local memory bandwidth and synchronization costs (there are 2 local/full barriers for every 256 bodies, and N * 16 bytes local memory writes + reads per work-group).

I heard that nvidia kepler series did not have enough data bandwidth to feed all cores concurrently. Does this mean amd is even worse and optimized for mainly "register" usage, hence, for embarrasingly parallel algorithms that don't rely on sync performance?

[@JohnSmith-ps6on]

Great stuff.

[@makismakiavelis5718]

Wow. I was going to make a joke along these lines: _"Easy, I can do this with my outdated computer. I just need 25 years to render"_ I was surprised to see that they used a GTX 780 and my GPU is a GTX 780Ti... I wonder what CPU they used.

[@ctorange]

If I understand correctly, it ran solely on their GPU. I think one purpose of their compute toolchain is that it can run on a GPU or CPU independently. Presumably it takes advantage of GPU-specific features when it runs on a GPU.

[@makismakiavelis5718]

@@ctorange That's really interesting but you reminded my comment from 1 year ago and that made my sad. My 780Ti died and with the GPU prices going crazy the past few months I was forced to unearth my 10 year old Radeon HD6450...

[@nathanhelmburger]

This would be so cool to see in 3d in VR....

[@mrgoodpeople]

you need add a dark energy!

[@crowxe]

Damn.. i can watch the progress of these videos for hours

[@jonathanbaincosmologyvideo3868]

Very impressive. Notice how nothing like a solar system forms with just gravity alone. No natural ecliptic plane. I did a 9-body- simulation of the solar system with the emphasis on individual accuracy of each body, rather than the monstrous numbers of objects you got here. Link to follow.

[@jonathanbaincosmologyvideo3868]

kzbin.info/www/bejne/enSYm4RsbbqSr6s

[@singadorito7802]

So... This is what IC 1101 looks like...

[@gatoradeee]

trippin off acid

[@VinniusHKruger]

What kind of collision ? 100% elastic ?

[@VinniusHKruger]

Looks like crab supernova.

[@arithene]

So scary

[@ORGOrange]

2:09 uhhhh

[@maciejjedrzejczyk9028]

Bigbang simulation ;D

[@francomay3963]

i could see my house from there

[@EddieVBlueIsland]

Looks like the " game of life" in 3D and gravitational bias. Nice work.

[@Kergan63]

What are the initial conditions? I mean : why the bubble initially expands?

[@a2flo]

github.com/a2flo/floor_examples/blob/f71b0683708edb190f21de24ed573219361ba6ee/nbody/src/main.cpp#L492 :) Initial collapse is due to their initial velocity (though with a 0 velocity, this would still collapse, just more slowly). Expansion happens, because the velocities are very high and point in all directions once all/most bodies hit the center + velocities are larger than the mutual attraction, so this doesn't clump up initially.

[@MrRenanwill]

O feel like being god

[@tomjerry84]

Looks like how the universe works

[@DeMooniC]

except is not expanding and is way smaller but yeah

[@hamidaminirad]

No. It looks exactly the way the universe doesn't work. Nothing is rotating there and nothing is expanding there. But everything is collapsing again and again, in a straight line.

[@SimulatingPhysics]

These simulations are very cool. But they completely lack numerical precision. Energy doesn't conserve in this simulations, although it is a fundamental physical law. Dark matter effects aren't implemented, and they have a big impact on galaxies rotation.

[@tomjerry84]

Rafael Lol, of course I know it😉😉

[@GeneticResearch]

The simulation of the big bang, the following cosmic web and the big crunch at once.

[@Noor.1011]

بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيمِ قُلْ هُوَ اللَّهُ أَحَدٌ (1) اللَّهُ الصَّمَدُ (2) لَمْ يَلِدْ وَلَمْ يُولَدْ (3) وَلَمْ يَكُنْ لَهُ كُفُوًا أَحَدٌ (4)

[@mehmetalivat]

These verses are real and are the words of the creator who establishes the dynamics of the universe you live in. As for this simulation, it works within a limited computation, which is far from the truth for the actual galactic system. I understand your feelings, but this is not the place to share.

[@Noor.1011]

@@mehmetalivat My brother , I shared the the words because of a beautiful secret i am keeping for myself.

[@petterlarsson7257]

this is basically a big bounce scenario lol

[@student369]

Do you have any tutorial of GADGET-2 or GADGET-4 and AREPO?

[@Leo_1157]

How can i use this? Or where i have to use your Github codes?

[@nicolasribeiro7914]

Universe sandbox ³ looking great

[@kris_soju]

Me a bachelor degree getting this Assignments

[@AZ-be4hg]

Any formulas?

[@danielmichalski2436]

Oh no! The big crunch :D

[@javiermachin1]

This video deserves millions of views. Thanks for sharing.

[@busterdafydd3096]

I bet those doesn't deal with collisions

[@muuubiee]

I think you have to do a distance check, so it'd be easy to add colissions.

[@a2flo]

Nope, it doesn't. But star collisions are also very unlikely. I would assume the number of star deaths/births is much greater than the number of star collisions, and I'm not simulating that either.

[@TheMohan1986]

yeah wow, cos the universe is not sensitive to initial conditions, and is typically restricted... Great use of a solver software with clustering coefficients to describe how the universe truly began. You took no chances with that huh

[@toshibamaster2210]

somewhere you can find a portable version visual studio where it can be run quickly or even the image of the system disk so that it can be started immediately

[@Pauly421]

Omg thats so cool! How do I run this program? :)

[@CursedKyuubi]

Beautiful are art piece, with great computing tech/person behind it. Nice work

[@OriruBastard]

Oh shit, it's starting form a brain! Hurry, turn it off before it gains consciousness! =0