多核环境下面向数据并行编程模型的性能和可伸缩性研究

论文摘要

近10年来对于大规模数据处理的需求变的日益迫切,等待处理的数据如雪崩一般不断增长。据权威咨询公司IDC于2007年统计,截至2006年存储于电子介质中的数据量达到惊人的161艾字节（Exabyte）,并且预计至2010年这一数字将来到998艾字节。毫无疑问数据密集型应用已经成为当今最为重要的计算机应用之一。与此同时,随着多核技术的日益普及,片上核数目的快速增长,多核平台在大规模数据处理领域呈现出极为广阔的应用前景。然而这些以多核形式提供的强大计算能力,只有通过并行程序才能得以充分利用,发挥出与核数目的增长一致的实际效果。高效并行程序的编写历来是困扰程序员的难题,因为除了业务逻辑本身,程序员还必须面对包括数据分布、可伸缩性、负载平衡和系统容错在内的大量与并行性相关的复杂问题。权威调研机构Gartner于2008年列出了未来25年IT市场面临的七大挑战,多核时代的并行编程位居第二。面向数据并行编程模型无疑是这一挑战的最好解答,通过合理的抽象向应用程序员隐藏并行性相关问题,在将业务逻辑开发留给应用程序员的同时,将实现并行的挑战留给并行计算专家。然而现有的面向数据并行编程模型和运行时支持大多针对集群平台设计和实现,并没有充分考虑到多核平台的自身特点,比如高速核间通信、共享缓存竞争和整机故障模型等,因此也就不能有效的利用多核技术带来的强大计算能力。此外,现有的并行编程模型设计更多的关注于通用性而缺乏针对性,限制了模型在某些应用领域和计算需求下的执行效果。本文在深入分析现有MapReduce并行编程模型在多核平台上存在的性能和可伸缩性问题的基础上,提出了一个系统的解决方案。首先以MapReduce模型为基础采用分治策略针对多核平台特点进行扩展,然后基于分治MapReduce模型提出了针对内存占用、缓存局部性和任务并行性三个方面的多个优化,最后以在线聚集计算和增量计算为例分析并验证了分治MapReduce模型对于不同领域和不同需求应用的高效支持。相对于之前的研究而言,该研究致力于设计和实现针对多核平台的面向数据并行编程模型,充分利用资源获得与之相匹配的性能和可伸缩性,并为更多的领域和应用提供高效地支持。具体而言,本文的主要贡献如下：1.从面向数据并行编程模型的角度深入分析多核平台与集群平台间存在的主要差异,并在此基础上揭示了面向集群平台设计的MapReduce并行编程模型在多核平台上存在的主要问题。提出利用分治策略对MapReduce并行编程模型进行扩展,将大型任务分解为多个子任务迭代执行,并改进原有的容错机制,以达到充分适应多核平台特点的目标。2.提出基于分治MapReduce模型,涉及内存、缓存和处理器三个方面的多个运行时优化。采用动态数据加载和缓冲区重用技术减少并缩短内存资源占用,采用面向非一致缓存/内存访问（NUCA/NUMA-aware）的调度策略提高缓存局部性,采用软件流水线技术（Software Pipeline）和任务窃取技术（Work Stealing）消除处理器空闲。3.基于分治MapReduce模型以及相关运行时优化,在多核平台设计并实现了名为Ostrich白勺原型系统。深入评测的结构表明,分治MapReduce模型的接口扩展相对于其它MapReduce模型实现并不会对程序员产生额外负担。其次,在16核Intel处理器构成的测试平台上,Ostrich运行时不但在所有基准测试中都具有更好的可伸缩性,并且在性能测试中节省高达85%的内存,降低3.1倍至7.1倍的缓存缺失率,以及提高整体性能1.2倍至3.3倍。4.利用分治MapReduce模型提供的强大支持,设计并实现了两个针对不同领域和不同计算需求的案例应用。Oops系统实现了对在线聚集计算的支持,能够在执行过程中向用户反馈当前进度下的近似结果,并能够高效地支持多级在线计算。Ostrichlnc系统提出在子任务级别实现计算复用,实现了对严格增量计算和部分增量计算的高效支持。评测结果表明,分治MapReduce模型在保持原有通用性的前提下,对多种不同领域和不同需求的应用能够提供高效支持。

论文目录

• 目录
• 摘要
• Abstract
• 第一章 绪论
• 1.1 多核平台
• 1.2 面向数据并行编程模型
• 1.2.1 面向数据并行编程模型
• 1.2.2 多核平台带来的挑战
• 1.3 相关研究
• 1.3.1 多核平台
• 1.3.2 面向数据并行编程模型
• 1.4 本文的主要贡献
• 1.4.1 之前研究工作的不足
• 1.4.2 本文的主要贡献
• 1.5 本文结构安排
• 第二章 基于分治策略的MapReduce模型扩展
• 2.1 背景知识
• 2.1.1 MapReduce并行编程模型
• 2.1.2 Phoenix多核运行时环境
• 2.1.3 分治策略
• 2.2 MapReduce模型在多核平台上存在的主要问题
• 2.3 分治MapReduce并行编程模型
• 2.3.1 模型设计
• 2.3.2 运行时实现
• 2.3.3 执行流程
• 2.3.4 容错支持
• 2.4 小结
• 第三章 分治MapReduce模型的运行时优化
• 3.1 内存负载优化
• 3.1.1 现有实现分析
• 3.1.2 输入缓冲区重用技术
• 3.2 缓存局部性优化
• 3.2.1 现有实现分析
• 3.2.2 背景知识
• 3.2.3 面向非一致缓存/内存访问调度器
• 3.3 任务并行性优化
• 3.3.1 现有实现分析
• 3.3.2 软件流水线技术
• 3.3.3 任务窃取调度
• 3.4 小结
• 第四章 分治MapReduce模型和实现的评测
• 4.1 评测环境和方法
• 4.1.1 评测环境
• 4.1.2 测试用例
• 4.2 易用性评测
• 4.3 性能和可伸缩性评测
• 4.3.1 整体性能
• 4.3.2 可伸缩性
• 4.3.3 内存资源消耗
• 4.3.4 缓存局部性
• 4.3.5 任务并行性
• 4.4 容错技术评测
• 4.4.1 性能开销
• 4.4.2 存储开销
• 4.4.3 容错恢复
• 4.5 小结
• 第五章 分治MapReduce模型对应用的支持
• 5.1 案例一:在线聚集计算
• 5.1.1 在线聚集计算简介
• 5.1.2 HOP在线聚集系统
• 5.1.3 Oops在线聚集系统
• 5.1.4 评测
• 5.2 案例二:增量计算
• 5.2.1 增量计算简介
• 5.2.2 DryadInc增量计算系统
• 5.2.3 OstrichInc增量计算系统
• 5.2.4 评测
• 5.3 小结
• 第六章 总结与展望
• 6.1 工作总结
• 6.2 工作展望
• 6.2.1 软件栈各层优化支持
• 6.2.2 虚拟化环境优化研究
• 6.2.3 异构平台支持研究
• 6.2.4 更多应用领域和计算需求的支持
• 参考文献
• 发表文章目录
• 致谢