数据密集型计算并行编程关键技术研究

摘要

数据密集型计算是一种针对海量、分布、异构、变化的数据集进行的并行计算。随着各领域信息化程度的提高，数据规模快速增长，数据密集型计算成为解决海量数据处理问题的主要手段，以数据密集型计算编程模型为主导的并行编程技术成为设计与实现海量数据并行处理算法的重要基础，以MapReduce为代表的数据并行编程模型及相关技术已成为工业界、科学界与计算机学术界共同关注的数据密集型计算并行编程研究热点。
　　虽然数据密集型计算并行编程的理论与技术研究已有多年的发展历史，取得了许多重要的研究成果，有力地推动了数据密集型计算技术的发展与普及，不过在平台架构、通用性与复杂作业处理、多核集群并行化扩展、算法适用性等方面仍然存在诸多问题，需要进一步分析和研究。本文围绕这些问题，对数据密集型计算并行编程技术展开了深入研究，主要研究工作及创新点如下：
　　（1）研究了云计算平台、高性能计算平台和大数据系统的体系结构，提出了一种基于一体化设计方法构建的数据密集型计算平台架构，其中：用户应用层用于部署各类数据密集型应用。应用开发与管理层提供与数据密集型应用开发和运行管理相关的各种服务，主要包括客户端、集成开发与运行环境、作业管理模块。海量数据处理层支持多种编程模型及计算框架，主要包括计算资源管理、计算框架、多计算框架管理、编程模型连接池模块。海量数据存储层负责针对结构化数据与非结构化数据进行合理存储和管理，并提供统一的数据访问接口。系统管理层负责数据密集型计算平台的日常管理与运行维护，主要包括权限管理、用户管理和系统配置模块。基础设施层通过虚拟化技术将各种物理资源转化为虚拟机、虚拟存储、虚拟网络组成的资源池，为上层的海量数据获取、存储与处理服务按需提供资源。
　　（2）在对离线计算框架MapReduce的基本原理、系统结构、工作流程、优势与局限性，以及相关的计算框架（包括迭代式MapReduce计算框架、DAG计算框架和内存计算框架）进行深入分析的基础上，研究了编程模型与计算框架的通用性问题，提出了基于多种编程模型、支持复杂作业处理的通用计算框架（GCF-MPM），可在满足通用性要求的同时，高效处理由多个不同类型计算任务构成的复杂作业。
　　GCF-MPM框架的复杂作业管理与控制层借鉴现有的DAG任务调度模型，采用本文提出的一种基于双排序值的作业调度器（DRJ Scheduler）。GCF-MPM的资源管理与调度层采用本文提出的DL-QoS-SA Scheduler资源调度器。该调度器可对 YARN自带的公平调度器进行合理扩展，使用基于数据本地性服务质量和统计分析方法的作业排序算法（DL-QoS-SA Job Prioritizer）替代原有的Fair策略。GCF-MPM计算框架包含多个基于MRv1开发的数据并行计算子框架，可容易地支持不同类型的编程模型，每一种子框架只负责处理特定类型的计算任务，从而满足了用户对并行编程环境的通用性要求。
　　（3）研究了MRv1计算框架在多核集群上的并行化扩展问题，提出了面向多核集群的MapReduce-TBB混合编程模型。多核集群系统具备强大的节点间并行与节点内并行处理能力，面对集群节点内多核处理器所提供的并行计算资源，现有的数据密集型计算编程模型的并行化扩展能力不足。由于任务级并行编程模型TBB在支持多核平台并行编程方面具有明显优势，本文首先将多核集群中基于MapReduce开发的计算框架并行化扩展问题抽象为面向 CMP-Cluster的MapReduce编程模型并行化扩展问题，然后使用 Hadoop Pipes编程接口将 TBB并行算法模板函数（主要包括 parallel_for和 parallel_reduce）与MapReduce数据处理引擎进行连接，从而提升了 MRv1框架对多核集群上多级并行化资源的利用率。实验结果表明，MapReduce-TBB混合编程模型能够充分利用多核集群节点内多核处理器提供的并行计算资源，为GCF-MPM框架和其他基于MapReduce开发的计算框架在多核集群上实现多级并行化扩展奠定了重要基础。
　　（4）应用GCF-MPM框架与MapReduce-TBB混合编程模型，基于本文提出的数据密集型计算平台架构，设计并实现了一个数据密集型计算并行编程系统（DICPPS）。该系统的主要功能模块包括：客户端管理、作业管理、资源管理、子框架管理、多核任务管理、数据管理和系统管理模块。基于DICPPS系统，本文研究了实现形态学图像处理算法和数字社区商圈划分算法的适用性问题，提出并实现了将业务商圈与自然商圈相结合的综合商圈划分算法。实验结果表明，DICPPS系统不但在处理复杂作业方面具备较高的可用性和通用性，而且在多核集群上也表现出良好的多级并行化处理能力。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 研究背景

1.2 存在问题及研究现状

1.3 研究内容与创新点

1.4 论文结构

2 数据密集型计算平台体系结构研究

2.1 引言

2.2 相关研究进展

2.3 设计原则和设计方法

2.4 体系结构设计

2.5 本章小结

3 数据并行编程模型分析

3.1 引言

3.2 数据并行编程模型的特点

3.3 相关研究工作

3.4 实验与分析

3.5 本章小结

4 支持复杂作业处理的通用计算框架研究

4.1 引言

4.2 支持多种计算框架的通用计算系统研究进展

4.3 通用计算框架总体设计

4.4 资源管理与调度层设计

4.5 复杂作业管理与控制层设计

4.6 实验与分析

4.7 本章小结

5 面向多核集群的编程模型扩展机制研究

5.1 引言

5.2 相关研究进展

5.3 MapReduce-TBB混合编程模型设计

5.4 MRT计算框架设计

5.5 实验与分析

5.6 本章小结

6 原型系统开发与应用实例分析

6.1 DICPPS系统的结构与部署

6.2 DICPPS系统在形态学图像处理中的应用

6.3 DICPPS系统在数字社区商圈划分中的应用

6.4 本章小结

7 总结与展望

7.1 论文总结

7.2 研究工作展望

致谢

参考文献

附录1 攻读博士学位期间发表的论文目录