5

私は反復アルゴリズムを実装しました。このアルゴリズムでは、各反復で順序ツリーのトラバーサル (下向きの累積と呼ばれることもあります) が行われ、その後に順序ツリーのトラバーサル (上向きの累積) が続きます。各ノードへの訪問ごとに、次の訪問に使用するための情報を計算して保存する必要があります (後続のポストオーダー トラバーサルまたは後続の反復のいずれかで)。

事前注文トラバーサル中、各ノードは、それとルートの間のすべてのノードがすでに処理されている限り、個別に処理できます。処理後、各ノードはタプル (具体的には 2 つの float) をそれぞれの子に渡す必要があります。ポストオーダー トラバーサルでは、すべてのサブツリー (存在する場合) が既に処理されている限り、各ノードを個別に処理できます。処理後、各ノードは単一のフロートをその親に渡す必要があります。

ツリーの構造は静的で、アルゴリズム中は変更されません。ただし、下向きのトラバーサルの過程で、渡される 2 つの float が両方とも 0 になった場合、このノードの下のサブツリー全体を処理する必要はなく、このノードの上向きのトラバーサルを開始できます。(後続の反復で渡された float がこのノードで非ゼロになる可能性があり、トラバーサルが再開されるため、サブツリーを保持する必要があります)。

各ノードでの計算の強度は、ツリー全体で同じです。各ノードでの計算は簡単です。ノードでの子の数と同じ長さの数値のリストで、いくつかの合計と乗算/除算を行うだけです。

処理中のツリーはバランスが取れていません。通常のノードには 2 つのリーフと 0 ～ 6 個の追加の子ノードがあります。したがって、単純にツリーを比較的バランスの取れたサブツリーのセットに分割することは (私には) 自明ではありません。さらに、ツリーは使用可能なすべての RAM を消費するように設計されています。処理できるツリーが大きいほど、優れています。

私のシリアル実装は、私の小さなテスト ツリーだけで毎秒 1000 回の反復を達成しています。「本物の」木では、1桁（またはそれ以上？）遅くなる可能性があると思います。アルゴリズムが許容できる結果に到達するには、少なくとも 1 億回 (場合によっては最大 10 億回) の反復が必要であることを考えると、アルゴリズムを並列化して、複数のコアを活用したいと考えています。並列プログラミングの経験はありません。

アルゴリズムの性質を考慮した並列化の推奨パターンは何ですか?

4

3 に答える 3

4

純粋関数で構成されるようにアルゴリズムを書き直してみてください。つまり、すべてのコードは本質的に（小さな）静的関数であり、グローバル変数や静的変数に依存せず、すべてのデータは不変として扱われます---変更はコピーに対してのみ行われます---そしてすべての関数は操作するだけです（新しい）データを返すことによって（「操作する」という言葉の大まかな意味で）状態。

すべての関数が参照透過性である場合---出力を計算するために入力のみに依存し（非表示状態はありません）、同じ入力を使用するすべての関数呼び出しは常に同じ出力を生成します---アルゴリズムを並列化する：コードがグローバル変数（またはファイル、サーバーなど）を変更することはないため、関数が実行する作業を安全に繰り返す（関数の結果を再計算する）か、完全に無視する（将来のコードがこの関数の副作用に依存しない）ことができます。したがって、呼び出しを完全にスキップしても、何も中断されません）。次に、一連の関数を実行すると（たとえば、MapReduceの一部の実装では、hadoopなど）関数のチェーンは、ある関数の出力と別の関数の入力のみに基づいて依存関係の魔法のカスケードを引き起こし、（純粋関数を介して）計算しようとしているものは、のORDERから完全に分離されますこれを計算しようとしています（MapReduceのようなフレームワークのスケジューラーの実装によって答えられる質問）。

この考え方を学ぶのに最適な場所は、並列/マルチコアプログラミングをすぐにサポートするプログラミング言語Haskell（またはF＃またはOcaml）でアルゴリズムを作成することです。Haskellはコードを純粋にするため、アルゴリズムが機能する場合は、おそらく簡単に並列化できます。

于 2010-02-09T01:16:53.323 に答える
3

通常の方法は、ある種の深さ優先の作業分割を使用することです。アイドル キューで待機している多数のワーカーから開始し、1 つのワーカーがルートでトラバーサルを開始します。作業のあるワーカーは、最初に深さをトラバースし、ノードに複数の子が残っている場合は常に、アイドル ワーカー キューをチェックし、それが空でない場合は、サブツリー (子) を別のワーカーにファームします。ワーカーがサブツリーを終了するときに結合を処理するのは複雑ですが、一般に、これはさまざまなツリー構造 (バランスまたはアンバランス) に対してうまく機能します。

于 2010-02-09T00:50:54.343 に答える
2

この回答では、私が日常的に取り組んでいる並列言語とランタイム システムであるCharm++を使用してそれを行う方法について説明します。このフレームワーク内のシーケンシャル コードに使用される言語は C または C++ であるため、計算コードの移植には多少の労力が必要になることに注意してください。Charm++ には、Python コードと相互運用するためのメカニズムがいくつかありますが、私はそれらの側面にあまり詳しくありません。ドライバーとインターフェイスのコードを Python のままにして、重い計算コードを C++ に入れるだけでよい可能性があります。いずれにせよ、シーケンシャル コードへの移植作業により、次のパフォーマンスが向上する可能性があります。

デザイン：

並列オブジェクトの配列 (私たちの環境ではcharesと呼ばれます) を作成し、サブツリーのルートから部分的に下に向かって伸びる内部ツリー ノードのワークリストをそれぞれに割り当てます。これらのノードに接続されている葉も、その葉に属します。

各並列オブジェクトには、2 つの非同期リモート呼び出し可能なメソッド (エントリ メソッドpassDown(float a, float b)および と呼ばれる) が必要でありpassUp(int nodeID, float f)、これらがそれらの間の通信ポイントになります。passDown事前注文の計算を行うために使用される任意のノード メソッドを呼び出し、オブジェクト外の子を持つノードはpassDownそれらの子孫オブジェクトを呼び出します。

下向きの作業がすべて完了すると、オブジェクトは葉の上向きの作業を計算し、その子孫を待ちます。の呼び出しはpassUp、すべての子からデータを受信して​​いない親に到達するまで、受信オブジェクトのツリーを可能な限り計算します。オブジェクトのルート ノードが上向きの作業で完了するとpassUp、親ノードを保持しているオブジェクトが呼び出されます。ツリー全体のルートが完了すると、反復が完了したことがわかります。

実行結果:

これが実装されると、ランタイム システムが並列実行を処理します。プロセッサ間、さらには別々の計算ノード間でオブジェクトを分散します (したがって、使用可能なメモリがはるかに大きくスケーリングできるため、ツリー サイズの上限が劇的に上がります)。プロセッサとノード間の通信は、インプロセス通信 (非同期メソッド呼び出し) と同じように見えます。ランタイムは、オブジェクトの負荷を分散して、各反復の間、すべてのプロセッサを可能な限りビジー状態に保つことができます。

チューニング：

この方法で並列パフォーマンスを調整する段階に達した場合は、メッセージに優先順位を設定して、クリティカル パスの長さを短く保つこともできます。私の頭の上から、私が提案する優先順位付けはこの順序で機能するでしょう

  1. ゼロでない下方作業
    • 根元に近づくほど早くなる
  2. 上向きの仕事
    • 葉に近づくほど早くなる

Charm++ は Projections と呼ばれるパフォーマンス分析ツールと連携して、プログラムのパフォーマンスをさらに詳しく知ることができます。

于 2010-02-09T17:34:40.827 に答える