0

CUDA を使用して、ノードのリストから無向グラフを作成しています。各ノードには 3 次元の座標があり、ノードがカットオフ距離 d 未満で分離されている場合、私のプログラムは 2 つのノード間にエッジを作成します。

現在、エッジを隣接リストの形式で保存しています。問題は、ペアごとの距離を非同期で計算する 1024 のスレッドがあることです。ノード A と B の間でエッジが「発見」されたら、ノード A のエッジの数を増やし、ノード B を隣接リストの「次に利用可能な」位置に配置する必要があります。

ここで、CUDA は私に悪夢を与えています。adjacency-list-update プロセスを重要にしたいのですが、CUDA は atomicAdd() 以外のものを提供していないようです。その結果、コードを実行するたびに、予期しない動作と異なる隣接リストが表示されます。

隣接リストを非同期的に作成する方法はありますか? おそらく、より巧妙なデータ構造を介してですか？

4

2 に答える 2

1

atomicAdd（）をプレフィックススキャンに置き換えて、再現性のある結果を得ることができます。または、別の手順で結果を並べ替えることもできます。

于 2012-12-09T20:06:06.593 に答える
1

ノードの数が十分に多い場合は、1 つのスレッドを 1 つのノードにマップするので、各ノードは他のすべてのノードまでの距離を計算し、プライベート隣接リストに格納します。その場合、計算の順序が定義されている場合 (ノード リストの順序付けによって行われること)、不確定性は発生しません。いくつかのコード:

for(int i = 0; i < listOfNodes.length(); i++)
    if(dist(listOfNodes[threadId], listOfNodes[i]) < cutoffDist) {
        int n = adjacencyLists_sizes[threadId]++;
        adjacencyLists[threadId][n-1] = listOfNodes[i];
    }

ノードの数が十分に大きくない場合(CUDAを使用していると思います)、1つのブロックのスレッド間で1つのノードと他のすべてのノードの間で計算を分割できます。各スレッドは距離の等しい部分を計算します。を使用__syncthreads()すると、決定性が保証されます。

于 2012-12-10T01:04:37.310 に答える