問題タブ [reduction]

OpenMPを使用して並列化した素数を計算するコードがあります。

私はそれをGPUに移植しようとしていますが、上記のOpenMPの例で行ったようにカウントを減らしたいと思います。以下は私のコードですが、間違った結果を出すことは別として、遅いです：

まず、このカーネルを高速化するにはどうすればよいですか。ボトルネックはforループだと思いますが、どのように置き換えるかはわかりません。そして次に、私のカウントは正しくありません。'％'演算子を変更しましたが、いくつかの利点に気づきました。

配列ではflags、2からsqroot（N）までの素数をマークしました。このカーネルでは、sqroot（N）からNまでの素数を計算していますが、{sqroot（N）、N}の各数値を確認する必要があります。 {2、sqroot（N）}の素数で割り切れる。o_flags配列には、各ブロックの部分和が格納されます。

編集：提案に従って、コードを変更しました（syncthreadsに関するコメントについて理解が深まりました）。私はflags配列は必要なく、私の場合はグローバルインデックスだけが機能することに気づきました。この時点で私が懸念しているのは、forループに起因する可能性のあるコードの遅さ（正確さ以上）です。また、特定のデータサイズ（100000）の後、カーネルは後続のデータサイズに対して誤った結果を生成していました。データサイズが100000未満の場合でも、GPU削減の結果は正しくありません（NVidiaフォーラムのメンバーは、データサイズが2の累乗ではないことが原因である可能性があると指摘しました）。したがって、まだ3つの（関連している可能性がある）質問があります-

1. どうすればこのカーネルを高速化できますか？各tidをループする必要がある場合は、共有メモリを使用することをお勧めしますか？

2. 特定のデータサイズに対してのみ正しい結果が生成されるのはなぜですか？

3. どうすれば削減を変更できますか？

   /li>

3SAT≤p3COLOR（つまり、3SATは3COLORに還元可能な多項式時間）であることがわかっています。なぜ3COLOR≤p3SATなのか、誰かが短い議論をすることができますか？そして、3COLOR≤p3SATであることを示す実際のクックリダクションを与えてください。

データを CPU ホストに送り返す必要なく、カーネルから配列を総和しようとしていますが、正しい結果が得られません。これが私が使用する合計カーネルです（NVIDIAが提供するものからわずかに変更されています）：

何か不足していますか？ありがとう！

書こうとしている CUDA プログラムに問題があります。約 524k の浮動小数点値 (1.0) の配列があり、リダクション手法を使用してすべての値を追加しています。1 回だけ実行したい場合は問題なく動作しますが、実際にはカーネルを数回実行して、最終的に 10 億を超える値を合計できるようにしたいと考えています。

これを 524k のチャンクで行っている理由は、GPU で約 100 万を超えると常にゼロが返されるためです。カードのメモリを超えてはいけませんが、その時点で常に失敗します。

とにかく、カーネルを 1 回だけループすると、すべて正常に動作します。つまり、ループしなくても問題ありません。ループを実行すると、ゼロが返されます。どこかで限界を超えているのではないかと思いますが、それがわかりません。それは私を夢中にさせています。

どんな助けでも大歓迎です、

ありがとう、

アル

コードは次のとおりです。

さて、問題をデバイスの V_d に絞り込んだと思います。何らかの方法で配列の境界を超えていると思われます。実際に必要なメモリ量の 2 倍を割り当てると、プログラムは期待どおりの結果で終了します。問題は、何が問題を引き起こしているのかを理解できないことです。

アル

並列化のオーバーヘッドを最小限に抑えるために、並列領域内に while を保持しながら、反復プロセスのコードを作成しようとしています。

コードはこのようなものです 問題はそれが決して終了しないことです。可能であれば、これについてのあなたの考えを教えてください

これは難しいので、すべての助けが本当に感謝しています!

NP完全であるため、多項式時間で解決できないことはわかっていますが、分析の助けを求めて、どのタイプのNP完全問題に還元されるか、類似の問題を思い出させます.

話は次のようになります。私はn台のトラックでアイスクリーム トラック ビジネスを所有しています。私が配達を行う停留所はmあります。各場所m _iにはp _i人が私を待っています。アイスクリームを買った後、誰もが去ります。p _iは、アイスクリームを求めて並ぶ人が増えるにつれて、時間とともに増加します。

特定の日の利益を最大化するために、トラックを次にどこに送るかをどのように判断できますか?

注意事項:

• 同じ時間に同じ場所に停車する 2 台のトラックは、1 回だけ利益を得ます。つまり、1 台のトラックが到着すると、人々は立ち去ります。
• トラックはある場所から別の場所に移動するのに時間がかかります
• p _iは各停留所で時間とともに増加しますが、一部の停車地は他の停留所よりも速く増加します。つまり、いくつかの場所はモールの近くにあります (場所、場所、場所)

私はこれを複数マシンのスケジューリング問題、巡回販売員の問題、ILP などに還元しようとしましたが、主な問題は、すべての場所でのp _i (つまり、TSP での距離またはスケジューリング問題での仕事の長さ) が常に増加しています。

前もって感謝します！

これは私の以前の質問(古いトップ コーダーのなぞなぞについて)のフォロー アップです。

数字の文字列が与えられた場合、その文字列が目的の数値に等しくなるために必要な加算の最小数を見つけます。各追加は、数字の文字列のどこかにプラス記号を挿入することと同じです。すべてのプラス記号が挿入されたら、通常どおり合計を評価します。

たとえば、「303」と目標の合計が 6 であるとします。最適な戦略は「3+03」です。

私は（それを証明していませんが）問題はNP完全だと思います。どう思いますか？よく知られている NP 完全問題をこの問題にどのように還元しますか?

これが私がopenCLに変換したいループです。

そして、これが私がこれまでに持っているものですが、それは正しくなく、いくつかのことが欠けていることを私は知っています。

私はこの種のことの完全な初心者です。まず第一に、私はグローバルダブルポインターをopenCLカーネルに渡すことができないことを知っています。可能であれば、解決策を投稿する前に数日ほど待ってください。私はこれを自分で理解したいと思いますが、正しい方向に私を向けるのを手伝っていただければ幸いです。

ウィキペディアのラムダ計算の前任者関数の説明に行き詰まっています。

ウィキペディアには次のように書かれています。

誰かが削減プロセスを段階的に説明できますか?

ありがとう。

いくつかの例を見て、要素の配列を 1 つの要素に減らしましたが、成功しませんでした。誰かがこれを NVIDIA フォーラムに投稿しました。浮動小数点変数から整数に変更しました。

これは正しく見えますか？3 番目の引数「サイズ」は、ローカル ワーク サイズですか、それともグローバル ワーク サイズですか。

私は自分の主張を次のように設定しました。

入力である最初の引数は、その前に起動されたカーネルの出力から保持しようとしています。

今日は、次の cuda リダクションの例を openCL に変換しようと考えています。

より最適化されたものがあります (完全にアンロール + スレッドごとに複数の要素)。

http://developer.download.nvidia.com/compute/cuda/1_1/Website/projects/reduction/doc/reduction.pdf

これはopenCLを使用して可能ですか?

グリズリーは先日こんなアドバイスをくれた

「... n 要素で動作するリダクション カーネルを使用し、それらを n / 16 (またはその他の数値) のようなものに減らします。次に、結果である 1 つの要素になるまで、そのカーネルを繰り返し呼び出します。」

これもやってみたいのですが、どこから始めればいいのかよくわからず、まずは何かを動かしたいです。