【优博微展2017】章明星：大规模图数据的高效计算关键技术研究

章明星：2017年清华大学优秀博士学位论文一等奖获得者

大规模图数据的高效计算关键技术研究

Research on Efficient Large-scale Graph Data Processing Technologies

作    者：章明星

指导教师：武永卫

培养院系：计算机系

学    科：计算机科学与技术

读博感言：图计算真是博大精深！

研究背景/选题意义/研究价值

由于具有良好的表达能力，图数据结构被广泛用来对元素间具有复杂联系的数据进行建模。而随着信息化技术的更新和互联网应用的发展，进行图计算时输入的数据规模越来越大。因此，可以对大规模图数据进行分析的处理技术逐渐成为当前学术界和工业界的热门研究话题之一。已有为数众多的图计算系统被提出和应用，并取得了巨大的商业成功。

主要研究内容

现有图计算系统基于一些简单化假设实现，如“点权不可分割”、“单个计算操作可以孤立地执行”等，因此很难达到下层硬件所能⽀持的最⾼计算效率。为解决这一问题，本文通过分析，发现图计算应用的主要效率瓶颈在于数据载入速度。因此，本文将不同环境下图计算系统的数据载入途径分为网络传输、磁盘读取、内存计算和PIM计算等四个不同的阶段，并分别进行了研究优化。

三围划分利用点权可分的特点拓展了一个新的划分维度。可以减少重的通讯量

矩阵操作的自动融合可以通过流水线的方式极大地减少对内存的访问，从而提升程序的局部性。

主要创新点

1、 提出了一种三维图计算应用任务划分方法。该方法基于数据图中点权可进一步划分这一发现，拓展了一个全新的任务划分维度。测试结果显示，三维划分方法最高可以减少 90.6%的通讯量。

2、 提出了一种矩阵图计算引擎的自动优化算法。该算法可以通过自动流水线化的方法提升图计算应用的数据局部性，最高可将原程序加速 5.8 倍。

3、 针对存算融合这一全新的支持直接在内存器件上进行计算的体系结构，提出了与之相适配的新型图计算模型，最高可以减少近20 倍的通讯量。

代表性学术发表

1、 Exploring the hidden dimension in graph processing. OSDI ‘16

2、 Measuring and optimizing distributed array programs. VLDB ‘16

3、 AI: A Lightweight System for Tolerating Concurrency Bugs. FSE ’14  获颁 ACM SIGSOFT Distinguished Paper Award.

编辑：研究生院  周明坤