并行计算总和

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

您可以将值广播到每个节点，并从其他每个节点接收值。 这样，每个节点都将进行加法运算并知道结果。 不过，我认为这可能效率很低。

我更喜欢前面的答案中的想法，即从上一个节点接收部分总和，添加您自己的值，然后将新的总和传递给下一个节点。 然后，您必须在另一个方向上传输最终结果，以便每个节点最后都知道答案。

但是，如果您想利用所有节点可以同时运行的事实，则可以从两端开始进行第一次传播，并在中间得到最终结果，然后再从两个方向进行遍历。 这样可以节省您一半的时间。 更好的是，按照相同的思想，您可以成对计算总和，并将部分结果发送到第四个节点，然后发送到第8个节点，依此类推。 该策略仅需O（lg n）即可到达中间位置。

Answer 2

一种解决方案：

每个节点将其收到的总和发送到系统中的下一个节点。 每个节点第一次收到上一个节点的号码时，都会记下来。 下次收到数字时->从前一个数字中减去该数字即为总和。

receive将收到系统中前一个节点的号码，并添加自己的号码，send将其发送到系统中的下一个节点，然后receive将等待前一个节点的另一个输入