How do I determine the most efficient algorithm for parallel addition? -

How do I determine the most efficient algorithm for parallel addition? -

after asking question mapreduce algorithm, has got me thinking how determine efficient way of arriving @ total sum of n values using parallel processing. problem can simplified follows:

suppose have n processors, each holding integer. want determine sum of integers possible.

now each processor 2,..,n pass integer processor 1. processor 1 adds each of numbers in turn produce result. means n - 1 passes of data, these can happen in parallel. followed n - 1 add-on operations, occurring in sequence.

alternatively, each odd numbered processor pass integer next numbered processor (let's assume n even, sake of argument). each numbered processor performs 1 add-on operation, in parallel, adding own number 1 it's been passed. end 1/2 n integers add together together. utilize previous method add together remaining values.

of course, there many other ways of doing this. how determine efficient? suspect depends on relative cost of add-on operation vs passing integer (in real life, think cpu vs network speed), , on size of n. after all, if n large, adding network hop in order halve n may worth it, if each add-on relatively cheap.

this more of comment answer, little box confining ...

define most efficient. concerned theoretical efficiency or speed in practice ?

i think you're asking right questions, , seem have realised if have 100,000 processors each 1 integer critical resource communications speed not computation speed. scheme devise sum n integers starting n processors bear in mind communications time dominated not bandwidth (time send 1 integer) latency (time send 0 size message). practical purposes expect issue kill fancy schemes dead.

and question: did integers originate ? if originated on 1 process(or) , distributed other n-1 you've wasted more time sending them out have taken 1st process(or) calculate sum. if integers originated as, perhaps, result of process running on each processor then, no matter (in)efficiency, you'll have kind of reduction anyway , pay communications cost.

in practice you're going boost in speed when calculating sum of n integers on p processors when n much larger p. figure out numbers on parallel computer there's no replacement experimentation.

algorithm parallel-processing