检索结果-南通市图书馆

计算机工程与科学 2022年第2期44卷 191-198页

作者：白皓甘新标杨文祥贾孟涵涂旭平张一鸣郭敏来乐张意朱春平国防科技大学计算机学院湖南长沙410073 中国空气动力研究与发展中心计算空气动力研究所四川绵阳621000 黄冈师范学院计算机学院湖北黄冈438000 中国人民解放军66061部队北京100144

近年来,图计算在诸多领域发挥着越来越重要的作用。连通分量算法是图计算的重要基础算法,可以应用于可达性查询、一致性检测等众多场景。面向大规模图遍历graph500标准测试,对连通分量算法进行了算法和数据结构优化。主要有以下创新:(1... 详细信息

近年来,图计算在诸多领域发挥着越来越重要的作用。连通分量算法是图计算的重要基础算法,可以应用于可达性查询、一致性检测等众多场景。面向大规模图遍历graph500标准测试,对连通分量算法进行了算法和数据结构优化。主要有以下创新:(1)对并查集提出了捷径向量算法,并测试了算法和数据结构的配合程度;(2)利用多线程迭代轮转对算法实现并行加速;(3)从多个维度比较了不同实现方法的优缺点。基于优化方法,对性能进行了评估分析,当scale=25(包含2^(25)个节点)时,捷径向量算法对基于二维向量和链表的按秩合并算法的加速比分别是1.38倍和1.40倍,对BFS和DFS的加速比分别为4.76倍和4.70倍,且空间占用为该2个算法的4.1%~4.6%,此外,并行对串行的加速比为1.57倍。

关键词：图计算图遍历连通分量算法 graph500 捷径向量算法

在线全文

学校读者我要写书评

暂无评论

面向高通量计算机的图算法优化技术

计算机研究与发展 2020年第6期57卷 1152-1163页

作者：张承龙曹华伟王国波郝沁汾张洋叶笑春范东睿计算机体系结构国家重点实验室(中国科学院计算技术研究所) 北京100190 中国科学院大学计算机与控制学院北京100049

随着互联网技术的蓬勃发展,图数据的规模呈爆炸式增长.如何高效地处理大规模图数据逐渐成为工业界和学术界关注的焦点.宽度优先搜索算法是解决图遍历问题的经典算法,也是graph500基准的核心测试程序之一.高通量计算机采用ARM架构的众核... 详细信息

随着互联网技术的蓬勃发展,图数据的规模呈爆炸式增长.如何高效地处理大规模图数据逐渐成为工业界和学术界关注的焦点.宽度优先搜索算法是解决图遍历问题的经典算法,也是graph500基准的核心测试程序之一.高通量计算机采用ARM架构的众核体系结构,具有高并发、强实时、低功耗等适于大数据计算的特点.在单节点上,BFS算法的优化已取得一系列进展,首先对现有的优化技术进行系统的介绍,并在此基础上提出2种面向高通量计算机的优化手段,通过减少冗余访存和提高缓存局部性,有效提高了算法的访存效率.通过这些优化手段,在高通量计算机上对BFS算法的性能进行了系统的评估.对于顶点规模为230的Kronecker图(顶点数为230,边数为234),优化后的BFS算法在高通量计算机上的平均性能为24.26 GTEPS.与两路x86架构服务器相比,单节点具有1.18倍的性能优势.在性能功耗比方面,高通量计算机的结果为181.04 MTEPS W.在2019年6月份的Green graph500面向大数据集的排行榜上取得第2名的成绩.综上,高通量计算机的高并发和低功耗等特点非常适合处理大规模图计算等数据密集型应用.

关键词：宽度优先搜索高通量 graph500 图算法超算

在线全文

学校读者我要写书评

暂无评论

基于双向位图的CSR大规模图存储优化

计算机研究与发展 2021年第3期58卷 458-466页

作者：甘新标谭雯刘杰国防科技大学计算机学院长沙430017

大数据时代,graph500是评测超级计算机处理数据密集型应用能力的重要工具,E级验证系统的图遍历处理能力主要受限于内存空间和访存带宽,尤其是内存空间利用率直接决定了图的测试规模和测试性能.针对天河E级验证系统小内存特征,提出了基... 详细信息

大数据时代,graph500是评测超级计算机处理数据密集型应用能力的重要工具,E级验证系统的图遍历处理能力主要受限于内存空间和访存带宽,尤其是内存空间利用率直接决定了图的测试规模和测试性能.针对天河E级验证系统小内存特征,提出了基于双向位图的大规模图数据压缩存储方法(bidirectional-bitmap based CSR,Bi-CSR),Bi-CSR在CSR矩阵压缩的基础上引入行方向位图和列方向位图协同完成稀疏矩阵压缩存储,行方向位图主要负责行方向位图的压缩存储与索引,列方向位图除了进一步压缩图存储空间,还负责为顶点遍历向量并行优化提供加速空间.Bi-CSR大幅度减少了稀疏矩阵存储空间.面向天河E级验证系统,当图输入规模为237时,graph500的图存储空间节约效率接近70%,全系统稳定测试性能为2.131E+12TEPS,性能最大加速比超过100倍.

关键词： graph500 双向位图稀疏矩阵压缩存储图遍历天河E级验证系统

在线全文

学校读者我要写书评

暂无评论

高通量计算机的图算法优化技术研究

无线互联科技 2022年第4期19卷 68-69页

作者：贾子昂北方工业大学电气与控制工程学院北京100144

高通量计算机具有高并发、强实时、低功耗等适于大数据计算特点,在单节点上,BFS算法的优化已取得一系列进展。文章对BFS算法的性能进行了系统的评估,优化后的BFS算法在高通量计算机上评价性能为24.26 GTEPS和两路X86构建服务器相比,单... 详细信息

高通量计算机具有高并发、强实时、低功耗等适于大数据计算特点,在单节点上,BFS算法的优化已取得一系列进展。文章对BFS算法的性能进行了系统的评估,优化后的BFS算法在高通量计算机上评价性能为24.26 GTEPS和两路X86构建服务器相比,单节点更具性能优势。

关键词：宽度优先搜索高通量 graph500 图算法

在线全文

学校读者我要写书评

暂无评论

E级计算之远景

科技导报 2016年第21期34卷 85-94页

作者：邓越凡张黎浩美国纽约州立石溪大学美国纽约11794 山东科学院国家超级计算济南中心济南250101 中山大学数据科学与计算机学院广州510006

超级计算机在当今科技发展中占有举足轻重的地位。在向着E级计算时代迈进之时,精确衡量超算的性能是一个事关超算架构和应用的关键问题。评价一台超算采用不同的基准会产生不同的结果。本文介绍超算中主要的3种排名及其对应的评测基准,... 详细信息

超级计算机在当今科技发展中占有举足轻重的地位。在向着E级计算时代迈进之时,精确衡量超算的性能是一个事关超算架构和应用的关键问题。评价一台超算采用不同的基准会产生不同的结果。本文介绍超算中主要的3种排名及其对应的评测基准,并分析了超算本身的发展及应用远景。

关键词：超级计算机戈登贝尔奖 Top500 Green500 graph500 太湖之光天河二号

并行原型系统上BFS算法设计实现与测试分析

在线全文

学校读者我要写书评

暂无评论

计算机工程与科学 2017年第1期39卷 27-34页

作者：衡冬冬唐玉华易晓东刘向阳周侗国防科学技术大学计算机学院湖南长沙410073

相对于传统应用,大数据应用表现出并行性高、访存数据量大、访存模式不规则、程序访存时空局部性差等特性,对传统的计算机体系结构提出了新的挑战。graph500是评测计算机系统大数据处理能力的基准测试排名,BFS算法是graph500的核心程序... 详细信息

相对于传统应用,大数据应用表现出并行性高、访存数据量大、访存模式不规则、程序访存时空局部性差等特性,对传统的计算机体系结构提出了新的挑战。graph500是评测计算机系统大数据处理能力的基准测试排名,BFS算法是graph500的核心程序,是典型的数据密集型应用。从1-D数据划分、优化的混合算法设计和远程通信方式设计三个方面开展研究,在课题组设计的大数据处理并行结构原型系统上设计实现了多节点的并行BFS算法,在222顶点、226边的数据规模下取得了803.8MTEPS的性能,并在此基础上进行多节点并行BFS算法的性能测试分析,为进一步的研究工作奠定了基础。

关键词：大数据处理 graph500 并行BFS 并行结构原型系统性能测试分析

在线全文

学校读者我要写书评

暂无评论

面向多种体系结构的BFS算法研究

面向多种体系结构的BFS算法研究

作者：彭紫微国防科技大学

学位级别：硕士

广度优先搜索（BFS）是许多图形应用程序的底层内核算法,如社交网络,医疗信息学,传输系统等。因此,它已被吸收为graph500的核心,用于评估超级计算机大数据处理的能力。本文依托广州超算中心“天河二号”提供的平台,针对分布式内存体系... 详细信息

广度优先搜索（BFS）是许多图形应用程序的底层内核算法,如社交网络,医疗信息学,传输系统等。因此,它已被吸收为graph500的核心,用于评估超级计算机大数据处理的能力。本文依托广州超算中心“天河二号”提供的平台,针对分布式内存体系结构和共享内存体系结构对BFS算法进行了研究。首先,本文量化分析了分布式内存体系结构上BFS算法的性能瓶颈。并且提出了分布式内存体系结构上关于负载均衡的优化方法,在“自顶向下”阶段同步重点是否被访问过的信息,在“自底向下”阶段同步重点队列信息来达到平衡各个进程通信次数的目的。同时,本文通过对异步小消息通信库重新封装消息头的方式来减少通信消息的长度和通过本地标记的方式来减少无效通信次数的方式,减少了分布式内存体系结构上的通信量。其次,本文针对Knights Landing（KNL）芯片对共享内存体系结构的BFS算法进行了优化。对于KNL的异构存储器层次结构,本文利用KNL芯片提供的Flat模式,利用MCDRAM和DRAM的性能差异,通过将顶点数据、父节点数据分配在MCDRAM上,把边缘数据、临时变量和数组分配在DRAM上的方式来实现更快的读写数据和内存访问。同时,对于高速缓存更新策略,本文的主要工作是利用Clik来对算法的细粒度进行重新划分,来保证每个工作线程读取恰好适合一个CPU缓存行大小所对应的顶点的值,并且每个值的更新不会影响其他的缓存行。最后,我们在Tianhe-2超级计算机和KNL芯片上评估了本文的实验。实验结果表明,在分布式内存体系结构下,我们的方法有效缩短了通信时间,与自上而下的方法相比,获得了 3倍左右的加速比。在KNL平台,我们的方法有效的减少了最后一级缓存load和store指令数,在rmat图上获得了 10倍左右的加速比。

关键词： graph500 广度优先搜索算法 KNL 通信优化高速缓存更新策略

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

并行广度优先搜索算法的研究与优化

并行广度优先搜索算法的研究与优化

作者：刘成尧国防科技大学

学位级别：硕士

在大数据问题的处理中,图算法应用十分广泛,其中宽（广）度优先搜索算法（BFS）为图计算中的经典问题,同时也是许多其他图形搜索算法的基础。由于BFS自身特性,在大规模分布式系统中其通信成本通常远高于计算成本,算法的可拓展性会在一... 详细信息

在大数据问题的处理中,图算法应用十分广泛,其中宽（广）度优先搜索算法（BFS）为图计算中的经典问题,同时也是许多其他图形搜索算法的基础。由于BFS自身特性,在大规模分布式系统中其通信成本通常远高于计算成本,算法的可拓展性会在一定程度受到限制。本文提出了一种基于二维分区的方向优化方法。通过采用二维分区方法,我们将每一层级通信划分为竖直（expand）和水平（fold）两个阶段,前者在处理器间复制部分前沿集合并在本地计算下一层级的前沿,后者则是在处理器间传输边信息（包含两端节点）。这种分区方法降低了每次参与通信的通信端数量,使通信规模从降为√。在此基础上,本文将自下而上遍历和传统的自上而下遍历相结合,在前沿集合抵达最大值之前调整遍历方向,即从“寻找前沿中节点的子节点”调整为“在未访问过的节点中寻找其在前沿中的父节点”,这一改变有效降低了无效访问,并无需采用原子操作即可完成父节点数组的更新。二维分区的天然特性解决了如何快速在前沿中确定成员关系的问题;另外,通过“水平轮动”的方法,在处理器行间水平传递节点访问完成信息,一旦处理器接收到来自左侧处理器节点的访问标记,则自动跳过对节点的处理,内循环遍历可以立即终止。此外,本文还设计了一种基于删减和压缩的通信优化算法,通过建立“删减表”数据结构,在预处理过程中记录分别来自两个处理器的节点间连接边的信息,并据此提前删减掉本应发送出去的无意义数据。这步操作进一步稀疏化了前沿矩阵,使得后续在expand阶段采用的Concise压缩方法效果更加显著。fold阶段处理器间传递的主要信息为节点元组（,）形式,利用节点来自于同一处理器故序号相近的特征,采用差分编码和VLQ压缩相结合的方式进行压缩;节点存储在同一处理器行,其分布成阶梯型,我们利用阶梯记录方法进行压缩。结果显示,优化BFS算法通信量相比之前减少36.7%,效果比较明显。

关键词： graph500 广度优先搜索通信优化