A very common problem on a N-body problem is the use of a double cycle to calculate the interactions between the particles. Considering a N body problem with n particles, the cycle can be written has
for (i = 0, i < n; i++)
for (j = i+1, j < n; j++)
// calculate interaction
My question is about how can this cycle be parallelized using different threads. The objective is that each thread would "ideally" have to calculate the same number of interactions.
My idea was to separate the outer cycle, the i-cycle, on different intervals, say a_k=a(k), where k = 1,2,...,p where p is the number of threads we want to divide the problem into.
So, the cycle could be written as
for (k = 1, k < p; k++)
for (i = a(k), i < a(k+1); i++)
for (j = i+1, j < n; j++)
// calculate interaction
Where the most outer cycle, the k-cycle, is the one to be parallelized.
Because the number of interactions of the most inner cycle, the j-cycle, is n-(i+1), the number of interactions calculated by each thread is
\sum_{i=a(k)}^{a(k+1)} n - (i+1)
This means that one would like find the discrete function a_k such that the functional
f[a_k] = \sum_{i=a(k)}^{a(k+1)} n - (i+1)
with the boundary conditions a(1)=0 and a(p)=n is a constant functional, thus forcing the number of interactions on each thread to be the same.
I've tried using different "heuristics"(e.g. a_k polynomial, exponential, log), and so far none have gave me a satisfactory answer. A direct solution of this problem is not evident to me.
For small p, this problem can be put on the "minimization sack problems" where basically each a_k is a variable to minimize the function
f(a_1,a_2,a_3,...) = sum(|f[a_k] - n/p|^2)
But has you might guess, this is not efficient (or even converge) for higher values of p.
Does anyone have any ide