首页 > 图书中心 >图书详情

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

前沿性、系统性、可读性 深入专题研究领域的阶梯 进入交叉学科的桥梁 启迪研发创新的源泉

作者:章明星
定价:89
印次:1-1
ISBN:9787302542537
出版日期:2020.05.01
印刷日期:2020.04.15

由于具有良好的表达能力,图数据结构被广泛用来对元素间具有复杂联系的数据进行建模,如社交网络、知识图谱等。因此,可以对大规模图数据进行分析的处理技术逐渐成为当前学术界和业界的热门研究话题之一。目前,已有为数众多的图计算系统被提出和应用,并取得了巨大的商业成功。本书通过将不同环境下图计算系统的数据载入途径分为四个阶段分别进行了研究,总结出了一系列的优化方法,可为相关研究人员提供参考。

more >

导师序言 由于具有良好的表达能力,图数据结构被广泛用来对元素间具有复杂联系的数据进行建模。因此,可以对大规模图数据进行分析的处理技术逐渐成为当前学术界和业界的热门研究课题。已有为数众多的图计算系统被提出和应用,并取得了巨大的商业成功。在前人的基础上,本书作者章明星博士持续创新,通过不断地优化图数据在各种不同场景下的载入速度,在多个方向上都取得了重要成果,并在 OSDI、ASPLOS、VLDB、ATC、HPCA、ICS等国际高水平会议上发表了多篇论文。此外他的博士学位论文还获评 ACM SIGSOFT杰出论文,清华大学优秀博士学位论文,北京市优秀博士学位论文, IEEE TCSC卓越奖(优秀博士学位论文)。 更重要的是,章明星博士在研究图计算这一领域的过程中总结出了一整套的系统优化方法。他通过深入分析,根据图计算本身具有数据局部性差、单个点 /边的计算开销小的特点,发现其性能的主要瓶颈在于图数据的载入。基于这一发现,章明星博士将不同场景下的图计算优化统一成一套一致的优化思路,即将整个分布式系统想象成一个多阶的体系结构 (Cache/PIM→内存 →磁盘 /网络 ),然后通过优化每两层之间的局部性来提升整体的运行效率。通过这一思路,在并行图计算、单机内存图计算、单机外存图计算、存算融合加速等多个场景下进行了针对载入瓶颈的细致优化,因而都取得了较大的性能提升。 本书首先描述了现有的图计算系统主要基于一些简单化假设实现这一现象,如点权不可分割、单个计算操作可以孤立地执行等,因此很难达到下层硬件所能支持的最高计算效率。为解决这一问题,作者通过分析发现图计算的主要效率瓶颈在于数据载入速度,于是将不同环境下图计算系统的数据载入途径分为四个阶段分别进行了研究。其主要创新成果包括:①提出了一种三维图计算应用任务划分方法。该方法基于数据图中点权可进一步划分这一发现,最高可以减少 90.6%的通讯量,达成 4.7倍的提速。这一成果发表于 OSDI 2016,为该会议上并列首篇以国内大学为第一单位且有国内大学教师署名的论文。②提出了一种分层的图数据组织格式。通过在外存设备上分层存储图数据,最高可达 6.4倍的加速比。③提出了一种矩阵图计算引擎的自动优化算法。该算法主要基于循环融合优化的原理,并同时考虑了分布式环境下关于数据一致性的要求,最高可将原程序加速 5.8倍。④提出了一种针对新型存算融合器件的图计算模型。针对存算融合这一全新的支持直接在内存器件上进行计算的体系结构,提出了与之相适配的新型图计算模型,最高可以减少近 95%的通讯量。 摘要 由于具有良好的表达能力,图数据结构被广泛用来对元素间具有复杂联系的数据进行建模,如社交网络、知识图谱等。随着信息化技术的迭代更新和互联网应用的蓬勃发展,可以对大规模图数据进行分析的处理技术逐渐成为当前学术界和业界的热门研究课题之一。已有为数众多的图计算系统被提出和应用,并取得了巨大的商业成功。 然而,现有的图计算系统主要基于一些简单化假设实现,如点权不可分割、单个计算操作可以孤立地执行等,因此很难达到下层硬件所能支持的最高计算效率。为解决这一问题,本书通过分析,发现大量图计算应用的主要效率瓶颈在于数据载入速度,于是将不同环境下图计算系统的数据载入途径分为四个方面分别进行了研究。本书的主要创新成果如下。 (1)提出了一种三维图计算应用任务划分方法。该方法基于数据图中点权可进一步划分这一发现,拓展了一个全新的任务划分维度。与传统的一维和二维划分方法不同,三维划分方法允许将数据图中的点进一步划分为子点,并分配给不同的计算节点。测试结果显示,三维划分方法最高可以减少 90.6%的通讯量,从而达成提升整体运行效率的目的。 (2)提出了一种分层的图数据组织格式。通过在外存设备上分层存储图数据,计算系统可以一次性载入更多的点,从而降低单个点重复读取的次数,达到提高计算效率的目的。测试表明基于这一设计实现的新型外存图计算系统比已有系统有明显的性能提升,最高可达 6.4倍的加速比。 (3)提出了一种矩阵图计算引擎的自动优化算法。该算法主要基于循环融合优化的原理,并同时考虑了分布式环境下数据一致性的要求。在保证计算正确性的同时,该算法可以通过自动流水线化的方法提升图计算应用 的数据局部性,从而减少内存带宽压力。实验表明该方法最高可将原程序加速 5.8倍。 (4)提出了一种针对新型存算融合器件的图计算模型。针对存算融合这一全新的支持直接在内存器件上进行计算的体系结构,提出了与之相适配的新型图计算模型。该模型通过限定用户的编程接口,使得自动的通讯去冗余成为可能。并进一步提出了基于广播树的更新传播算法,可以有效减少瓶颈链路上的通讯量。计算结果显示,上述两种方法最高可以减少近 95%的通讯量。 关键词:图计算;分布式计算;矩阵计算;局部性; PIM Abstract Due to its good expressivity, graph has been widely used to model the relationship among data elements. As a result, many large-scale graph processing systems have been proposed and deployed in the real world, and have achieved great successes. The optimization for these systems is also a hot research topic in both the academic and industry. However, the current implementation of graph processing systems are typically based on certain simplification assumptions, such as “vertex is indivisible” and “each compute operation can be executed isolatedly”, and hence cannot achieve the best performance that the hardware can deliver. To resolve this problem, we investigate the field and found that the bottleneck of most graph applications is the speed of loading data. Based on this observation, we partition the load path of graph data into four stages and propose optimizations for them respectively. The main innovations of this book are as follows. (1) We design a novel 3D graph partition algorithm. This algorithm is based on the fact that the vertex property of many graph applications is actually divisible. Through exploring this novel dimension that have never been considered by existing methods, our algorithm can reduce up to 90.6% of the original communication cost. (2) We define a layered graph organization format. This format enables the processing system to load more vertices at a time, and hence reduce the average loading times of each vertex. As a result, our method can decrease total disk I/O for out-of-the-core graph processing systems and leads to up to a 6.4 times speedup. (3) We propose an automatic optimization algorithm for matrix execution engine. This algorithm is mainly based on loop fusion and has also considered the consistency requirement of a distributed environment. It is able to assure the correctness, and simultaneously, achieve a speedup up to 5.8 times. (4) We implement a process-in-memory-oriented graph processing framework. By enforcing certain constraints in the programming model, our framework makes it possible to automatically remove redundancy in the communication. It also provides a broadcast-based optimization that reduce communication load on bottleneck links. According to our calculation, it can reduce the communication cost to as low as only 5% of the original. Key words: graph computing; distributed computing; matrix computing; locality; PIM

