問題タブ [prefix-sum]

私はいくつかのデータ並列Haskellコードで遊んでいて、プレフィックス合計が必要であることに気づきました。ただし、プレフィックス合計のdphパッケージに基本的な演算子はありませんでした。

私は自分でロールしましたが、dphを初めて使用するため、並列化を適切に利用しているかどうかはわかりません。

まず、アルゴリズムへのリンクは次のとおりです。

GPU Gems 3、第39章：CUDAを使用した並列プレフィックス合計（スキャン）。

バンクの競合を回避するために、NUM_BANKS（つまり、計算可能性2.xのデバイスの場合は32）要素ごとに共有メモリ配列にパディングが追加されます。これは（図39-5のように）によって行われます。

ai/NUM_BANKSがマクロとどのように同等であるかわかりません。

等しいではありませんか

どんな助けでも大歓迎です。ありがとう

プレフィックスの合計を並列に計算するためのアルゴリズムの実装に問題があります。このアルゴリズムには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つの値に前の値が追加されます。

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

プレフィックス合計アルゴリズムを実装する必要があり、可能な限り高速である必要があります。
元：

与える必要があります：

SSE SIMD CPU命令を使用してこれを行う方法はありますか？

私の最初のアイデアは、すべての合計が以下のように計算されるまで、各ペアを再帰的に並列に合計することです。

アルゴリズムをもう少し明確にするために、zは最終出力ではなく、出力の計算に使用されます。

私はいくつかの比較を行い、2つのオブジェクトが衝突するかどうかを決定するカーネルを持っています。衝突するオブジェクトのIDを出力バッファに保存したい。出力バッファにギャップを持たせたくありません。各衝突を出力バッファの一意のインデックスに記録したいと思います。

そこで、共有メモリ（ローカル合計）とグローバルメモリ（グローバル合計）にアトミック変数を作成しました。以下のコードは、衝突が見つかったときの共有変数の増分を示しています。今のところ、グローバルメモリでアトミック変数をインクリメントすることに問題はありません。

私の問題は、多くのスレッドがアトミック変数をインクリメントしようとすると、シリアル化されることです。prefix-sumのようなものを書く前に、これを効率的に行う方法があるかどうかを尋ねたかったのです。

この1行があるため、カーネルの経過時間は13ミリ秒から44ミリ秒に増加します。

プレフィックスサムのサンプルコードを見つけましたが、NVIDIAのディスカッションボードがダウンしているため、参照されているリンクが失敗します。 https://stackoverflow.com/a/3836944/596547

編集：上記にコードの最後も追加しました。実際、私には階層があります。すべてのコード行の影響を確認するために、すべてのオブジェクトが互いに衝突するシーン、極端な場合、およびオブジェクトがほとんど衝突しない別の極端な場合を設定します。

最後に、共有アトミック変数をグローバル変数（gColCnt）に追加して、衝突の数を外部に通知し、正しいインデックス値を見つけます。ここでは何らかの方法でatomicAddを使用する必要があると思います。

私はランダムな整数の配列を持っています。たとえば[132, 2, 31, 49, 15, 6, 70, 18 ... , 99, 1001]。たとえば、100 を超えるすべての数値の配列を生成し、その配列のサイズを取得したいと考えています。

次の 2 つの方法があります。

1. PyOpenCL の新機能copy_if。これは、 Prefix SumsGenericScanKernelをさらに深く掘り下げた場合に基づいてい ます。
2. Atomicsを使用した純粋な OpenCL ソリューション

copy_if常に正しく動作しますか? 私が見ることができるようにcopy_if、原子を使用していません。を使用してトラブルに直面することは可能copy_ifですか?

copy_ifアトミックな方法と比較してのパフォーマンスはどうですか?

あなたは何を選びますか、そしてその理由は何ですか？

そのため、一連の数値に対して接頭辞の合計を実行するアセンブリ コードを作成する任務を負っています。

与えられた例は2 4 6 -1であり、戻り値は である必要があります12 10 6。-1ストッパーとして機能します。

したがって、基本的に私のコードは印刷6 10 12され、この出力を逆にする方法を見つける必要があります。何か案は？

ローカル メモリをまったくサポートしない Mali GPU を使用しています。ローカル メモリで構成されるコードを実行するたびに、デバイスからいくつかのエラーが発生します。そのため、コードをグローバル メモリのみを使用するバージョンに転送したいと考えています。GPU のみでグローバル メモリを使用してプレフィックス サム/パラレル リダクション アルゴリズムを実行できるかどうかを考えていました。

EDITED: エラーをデバッグしていて、ある特定の行でエラーが発生しているという奇妙なことがわかりました。次のような行があります。

ふたはローカルIDで、サイズ32のqorkグループを使用しました。強調表示された行がエラーの原因であることがわかりました。lm_sum固定値を使用してみましたが、ステートメントの右側には使用できないことがわかりました。もしそうなら、それは私にエラーを与えます。たとえば、次の行でもエラーが発生します。 int temp= lm_sum[0][0]

何が起こっているかについて何か考えはありますか？

エラー：

CUDA または OpenCL を使用したプレフィックス サム/スキャン アルゴリズムのグローバル メモリ実装を探していました。すべての実装は、ローカル メモリを使用して行われています。誰かがアルゴリズムと私がどのように進めるべきかについて私を助けることができますか?

私と私の友人は、単純な Python プロジェクトに取り組んでいます。実際には、独自の方法で前置並列合計アルゴリズムを実装しています。

非常に奇妙な形式のバイナリ ツリーを作成して処理しています。この形式を、ete2 などの Tree 印刷ライブラリ/ソフトウェアで受け入れられる形式に変換したいと考えています。

したがって、ツリーのすべてのレベルがそのようにリストにプッシュされます

私たちの形式では、すべての内部リスト (ツリーのレベル) に偶数のノードまたはリーフがあります。

たとえば、次の入力があるとします[1, 2, 3, 4, 5]。これにより、次の出力リストが生成されます。[[1, 2, 3, 4], [3, 7], [10, 5], [15]]

上記の出力例の問題は、葉が最終レベルにない場合があることですが、それらは上位レベルのリストに含まれています。これにより、リストのリストを処理し、ノードとリーフを区別し、それらを正しい位置に配置することが難しくなります。

これを次のように視覚化したいと思います。

http://i.imgur.com/BKrqNZi.png

ここで、括弧内の数字はノードで、それ以外は葉です。

この出力ツリーを生成するために、1 つの Tree 描画ライブラリを使用したいと考えています。それらのほとんどは、このタイプのフォーマットを期待しています:[root, [left], [right]]

したがって、この例では、フォーマットは次のようになります。

現時点では、コードのロジック全体を書き直す立場にないため、奇妙な形式をその形式に変換するスマートな方法を探しています。

どんなアイデアでも大歓迎です。事前にどうもありがとうございました。