面向多核可伸缩的MapReduce库的研究

摘要

并行编程是有效利用多核资源的重要方式。然而，传统的并行编程模型要求程序员手动管理诸多的并发细节，使得并行编程变得困难且易错。MapReduce编程模型通过自动管理并发任务，简化并行编程。Phoenix是MapReduce模型在多核系统上的一种实现，它证明了应用程序通过使用MapReduce能够获得与Pthreads相媲美的性能。但是，Phoenix的可伸缩性较差。
　　本文旨在分析影响Phoenix可伸缩性的关键因素，然后设计并实现一个具有较好可伸缩性的MapReduce库SMR。本文的主要贡献为:
　　(1)通过实验测试以及使用Linux Perf等性能分析工具，深入分析影响Phoenix可伸缩性与性能的关键因素。Phoenix因Pthreads线程对共享地址空间的竞争导致其较差的可伸缩性，因map和reduce阶段间存在同步屏障影响性能。
　　(2)利用课题组已有的新型线程模型Sthread，设计并实现一个Phoenix接口兼容且具有较好可伸缩性的MapReduce库SMR。SMR通过避免多个线程对共享地址空间的竞争，提升系统的可伸缩性;通过让map和reduce阶段间的无阻塞流水线并行，提升系统的性能。
　　(3)在一台32核机器上使用Phoenix测试程序对SMR和Phoenix进行性能评估，还分析了近年来Linux内核的优化对多核MapReduce库可伸缩性与性能的影响。实验结果表明，基于SMR运行的五个测试用例都具有较好的可伸缩性和性能。32核CPU下，SMR相比Phoenix的性能提升为9.0倍～26.7倍。Linux内核的优化能够有效提升Phoenix的执行效率，而对于SMR的影响较小。
　　(4)为了高效支持迭代型MapReduce应用，本文初步设计并实现了面向多核可伸缩的迭代式MapReduce库iSMR。SMR因每次迭代计算都需要重复地创建和销毁环境，浪费大量的时间，致使其无法高效地支持迭代型应用。iSMR只在处理流程的开始和结束时创建和销毁环境，并且它采用线程池复用线程，以提升迭代型应用的处理效率。
　　本文提出的SMR为程序员提供了一种简单高效的方式使用多核资源。此外，本文关于多核MapReduce库可伸缩性的分析，对其他Pthreads程序的分析具有指导意义;关于近年来Linux内核优化的分析，对Linux的相关研究工作具有参考价值。

目录

声明

摘要

第1章 绪论

1．1 研究背景

1．2 相关工作

1．2．1 面向集群MapReduce的发展现状

1．2．2 多核MapReduce的相关研究

1．2．3 多核可伸缩性的相关研究

1．3 研究内容

1．4 论文组织

第2章 基础知识与问题分析

2．1 Phoenix

2．1．1 执行流程与编程接口

2．1．2 中间结构的设计

2．1．3 可伸缩性评估

2．1．4 Phoenix局限性总结

2．2 Phoenix较差可伸缩性的分析

2．2．1 Linux进程地址空间的组织

2．2．2 多线程对共享地址空间的竞争

2．2．3 线程睡眠唤醒的开销

2．3 已有减少地址空间竞争的方案

2．3．1 地址空间的重新组织

2．3．2 锁的优化

2．3．3 VMA cache机制的改进

2．4 本章小结

第3章 基于新型线程模型Sthread设计并实现SMR

3．1 概述

3．2 新型线程模型Sthread

3．2．1 Sthread及其编程接口

3．2．2 无边界通道与重映射机制

3．2．3 Sthread的特点与优势

3．3 SMR的设计与实现

3．3．1 SMR运行时系统

3．3．2 无阻塞的流水线并行

3．3．3 Sthread隔离地址空间为SMR带来编程挑战

3．4 SMR中间结构的设计与优化

3．4．1 map私有中间结构的设计与实现

3．4．2 中间结构的底层实现

3．4．3 底层实现的优化

3．5 本章小结

第4章 实验评估

4．1 测试环境与数据集

4．2 SMR的性能与可伸缩性的评估

4．2．1 性能评估

4．2．2 可伸缩性评估

4．3 评估影响SMR性能的因素

4．3．1 缓存优化对性能的影响

4．3．2 开启combiner对性能的影响

4．3．3 SMR较高的初始化时间

4．4 Linux内核版本对多核MapReduce库性能的影响

4．4．1 内核优化对多核MapReduce库的影响评估

4．4．2 最新内核版本下多核MapReduce库的性能评估

4．5 本章小结

第5章 面向多核可伸缩的迭代式MapReduce的探究

5．1 研究背景

5．2 Sthread实现迭代式MapReduce库的局限性和挑战

5．3 iSMR的设计与实现

5．3．1 混合线程模型PMthreads

5．3．2 线程池的设计和iSMR的实现

5．4 本章小节

第6章 结束语

参考文献

致谢

在读期间发表的学术论文与取得的研究成果