面向Graph500图遍历的存储结构和访存优化研究
发布时间：2021-08-27 05:42
信息技术的进步与发展进一步推动了社会生产力的发展。新兴产业得到了很大的发展,每时每刻各个行业数据量都发生着的巨大变化,数据量的快速增长推动了大数据产业和高性能计算领域的快速发展。图计算方法被广泛的应用到大数据问题的处理中,其中广度优先搜索算法（Breadth First Search,BFS）是图计算中的一个经典问题,也是高性能计算机benchmark Graph500基准测试的核心。BFS算法具有访存数据量大,计算复杂度低等特征,这与大数据问题非常相似;除此之外,由于BFS算法自身重复判断的问题也会导致它的访存不规律,空间局部性差,进一步造成计算机的Cache失效率上升,因此无法达到高时效高性能的要求;并且Graph500测试的生成图的规模巨大,经常会因为计算机内存不足而出现数据越界的问题。为了解决这一系列问题,可以从程序的内存和访存两个方面进行优化,在提高Graph500基准测试程序的计算效率的同时减小程序运行过程中对内存空间的消耗。在内存优化方面,采用压缩生成图变量数据类型的方法使得优化后的生成图能更加适合BFS算法的搜索;在访存优化方面,对生成图数据的格式分配程序进行降位处理,...
【文章来源】：中国科学院大学(中国科学院深圳先进技术研究院)广东省
【文章页数】：64 页
【学位级别】：硕士
【部分图文】：
超级计算机的发展历程及代表
面向Graph500图遍历的存储结构和访存优化研究表2.1Graph500测试基准的7个版本基本信息数据规模scaleedgefacter所需存储空间Toy261617.6128GBMini2916140.6974GBSmall32161.0995TBMedium361617.5922TBLarge391640.7375TBHuge42161.0995EB2.2Graph500测试基准的设计原理Graph500基准测试程序的设计原理是将测试模块与被测试的生成图数据模块分离设计，这种设计满足高内聚低耦合的程序设计要求。Graph500基准测试程序主要分为生成图数据、建立被测数据/建图、BFS搜索验证和数据结果输出4个模块。Graph500基准测试程序流程如图2.1所示。图2.1Graph500基准测试程序流程图生成图数据：Graph500基准测试程序的图生成方式是采用R-MAT（多递归生成器）方法生产一个特殊的张量积克罗内克无向图用于BFS算法搜索，并14
第2章Graph500基准测试程序分析依据设定的图规模（即图的顶点数和边数）来界定图的性质。控制图的规模的参数有两个，分别是scale和edgefactor，其中scale控制图的顶点数，表示生成图的顶点数以2为底的对数；edgefactor用来控制生成图的边数，表示图的顶点数与边数的比值；假如分别用N和M表示生成图顶点数和边数，则生成图的顶点数是N=2，边数是M=edgefactor×N。Graph500基准测试程序中默认scale等于14、edgefactor等于16，即标准条件。图生成算法可以将生成的克罗内科图规约成一系列边的元组信息，图中每个顶点相关联边的存储位置区间从start_edge_index到end_edge_index-1，用于存储边集合的数组长度是end_edge_index-start_edge_index，每条边都是由头顶点head_vertex和尾顶点end_vertex构成。这部分代码在文件generator/graph_generator.c中，代码在OpenMP和CrayXMT上是并行的。建立被测数据：这个模块的主要任务是把边元组信息转换成顺序表（list）和行压缩矩阵（csr）两种不同的图数据结构，这一部分生成后不能被后面的搜索程序改变，这部分内容主要在文件Graph500.c中。这一部分和前面的图生成部分均属于数据的准备部分，下图2.2是Graph500测试基准数据准备流程图。图2.2Graph500测试基准数据准备流程图图中设置图的大小指的是根据不同的机器设置不同的scale值和edgefactor值，以免出现取值太小造成数据精度不足，或者取值太大造成数组越界。BFS遍历及验证：此过程中程序随机选定一个根顶点，以该顶点为源点，对15
【参考文献】：
期刊论文
[1]高性能计算应用驱动发展研究分析[J]. 顾蓓蓓. 科研信息化技术与应用. 2019(04)
[2]基于大数据挖掘的企业智能知识管理与决策的研究[J]. 赵舰波. 经济研究导刊. 2018(15)
[3]高性能计算系统性能评测方法及其应用[J]. 魏敏,孙婧,沈瑜,肖华东,李娟. 应用气象学报. 2013(06)
[4]高性能计算在工业工程领域的应用[J]. 王普勇,丁峻宏. 科研信息化技术与应用. 2012(06)
[5]由具体尝试到抽象分析——欧拉解决哥尼斯堡七桥问题的思路与方法[J]. 赵树智. 中学数学. 1985(07)
博士论文
[1]计算机辅助的酶的底物虚拟筛选和底物生长系统的设计与开发[D]. 姚志强.华东理工大学 2016
硕士论文
[1]面向图搜索的流寄存器文件设计与协同BFS算法优化[D]. 叶帅.国防科学技术大学 2015
本文编号：3365767
【文章来源】：中国科学院大学(中国科学院深圳先进技术研究院)广东省
【文章页数】：64 页
【学位级别】：硕士
【部分图文】：
超级计算机的发展历程及代表
面向Graph500图遍历的存储结构和访存优化研究表2.1Graph500测试基准的7个版本基本信息数据规模scaleedgefacter所需存储空间Toy261617.6128GBMini2916140.6974GBSmall32161.0995TBMedium361617.5922TBLarge391640.7375TBHuge42161.0995EB2.2Graph500测试基准的设计原理Graph500基准测试程序的设计原理是将测试模块与被测试的生成图数据模块分离设计，这种设计满足高内聚低耦合的程序设计要求。Graph500基准测试程序主要分为生成图数据、建立被测数据/建图、BFS搜索验证和数据结果输出4个模块。Graph500基准测试程序流程如图2.1所示。图2.1Graph500基准测试程序流程图生成图数据：Graph500基准测试程序的图生成方式是采用R-MAT（多递归生成器）方法生产一个特殊的张量积克罗内克无向图用于BFS算法搜索，并14
第2章Graph500基准测试程序分析依据设定的图规模（即图的顶点数和边数）来界定图的性质。控制图的规模的参数有两个，分别是scale和edgefactor，其中scale控制图的顶点数，表示生成图的顶点数以2为底的对数；edgefactor用来控制生成图的边数，表示图的顶点数与边数的比值；假如分别用N和M表示生成图顶点数和边数，则生成图的顶点数是N=2，边数是M=edgefactor×N。Graph500基准测试程序中默认scale等于14、edgefactor等于16，即标准条件。图生成算法可以将生成的克罗内科图规约成一系列边的元组信息，图中每个顶点相关联边的存储位置区间从start_edge_index到end_edge_index-1，用于存储边集合的数组长度是end_edge_index-start_edge_index，每条边都是由头顶点head_vertex和尾顶点end_vertex构成。这部分代码在文件generator/graph_generator.c中，代码在OpenMP和CrayXMT上是并行的。建立被测数据：这个模块的主要任务是把边元组信息转换成顺序表（list）和行压缩矩阵（csr）两种不同的图数据结构，这一部分生成后不能被后面的搜索程序改变，这部分内容主要在文件Graph500.c中。这一部分和前面的图生成部分均属于数据的准备部分，下图2.2是Graph500测试基准数据准备流程图。图2.2Graph500测试基准数据准备流程图图中设置图的大小指的是根据不同的机器设置不同的scale值和edgefactor值，以免出现取值太小造成数据精度不足，或者取值太大造成数组越界。BFS遍历及验证：此过程中程序随机选定一个根顶点，以该顶点为源点，对15
【参考文献】：
期刊论文
[1]高性能计算应用驱动发展研究分析[J]. 顾蓓蓓. 科研信息化技术与应用. 2019(04)
[2]基于大数据挖掘的企业智能知识管理与决策的研究[J]. 赵舰波. 经济研究导刊. 2018(15)
[3]高性能计算系统性能评测方法及其应用[J]. 魏敏,孙婧,沈瑜,肖华东,李娟. 应用气象学报. 2013(06)
[4]高性能计算在工业工程领域的应用[J]. 王普勇,丁峻宏. 科研信息化技术与应用. 2012(06)
[5]由具体尝试到抽象分析——欧拉解决哥尼斯堡七桥问题的思路与方法[J]. 赵树智. 中学数学. 1985(07)
博士论文
[1]计算机辅助的酶的底物虚拟筛选和底物生长系统的设计与开发[D]. 姚志强.华东理工大学 2016
硕士论文
[1]面向图搜索的流寄存器文件设计与协同BFS算法优化[D]. 叶帅.国防科学技术大学 2015
本文编号：3365767
本文链接：https://www.wllwen.com/kejilunwen/jisuanjikexuelunwen/3365767.html
