3

次の問題を解決するアルゴリズムを探しています。

nマルチキャストを介して通信できるソフトウェア コンポーネントがあります。さらに、オブジェクトのあるプールがありmます。すべての sw コンポーネントは、そのプールに何が含まれているかを認識しています。オブジェクトには異なる値があります。値に応じて、オブジェクトを sw コンポーネントに配布します。つまり、値が大きいオブジェクトを優先する必要があり、値が小さいオブジェクトは無視する必要があります (たとえば、すべての sw コンポーネントがそれ以上のオブジェクトを取得できない場合)。

オブジェクトが複数回配布されないことが非常に重要です。1 つのオブジェクトが sw コンポーネントに割り当てられている場合、別の sw コンポーネントに割り当ててはなりません。

さらに、すべてを分散アルゴリズムとして実装したいと考えています。つまり、その分散を実行する中央ユニットは必要ありません。

何か案は？

4

1 に答える 1

0
  1. 1 つの解決策は、相互排除アルゴリズム (非常に単純なものはベーカリー アルゴリズム) を実装することであり、各 sw は順番が来ると最高のオブジェクトを取得します。(これはファイルへの書き込みの相互排除のようなものです)
  2. もう 1 つは、ノード間で多くの通信が必要になります。N>=M の一般的なケースを考えてみましょう。各 sw が n/m コンポーネントを取り、最大値を取り、残りの x コンポーネントを x sw にマルチキャストしますが、追加の値はこれらのコンポーネントの最大 *casted であるとします。受信者は、受信した値よりも値が大きいかどうかを確認し、交換してリストからその値を削除しますが、古い値を挿入します。次に、計算された最大値を持つコンポーネントを同じ x sw コンポーネントにキャストします。アイデアは、すべてのノードが異なる値を持つまで、sw のセット X が互いに通信するということです。この X セットがいくつかあります。もちろん、このアルゴリズムは、すべての sw が異なる値を持つように改良する必要があり、これが確実に起こることを証明する必要があります。

しかし、あなたが望んでいたので、私はあなたに2を与えました.それが役に立てば幸い. アルゴリズムの実装は、OpenMPI (C または C++ を使用) になります。少なくとも、OpenMPI (および Lam MPI ですが、現在は廃止されています) で分散アルゴリズムを実装しました。

于 2012-07-07T17:39:28.863 に答える