7

配列[x1、x2、x3、...、xk]が与えられた場合、xiはボックスi内のアイテムの数ですが、ボックスにN個を超えるアイテムが含まれないようにアイテムを再配布するにはどうすればよいですか。Nはsum（xi）/ kに近い-つまり、Nは同じ数のアイテムを持つすべてのボックスに近い。中間ボックスを使用してアイテムを運ぶことはできません。x1に余剰があり、x2とx3に不足がある場合、x1は一部のアイテムをx2とx3に送信する必要がありますが、すべてのアイテムをx2に送信してから、x2に余剰を解決させる必要はありません。 。

実際の問題は、各コンピューティングノードにサンプルのセットがあり、リサンプリングステップの後、一部のコンピューターノードには余剰があり、他のコンピューターノードには不足がある可能性があるため、通信を最小限に抑えながらサンプルを再配布したいと思います。

この種の問題には名前があると思います。

4

7 に答える 7

3

この問題は、最小コストフローのインスタンスとしてモデル化できます。

Gを頂点s、t、a 1、…、a k、b 1、…、b k 、容量xiのアークs→ ai、コスト0、無限容量のアークai →bjを持つ有向グラフとします。 i = jの場合はコスト0、i≠jの場合はコスト1、容量Nとコスト0のアークb j →t。∑ <sub>ixiユニットをsからtに移動する最小コストフローが必要です。yユニットがai →bjを流れる場合、yアイテムはボックスiからボックスjに移動されます（i≠jの場合、i = jの場合、移動は発生しません）。

この単純な問題を解決するために最小コストフローを使用することは、もちろんスレッジハンマーを使用してナットを割ることですが、いくつかの変形はネットワークフロー問題としてモデル化できます。

  • ノードi、jのペアが直接接続されていない場合は、 ai → bjアークを削除します。

  • ノードに「a」側または「b」側のみの頂点を与えることで、ノードを起動およびシャットダウンできます。

  • 均一からコストを調整することで、通信速度の違いをモデル化できます。

  • アークの容量を制限することで、2つのノードが交換するアイテムの数を制限できます。

  • より多くの内部頂点を導入し、接続の完全2部トポロジを変更して、ネットワーク競合の影響をモデル化できます。

于 2011-12-10T22:40:36.030 に答える
3

私はあなたの問題が（述べられているように）独立した研究を引き付けるほど複雑であるとは思わない。マシン数（これを数千と呼びますC）が数千であり、サンプル数が数兆にもなる場合は、サンプル数を調整マスターノードに送信するのは簡単です。

次に、マスターは自明に（O(C)）計算Nし、この境界に違反しているノードを識別し、その量を特定できます。境界を超える超過の合計は、必要な通信の最小量であることに注意してください。計算時にスラックパラメータを挿入することによりN（つまり、不均衡を受け入れることにより）、この量を制御できます。

ソートを使用すると、サンプル数によるノードの順序付けをで行うことができますO(C log C)。2つのカーソルを、一方の端から中央に向かって歩きます。各ステップで、ラージノードからスモールノードへの転送をスケジュールします。サイズは、ラージの残りの超過分、またはスモールの残りのスラックの最小値になります。最後の文でアクティブな制約があったノードのポインターを進め、新しいラージが超過しなくなるまで繰り返します。（これは@Noxvilleが得ていた欲張りアルゴリズムだと思います。）

ノードあたりのサンプルの平均数よりも多いと仮定するとN、これが最小限の通信で理想的であることがわかります。

マシンのネットワークに、リンクがない、最大フロー、またはエッジ全体の変動費などの制約がある場合は、グラフフローを分割する必要があります。ただし、このようなことについては何も言及していません。同じデータセンター内のコンピュータークラスターには通常、何もありません。

于 2011-12-11T02:35:32.560 に答える
1

コンシステントハッシュ法を使用したいようです

http://en.wikipedia.org/wiki/Consistent_hashing

基本的に、優れたランダムハッシュ関数を使用すると、サンプルの一意のIDを取得して、均等に分散させることができます。そうすれば、サンプルをノードのセット全体に一貫して分散させるのは簡単です。

