動的プログラムを取り、それを並列化する方法を議論している良い論文はありますか？
6105 次
3 に答える
13
最近、共有ロックフリーハッシュテーブルを使用して共有メモリマルチコアコンピューター上のdpを並列化する方法を示す論文を公開しました。
Stivala、A.とStuckey、PJとGarcia de la Banda、M.とHermenegildo、M.とWirth、A.2010「ロックフリー並列動的計画法」J.ParallelDistrib。計算します。70：839-848 doi：10.1016 / j.jpdc.2010.01.004
http://dx.doi.org/10.1016/j.jpdc.2010.01.004
基本的に、複数のスレッドを開始し、計算するdpの値から開始して同じコードを実行し、トップダウンで（再帰的に）計算し、共有のロックフリーハッシュテーブルにメモ化しますが、順序はランダム化されます。サブ問題は、スレッドが計算するサブ問題で分岐するように計算されます。
実装に関しては、UNIXタイプのシステムでCとpthreadを使用しました。必要なのは、共有メモリと、スレッド間のロックフリー同期のためのCompareAndSwap（CAS）を使用できることだけです。
この論文はエルゼビアのジャーナルに掲載されているため、大学図書館などから購読して上記にアクセスする必要があります。ただし、Stuckey教授のWebページからプレプリントコピーを入手できる場合があります。
于 2010-09-28T01:36:52.643 に答える
6
IIRC、動的計画法で通常行うことは、問題を再帰的にサブ問題に分割し、最適なサブソリューションから最適なソリューションを組み立てることです。それを効果的にするのは、すべての最適なサブソリューションがキャッシュに組み込まれているため、再計算する必要がないことです。
問題をいくつかの方法で分割できる場合は、サブソリューションごとにソルバーをフォークできます。各（サブ）問題の平均が1 +イプシロン（興味深いことにゼロより大きいイプシロンの場合）の可能なサブソリューションである場合、この方法で多くの並列処理が得られます。個々のソリューションが複数回構築されるのを防ぐために、キャッシュエントリをロックする必要があります。
サブタスクを解決するための作業よりも安価にフォークできる言語が必要です。また、一度に多くのフォークされたタスクを実行できる言語が必要です。ほとんどの言語の典型的な並列オファリングはこれをうまく行いません。「ビッグスタックモデル」を使用するシステムでは、フォークされたタスクをたくさん持つことはできません（スタックレス言語はどのように機能しますか？を参照）。
適切なプロパティを持つ言語を取得するために、並列プログラミング言語PARLANSEを実装しました。
于 2009-07-20T03:26:20.080 に答える
0
GPUでの動的計画法アルゴリズムの実装に関連するいくつかの作業があります。例：
于 2020-07-22T13:20:53.943 に答える