有没有将图形映射到CUDA编程块上的有效方法？

在并行计算中，通常是将原始问题分解为子任务并将其映射到块和线程上的第一步。有没有将图形映射到CUDA编程块上的有效方法？

对于具有常规数据结构的问题，这是很容易且有效的，例如，矩阵乘法，FFT等。

但图形理论问题，如最短路径，图的遍历，树搜索，有不规则的数据结构。至少在我看来，使用GPU分割问题到块和线程似乎并不容易。

我想知道是否有这种分区有效的解决方案？

为简单起见，取单源最短路径问题作为一个例子。我被困在如何划分图形，使地方和凝聚。

来源

2012-04-01 konjac

这是一个很广泛的问题，这将是非常难以回答。你有没有特别的应用？你能否改进你所问的范围？ – talonmies 2012-04-01 09:08:50

你能否多说一下你正在寻找的算法的应用领域？我可以在最近邻居搜索中分享经验，但我无法帮助如果您询问生成树搜索等一些常见图形问题... – geek 2012-04-01 17:47:58

@ marina.k我不是在单源最短路径问题上工作。首先，如果在多核系统中实现Dijkstra算法似乎很难。其次，如果使用类似于Dijkstra算法的迭代解决方案，由于节点之间的约束非常复杂且不规则，因此很难保证局部性和合并性，即使使用共享内存来缓存。 – konjac 2012-04-03 05:12:04

树数据结构旨在最佳地优化顺序进展方式。在树状搜索中，由于每个状态都高度依赖于以前的状态，我认为并行化树上的遍历并不是最优的。

至于图形而言，每个连接的节点都可以被平行分析，但我想有可能是冗余操作为重叠的路径。

来源

2012-04-03 03:08:12

你可以使用MapGraph，它使用GAS方法来处理所有你提到的事情......他们也有一些相同的实现和库，包括收集，应用和分散GPU和CPU的cuda实现。

您可以在这里找到最新版本：http://sourceforge.net/projects/mpgraph/files/0.3.3/

来源

2015-06-18 08:51:35

有没有将图形映射到CUDA编程块上的有效方法？

回答

相关问题