問題タブ [prefix-sum]

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]]

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

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

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

C# で Parallel プレフィックス合計を書きたいと思います。私はこのアルゴリズムを使用しました：

そして、c# での私の最終的なコードは次のとおりです。

ライトの出力は [4,7,15,17,26,27,30,35,41,44] です
が、私の出力コードは [4,7,8,2,9,1,3,5, 6,3]
私のコードの何が問題なのか知っている人はいますか?
編集:
すべてのプロセッサがローカルで配列 A を参照していることがわかりました。問題は、すべてのプロセッサが 1 つの配列を参照できるように、配列 A をグローバルに定義する方法です。

コードを並列化するために openmp を使用しています。私は元の配列を持っています:

およびマーク配列:

配列 M を使用すると、元の配列をこのパック配列に圧縮できます。

マルチスレッドアプローチを使用してこの問題を解決したいと思います。C++ 用のライブラリ 'Thrust' はこの問題を解決しますが、Fortran 用の同様のツールを見つけることができません。ストリーム圧縮を実行するために使用できる、C++ の「thrust」のようなライブラリはありますか? または、これを解決するために、fortran と openmp を使用して自分で作成できるアルゴリズムはありますか?

配列のプレフィックス合計 [1] を返し、要素を更新し、要素を配列に挿入/削除できるデータ構造はすべて O(log n) ですか?

[1] 「接頭辞の合計」は、最初の要素から指定されたインデックスまでのすべての要素の合計です

たとえば、負でない整数の配列が与えられた場合、8 1 10 7最初の 3 つの要素のプレフィックスの合計は19( 8+ 1+ 10) です。最初の要素を に更新し、2 番目の要素として7挿入3し、3 番目の要素を削除すると、 が得られ7 3 10 7ます。繰り返しますが、最初の 3 つの要素のプレフィックスの合計は になります20。

プレフィックスの合計と更新には、フェンウィック ツリーがあります。しかし、O（log n）での追加/削除を処理する方法がわかりません。

一方、赤黒木などの二分探索木はいくつかあり、それらはすべて対数時間で更新/挿入/削除を処理します。しかし、指定された順序を維持し、O(log n) でプレフィックスの合計を行う方法がわかりません。

プレフィックスサムの問題に並列アルゴリズムを割り当てると、いくつかの問題があります。並列実装に openMP を使用しています。私は以下のようにcでコードを持っています。

結果表示:

お知らせ下さい。ありがとう。

本 GPU Gems 3、Chapter 39: Parallel Prefix Sum (Scan) with CUDAでカーネルを呼び出すコードを書きました。

ただし、得られる結果は、プレフィックススキャンではなく、一連の負の数です。

カーネル呼び出しが間違っているのでしょうか、それとも GPU Gems 3 ブックのコードに何か問題がありますか?

これが私のコードです：

並列リダクションのアルゴリズムのほとんどは、共有 (ローカル) メモリを使用します。

Nvidia、AMD、インテルなど。

ただし、デバイスに共有（ローカル）メモリがない場合。

どうすればいいですか？

同じアルゴリズムを使用しているが、グローバル メモリに一時的な値を保存している場合、問題なく動作しますか?

OpenCL での scan(prefixsum) の高速実装を探しています。私が見つけた最高のものはNvidia SDKにありますが、それは古いです（2010）。OpenCLでのスキャンの他の実装を知っている人はいますか?