|
This type of performance should be compared with classic grid problems in d dimensions where overhead proportional to edge over area and goes like 1/n1/d
|
|
So that grain size in 3D local problems is "cube" of that needed in O(N2) problem
|
Of course reason that communication overhead is so small is that computation is exceptionally large!
-
Every silver lining has a cloud
|
|
Note can "understand" 1/n dependence as write formula as Sj Si Force on i = function(i and j) --
|
|
important that outer sum is j not i!
|
|
Each j is communicated to each node and is then used to increment force on n/2 (divided by two due to Newton's law of action and reaction) particles in given node
|
