多核CPU-GPU协同的并行深度优先算法.pdf

《多核CPU-GPU协同的并行深度优先算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第31卷第10期计算机应用研究V01．31No．102014年10月ApplicationResearchofComputers0ct．2014多核CPU—GPU协同的并行深度优先算法术余莹，李肯立(1．衡阳师范学院计算机科学系，湖南衡阳421002；2．湖南大学信息科学与工程学院，长沙410082)摘要：针对多核CPU和GPU环境下图的深度优先搜索问题，提出多核CPU中实现并行DFS的新算法，通过有效利用内存带宽来提高性能，且当图增大时优势越明显。在此基础上提出一种混合方法，为DFS每一分支动态地选择

2、最佳的实现：顺序执行；两种不同算法的多核执行；GPU执行。混合算法为每种大小的图提供相对更好的性能，且能避免高直径图上的最坏情况。通过比较多CPU和GPU系统，分析底层架构对DFS性能的影响。实验结果表明，一个高端single．socketGPU系统的DFS执行性能相当于一个高端4：socketCPU系统。关键词：多核CPU；GPU；深度优先搜索；并行；异构中图分类号：TP391．9文献标志码：A文章编号：1001—3695(2014)10—2982—04doi：10．3969／j．issn．1001·

3、3695．2014．10．023Paralleldepthfirstsearchalgorithmonmulticore—CPUandGPUYUYing．LIKen—li(1．Dept．ofCompuperScience，HenyangNormalUniversity，HenyangHunan421002，China；2．ColegeofInformationScience&Enginee—r，HunanUniversity，Changsha410082，China)Abstract：Inorderto

4、solvethedepthfirstsearchonmulti—coreCPUandGPUenvironment，thispaperputforwardakindofparallelDFSalgorithmonmulticoreCPU．Througheffectiveutilizationofmemorybandwidthtoimproveperformance，anden—hanceditsadvantageasthesizeofthegraphincreased．Thenthepaperpropos

5、edahybridmethodwhichofereddynamicalchoicesfromasequentialexecution，twodifferentalgorithmsofmuhi—coreexecution，andaGPUexecution，foreachbranchofDFSbestimplementation．Suchhybridmethodcouldprovidethebestperformanceforeachsizeofthegraph，andavoidedtheworst—cas

6、eperformanceonhigh—diametergraphs．Finally，thepapercomparedthemultipleCPUandGPUsystemstoanalysetheinfluenceoftheunderlyingarchitectureonDFS．Experimentalresultsshowthatahigh—endGPUsystemonDFSperformaswellasaquad—sockethi【gh—endCPUsystem．Keywords：multi—core

7、CPU；GPU；depthfirstsearch(DFS)；parallel；heterogeneous当今多核CPU已广泛应用到高性能计算和消费者电子产种实现，应用了一系列的优化技术，本文在此基础上提出了一品领域，将GPU用于通用计算也成为了目前的热点问题。种类似的实现方法，伪代码如算法1。代码中BitmapV(第3并行(CPU和GPU上的多个线程)和异构(同步使用CPU和行)对访问的节点集进行编码。因为该集合在算法中是最经GPU)的扩展，已经大大提高了许多传统计算密集型工作的性常访问的数据，使用位图

8、数据结构能最小化它的大小，允许缓能。然而，实际上存在一些有效并行计算或异构实现尚未存来保存该集合最大可能的部分。通过使用内在原子操作和被确定而需要快速计算的问题，图搜索就是一个重要的例子。testandtest-and—set操作来最小化位图并行访问的开销。下一图是一个基本的数据表示，广泛应用于很多领域，如情报分分支节点首先存储在每个线程的本地堆栈(LS)中，直到它们析j、机器人j、社会网络分析和计算生物学等。由于这批量插入到全局堆栈。这种