13

こんにちは、私は長さ N の配列を持っています。これを「サイズ」のプロセッサ間でできる限り分割したいと考えています。N/サイズには余りがあります。たとえば、1000 個の配列要素を 7 プロセスで割ったもの、または 14 プロセスを 3 プロセスで割ったものです。

私は、MPI で作業を共有する方法が少なくともいくつかあることを認識しています。

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

ただし、これは配列を連続したチャンクに分割しません。これは、IO の理由でより高速であると信じているため、実行したいと考えています。

私が知っているもう1つは次のとおりです。

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 = カウントが得られます。したがって、最後のランクは 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;
     }

これは面倒に思えますが、それが最善の解決策である場合、他の場所で見たことがないことに驚いています。

助けてくれてありがとう！

4

8 に答える 8

11

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
*/
于 2014-10-24T19:10:45.290 に答える
3

「1000 のステップと 7 つのプロセス」の例を考えてみましょう。

  • 単純な除算は機能しません。これは、(C での) 整数除算で床が得られ、残りがいくらか残るためです。つまり、1000 / 7 は 142 であり、6 つの doodads がぶら下がっています。

  • 天井分割には逆の問題があります。ceil(1000/7) は 143 ですが、最後のプロセッサが配列をオーバーランするか、他のプロセッサよりも実行することが少なくなります。

プロセッサ間で残りを均等に分配するスキームを求めています。一部のプロセスには 142 が必要で、他のプロセスには 143 が必要です。より正式なアプローチが必要ですが、この質問が過去 6 か月間に得られた注目を考慮すると、そうではない可能性があります。

これが私のアプローチです。すべてのプロセスはこのアルゴリズムを実行する必要があり、必要な答えを選択するだけです。 

#include <mpi.h>
#include <stdio.h>
#include <stdlib.h>

int main (int argc, char ** argv)
{
#define NR_ITEMS 1000
    int i, rank, nprocs;;
    int *bins;

    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &nprocs);
    bins = calloc(nprocs, sizeof(int));

    int nr_alloced = 0;
    for (i=0; i<nprocs; i++) {
        remainder = NR_ITEMS - nr_alloced;
        buckets = (nprocs - i);
        /* if you want the "big" buckets up front, do ceiling division */
        bins[i] = remainder / buckets;
        nr_alloced += bins[i];
    }

    if (rank == 0)
        for (i=0; i<nprocs; i++) printf("%d ", bins[i]);

    MPI_Finalize();
    return 0;
}
于 2013-10-11T16:23:54.737 に答える
0

これはどう？

int* distribute(int total, int processes) {
    int* distribution = new int[processes];
    int last = processes - 1;        

    int remaining = total;
    int process = 0;

    while (remaining != 0) {
        ++distribution[process];
        --remaining;

        if (process != last) {
            ++process;
        }
        else {
            process = 0;
        }
    }

    return distribution;
}

最初のプロセスに要素を割り当て、次に 2 番目のプロセスに要素を割り当て、次に 3 番目のプロセスに要素を割り当て、というように、最後のプロセスに到達するたびに最初のプロセスに戻るという考え方です。

この方法は、プロセス数が要素数よりも多い場合でも機能します。非常に単純な操作のみを使用するため、非常に高速です。

于 2015-09-12T20:19:41.423 に答える
0

最善の解決策は、作業をプロセス間で十分に均等に分割するための小さな関数を自分で作成することだと思います。ここにいくつかの疑似コードがあります。あなたは私よりも 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
于 2013-03-27T17:03:54.340 に答える
0

同様の問題がありましたが、Python と mpi4py API を使用した最適でないソリューションを次に示します。最適なソリューションでは、プロセッサのレイアウト方法を考慮に入れる必要があります。ここでは、余分な作業が下位ランクに分散されます。不均一な作業負荷は 1 つのタスクだけが異なるため、一般的には大した問題にはなりません。

from mpi4py import MPI
import sys
def get_start_end(comm,N):
    """
    Distribute N consecutive things (rows of a matrix , blocks of a 1D array)
    as evenly as possible over a given communicator.
    Uneven workload (differs by 1 at most) is on the initial ranks.

    Parameters
    ----------
    comm: MPI communicator
    N:  int
    Total number of things to be distributed.

    Returns
    ----------
    rstart: index of first local row
    rend: 1 + index of last row

    Notes
    ----------
    Index is zero based.
    """

    P      = comm.size
    rank   = comm.rank
    rstart = 0
    rend   = N
    if P >= N:
        if rank < N:
            rstart = rank
            rend   = rank + 1
        else:
            rstart = 0
            rend   = 0
    else:
        n = N//P # Integer division PEP-238
        remainder = N%P
        rstart    = n * rank
        rend      = n * (rank+1)
        if remainder:
            if rank >= remainder:
                rstart += remainder
                rend   += remainder
            else:
                rstart += rank
                rend   += rank + 1
    return rstart, rend

if __name__ == '__main__':
    comm = MPI.COMM_WORLD
    n = int(sys.argv[1])
    print(comm.rank,get_start_end(comm,n))
于 2015-12-23T21:31:36.123 に答える