大规模图计算系统关键技术研究

发布时间：2018-10-26 11:46

【摘要】：最近十年,随着信息与通信技术的蓬勃发展,人类社会步入了大数据时代。每时每刻,海量的信息都正在被生成,并累积为“数据金矿”。在这些海量的数据当中,实际上,许多的各种类型的信息可以很自然地被抽象为图结构数据,例如,社交网络图,网页链接图,消费者-产品关系图等,从而相应的实际问题可以很自然地转换为图计算问题。最近几年,随着图结构数据的规模越来越大,高效地分析和处理大规模图结构数据能够带来越来越显著的科研、经济以及社会效益,大规模图计算问题正受到学术界和工业界的广泛关注。大规模图计算问题涉及到图算法、存储以及计算等方面,作为一名计算机系统结构研究者,我们主要关注计算与存储。以系统结构研究者的视角来看,高能效的大规模图计算系统本质上主要包含两方面挑战:如何高效地处理图数据,如何高效地存储和快速地访问图数据。对于第一个方面的挑战,我们提出了 StreamGraphChi和Mernmaid两个系统,旨在提升基于磁盘的单机大规模图计算系统性能。由于摩尔定律和缩放定律逐渐失效,“异构计算”正愈发受到青睐。我们提出了 TuNao,旨在利用图计算专用硬件促进大规模图结构数据的高能效处理。对于第二个方面的挑战,我们主要以图数据库中常用的“哈希查找表”数据结构为切入点,提出了 FAHT,旨在加速数据库的查询性能。具体地,我们主要做了如下工作:· StreamGraphChi:基于“边为中心”流处理的单机大规模图计算系统。在本工作中,我们设计并实现了新的图计算编程框架和执行引擎,遵循“边为中心”图计算模式,支持流式地访问磁盘并避免了产生大量中间临时数据。并且,针对计算平台物理内存容量限制和输入数据集规模大小,我们实现了 IM-StreamGraphChi和OM-StreamGraphChi两类执行引擎,依据现实世界大规模图数据所具有的“长尾”特征,系统能自适应地选择合适的执行引擎处理输入图结构数据。StreamGraphChi旨在进一步提升磁盘带宽利用率和减少磁盘访问量,进而促进图计算系统性能提升。· Mermaid:基于混合计算模式的单机大规模图计算系统。以“顶点为中心”和以“边为中心”是两种常见的图计算模式。在本工作中,我们分析了这两种计算模式的优缺点,得到“顶点为中心”模式适用于度高的顶点而“边为中心”模式适用于度低的顶点的结论。现实世界大规模图结构数据的顶点度的分布常呈现出“长尾”现象,已有的图计算系统常使用其中一种计算模式,未能有效发掘“长尾”特性。因此,我们在IM-StreamGraphChi引擎的基础上,重新设计图结构数据的表示方法、编程框架和执行引擎,使得两种图计算模式巧妙整合到一起,充分利用“长尾”特性提升系统性能。· TuNao:高能效的可重构图计算加速器。当前,采用定制化硬件加速器来提升特定领域应用处理的能效已获得学术界和工业界的普遍认可。幸运地,现实世界大规模图结构数据处理遵循类似的计算框架,使得设计大规模图计算硬件加速器成为可能。本工作中,在采用现有内存存储技术的前提下,我们主要围绕访存、计算和适用性三方面进行设计,并充分利用现实世界图结构数据特性。在访存方面,尽可能减少随机访问,尽可能利用数据局部性,减少片外访存。在计算方面,尽可能采用流水线技术,提高并行性。在适用性方面,采用可重构技术以适应不同的图计算应用。· FAHT:快速近似哈希查找表。哈希查找表是一种常见的数据结构,被广泛运用于需要依据关键字快速查询与其相匹配的数据值的应用中,包括图数据库等。传统哈希表中,查询操作过程与“关键字”相关的开销,主要包括存储开销、访问开销和计算开销。哈希表中“关键字”存在的目的,主要是为了确保哈希查询操作所返回的结果总是正确的。随着哈希表的规模扩大,以及在一些哈希关键字比较大的场景下,由关键字带来的这些开销不容忽视。一些工作提出,哈希表表项中只存储数据值而不存储关键字将能明显提升查询性能。当然,这意味着难以确保查询操作总能返回正确的结果。在现实世界中,不少应用是能够容忍一定错误率的。因此,我们重新设计哈希查找表动态插入、动态删除和查找算法,并采用双层存储结构,期望在提升查询性能的同时尽可能地减少查询错误发生概率。同时,我们对FAHT所需的存储空间大小和查询操作错误发生的概率进行理论分析,并给出了相应的计算公式。理论分析和模拟实验表明,FAHT明显优于已有工作。
[Abstract]:......
【学位授予单位】：中国科学技术大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：TP311.13

【相似文献】