私は並列プログラミングを始めており、mapreduce やその他の分散アルゴリズムを研究しています。mapreduce を学ぶのが最善ですか、それとももっと役立つより一般的なアルゴリズムがありますか?
4 に答える
アルゴリズムを何に使用するかによって異なります。
MapReduceは、一般化された非常に便利なプログラミング モデルです。(Google は、内部のインデックス作成プロセスの多くをこれに基づいています)。それを学ぶことは確かにあなたに害を及ぼすことはありません。
MapReduce はプログラミング モデルであり、大規模なデータ セットを処理および生成するための関連する実装です。ユーザーは、キーと値のペアを処理して一連の中間キーと値のペアを生成する map 関数と、同じ中間キーに関連付けられたすべての中間値をマージする reduce 関数を指定します。論文に示されているように、このモデルでは多くの現実世界のタスクを表現できます。
学ぶべき最も重要な並列処理の概念は非常に単純です。効果的な高速化を達成したい場合は、同期を最小限に抑える必要があります。
のために努力:
- ワークチャンクの粒度が大きい
- 作業チャンクのサイズを同じサイズに保つ
- 同期ステップの数を最小限に抑える
多くの「通常の」シリアル アルゴリズムには並列バージョンがあり、その一部は MapReduce でモデル化できます。MapReduce は新しくてエキサイティングなので、確かに学んでください。しかし、これはツールボックスの 1 つのツールにすぎません。
並列処理について何かを学びたい場合、単一のアルゴリズムを選択しても重要な洞察が得られるとは思いません。
Mapreduce はmap
とreduce
演算の合成です。これらは、関数型言語が提供する典型的な高階関数です。
まず、Scheme や Clojure などの関数型言語を学ぶことをお勧めします。Scheme では、「コンピュータ プログラムの構造と解釈」が大流行しているようです。
並列プログラミングを実際によく理解するには、1つの並列プログラミングフレームワークだけでなく、いくつかの並列プログラミングモデルを研究する必要があります。並列プログラミングへの共有メモリ(pthreadなど)とメッセージパッシング(MPIやMapReduceなど)の両方のアプローチを検討する必要があります。
MPIは、メッセージパッシングアプリケーションを作成するための非常に汎用的なツールです。MPIを広範囲に使用すると、MPIプログラムの一部の要素が何度も繰り返されることがわかります。たとえば、作業を「ワーカー」プロセスに分割し、結果を集約する「マスター」プロセスを設定するなどです。MapReduceは、メッセージパッシングフレームワークの特定の実装であり、MPIよりも単純なプログラミングモデルを提供します。並列アプリケーションで非常に頻繁に発生するコードを処理し、さらに重要なことに、障害回復やデータの局所性などの問題を処理します。オープンソースのHadoopは、MapReduceを模倣しようとします。
独自のMPIプログラムをいくつか作成することで、MapReduceの機能と、それがどのように実装されるかをよりよく理解できるようになると思います。Hadoopを学ぶことは害にはなりませんが、並列プログラミングの一般的な知識に関しては、pthread、OpenMP、MPIなどの基本に精通しているとよいでしょう。