The O(N2) long range force algorithm has largest communication load but the smallest known form of overhead (except pleasingly parallel problems) which is proportional to 1/n where n grain size
-
Computation is even larger than communication!
|
|
Compare Laplace (general PDE) in two dimensions which has overhead proportional to 1/n1/2 in two dimensions and 1/n1/3 in 3 dimensions
|
|
Such PDE's have small (edge) communication but an algorithm with computation proportional to N not N2 each iteration
|
N-body problem has computation proportional to N2 and general rule is that as algorithms get either more complex or more compute intense, the relative amount of communication decreases and does NOT increase
-
complexity increases computation more than communication
|
