分散グラフアルゴリズムのパフォーマンスをどのように高速化するには？

Question

次のようなグラフの問題があり、実行時間のパフォーマンスを最適化する必要があります。私はプログラミングテクニックを探していて、アルゴリズムの最適化ではなく、パフォーマンスを改善するためにを探しています。グラフG（V、E）が与えられた場合、各ノードuは、uの2ホップの隣接ノードがすべて隣接ノードであるようなマルチノードリレー（M_r（u））と呼ばれる隣接ノードN M_r（u）の少なくとも1つのノードに送信する。ノードuにおけるM_r（u）の構成は以下の通りである。

construct_mr(u) 
1) M_r(u) is initially empty. 
1') The set of non-covered 2-hop of neighbors of u is the set of all 2-hop neighbors of u. 
// a covered 2-hop neighbor of u: is a 2-hop neighbor of u that is also a neighbor to at least one of the nodes of M_r(u). 
2) while (M _r(u) is not a multiset relay set) 
2a) update the set of non-covered 2-hop neighbors of u. 
2b) add to M_r(u) a neighbor v that cover the most non-covered 2-hop neighbors of u. 

さて、私がやったことは以下の通りであった：

for each node u \in V: construct_mr(u). 

それはシリアル化された実装であり、グラフが大きく、緻密でひどい実行時間を持っている、本明細書の問題。私はそのようなアルゴリズムのパフォーマンスを加速するメソッドを探しています - できればjavaまたはC++を使用してください。私はマルチスレッドを使用していますが、良いパフォーマンスを得るためにスレッドスケジューリングを行うべきでしょうか？ [メッセージを受け渡すプログラミングモデルは何の効果もありません。

Answer 1

分散実装が役立つかどうかは疑問です。

問題の中心には、2ホップの隣接関係をそれぞれ識別するグラフトラバーサルプロセスがあります。各インスタンスは、グラフ全体を必要とし、niave場合

• これを行うために、アルゴリズムの分散バージョン内のインスタンスの各々は、グラフのコピーを必要とします。インスタンスにグラフを配布するのにかかる時間が、純粋に並列なフェーズのどのスピードアップよりも速いことが分かります。

• 代わりに、グラフを分割し、各インスタンスにグラフの一部を送信することもできます。しかし、グラフのノードにないグラフノードを見つけるためにインスタンスが他のインスタンスと話す必要があるという問題を導入しました。おそらく並列性を否定するでしょう。

（あなたはインスタンス間で大量のデータを移動する必要がない場合は、と計算が大幅に他の人と話をすることなく、インスタンスが実行することができれば経験則として、分散型ソリューションが最適です。通信コストとインスタンス間の同期は並列処理を中止する傾向があります）。

いいえ、これを並列化したい場合は、単一のJVMでマルチスレッドを使用することをお勧めします。アルゴリズムの実装で最高のパフォーマンスを得るには、スレッド数を使用可能なプロセッサーの数と同じに設定します。それより多くのスレッドを作成すると、状況は悪くなく良くなります。 （そして、それは助けにはなりません...スレッドのスケジューリングをいじるません。）

---

は、私はあなたの計算が遅い本当の理由は、アルゴリズムの詳細および方法であると思われる、と述べましたあなたがデータ構造を実装したことを示します。

遅いアルゴリズムを高速にすることのできる魔法の「プログラミングテクニック」はありませんが、それを変更することはありません。

（コードをプロファイルし、ほとんどの時間が費やされている場所を特定し、それを深く考えた後に...コード/データ構造を再設計して改善することですここに魔法はありません。ただの努力と思考。）