云环境下面向大规模图数据处理的资源优化机制研究

The graph processing applications, such as Social Network analysis and Semantic Web analysis, are increasing popular in these years. Many cloud-computing-based graph computation frameworks have been developed to handle the massive graph data. The recent works mainly focus on the designs and the optimization techniques of the frameworks, but few of them optimize the underlining resource allocation that may significantly impact computation efficiency. The goal of our project is to improve the efficiency of graph computation through optimizing the resource allocation. The optimization mechanisms are based on the virtualization techniques, aiming to minimize the resource requirement and optimize the resource allocation and the resource re-allocation processes. Specifically, a personalized graph partition algorithm will be proposed, which tries to reduce the resource requirement; a topology-aware virtual resource allocation mechanism will be studied, which optimizes the resource allocation when initializing the graph applications; a resource requirement prediction technique for graph computation will be investigated, which extracts the pattern of the dynamic resource requirement; and a resource-pattern-aware re-allocation technique will be proposed, which adjusts the allocation of the virtual resource on-line when the graph applications are performing. With the theoretical solutions, a cloud-computing-based graph computation framework utilizing the resource optimization techniques will be developed, applying the theoretical solutions to the real-world environment. In conclusion, our project accelerates the graph processing applications by the proposed resource-optimization theories and techniques.

随着社交网络分析、语义Web分析等新兴应用的快速发展，基于云环境实现大规模图数据的快速高效处理成为研究热点。现有工作主要关注于提供图数据处理基本执行框架及相关优化机制，没有考虑资源分配对图数据处理执行性能的影响，难以实现应用的高效执行。为此本项目以提高大规模图数据处理执行性能为目标，基于虚拟化技术，分别从资源需求优化、资源初始分配优化及资源运行时优化入手，对云环境下大规模图数据处理资源优化关键技术进行深入研究：研究个性化图数据划分算法，通过对图数据的有效划分以减少执行所需资源；研究基于拓扑感知的虚拟资源高效分配机制，以优化资源初始放置；研究图应用执行模式抽取与预测机制，并针对应用动态运行时资源优化问题，研究执行模式感知的虚拟机在线调整及优化机制，为图应用高效执行提供资源保障。在此基础上基于实际云环境开发支持资源优化的大规模图数据处理原型系统，为图处理应用快速、高效执行提供理论和技术支撑。

本项目针对面向大规模图数据处理的资源优化面临的三个新的挑战，重点研究了云环境下大规模图数据处理的资源优化关键技术，构建了支持资源优化的大规模图数据处理原型系统，实现了大规模图数据的快速高效处理。具体地，在理论研究方面，项目组提出了面向资源需求的图数据个性化划分机制、基于拓扑感知的虚拟资源高效分配机制、大规模图数据执行模式抽取与预测机制、虚拟机在线迁移及带宽动态分配机制等技术；在系统开发与平台搭建方面，基于项目理论研究成果，开发了支持资源优化的大规模图数据处理原型系统，分别从资源需求优化，资源初始分配优化及资源动态运行时优化三方面入手，对底层资源分配过程进行全面优化，提高了图数据处理应用的执行性能。在项目执行期内，项目组在包括JSAC、TPDS、TSC、WWWJ、ICPP、CLUSTER等在内的国际国内重要期刊和会议上共发表和录用高质量论文39篇，申请/授权国家发明专利14项，申报软件著作权1项，培养了一批在云计算和大数据方向具有创新能力的优秀青年人才。推动了面向大规模图数据处理的资源优化以及云计算等相关领域的技术发展，圆满完成了预期目标。此外，项目组还将研究成果成功应用到电子商务与智能制造领域，通过促进科研、技术与社会产业融合，取得了显著的社会和经济效益。相关成果还将广泛应用到互联网、社交网络、电子商务及生物计算等大规模图数据分析应用中，进一步推动我国大数据分析挖掘领域的技术发展，为国家经济建设服务。