你好,游客 登录 注册 发布搜索
背景:
阅读新闻

[CAJ]基于多核的极图构造并行算法研究

[日期:2014-08-13] 来源:北京交通大学   作者:郑瑞君 [字体: ]

基于多核的极图构造并行算法研究

北京交通大学  郑瑞君

本文首先对串行极图构造算法FCG的可并行化部分进行了系统分析,然后实现了基于OpenMP的并行极图构造算法FCG-MP。在深入研究MapReduce并行编程模型的基础上,利用多核平台Phoenix实现了基于MapReduce的极图构造的并行算法FCG_Phoenix。并对算法进行了性能优化:通过增加任务标识符对不同Map的执行结果进行区分,避免了结果冲突;通过合理分配任务数据使系统的负载更加均衡。最后通过构造小顶点的极图进行了对比试验,结果表明FCG_Phoenix的执行效率要远好于FCG-MP。为验证算法的有效性,本文利用FCG_Phoenix在8核服务器上构造了不超过28个顶点且不含六边形的极图集合。通过与单处理器算法FCG的试验结果进行对比,本文设计的多核并行算法的平均加速比为7.043,平均执行效率为88.04%。其中,当顶点数为21时结果集中图的规模达到最大,共有7,856,799个图;此时,算法FCG_Phoenix的性能也达到了最优,执行效率达到88.92%。最后,利用算法FCG Phoenix构造出了不超过29个顶点的不含六边形的所有极图,结果表明29个顶点不含六边形的图的边数最多为72,且这样的图共有3个。


基于多核的极图构造并行算法研究

收藏 推荐 打印 | 录入:574107552 | 阅读:
相关新闻       并行计算 极图 MapReduce Phoenix 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数
点评:
       
评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款