0

私は遺伝的アルゴリズムに取り組んでおり、価値のあるスピードアップを達成できるかどうかを確認するために、いくつかの関数を cuda に入れてみたかったのです。

現時点でのデータ構造はノードのツリーであり、関数ノードには、それらが持つ可能性のある子ノードへのポインターのベクトルが含まれています。このツリーをリンクされたリスト、おそらくノードのベクトル (ポインターではない) に折りたたむ必要があると思います。これらのノードには、子ノードへの整数インデックスのリストが含まれます。このようにして、構造体を cuda に値で渡すことができます。

  root/             (0)
  ├── add           (1)
  │   ├── 5         (2)
  │   └── divide    (3)
  │       ├── 10    (4)
  │       └── 5.7   (5)
  └── multiply      (6)
      ├── 1.2       (7)
      └── 77        (8)

非常に簡単に平坦化できますが、これらの変更を行うにはいくつかのカスタム関数が必要になり、node->childNode[x] スタイル構造よりもはるかに計算コストが高くなる可能性があるのではないかと心配しています。

たとえば、除算とそのサブ構造を数字の 7 に置き換えたい場合は、次のようにする必要があります。

  • ポップメンバー 4,5
  • インデックス 3 の分割を数値 7 に変更します。
  • ルート関数を更新して、2 番目の子への参照が 4 になるようにします。
  • 乗算関数を更新します。現在は 4 です。つまり、子ノードは現在 5 と 6 です。

もっと良い方法があるはずですか？私は C++ の専門家ではないので、アドバイスやコード例を探しています。とても役に立ちます!

4

1 に答える 1

2

テラが言うように、ポインターを配列へのインデックスに置き換えることを除いて、ツリー構造をそのまま維持することをお勧めします。

私が話しているのはどの配列ですか？メモリ プール (別名固定サイズ ブロック アロケータ) を設定する必要があります。これをググることができます。プールは基本的に、ノード タイプが何であれ、その配列です。事前に最大サイズ (ツリーで必要になるノードの最大数) を選択する必要があります。その後、この配列のサイズを変更/拡大する必要はありません。メモリ プール クラスには allocate メソッドと free メソッドがありますが、これらはポインタではなく、配列へのインデックスで動作します。

このアプローチを使用すると、あなたが言及したツリーの変更を非常に安価に行うことができます.メモリプールを使用すると、アイテムの割り当てと削除は非常に安価であり、メモリ内でノードをコピー/移動することは決してありません.

メモリ プールの配列と共に、ツリーのルート (ここでも、ポインタではなく単なるインデックス) を GPU に渡します。

于 2013-04-26T09:30:03.470 に答える