多核CPU-GPU协同的并行深度优先算法-计算机应用研究.PDF

第３１卷第１０期 计 算 机 应 用 研 究 Ｖｏｌ．３１Ｎｏ．１０ 　 　 ２０１４年１０月　 ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓ Ｏｃｔ．２０１４ 多核 ＣＰＵＧＰＵ协同的并行深度优先算法 １ ２ 余　莹 ，李肯立 （１．衡阳师范学院 计算机科学系，湖南 衡阳 ４２１００２；２．湖南大学 信息科学与工程学院，长沙 ４１００８２） 摘　要：针对多核ＣＰＵ和ＧＰＵ环境下图的深度优先搜索问题，提出多核 ＣＰＵ中实现并行 ＤＦＳ的新算法，通过 有效利用内存带宽来提高性能，且当图增大时优势越明显。在此基础上提出一种混合方法，为ＤＦＳ每一分支动 态地选择最佳的实现：顺序执行；两种不同算法的多核执行；ＧＰＵ执行。混合算法为每种大小的图提供相对更好 的性能，且能避免高直径图上的最坏情况。通过比较多ＣＰＵ和ＧＰＵ系统，分析底层架构对ＤＦＳ性能的影响。实 验结果表明，一个高端ｓｉｎｇｌｅｓｏｃｋｅｔＧＰＵ系统的ＤＦＳ执行性能相当于一个高端４ｓｏｃｋｅｔＣＰＵ系统。 关键词：多核ＣＰＵ；ＧＰＵ；深度优先搜索；并行；异构 中图分类号：ＴＰ３９１．９　　　文献标志码：Ａ　　　文章编号：１００１３６９５（２０１４）１０２９８２０４ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１３６９５．２０１４．１０．０２３ ＰａｒａｌｌｅｌｄｅｐｔｈｆｉｒｓｔｓｅａｒｃｈａｌｇｏｒｉｔｈｍｏｎｍｕｌｔｉｃｏｒｅＣＰＵａｎｄＧＰＵ １ ２ ＹＵＹｉｎｇ，ＬＩＫｅｎｌｉ （１．Ｄｅｐｔ．ｏｆＣｏｍｐｕｐｅｒＳｃｉｅｎｃｅ，ＨｅｎｙａｎｇＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，ＨｅｎｙａｎｇＨｕｎａｎ４２１００２，Ｃｈｉｎａ；２．ＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅ＆Ｅｎｇｉｎｅｅ ｒｉｎｇ，ＨｕｎａｎＵｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｓｈａ４１００８２，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：ＩｎｏｒｄｅｒｔｏｓｏｌｖｅｔｈｅｄｅｐｔｈｆｉｒｓｔｓｅａｒｃｈｏｎｍｕｌｔｉｃｏｒｅＣＰＵａｎｄＧＰＵｅｎｖｉｒｏｎｍｅｎｔ，ｔｈｉｓｐａｐｅｒｐｕｔｆｏｒｗａｒｄａｋｉｎｄｏｆ ｐａｒａｌｌｅｌＤＦＳａｌｇｏｒｉｔｈｍｏｎｍｕｌｔｉｃｏｒｅＣＰＵ．Ｔｈｒｏｕｇｈｅｆｆｅｃｔｉｖｅｕｔｉｌｉｚａｔｉｏｎｏｆｍｅｍｏｒｙｂａｎｄｗｉｄｔｈｔｏｉｍｐｒｏｖｅｐｅｒｆｏｒｍａｎｃｅ，ａｎｄｅｎ ｈａｎｃｅｄｉｔｓａｄｖａｎｔａｇｅａｓｔｈｅｓｉｚｅｏｆｔｈｅｇｒａｐｈｉｎｃｒｅａｓｅｄ．Ｔｈｅｎｔｈｅｐａｐｅｒｐｒｏｐｏｓｅｄａｈｙｂｒｉｄｍｅｔｈｏｄｗｈｉｃｈｏｆｆｅｒｅｄｄｙｎａｍｉｃａｌ ｃｈｏｉｃｅｓｆｒｏｍａｓｅｑｕｅｎｔｉａｌｅｘｅｃｕｔｉｏｎ，ｔｗｏｄｉｆｆｅｒｅｎｔａｌｇｏｒｉｔｈｍｓｏｆｍｕｌｔｉｃｏｒｅｅｘｅｃｕｔｉｏｎ，ａｎｄａＧＰＵｅｘｅｃｕｔｉｏｎ，ｆｏｒｅａｃｈｂｒａｎｃｈｏｆ ＤＦＳｂｅｓｔｉｍｐｌｅｍｅｎｔａｔｉｏｎ．Ｓｕｃｈｈｙｂｒｉｄｍｅｔｈｏｄｃｏｕｌｄｐｒｏｖｉｄｅｔｈｅｂｅｓｔｐｅｒｆｏｒｍａｎｃｅｆｏｒｅａｃｈｓｉｚｅｏｆｔｈｅｇｒａｐｈ，ａｎｄａｖｏｉｄｅｄｔｈｅ ｗｏｒｓｔｃａｓｅｐｅｒｆｏｒｍａｎｃｅｏｎｈｉｇｈｄｉａｍｅｔｅｒｇｒａｐｈｓ．Ｆｉｎａｌｌｙ，ｔｈｅｐａｐｅｒｃｏｍｐａｒｅｄｔｈｅｍｕｌｔｉｐｌｅＣＰＵａｎｄＧＰＵｓｙｓｔｅｍｓｔｏａｎａｌｙｓｅ ｔｈｅｉｎｆｌｕｅｎｃｅｏｆｔｈｅｕｎｄｅｒｌｙｉｎｇａｒｃｈｉｔｅｃｔｕｒｅｏｎＤＦＳ．Ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