0

我正在使用 CUDA 从节点列表构建无向图。每个节点都有一个 3 维坐标，如果节点之间的距离小于某个截止距离 d，我的程序会在两个节点之间创建一条边。

现在我以邻接表的形式存储边缘。问题是，我有 1024 个线程异步计算成对距离。一旦在节点 A 和 B 之间“发现”一条边，我需要增加节点 A 的边数并将节点 B 放在邻接列表中的“下一个可用”位置。

在这里，CUDA 让我做噩梦。我希望邻接列表更新过程至关重要，但 CUDA 似乎没有提供任何超出 atomicAdd() 的功能。结果，每次运行代码时，我都会遇到不可预知的行为和不同的邻接列表。

有没有办法异步创建邻接列表？也许通过更聪明的数据结构？

4

2 回答 2

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），您可以在一个块的线程之间划分一个节点和所有其他节点之间的计算，每个线程计算相等部分的距离。使用__syncthreads()确保确定性。

于 2012-12-10T01:04:37.310 回答
1

您可以用前缀扫描替换 atomicAdd()以产生可重现的结果。或者，您可以在单独的步骤中对结果进行排序。

于 2012-12-09T20:06:06.593 回答