并行化:通信模型的选择

Question

免责声明:如果您不喜欢并行化(集群)，那么这个问题可能对您不感兴趣，可能也不值得一读。

TL;DR:我搜索一个通信模型(最好与MPI兼容)，它能有效地确保每条数据线被处理一次。阅读下一段，了解我所说的数据行是什么意思。

考虑以下问题:算法接受数据线(在我的例子中，是一个大小固定的整数数组)并生成各种数据线，然后需要由相同的算法处理。每个唯一的数据线只需要处理一次，因为结果纯粹是确定性的。唯一的数据线集是有限的，因此经过有限次递归调用后，该算法生成整个集合。我们的目标是找到这套。

我已经实现了算法，也实现了并行化。显然，由于我们需要处理每个唯一的数据线，所以在每一时间，所有当前未处理的数据线都可能由不同的处理器并行处理。

另一方面，并行化引入了防止不同处理器进行冗余工作的问题。

一个简单的实现会将数据线发送到处理器，收集所有结果并再次分发。这可能是低效的，因为在完成任何进一步的工作之前，必须合并(可能是大的)结果列表。如果所有列表都在同一时间返回，那么主服务器将被大量的数据淹没，而所有从站都处于空闲状态，直到所有合并完成为止。

我(据我看来，改进的)交流模式基本上仍然是主从模式：

师父就是这样做的：

Distribute initial chunk of data lines to slaves
While there is at least one active slave
  for each active slave
    Request data line
    if slave doesn't have a data line
      set slave inactive, break
    else
      if the data line was previously processed
        break
      endif
      if there is an inactive slave
        send the data line to inactive slave and mark that slave as active
        send the sending slave a notification to not process the data line
      else
        notify the slave to process the data line it just sent
      endif
    endif
  endfor
endwhile

每个奴隶都这样做：

while true
 wait for request
 if data line available
   send it
   wait for master to say if the line should be processed here
   process if necessary
   go back to beginning
 else
   notify master
   wait for master to send a data line
   process the received line
   go back to beginning
 endif

从服务器管理自己的已处理和未处理数据线的本地列表。对于每个请求，一个未处理的元素被移动到处理的请求中。这两个列表中只有唯一的条目被存储。

总结:只有主人才知道完整的处理线集。如果并且只有当主程序说它以前没有被处理时，从属程序才会处理数据行。主服务器不知道每个数据行的结果，直到它向每个从服务器请求了所有可用的行。

据我所知，这种传递处理过的数据线列表的模型非常有效，但我对并行化的世界并不熟悉，特别是在集群上的并行化世界中。

在多个处理器之间有效地通信数据线的其他方法是什么，以确保每条数据线被精确地处理一次？

这个问题基本上不受C++和MPI组合的约束，尽管任何反映消息传递接口工作方式的答案都会受到极大的赞赏。

Answer 1

免责声明:我没有任何真正的MPI /集群经验。

也要注意我可能不正确地使用术语。

我的基本思想是将哈希函数应用于输入和输出数据线。从散列中计算一个整数K(介于1和NumSlaves之间)，以决定从(NumSlaves)的哪个(K)应该处理这条数据线。

每个奴隶都有一个哈希范围。如果数据线的哈希落入该从属程序的哈希范围内，则数据行将由该从属程序处理。

这一基本方案要求奴隶之间直接通信。主程序将充当日志管理员，它接收来自每个节点的计算输出的副本，但不参与任务分配。

当从一个输入数据线导出一个或多个输出数据线时，它将在每个输出数据线上计算这个散列函数，并为每个输出数据线确定一个处理它的从数据线。

此基本方案在运行时不提供容错或更改从站数；除非使用了其他一些分布式处理技术(例如一致散列等)。

每个从站必须缓存属于其散列范围的所有数据线，以避免重新计算。

此方案可能需要比当前计划更多的沟通，但可能更好地防止重复工作。