3

プレフィックスの合計を並列に計算するためのアルゴリズムの実装に問題があります。このアルゴリズムには3つのステップがありますが、擬似コードが指定されていないため、コードを記述できません。

Webやスタックオーバーフローについてさまざまな資料を調べましたが、 wikiに記載されているアルゴリズムの正確な実装を取得できませんでした。ウィキには次のことが記載されています。

プレフィックスの合計は、次の手順で並行して計算できます。

  1. ペアの最初のアイテムが偶数のインデックスを持つアイテムの連続するペアの合計を計算します：z0 = x0 + x1、z1 =x2+x3など。
  2. シーケンスz0、z1、z2、..のプレフィックス合計w0、w1、w2、...を再帰的に計算します。
  3. シーケンスw0、w1、w2、...の各項を全体的なプレフィックス合計の2つの項に展開します：y0 = x0、y1 = w0、y2 = w0 + x2、y3 = w1など。最初の値の後、それぞれ連続番号yiは、wシーケンスの半分の位置からコピーされるか、xシーケンスの1つの値に前の値が追加されます。

誰かが私がチェックして実装するための擬似コードの実装を提案できますか？

4

2 に答える 2

5

提供された回答はアルゴリズムを理解するのに十分ではないと思うので、ここでより包括的な擬似コードを使用して実際の回答を提供しました：https ://stackoverflow.com/a/12874227/697862 CUDAを使用した並列プレフィックス合計（スキャン）に基づく以下による最適な並列アルゴリズムを説明する完全な記事：

Blelloch、GuyE.1990.「プレフィックス合計とそのアプリケーション」。テクニカルレポートCMU-CS-90-190、カーネギーメロン大学コンピュータサイエンス学部。

于 2012-10-13T15:00:09.550 に答える
1

あなたが書いたものは、それ自体でほとんど擬似コードですが、これが役立つことを願っています。

prefix_sum(List x):List
begin
   //This step is split in multiple tasks that are running in paralell
   //build z, be careful around the end
   w = prefix_sum(z)

   //This step should also be split in multiple tasks
   //build y, using w and x
   return y
end

編集：y iは、取得したい合計であり、i％2 ==1の場合はyi= w i / 2、それ以外の場合はw i / 2-1 + xです。ここでは、w -1 =0と仮定します。

于 2012-04-08T11:01:37.800 に答える