论文部分内容阅读
随着大数据时代的到来,传统的数据处理方式已经无法满足越来越大的计算需求。按照处理器超线程和多核化的发展趋势,基于集群的分布式编程和基于多核的多线程并发编程已经成为提升计算性能的两个最重要的途径。(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)的上下界,从而确定了他们的准确值。