随着计算机科学的发展,当前很多计算机研究领域都需要强大的计算能力对大规模数据进行分析。很多情况下,传统的单处理器串行程序难以在较短时间内解决问题,因此对基于多核处理器的并行化算法的研究已成为热门方向之一。极图指的是满足给定条件的边数最多的图,小规模的极图问题可以通过构造算法有效解决,然而当极图问题规模随着的顶点数增加时,算法执行时间以指数级增长,这时单核机器的计算能力已经难以在较短时间内求解该问题。本文首先对串行极图构造算法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个。