Exploring CUDA through computing Coulomb's Law

This is more like a physics post than anything else. I loved physics when i was doing my secondary school (that's high school in some countries) til pre-university days and at one point in time - i decided i was going to be a physicist! but i chose Computer Science. Well, that's a tad short bit of history for you anyway.

So, this post isn't how i DIDN'T make it to be a physicist but rather an interesting application (admittedly, contrived) of CUDA into physics, namely the computation of force vectors between sets of charged particles.

Some basics in Physics is in order ...

Coulomb's Law
Atoms and molecules have the same number of protons as electrons and are neutral (without overall charge).  Electrons can be transferred from one object to another.  When this happens, there is an excess of electrons in one place and a deficiency of electrons in another. Charge is the result of an excess or deficiency of electrons.  Where an object has excess electrons, the object is negatively charged. Where there is a deficiency of electrons, the object is positively charged. Electric charge is usually represented in equations by the letter q or Q.

So, the next question is to ask whether 2 charged particles next to one another would "feel" a force of attraction or repulsion? (FYI: 2 charged particles would attract one another if they had opposite charges and repel one another if they had same charge.)

In fact, they do and this felt force is computed via Coulomb's Law. Two charges, Q and q, separated by a distance, r, each experience a force of magnitude

F = k|Qq|/r² where k = 9 x 10⁹ and |Qq| is the positive value of the product of Q and q

The above formulation is what is called the scalar form. The k is known as the Coulomb Constant. Here's an image i dragged off Wikipedia to illustrate how charged particles can be thought of in their scalar & vector forms:

Force Vectors

 The takeaway from this picture is that (1) like charges repel (top row) (2) opposite charges attract (bottom row) and (3) each repulsion/attraction can be expressed as a vector in 2D (You can extend this to 3D if you like). This is something i can imagine quite well but when i attempt to extrapolate it to say 6 x 10 pow 23 or some other big number; then it becomes a bit mind boggling. Question that i have is whether i can find some way to compute the electrostatic force from this imaginary large number of charged particles?

Turns out you can by applying the Law of Superposition to Coulomb's Law over large numbers of such particles and the net effect is saying that the net force on any particle, p ,  is the vector sum of the other charged particles acting on this particle, p.

Modelling the problem

To model it, i need to create 2 or more sets of charged particles and have CUDA compute their net force by applying both laws. Each particle can be represented by a float4 type (basically, a element that has 4 ordinates x,y,z,w) ; each particle would be given a set of coordinates in 3D populated into their respective x, y, z and w will become the charge.

The parallel portion is shown below and in case you are wondering about force_calc; don't worry about it because its just the computation of Coulomb's Law which you can find samples of anywhere.

Side Note:

Another important thing you should remember (or probably know) is that we should always create the exact algorithm that'll run on a CPU (single core preferably). This serves the purpose of creating a reference implementation which you can debug your parallel stuff against and also to determine what kind of optimizations you need when you compare their run times.

done with host force eval kernel
host force eval took 157.8 ms
done with gpu force eval kernel
gpu force eval took 33.3 ms

Summary:

Think you get the idea now :) also from the output, you can see that the run times is a 4.7 fold drop :) and that's w/o any kind of optimization (you can tell right?) and a couple of optimizations you can apply and that's one simple application of CUDA to high performance computing.