Parallelism in O(N2) N Body Approach I
O(N2) Algorithms are extremely efficient on parallel machines as
- Load balancing guaranteed with equal numbers of particles in each node
- Communication overhead goes like 1/(grain size n = number of particles in node) . Typical time to communicate word/ typical time to do floating computation) ~ 0.25(from algorithm details) . 10( = tcomm/tfloat)/n
- So very efficient along as around 50 particles or more per processor