并行计算总和

问题描述 投票:1回答:2

这是一个面试问题。

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) 

编写可同时在每个节点上运行的单个代码,这样,当完成运行时,系统中的每个节点都将知道系统中所有节点的值之和。

algorithm parallel-processing
2个回答
5
投票

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

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

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


0
投票

一种解决方案:

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

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

热门问题
推荐问题
最新问题