基于多核的Ramsey数算法研究

发布时间：2017-11-20 20:08

  本文关键词：基于多核的Ramsey数算法研究

  更多相关文章： 并行计算 MapReduce Phoenix++ Ramsey数

【摘要】：随着大数据时代的到来,传统的数据处理方式已经无法满足越来越大的计算需求。按照处理器超线程和多核化的发展趋势,基于集群的分布式编程和基于多核的多线程并发编程已经成为提升计算性能的两个最重要的途径。(Google公司提出了一种能够并发处理海量数据的并行编程模型MapReduce,可用于处理数据密集型任务。目前,已经有多种不同的MapReduce模型的具体实现,其中基于多核共享存储的Phoenix++系统的执行效率较高。 图的Ramsey数在信息论和理论计算机科学中有重要的应用,但是确定它的准确值是NP困难问题。在研究Ramsey数时,随着图的顶点个数的增加,需要考虑的着色情况会以指数级增加。由于计算量的急剧增大,利用单核CPU的计算机难以在较短时间内求解出该问题。因此,本文对基于多核共享存储的Ramsey数求解算法进行研究。 首先对MapReduce编程模型的原理与执行过程、MapRedu ce模型的不同实现和基于多核的MapReduce模型的Phoenix++系统进行了详细介绍。然后设计了单核CPU下的圈集对完全图的Ramsey数求解算法,并采取数据预处理、合理的任务划分以及键值对设计等措施将其改进为基于Phoenix++系统的多核并行算法。通过试验对并行算法的正确性进行了验证,并对其性能进行了评估。试验结果表明,在4核CPU平台上,随着顶点数的增加,该并行算法的加速比最高达到了3.70,执行效率相应增大到92.50%。最后,利用该多核并行算法分别计算R(C≤n),Kn+1)(4≤n≤13)以及R(C≤n, Kn+2)(4≤n≤12)的上下界,从而确定了他们的准确值。
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP311.13;TP332

【参考文献】

中国期刊全文数据库 前7条

1 许进,张雷;DNA计算机原理、进展及难点(Ⅰ):生物计算系统及其在图论中的应用[J];计算机学报;2003年01期

2 陈国良;孙广中;徐云;吕敏;;并行算法研究方法学[J];计算机学报;2008年09期

3 李雨生;通讯频道的Shannon容量,图的Ramsey数和Erd銉s的一个猜想[J];科学通报;2001年18期

4 臧冬松;霍菁;梁栋;孙功星;;基于MapReduce的高能物理数据分析系统[J];计算机工程;2014年02期

5 王永贵;李鸿绪;宋晓;;MapReduce模型下的模糊C均值算法研究[J];计算机工程;2014年10期

6 代亮;许宏科;陈婷;钱超;梁殿鹏;;基于MapReduce的最小二乘支持向量机回归模型[J];计算机应用研究;2015年04期

7 李芳;关于程序正确性证明的进一步探讨[J];信息技术与信息化;2005年04期

，

本文编号：1208345