Re: Choose: O(n!) on single core vs O(n^2) on multi-core

I would suggest to group the elements, and lock the access to the net forces for a complete group while you're computing the interaction between all the elements of two groups.

For example if you have 1000 bodies, divide them in, say, 40 groups of 25 elements. An individual UOW should then handle all the interactions between two groups of elements. You only need to lock the access once for every group, so you'll be able to compute 25*25 interactions with two sync instruction.

You'll have memory contention at some point (some threads will have to wait for others to release access to a certain group), but my guess is that you should be able to use at least 80% of available CPU in an algorithm that will perform very much like n*(n-1)/2.

i'm sure i'm mis-understanding what you're describing.

Assume there are 9 bodies, put into 3 groups of 3
Group A: 123
Group B: 456
Group C: 789

i then define 6 units of work
UOW1: forces within A
UOW2: forces within B
UOW3: forces within C
UOW4: forces between A and B
UOW5: forces between A and C
UOW6: forces between B and C

And each group is completely locked while the UOW is running. This means that 4,5,6 cannot start until 1,2,3 are done; therefore the possible simultaneous executions are:
1,2,3: A,B,C
4: AB
5: AC
6: BC

So if i work it all out it's
UOW1,2,3:
/-- F12, F13, F23 --\
---+-- F45, F46, F56 --+--->
\-- F78, F79, F89 --/
UOW4:
------ F14,F15,F16,F24,F25,F26,F34,F35,F36 ----->

UOW5:
------ F17,F18,F19,F27,F28,F29,F37,F38,F39 ----->

UOW6:
------ F47,F48,F49,F57,F58,F59,F67,F68,F69 ------> Done

For a total of 36 calculations, but 6 happening in parallel, so effectivly it's 30 calculations; an 8% speed improvement.

i get the sense that if there are more groups, then there's more opportunity for parallelization; and that 9 groups really isn't really a great example case. But do i have your idea right?

.

Relevant Pages

  • Re: Do you understand Special Relativity?
    ... | "Experiments show that instantaneous interactions among bodies do not ... Thus a physics based on the assumption of ... | instantaneous propagation of interactions will not be correct. ... this experiment as to whether or not the train is in motion. ...
    (sci.physics.relativity)
  • Re: Do you understand Special Relativity?
    ... | "Experiments show that instantaneous interactions among bodies do not ... Thus a physics based on the assumption of ... | instantaneous propagation of interactions will not be correct. ...
    (sci.physics.relativity)
  • Re: with a view to what causes this motion to have the nature it does
    ... motion to have the nature it does, i.e., with a view to the ... interactions between bodies. ... Dynamics is a study that concludes that bodies do not move with a ...
    (alt.usage.english)
  • Re: [OT] Hints for an algorithm - avoiding O(n^2)
    ... The obvious way is to compute the force interactions ... > results will not be similar in time (I'm planning to manage about ... You are going to make a simulation, ... to do the calculations between objects much less frequently, ...
    (comp.lang.ada)
  • Re: Modern-Human-Neandertal Genetic Admixture
    ... > [more snip] ... The question of the Neanders being a separate species is probably impossible ... dates and locations of these potential interactions. ... > The whole framework of their calculations (whatever parameters and methods ...
    (sci.anthropology.paleo)