支持多I/O并行的单机大规模图计算系统

论文摘要

图是一种简单直观的数据表现方式,现实世界中的很多问题都可以转化成图,例如社交网络中的用户关系、电子商务应用中的用户评价都可以借助图来表示。很多基于图数据的处理系统也就应运而生,这些都统称为图计算系统。图计算系统大致有分布式图计算和单机图计算这两大类:分布式图计算的思想是,通过增加机器数量以达到分散数据、平衡负载的目的,常用于处理大规模图数据;单机图计算又可细分为单机内存式和单机外存式,分别用于对小规模和大规模数据的处理中,该类图计算系统一般根据服务器性能分配相应数量的线程以提高系统的并发能力,out-of-core技术也被运用到单机外存系统中以解决I/O数据加载问题。在相同资源条件限制下,单机系统往往具有比分布式系统更好的性能,这是因为分布式中多台机器的通信和同步都需要更高代价。在处理大规模数据时,通过增加廉价的外存设备资源以及对并行I/O技术的优化,单机外存系统就能达到不错性能,而无需浪费昂贵的分布式资源。现阶段已有一些针对单机外存系统的研究,例如GraphChi、X-stream、GridGraph。它们大都致力于优化外存数据访问以提高I/O性能,例如X-stream和GridGraph通过保证对外存数据的顺序读写来降低I/O延迟,GridGraph则是通过减少外存数据加载量、粗粒度的提交请求数据来减少I/O访问次数。但它们都疏忽了对内存处理效率的优化,随着I/O性能的提升,内存处理时间会逐渐突出,甚至上升为系统性能瓶颈,而那时它们不再占据优势。本文提出了一个通过并行I/O技术,能够在单机上运行大规模图数据的计算系统,并从计算和I/O加载的协同关系、内存访问方面进行优化,从而解决以上问题。本文提出的异步计算-I/O加载模型真正的让计算和I/O过程并行起来,而不再是GridGraph所用的同步模型的串行执行。在异步模型中,计算和I/O加载过程相对独立,可以根据各自任务的访问需求分配不同线程组,避免了同步模型中统一分配策略造成的I/O线程过量问题,从而达到充分利用内存和I/O带宽的目的;此外,本文系统通过异步I/O引擎LIBAIO不仅提升了外存访问带宽,而且还进一步平衡了各线程在内存中的工作负载;在内存访问方面,本文系统基于NUMA架构进行了优化,通过远端顺序和本地随机相结合的内存访问策略,避免了对远端数据的随机访问,极大的提高了内存访问效率。为了保证对远端数据的顺序访问,在预处理阶段,本文系统需要对图数据按照源点或目的顶点重新排列,为了减少排序开销,本文提出in-memory排序和归并外排相结合的排序策略,从而避免排序对预处理性能的影响。通过实验数据,不难发现,本文系统无论是在I/O性能还是内存访问效率方面都具有显著优势。

论文目录

• 摘要
• abstract
• 第一章 绪论
•   1.1 背景
•   1.2 研究目标
•   1.3 本文工作
•   1.4 论文结构
• 第二章 背景介绍及相关研究
•   2.1 单机图计算系统
•     2.1.1 图计算模型
•     2.1.2 数据加载方法
•   2.2 相关系统及其设计
•     2.2.1 内存图计算系统
•     2.2.2 Out-of-core图计算系统
•   2.3 相关技术
•     2.3.1 并行I/O技术
•     2.3.2 异步引擎LIBAIO
•     2.3.3 NUMA架构
•   2.4 本章小结
• 第三章 Out-of-core图计算系统的问题分析
•   3.1 同步计算-I/O加载模型的问题
•     3.1.1 CPU利用率低
•     3.1.2 带宽利用不充分
•     3.1.3 工作负载不平衡
•     3.1.4 可伸缩性达到瓶颈
•   3.2 NUMA架构下的数据布局问题
•     3.2.1 数据分布不均衡
•     3.2.2 远程访问次数多
•     3.2.3 统一分配不同访问模式数据的问题
•   3.3 机遇
•     3.3.1 计算和I/O加载的异步执行
•     3.3.2 NUMA特性下内存/外存的数据布局优化
•   3.4 本章小结
• 第四章 计算和I/O加载的并行设计
•   4.1 异步计算-I/O加载模型
•     4.1.1 计算和I/O的协同框架
•     4.1.2 新型的生产者消费者算法
•     4.1.3 自适应的I/O线程数量
•   4.2 非阻塞的I/O加载
•     4.2.1 异步I/O加载设计
•     4.2.2 batch机制优化计算任务平衡型
•   4.3 本章小结
• 第五章 内存数据处理和预处理设计
•   5.1 NUMA特性下数据布局优化
•     5.1.1 对不同访问模式数据的布局优化
•     5.1.2 外存数据的布局优化
•   5.2 内存访问策略
•   5.3 图数据预处理方法
•     5.3.1 图数据划分
•     5.3.2 多线程划分
•     5.3.3 In-memory排序和归并外排算法
•   5.4 本章小结
• 第六章 系统重要技术实现
•   6.1 系统主要模型和接口
•   6.2 异步I/O加载实现
•   6.3 双队列同步实现
•   6.4 拓扑数据的存储
•   6.5 本章小结
• 第七章 实验测评
•   7.1 测试环境
•   7.2 测试数据集
•   7.3 运行性能
•   7.4 I/O带宽与延迟
•   7.5 各线程的workload平衡
•   7.6 基于NUMA的内存访问性能
•   7.7 本章小结
• 第八章 总结与展望
•   8.1 工作总结
•   8.2 工作展望
• 参考文献
• 致谢
• 攻读学位期间发表的学术论文

文章来源

类型: 硕士论文

作者: 周晓丽

导师: 陈榕

关键词: 并行,异步

来源: 上海交通大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 上海交通大学

分类号: O157.5

DOI: 10.27307/d.cnki.gsjtu.2019.000916

总页数: 84

文件大小: 1868K

下载量: 16