论文部分内容阅读
MapReduce是支持数据并行的简单有效的编程模型,它最初为集群编程而设计。随着多核处理器的日益普及,研制面向多核的MapReduce编程库以充分利用多核单机系统的计算资源也变得十分重要。现有的面向多核的MapReduce库,如Phoenix等,大都使用Pthreads库在CPU核间分派任务,依靠共享内存进行任务间通信。由于线程交织运行的不确定性,当Reduce函数不可交换时,会导致基于这些库的MapReduce应用在执行时产生不确定的、甚至是错误的行为。本文旨在设计和实现一个确定的面向多核的MapReduce库,它不仅保证MapReduce应用程序确定地并行执行,而且具有好的性能。本文的主要贡献如下：(1)用确定的消息传递多线程编程库DetMP设计实现了与Phoenix编程接口兼容的、确定的MapReduce库DMR。为保证并行的确定性,DMR采用静态划分确定地将任务指派给各个Map和Reduce线程；并利用DetMP使线程之间缺省地内存隔离,只能通过显式声明的确定性通道进行通信。为提升并行执行的性能,对DMR进行了一些优化,包括面向应用的调度等。(2)基于DMR的开发以及用DetMP改写Pthreads程序dedup的经验,总结了DetMP的可编程性和编程规则。DetMP适合编写具有流水线并行的应用程序。利用DetMP简单的通道编程接口,程序员无须管理线程间数据流的存储和并发访问细节,简化了编程。但是,DetMP不能支持个别Phoenix应用中出现的堆共享等特征,DMR针对此扩展了Phoenix应用编程接口并给出了相应的实现对策。(3)在32核机器上对DMR进行性能评估,并分析DetMP的不同实现机制对程序性能的影响。本文使用Phoenix测试程序集评估Phoenix和DMR的性能,实验表明,DMR仅在kmeans上性能略差,而在其余6个程序上有与Pthreads相当或者更优的性能。原有的DetMP实现是建立在确定的共享内存模型SPMC之上,本文进一步用Pthreads共享内存实现DetMP接口,以考核内存模型对程序性能的影响。通过用7个Phoenix程序和改写的dedup进行测试,实验表明,当CPU核数为16和32时,基于SPMC的实现在除matrix-multiply和string-match的6个程序上有更好的性能,比基于Pthreads的实现最多快9.5倍,而在matrix-multiply和string-match上或者核数低于16时,两种实现的性能相当。