CUDA编程——图的表示及BFS算法

2023-09-25 8 0

CUDA编程——图的表示及BFS算法

  • 图的表示
  • BFS on CUDA

最近根据老板要求,在学习CUDA编程,昨天看了一篇很久之前的论文,《Accelerating large graph algorithms on the GPU using CUDA》,说是第一篇介绍CUDA图形算法的论文,主要包括BFS, SSSP和APSP在GPU编程中的实现过程。今天写这篇博客复盘一下。

图的表示

在一般的编程中,我们常用G(V,Z)来表示一个图,这一点在CUDA编程中并没有本质上的改变,我们常用邻接矩阵或者邻接表来表示图中的结点之间的连接关系,但是由于邻接矩阵对于稀疏图的表示存在很大的空间浪费,所以一般很常用邻接表。在CUDA中我们依然使用邻接表来表示图,但与之前我们熟悉的邻接表有所不同。之前我们熟悉的邻接表,每个结点都会有一个自己的链表,但在CUDA编程中,我们以紧凑的邻接表形式表示图,并将邻接表打包成一个大数组。 每个顶点都指向这个边的阵列中自己邻接表的开始位置。 图G(V,E)的顶点表示为数组Va。邻接列表的另一个数组Ea在V中所有的顶点的邻接表起始位置之后存储顶点连接的其他结点。 阵列Va对应于其Ea中的邻接表的起始索引。 Ea的每个条目都代表顶点阵列Va中的一个顶点。如下图:
在这里插入图片描述
在这个图中,0号结点分别于8、6结点之间有边连接,2号结点只与9号结点之间有边连接,以此类推,用两个数组和一些指针表示了邻接表。

BFS on CUDA

我们使用级别同步解决BFS问题。BFS遍历图, 一旦访问了一级(level),就不会再次访问它。 BFS frontier(边界)对应于当前级别正在处理的所有节点。 在执行BFS期间,我们不会为每个顶点维护一个队列,因为它将在维护内核的每个级别上产生维护新数组索引和更改网格配置的额外开销。 这减慢了CUDA模型的执行速度。

我们为每个顶点分配一个线程。 创建两个大小分别为 |V| 的布尔数组,分别为了存储Frontier和Visited,命名为Fa和Xa,用于存储BFS边界和受访顶点。 另一个整数数组,cost,Ca,存储源顶点S中每个顶点的最小边数。在每次迭代中,每个顶点都在边界数组Fa中查看其条目。若Fa中对应值为true,就从Ca中获取其cost,并使用边列表Ea更新邻居的所有成本(如果其cost超过自身cost加一个cost)。顶点从边界数组Fa中删除其自己的条目,并将其添加到访问数组Xa中。 如果还没有访问邻节点,它也会将其邻节点添加到边界数组中。 重复此过程,直到边界为空。

这段话不太好理解,有一段伪代码可以帮助我们更好的理解这个过程:
在这里插入图片描述
Algorithm1是CPU端的代码,Algorithm2是GPU端的kernel函数。

代码编程
赞赏

相关文章

【C】浅析 #define 宏和函数的区别
【C】浅析 关键字
【C】库函数之 sqrt
【C】折半(二分)查找
fio_generate_plots
【Linux】进程的调度算法