見る

http://www.lexemetech.com/2007/11/consistent-hashing.html http://www.tomkleinpeter.com/2008/03/17/programmers-toolbox-part-3-consistent-hashing/

詳細については。

于 2011-12-07T08:12:21.403 に答える
1

質問は次のように明確にする必要があると思います。

M余剰ノードと不足ノードがある場合は、ノード間でサンプルを再配分して、K余剰ノードが0で、（場合によっては）いくつかの不足ノードがある状態にする必要があります。サンプルはパックで交換する必要があり、これらのパックの数を最小限に抑える必要があります。

または、数学的には、行列があり、その各セルは、ノードからノードM*Kに渡されるサンプルの数を表し、各行に要素の合計が与えられ、各列に要素の合計の最大値が与えられます。目標は、ゼロ以外のセルの数を最小限に抑えることです。MK

これは一種の「制約充足問題」です。NP完全です。この質問に似た2つの古典的な問題を見つけました。「セットパッキング」と「一般化された正確なカバー」です。

問題を「パッキングの設定」に減らすには、（一時的に）いくつかの余剰ノードをN+1それぞれサンプルとともに追加して、再配布後に不足ノードが残らないようにする必要があります。次に、ノードごとに、余剰要素と「不足」要素のすべての可能なパーティションを生成する必要があります。次に、余剰と不足のパーティションのデカルト積に、サブセットの最小数を見つける「最適化」バージョンの「セットパッキング」を適用します。

問題を「一般化された正確なカバー」に減らすには、ノードごとに、余剰要素と「不足」要素に対して可能なすべてのパーティションを生成する必要があります。次に、カバー内のサブセットの数を最小限に抑えるために、、、...最適化ノードをM追加する必要があります。M+1次に、余剰と不足のパーティションと最適化ノードのデカルト積に、「一般化された正確なカバー」を適用します。最適化ノードの数が少ない場合、このアルゴリズムは失敗します。数が多い場合は、サブセットの最小数が検出されます。

「一般化された正確なカバー」は、「クヌースのアルゴリズムX」によって解決される可能性があります。「セットパッキング」のアルゴリズムがわかりません。

これらのソリューションはすべて正確な答えを提供しますが、計算が非常に複雑であるため、実際のスケジューラーで誰かがそれらを使用する可能性はほとんどありません。実用的なアプローチは、いくつかのヒューリスティックと欲張りアルゴリズムを使用することです。余剰ノードと不足ノードの両方を並べ替えて、「最適な」戦略を適用するだけです。

于 2011-12-11T10:32:57.207 に答える
1

私は通常、これをデータ再配布と呼びます。再配布する場合は、タスク間の均一性など、あるメトリックの下で分散を最適化する必要があることを理解しています。

これは、計算負荷分散を行おうとしているときに、科学/技術コンピューティングで発生します。複数の次元で計算を行っている場合でも、空間充填曲線によってプロセッサに割り当てた空間データを再配布する場合、この正確な問題が発生し、データを均等に分割したいことがよくあります。

手順は非常に簡単です。まず、x iの排他的なプレフィックスの合計を取得して、「左側」にあるアイテムの数を把握します。たとえば、上記のNoxvilleの例では、データがある場合

[9, 6,  1,  6,  2]

プレフィックスの合計は次のようになります

[0, 9, 15, 16, 22]

そして、（最後のプロセッサの合計とそのプロセッサの数から）合計で24個のアイテムがあることがわかります。

次に、理想的なパーティションの大きさを計算します。たとえば、ceil（totitems / nprocs）です。すべてのプロセッサがすべてのパーティションサイズに同意する限り、これは好きなように行うことができます。

これで、続行する方法がいくつかあります。データ項目がある意味で大きく、それらの2つのコピーをメモリに保持できない場合は、データを最も近い隣人だけにシフトし始めることができます。あなたはあなたの左側のアイテムの数とその方向の「過剰」または「不足」を知っています。そして、あなたはあなたが持っている数も知っています（そしてあなたが過剰または不足を修正するためにあなたの役割を果たした後に持っているでしょう）。したがって、左右のネイバーにデータを送信し始め、左側のプロセッサが集合的に適切な量のアイテムを取得するまで、左右のネイバーからデータを受信します。

