论文部分内容阅读
当前,科学与工程计算中大规模数据处理的需求与日俱增。与此同时,高性能并行机的发展和硬件价格的下降使得高性能机器得到了广泛推广,与之相伴的是各种并行编程模式和并行编程语言的纷纷出现,并行计算的发展为各学科带来福音的同时也带来了一系列的问题。并行机体系结构以及并行编程语言和模式的多样性为并行应用的开发带来了极大的困难,增加了普通程序员的编程难度。因此,简化并行编程,提高并行程序开发效率就成为了一个关键的问题。
很多并行编程模型和语言抽象层次太低,导致程序员要关心很多底层实现细节。而MapReduce模式具有高层次的抽象,在MapReduce运行时系统的支持下程序员只需要关注对具体数据的处理,以及数据相关性的处理,极大的降低了并行程序的开发难度。但是除了网络搜索领域外,如何使用MapReduce对其它领域(尤其是数值计算领域)的具体应用进行设计与分析还没有系统、详细的研究和阐述。为此,本文围绕这些环节展开研究工作,具体研究工作与成果如下:
第一,研究了并行算法空间中由任务组织、由数据分解组织和由数据流组织这几种并行问题组织原则与MapReduce模式的关系,综合MapReduce模式以及几种原则的特性,给出了如何用MapReduce对这几种不同原则描述的问题进行表述。
第二,将任务分解、分治策路、流水线等并行问题分析模式与MapReduce模式相结合,用MapReduce来描述这些并行模型,并且对每个模式中出现的典型应用或算法进行分析。并通过对MapReduce在这些模式上的应用和对具体应用的分析,给出了使用MapReduce模式分析问题的步骤及方法。
第三,提出了在用MapReduce模式解决问题时所用到的关键数据结构,一方面是输入数据的表示,其中包括输入数据和输入数据的特征,并结合矩阵数据划分的分析过程,给出了数据结构的设计要点和方法。另一方面,分析了key值的作用,研究了key值与MPI中通信模式的关系,给出了选择和设计key值的原则。
第四,将MapReduce引入数值计算领域,在HPMR上研究了数值计算的应用。使用MapReduce模式在HPMR上设计和实现了以矩阵计算为典型代表的若干数值计算应用,包括矩阵的LU分解与QR分解。在对具体问题的实现和分析过程中研究了使用MapReduce的步骤和各种数据结构的设计,体现了这种模式的简洁性和易用性。
实验测试表明,在HPMR上运用我们所提出的方法和步骤使用MapReduce模式来分析和解决有关并行计算问题有着很好的简洁性和易用性,且具有良好的运行时性能。