导师序言

由于具有良好的表达能力，图数据结构被广泛用来对元素间具有复杂联系的数据进行建模。因此，可以对大规模图数据进行分析的处理技术逐渐成为当前学术界和业界的热门研究课题。已有为数众多的图计算系统被提出和应用，并取得了巨大的商业成功。在前人的基础上，本书作者章明星博士持续创新，通过不断地优化图数据在各种不同场景下的载入速度，在多个方向上都取得了重要成果，并在OSDI、ASPLOS、VLDB、ATC、HPCA、ICS等国际高水平会议上发表了多篇论文。此外他的博士学位论文还获评ACM SIGSOFT杰出论文，清华大学优秀博士学位论文，北京市优秀博士学位论文，IEEE TCSC卓越奖（优秀博士学位论文）。

更重要的是，章明星博士在研究图计算这一领域的过程中总结出了一整套的系统优化方法。他通过深入分析，根据图计算本身具有数据局部性差、单个点／边的计算开销小的特点，发现其性能的主要瓶颈在于图数据的载入。基于这一发现，章明星博士将不同场景下的图计算优化统一成一套一致的优化思路，即将整个分布式系统想象成一个多阶的体系结构（Cache/PIM→内存→磁盘／网络），然后通过优化每两层之间的局部性来提升整体的运行效率。通过这一思路，在并行图计算、单机内存图计算、单机外存图计算、存算融合加速等多个场景下进行了针对载入瓶颈的细致优化，因而都取得了较大的性能提升。

本书首先描述了现有的图计算系统主要基于一些简单化假设实现这一现象，如点权不可分割、单个计算操作可以孤立地执行等，因此很难达到下层硬件所能支持的最高计算效率。为解决这一问题，作者通过分析发现图计算的主要效率瓶颈在于数据载入速度，于是将不同环境下图计算系统的数据载入途径分为四个阶段分别进行了研究。其主要创新成果包括：①提出了一种三维图计算应用任务划分方法。该方法基于数据图中点权可进一步划分这一发现，最高可以减少90.6%的通讯量，达成4.7倍的提速。这一成果发表于OSDI 2016，为该会议上并列首篇以国内大学为第一单位且有国内大学教师署名的论文。②提出了一种分层的图数据组织格式。通过在外存设备上分层存储图数据，最高可达6.4倍的加速比。③提出了一种矩阵图计算引擎的自动优化算法。该算法主要基于循环融合优化的原理，并同时考虑了分布式环境下关于数据一致性的要求，最高可将原程序加速5.8倍。④提出了一种针对新型存算融合器件的图计算模型。针对存算融合这一全新的支持直接在内存器件上进行计算的体系结构，提出了与之相适配的新型图计算模型，最高可以减少近95%的通讯量。