尽管array_size不能被进程数完全整除,但如何在MPI中的进程之间大致均匀地共享工作？

Question

大家好,我有一个长度为N的数组,我想在'size'处理器之间尽可能地划分它.N/size具有余数,例如1000个数组元素除以7个过程,或14个过程3个过程.

我知道MPI中至少有几种工作方式共享,例如:

for (i=rank; i<N;i+=size){ a[i] = DO_SOME_WORK } 

但是,这并没有将阵列划分为连续的块,我想这样做,因为我认为IO更快.

另一个我知道的是:

int count = N / size;
int start = rank * count;
int stop = start + count;

// now perform the loop
int nloops = 0;

for (int i=start; i<stop; ++i)
{
    a[i] = DO_SOME_WORK;
} 

但是,使用这种方法,对于我的第一个例子,我们得到1000/7 = 142 = count.所以最后一个等级从852开始到994结束.最后6行被忽略.

将这样的东西附加到上一个代码是最好的解决方案吗？

int remainder = N%size;
int start = N-remainder; 
if (rank == 0){
     for (i=start;i<N;i++){
         a[i] = DO_SOME_WORK;
     }

这看起来很混乱,如果它是最好的解决方案我很惊讶我没有在其他地方见过它.

谢谢你的帮助!

Answer 1

如果我有N任务（例如数组元素）和size工作人员（例如MPI等级），我将按照以下步骤进行：

int count = N / size;
int remainder = N % size;
int start, stop;

if (rank < remainder) {
    // The first 'remainder' ranks get 'count + 1' tasks each
    start = rank * (count + 1);
    stop = start + count;
} else {
    // The remaining 'size - remainder' ranks get 'count' task each
    start = rank * count + remainder;
    stop = start + (count - 1);
}

for (int i = start; i <= stop; ++i) { a[i] = DO_SOME_WORK(); }

它是这样工作的：

/*
  # ranks:                    remainder                     size - remainder
            /------------------------------------\ /-----------------------------\
     rank:      0         1             remainder-1                         size-1
           +---------+---------+-......-+---------+-------+-------+-.....-+-------+
    tasks: | count+1 | count+1 | ...... | count+1 | count | count | ..... | count |
           +---------+---------+-......-+---------+-------+-------+-.....-+-------+
                      ^       ^                            ^     ^
                      |       |                            |     |
   task #:  rank * (count+1)  |        rank * count + remainder  |
                              |                                  |
   task #:  rank * (count+1) + count   rank * count + remainder + count - 1

            \------------------------------------/ 
  # tasks:       remainder * count + remainder
*/

Answer 2

这是一个封闭式的解决方案。

\n\n

令 N = 数组长度，P = 处理器数量。

\n\n

从j = 0 到P -1，

\n\n

处理器上数组的起始点j = Floor( N * j / P )

\n\n

处理器上数组的长度j = Floor( N * ( j \xc2\xa0+\xc2\xa01)\xc2\xa0/\xc2\xa0 P ) \xe2\x80\x93 Floor( N * j \xc2\xa0/\ xc2\xa0 P )

\n

Answer 3

我认为最好的解决方案是自己编写一个小函数，以便在进程之间均匀地分配工作。这是一些伪代码，我相信你可以比我更好地编写 C （是你问题中的 C 吗？）。

function split_evenly_enough(num_steps, num_processes)
    return = repmat(0, num_processes)  ! pseudo-Matlab for an array of num_processes 0s
    steps_per_process = ceiling(num_steps/num_processes)
    return = steps_per_process - 1 ! set all elements of the return vector to this number
    return(1:mod(num_steps, num_processes)) = steps_per_process  ! some processes have 1 more step
end