Previous Algorithm is not as good as it looks for it has an efficiency of 50% reduced by terms of order 1/n
-
For some cases, efficiency is 100% if only want "potential" and not forces -- this is case of correlation histogram example given earlier
|
|
Degradation is because of Newton's law of action and reaction which says that
|
|
Fi,j = -Fj,i
|
|
which reduces sequential computation load by a factor of 2
|
This is not trivial to exploit in parallel algorithm as Fi,j and Fj,i are needed in different processors and so one MUST violate owner's compute rule to exploit
-
Thus very hard for a compiler to find the best algorithm although as in other set of data parallel foils, one can express in HPF with some difficulty
-
Most natural to express in message parallel syntax
|
