并行计算总和

Question

这是一个面试问题.

N个节点,每个节点由几个字段和方法组成.这些是:

// Every node has an ID. All of these IDs are sequential, and begin with 0.
//   i.e. all ids are uniquely in the range of 0 t N-1
int id;
int val; // Every node has a value
int max; // max = N. Every node knows how many nodes are in the system. 

void send(int idTo, int payload)
int recv(int idFrom) 

编写一段同时在每个节点上运行的代码,这样当它完成运行时,系统中的每个节点都知道系统中所有节点的值的总和.

Answer 1

您可以将值广播到每个节点,并从每个其他节点接收值.这样每个节点都会进行添加并知道结果.虽然,我认为这可能是非常低效的.

我更喜欢上一个回答中从前一个节点接收部分和的想法,添加自己的值并将新总和传递给下一个节点.然后你必须在另一个方向传输最终结果,这样每个节点都知道最后的答案.

但是如果你想利用所有节点可以同时运行的事实,你可以从两端开始第一次传播并在中间得到最终结果,并从那里进行第二次遍历也在两个方向上.这将为您节省一半的时间.更好的是,遵循相同的想法,您可以通过成对来生成总和,并将部分结果发送到第四个节点,然后发送到eigth,依此类推.这个策略只需要O(lg n)就可以到达中间位置.