1

（问题是尴尬的并行）

考虑一个包含 12 个单元的数组：

|__|__|__|__|__|__|__|__|__|__|__|__|

和四 (4) 个 CPU。

天真地，我会运行 4 个并行作业并为每个 CPU 提供 3 个单元。

|__|__|__|__|__|__|__|__|__|__|__|__|
=========|========|========|========|
   1 CPU    2 CPU    3 CPU    4 CPU

但是，似乎每个单元格都有不同的评估时间，有些单元格的评估速度非常快，有些则不然。

因此，我认为与其浪费“松弛的 CPU”，不如将每个单元及时馈送到每个 CPU 并继续，直到整个工作完成。

即：

一开始：

|____|____|____|____|____|____|____|____|____|____|____|____|
 1cpu 2cpu 3cpu 4cpu

如果，2cpu 在单元格“2”完成了他的工作，它可以跳转到第一个空单元格“5”并继续工作：

|____|done|____|____|____|____|____|____|____|____|____|____|
 1cpu      3cpu 4cpu 2cpu
       |-------------->

如果 1cpu 完成，它可以占用第六个单元：

|done|done|____|____|____|____|____|____|____|____|____|____|
           3cpu 4cpu 2cpu 1cpu 
  |------------------------>

依此类推，直到完成整个数组。

问题：

我不知道哪个单元是“快的”，哪个单元是“慢的”，所以我不能根据负载分配 cpu（更多的 cpu 慢，少的快）。如何使用 MPI 实现这种动态评估算法？

谢谢！！！！！

更新

我使用了一种非常简单的方法，如何使用 IO-MPI 将整个作业分成块：

给定：array[NNN] 和nprocs - 可用工作单元的数量：

for (int i=0;i<NNN/nprocs;++i)
{
  do_what_I_need(start+i);
}
MPI_File_write(...);

其中“开始”对应于特定的等级编号。简而言之，我根据可用 CPU 的数量将整个 NNN 数组划分为固定大小的块，每个 CPU 执行其块，将结果写入（公共）输出并放松。

是否有可能以这样的方式更改代码（不完全重写主/从范式），使得每个 CPU 将只获得一次迭代（而不是 NNN/nprocs）并且在它完成其工作并写入之后它对文件的一部分，将继续下一个单元格而不是放松。

谢谢！

4

3 回答 3

3

有一种众所周知的并行编程模式，有很多名称，其中一些是：任务包、主/工人、任务场、工作池等。其想法是有一个主进程，它将单元分配到其他进程（工人）。每个worker运行一个无限循环，在这个循环中它等待来自master的消息，计算一些东西然后返回结果。通过让主设备发送带有特殊标签的消息来终止循环。MPI_ANY_TAG工作人员可以使用通配符标签值来接收具有不同标签的消息。

大师比较复杂。它还运行一个循环，但直到所有单元格都已处理完毕。最初它向每个工作人员发送一个单元格，然后开始一个循环。在此循环中，它使用通配符源值从任何工作人员接收消息，MPI_ANY_SOURCE如果有更多单元格要处理，则将其中一个发送给已返回结果的同一工作人员。否则，它会发送一条带有标签的消息，该标签设置为终止值。

互联网上有很多很多现成的这种模型的实现，甚至还有一些在 Stack Overflow 上（例如这个）。请注意，此方案需要一个额外的 MPI 过程，而该过程通常做的工作很少。如果这是不可接受的，可以在单独的线程中运行工作循环。

于 2013-06-12T17:06:12.090 回答
1

要回答您更新的问题：

在主/从（或工作池，如果您喜欢这样标记）模型下，您基本上需要一个任务调度程序。主人应该知道哪些工作已经完成，哪些还需要做。master 会给每个进程一些工作要做，然后坐下来等待进程完成（使用非阻塞接收和 wait_all）。一旦一个进程完成，让它将数据发送给主节点，然后等待主节点响应更多的工作。继续这个直到工作完成。

于 2013-06-14T18:30:34.460 回答
1

你想实现一种客户端-服务器架构，让员工在下班时向服务器请求工作。

根据块的大小以及工作人员和服务器之间的通信速度，您可能需要调整发送给工作人员的块的大小。

于 2013-06-12T17:08:16.653 回答