ロードバランシング/再配布に関連するアルゴリズムの名前

Question

配列[x1、x2、x3、...、xk]ここで、xiはボックスiのアイテム数です。 どのようにしてアイテムを再配布できますか？ボックスにはN個以上のアイテムが含まれていません。 Nはsum（xi）/ kに近い。つまり、Nは同じ数の項目を持つすべてのボックスに近い。 x1は余剰があり、x2とx3に赤字がある場合、x1はx2とx3にいくつかの項目を送信するが、その項目をx2に送信してx2に余剰を解決させるべきではない。

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

私はこの種の問題に名前があると想像します。

Answer 1

この問題は、minimum-cost flowのインスタンスとしてモデル化できます。

レッツGは _K B、...、 B、頂点S、T、、...、 _Kと有向グラフであるとアークS →容量Xの _{I I}とコスト0、アーク容量Nの _J →トンB無限容量の _I → B _Jとi = jの場合は0、コストおよびI≠jの場合は1をコスト、アークが0を要します。我々は最小コストを求めている移動する流れΣ _i x _i単位sからt。アイデアは、y単位がフローすると、y単位がボックスiからjまで移動する（i≠jの場合、i = jの場合、移動は起こらない）ということです。

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

• ノードのペアI、Jが直接接続されていない場合、 _I → B _Jアークを削除します。

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

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

• 2つのノードが交換する項目の数を制限することができます。

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

Answer 2

それはあなたが

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/

を参照してください。

Answer 3

あなたは

[5, 5, 4, 5, 5] 

に

[9, 6, 1, 6, 2] 

から行きたい基本的に私はこれを行うための最善の方法は、床（合計（配列）/ LEN（配列））を算出することであると思うし、この位置に到達するために必要な差異を評価します。この場合、floor（（9 + 6 + 1 + 6 + 2）/ 5）= 4なので、[-5、-2、+3、-2、+2]の初期微分を見ています。次に、標識が異なる隣接する対（配列[2]→arr [1]から2を配列[4]→配列[3]から2に移すなど）で値を貪欲に入れ替えることができます。 [-5,0,1,0,0]が残っています。残りのビットを貪欲に割り当てることができます。

Answer 4

この再配布の問題は、コンピューティングのロードバランスとは少し違うと思います。

ロードバランシングアルゴリズムの用語は、通常、FUTUREロードの比較的均等な分散を保証するためのポリシー/ヒューリスティックスの収集を意味します（現在ではありません）。

この場合、ロードバランサは既存のサーバ/システムから負荷を再配分しませんが、新しい要求が到着すると、何らかのポリシー（つまり、最小負荷、ラウンドロビンなど）を使用して割り当てを試みます。長期間に渡ってサーバを比較的均等にロードしてください。

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

この質問では、負荷の再分配は、おそらく繰り返し、最小限のロードされたボックスにロードされた最大の項目を移動することで実現できます。

Answer 5

私はあなたの問題が（上記のように）独立した研究を引き付けるのに十分複雑であるとは思わない。マシンの数（Cと呼ぶ）が千単位で、サンプル数が数十億にも及ぶ場合、サンプルの数がに調整されたマスターノードに送信するのは簡単です。

マスターは次に、Nを計算し、この境界に違反しているノードを特定し、どれだけそのノードを識別できるかを確認します（O(C)）。境界を超えた超過分の合計は正確に必要な最小限の通信量であることに注意してください。 Nを計算するとき（すなわち、アンバランスを受け入れることによって）スラックパラメータを挿入することによって、この量を制御することができる。

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

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

マシンのネットワークにという制約がある場合は、欠落しているリンクまたは最大フローまたは可変コストのいずれかがある場合は、グラフフローの内容を分割する必要があります。しかし、このようなことは言及しておらず、同じデータセンター内のコンピュータクラスタには一般的に何もありません。

Answer 6

私は質問は、このように明確にすべきだと思う：

M余剰ノードとK赤字ノードで、我々は（おそらく）0余剰ノードといくつかの赤字のノードと状態にノード間のサンプルを再配布する必要があります。サンプルはパックで交換し、これらのパックの数を最小限に抑える必要があります。

あるいは、数学的に、我々はそれの各セルは、各行の要素の所与の和と、ノードKにノードMから通過するサンプルの数を表し、各列の要素の和の最大値が与えられ、M*Kマトリックスを有しています。目標は、ゼロでないセルの数を最小限に抑えることです。

これは"Constraint satisfaction problems"の種類です。それはNP完全です。私はこの質問に類似した2つの古典的な問題、すなわち「パッキングの設定」と「一般化された正確なカバー」を見つけました。

"Set packing"に問題を減らすには、それぞれにN+1サンプルの余剰ノードを（一時的に）追加する必要があります。その結果、再配布後に欠損ノードが残っていないようにします。次に、各ノードに対して、余剰要素と「不足」要素のすべての可能なパーティションを生成する必要があります。次に、余剰と不足のパーティションのCartesian productには、「最適化」バージョンで「パッキングを設定する」が適用され、最小数のサブセットが検索されます。

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

「一般化された正確なカバー」は"Knuth's Algorithm X"で解決できます。私は "パッキングを設定する"ためのアルゴリズムを知らない。

これらのソリューションはすべて正確な答えを示しますが、膨大な計算量を要します。誰かが実際のスケジューラでそれらを使用することはほとんどありません。実践的なアプローチは、ヒューリスティックスとグリーディーアルゴリズムを使用することです。余剰ノードと欠損ノードの両方をソートし、「最適」戦略を適用してください。

Answer 7

通常、これはデータの再配布と呼ばれていますが、再配布する場合は、タスク間の均等性のようなメトリックの下で配布が最適であることを理解しています。

これは、計算負荷分散を実行しようとしているときに、科学技術計算に現れます。いくつかの次元で計算を行っていても、スペース・フィリング・カーブでプロセッサーに割り当てた空間データを再配分すると、この正確な問題が発生し、データを均等に分割したいことがあります。

この手順はかなり簡単です。あなたはxiの排他的なprefix sumを取って、あなたの "左"にいくつのアイテムがあるかを知ることから始めます。例えば、上記の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