欢迎光临 x-algo
关注算法在工业界应用
Hi, 这是一个关注大数据算法在工业界应用的网站

GPU矩阵运算和BFS

矩阵稀疏表示

矩阵中有大量的0之后可以考虑使用稀疏表示,稀疏表示的时候可以使用类似邻接表的方式(按招行或者列都可以)存储;具体实现不仅可以使用二维嵌套数组,也可以使用三个一维数组实现,按行存储,三个数组分别存储值、列号、换到第几行。

QQ20170311-1

稀疏矩阵乘法

通过上面的稀疏表示,实现数据矩阵的乘法(一个稀疏矩阵乘以一个向量)就变得很简单,核心就是将这个乘法变为两个向量的对应位置相乘,一个thread负责一行的代码:

QQ20170311-2

这种方式的问题在于,warp执行的过程中出现thread之间工作量不均衡,整个时间有会是执行最久的决定。

所以有另外一种方式,就是每一个element一个thread,求完乘积之后通过segment sum得到最终结果。

Bell & Michael算法

是两种方式的结合,划线的标准是线的左边1/3为0的时候效果最佳。

QQ20170311-4

广度优先搜索

每一条边是一个thread,整个图是一个无向图,可能 会有环。

初始化kernel:

QQ20170311-6

循环kernel

QQ20170311-5

 

未经允许不得转载:大数据算法 » GPU矩阵运算和BFS

评论 抢沙发

*

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注大数据算法在工业界应用

本站的GitHub关于本站