ただし、データのコピーを2つ持つ余裕がある場合は、送信されるメッセージの数を最小限に抑える別のアプローチを取ることができます。左側のセルの数は、「グローバル」配列へのローカルデータの開始インデックスと考えることができます。各プロセッサが最終的にいくつのアイテムになるかがわかっているので、それらのアイテムが最終的にどのプロセスになるかを直接把握し、それらを直接送信できます。（たとえば、上記の例では、項目0..8を持つプロセッサ0は、最後のプロセッサ以外の各プロセッサが5つのデータ項目で終わる場合、値5〜8をプロセッサ1に送信できることを認識しています。 ）それらが送信されると、期待する量のデータが得られるまで受信するだけです。これで完了です。

以下は、CおよびMPIでこれを行う簡単な例ですが、基本的なアプローチはほとんどどこでも機能するはずです。MPIのプレフィックススキャン操作は包括的合計を生成するため、排他的合計を取得するには、独自の値の数を減算する必要があります。

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

void initdata(const int rank, const int maxvals, char **data, int *nvals) {
    time_t t;
    unsigned seed;

    t = time(NULL);
    seed = (unsigned)(t * (rank + 1));

    srand(seed);
    *nvals = (rand() % (maxvals-1)) + 1;
    *data = malloc((*nvals+1) * sizeof(char));

    for (int i=0; i<*nvals; i++) {
        (*data)[i] = 'A' + (rank % 26);
    }
    (*data)[*nvals] = '\0';
}

int assignrank(const int globalid, const int totvals, const int size) {
    int nvalsperrank = (totvals + size - 1)/size;
    return (globalid/nvalsperrank);
}

void redistribute(char **data, const int totvals, const int curvals, const int globalstart,
                  const int rank, const int size, int *newnvals) {

    const int stag = 1;
    int nvalsperrank = (totvals + size - 1)/size;

    *newnvals = nvalsperrank;
    if (rank == size-1) *newnvals = totvals - (size-1)*nvalsperrank;

    char *newdata = malloc((*newnvals+1) * sizeof(char));
    newdata[(*newnvals)] = '\0';

    MPI_Request requests[curvals];

    int nmsgs=0;

    /* figure out whose data we have, redistribute it */
    int start=0;
    int newrank = assignrank(globalstart, totvals, size);
    for (int val=1; val<curvals; val++) {
        int nextrank = assignrank(globalstart+val, totvals, size);
        if (nextrank != newrank) {
            MPI_Isend(&((*data)[start]), (val-1)-start+1, MPI_CHAR, newrank, stag, MPI_COMM_WORLD, &(requests[nmsgs]));
            nmsgs++;
            start = val;
            newrank = nextrank;
        }
    }
    MPI_Isend(&((*data)[start]), curvals-start, MPI_CHAR, newrank, stag, MPI_COMM_WORLD, &(requests[nmsgs]));
    nmsgs++;

    /* now receive all of our data */
    int newvalssofar= 0;
    int count;
    MPI_Status status;
    while (newvalssofar != *newnvals) {
        MPI_Recv(&(newdata[newvalssofar]), *newnvals - newvalssofar, MPI_CHAR, MPI_ANY_SOURCE, stag, MPI_COMM_WORLD, &status);
        MPI_Get_count(&status, MPI_CHAR, &count);
        newvalssofar += count;
    }

    /* wait until all of our sends have been received */
    MPI_Status statuses[curvals];
    MPI_Waitall(nmsgs, requests, statuses);

    /* now we can get rid of data and relace it with newdata */
    free(*data);
    *data = newdata;
}