more >
扫描二维码
下载APP了解更多

同系列产品more >

基于确定性现金流的财务危机预警模型...

谭智佳
定 价:79元

查看详情
狄拉克半金属的能带调控和超快动力...

鲍昌华
定 价:79元

查看详情
记者马克思

黄斐
定 价:89元

查看详情
介电常数近零媒质的集成光学掺杂理...

周子恒
定 价:79元

查看详情
风险感知、制度压力与基层干部社会...

程佳旭
定 价:79元

查看详情
图书分类全部图书
more >
  • “清华大学优秀博士学位论文丛书”(以下简称“优博丛书”)精选自2014年以来入选的清华大学校级优秀博士学位论文(Top 5%)。每篇论文经作者进一步修改、充实并增加导师序言后,以专著形式呈现在读者面前。“优博丛书”选题范围涉及自然科学和人文社会科学各主要领域,覆盖清华大学开设的全部一级学科,代表了清华大学各学科最优秀的博士学位论文的水平,反映了相关领域最新的科研进展,具有较强的前沿性、系统性和可读性,是广大博硕士研究生开题及撰写学位论文的必备参考,也是科研人员快速和系统了解某一细分领域发展概况、最新进展以及创新思路的有效途径。
  • “清华大学优秀博士学位论文丛书”(以下简称“优博丛书”)精选自2014年以来入选的清华大学校级优秀博士学位论文(Top 5%)。每篇论文经作者进一步修改、充实并增加导师序言后,以专著形式呈现在读者面前。“优博丛书”选题范围涉及自然科学和人文社会科学各主要领域,覆盖清华大学开设的全部一级学科,代表了清华大学各学科最优秀的博士学位论文的水平,反映了相关领域最新的科研进展,具有较强的前沿性、系统性和可读性,是广大博硕士研究生开题及撰写学位论文的必备参考,也是科研人员快速和系统了解某一细分领域发展概况、最新进展以及创新思路的有效途径。
more >
  • 目录

    第 1章引言 .......................................................................................1 

    1.1大规模图计算 .........................................................................1 

    1.2图计算系统的分类 ...................................................................2 

    1.3图数据高效计算的挑战 ............................................................5 

    1.3.1图计算的特点 ...............................................................6 

    1.3.2现状和主要优化方向 .....................................................7 

    1.4主要贡献 ................................................................................9 

    1.5本书组织结构 ....................................................................... 11

    第 2章相...

精彩书评more >

标题

评论

版权所有(C)2023 清华大学出版社有限公司 京ICP备10035462号 京公网安备11010802042911号

联系我们 | 网站地图 | 法律声明 | 友情链接 | 盗版举报 | 人才招聘