algorithm - map reduce アルゴリズムの並列効率を計算する式は何ですか?

Question

map reduce アルゴリズムの並列効率を示す式はありますか? (つまり、MR アルゴリズム A が MR アルゴリズム B よりも優れていることを数学的に証明する方法)

私はそれをグーグルで検索しましたが、ウィキで並列アルゴリズムの高速化と効率の定義を見つけることができましたが、それらの式がMRアルゴリズムにどのように適用されるかを誰かが示すことができれば良いでしょう.

Answer 1

要するにWikiを見てください。Bulk Synchronous ParallelBSP

別の複雑さの計算は、Rob Biselings の論文に含まれています。

並列科学計算: BSP と MPI を使用した構造化アプローチ

BSPへの抽象化MapReduceであり、リンクの下部にある複雑さ/コスト分析式が含まれています。

MapReduceしたがって、アルゴリズムをBSPバージョンに変換する必要があります。バリア同期は、たとえば、ステージ間の遷移MapまたはReduce新しいMapReduceジョブです。Mapメッセージ (通信) は、関数内のファイルシステムに送信するものですReduce。