int main(int argc, char **argv) {
    const int maxvals=30;
    int size, rank;
    char *data;
    int mycurnvals, mylvals, myfinalnvals;
    int totvals;

    MPI_Init(&argc, &argv);
    MPI_Comm_size(MPI_COMM_WORLD, &size);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);

    initdata(rank, maxvals, &data, &mycurnvals);

    MPI_Scan( &mycurnvals, &mylvals, 1, MPI_INT, MPI_SUM, MPI_COMM_WORLD );
    if (rank == size-1) totvals = mylvals;
    mylvals -= mycurnvals;

    MPI_Bcast( &totvals, 1, MPI_INT, size-1, MPI_COMM_WORLD );

    printf("%3d      : %s %d\n", rank, data, mylvals);

    redistribute(&data, totvals, mycurnvals, mylvals, rank, size, &myfinalnvals);


    printf("%3d after: %s\n", rank, data);

    free(data);
    MPI_Finalize();
    return 0;
}

これを実行すると、期待される動作が得られます。（ceil（totvals / nprocesses）を使用して）「望ましい」パーティショニングを決定した方法では、通常、最終的なプロセッサの負荷が低くなることに注意してください。また、再配布で順序が保持されるようにする試みは行っていません（ただし、順序が重要な場合は簡単に実行できます）。

$ mpirun -np 13 ./distribute 
  0      : AAAAAAAAAAA 0
  1      : BBBBBBBBBBBB 11
  2      : CCCCCCCCCCCCCCCCCCCCCCCCCC 23
  3      : DDDDDDD 49
  4      : EEEEEEEEE 56
  5      : FFFFFFFFFFFFFFFFFF 65
  6      : G 83
  7      : HHHHHHH 84
  8      : IIIIIIIIIIIIIIIIIIIII 91
  9      : JJJJJJJJJJJJJJJJJJ 112
 10      : KKKKKKKKKKKKKKKKKKKK 130
 11      : LLLLLLLLLLLLLLLLLLLLLLLLLLLL 150
 12      : MMMMMMMMMMMMMMMMMM 178

  0 after: AAAAAAAAAAABBBBB
  1 after: BBBBBBBCCCCCCCCC
  2 after: CCCCCCCCCCCCCCCC
  3 after: DDDDDDDCEEEEEEEE
  4 after: EFFFFFFFFFFFFFFF
  5 after: FFFHHHHHHHIIIIIG
  6 after: IIIIIIIIIIIIIIII
  7 after: JJJJJJJJJJJJJJJJ
  8 after: JJKKKKKKKKKKKKKK
  9 after: LLLLLLLLLLKKKKKK
 10 after: LLLLLLLLLLLLLLLL
 11 after: LLMMMMMMMMMMMMMM
 12 after: MMMM
于 2011-12-17T03:28:06.400 に答える
0

基本的にあなたはから行きたい

[9, 6, 1, 6, 2]

に

[5, 5, 4, 5, 5]

これを行う最良の方法は、floor（sum（array）/ len（array））を計算してから、この位置に到達するために必要な差を評価することだと思います。この場合、floor（（9 + 6 + 1 + 6 + 2）/ 5）= 4であるため、[-5、-2、+ 3、-2、+2]の初期差分を確認しています。次に、符号が異なる隣接するペアの値を貪欲に交換できます（たとえば、2をarray [2]-> arr [1]から転送し、2をarray [4]-> array [3]から転送します）。その後、[-5,0,1,0,0]が残り、ここから残りのビットを貪欲に割り当てることができます。

于 2011-12-07T13:16:10.860 に答える
0

この再分散の問題は、コンピューティングにおける負荷分散とは少し異なると思います。

負荷分散アルゴリズムの用語は、通常、将来の負荷（現在ではない）の比較的均等な分散を保証するためのポリシー/ヒューリスティックの収集を意味します。

この場合、ロードバランサーは既存のサーバー/システムからの負荷を再分散しませんが、新しいリクエストが発生すると、サーバーを比較的均等に保つポリシー（つまり、最小負荷、ラウンドロビンなど）を使用して割り当てを試みます。長期的にはロードされます。

http://en.wikipedia.org/wiki/Load_balancing_(computing）

この質問の負荷の再配分は、アイテムを最大負荷のボックスから最小負荷のボックスに繰り返し移動することで実装できます。

于 2011-12-07T14:11:47.520 に答える