伴随着“大数据时代”的深入以及互联网技术、云计算技术和智能设备的普及,全球数据量每年将以40%的速度增长,到2020年将达到35ZB(Zettabyte),大数据将迎来ZB时代。传统以追求计算速度为主要衡量指标的单机计算模式,正在向支持非结构化的、松耦合的分布式并行处理模式转变。其中,分布式并行编程模型是并行处理中的一个重要研究课题。MapReduce因其大规模的并行处理能力、简洁的编程模型、良好的可扩展性、容错性、易用性、以及高性价比等显著特征已成为目前最具影响力的分布式并行编程模型的代表。相比于传统只能处理关系型结构的数据库管理系统,MapReduce编程模型对处理非结构化数据的支持满足了大多数应用的需求。然而,面对数据不断涌现的新特点和多样化需求,MapReduce编程模型仍存在较大的优化空间,特别是在并行处理时的数据划分不均衡问题和平均执行执行效率低的问题是制约其发展的最大阻碍。因此,针对MapReduce编程模型的并行优化技术研究,已成为推动其不断发展的核心动力。本文针对上述两个优化问题进行了深入的分析与研究,提出了一系列通用性、有效性、稳定性的优化方法,具体而言,本文的主要研究内容和创新点可以概括为以下四点:1)针对MapReduce编程模型数据划分不均衡的问题,提出一种高效的增量式分区选择、分配方法。提出一种将分区向Reducer指派时按照多轮分配的分区策略。该方法首先在Map端产生多于Reducer个数的细粒度分区,同时在Mapper运行过程中实时统计各细粒度分区的数据量;然后由JobTracker根据全局的分区分布信息筛选出部分未分配的细粒度分区,并用代价评估模型将选中的细粒度分区分配到各Reducer上;依照此方法,经过多轮的筛选、分配,最终在执行Reduce函数前,将所有细粒度分区分配到Reduce端,以此达到各Reducer接收数据总量均衡的目的。2)针对创新点1中增量式分区分配方法无法根据数据分布特点自适应选择分区的问题,提出一种动态自适应的分区选择、分配优化方法,用于解决MapReduce编程模型中数据划分不均衡的问题。创新点1中的增量式分区方法在分区选择时采用的是等分原则,即每轮分配分区的个数相同;然而,由于数据分布的多样性,等分原则不能解决数据分布集中的问题,因此提出一种自适应的增量式分区优化方法。该方法将整个分区分配过程描述为一个完整的马尔可夫决策过程,首先建立分区的代价评估模型;然后在每轮分区选择时,选取能够取得收益最大的分区集合进行分配;接着,同样按照增量式的分配原则,经过多轮的筛选、分配,最终在执行Reduce函数前,将所有细粒度分区分配到Reduce端,以此解决增量式分区方法的自适应性问题,从而实现各Reducer接收数据的均衡性。最后在Zipf分布数据集和真实数据集上与现有的切分分区策略进行对比,增量式分区策略更好地解决了数据划分后的不均衡问题。3)针对在MapReduce编程框架下,基于多元切分方法的极大完全图并行枚举算法中,仍存在子图切分不均衡和平均执行效率低的问题,提出一种以二元切分方法进行极大完全图并行枚举的优化技术。该方法通过迭代的二元切分方式将数据图进行分区操作(Partition),同时,在切分过程中实现对子图的枚举。与以往工作的主要不同处是该方法在计算中进行迭代式的剪值,从而实现搜索的高效性和切分的均衡性。同时,为验证算法性能,分别实现单机算法和并行算法。对于单机算法,主要解决快速剪值问题,即高效性;对于MapReduce并行算法,除实现高效性外,还考虑各节点执行过程中的均衡性。最后,通过随机生成数据和真实数据,与经典方法进行对比,实验表明基于二元切分的并行枚举算法具有更高的执行效率。4)针对极大近似完全图并行枚举算法中存在的图切分不均衡和执行效率低的问题,将创新点3中的二元切分方法进行推广,提出适用于搜索空间更大、计算过程更复杂的近似完全图并行枚举优化方法。该方法以二元切分的方式对子图进行并行枚举,通过在搜索过程中计算,在计算中剪枝的方式,实现高效枚举。同时,针对不同规模的近似完全图,通过单机和并行环境,验证该方法在真实数据集和生成数据集上的执行效率。实验表明,与经典极大近似完全图枚举算法相比,基于二元切分方法的近似完全图并行枚举算法在搜索空间和运行时间都有性能的提升。