-
题名基于NUMA延迟发送的时变图弱连通分量求解
- 1
-
-
作者
梁锐杰
程永利
-
机构
福州大学计算机与大数据学院/软件学院
-
出处
《计算机系统应用》
2023年第3期322-329,共8页
-
基金
福建省自然科学基金(2020J01493)。
-
文摘
时变图连通分量已经被广泛应用到不同场景,如交通路网建设、推荐系统的信息推送等.然而当前多数连通分量求解方法忽视了NUMA体系结构对计算效率产生的影响,即过高的远程内存访问延迟导致低下的算法执行效率.本文针对时变图的弱连通分量求解问题,提出一种基于NUMA延迟发送的时变图弱连通分量求解方法,它通过合理的数据内存布局,合理控制NUMA节点间的信息交换次数,最大限度减少远程内存访问数量,显著提高了算法执行效率.实验结果表明,该方法的性能明显优于当前流行的图处理系统Ligra和Polymer提供的方法.
-
关键词
弱连通分量
NUMA
延迟发送
时变图
图计算
-
Keywords
weakly connected components
non-uniform memory access(NUMA)
delayed sending
time-evolving graph
graph computing
-
分类号
O157.5
[理学—基础数学]
-
-
题名基于染色的分布式弱连通分量求解算法
- 2
-
-
作者
肖有诰
谭菊仙
李璞
-
机构
江南计算技术研究所
-
出处
《计算机系统应用》
2014年第5期107-111,共5页
-
文摘
社交网络、生物信息网络等链接关系数据呈现爆炸性增加,对亿万个顶点级别的大图处理需求愈加迫切,传统的图算法对单点内存的计算依赖性已经不能满足数据规模急速增长的需求.本文针对图的弱连通分量求解问题,提出了一种快速、可扩展的迭代染色算法CR,并建立了算法的MapReduce模型.最后,在Hadoop平台上,对斯坦福大学社会网络分析实验室提供的四组通联数据进行测试,并和开源的数据挖掘工具箱XRIME提供的算法进行了对比.
-
关键词
弱连通分量
染色算法
MAPREDUCE
XRIME
-
Keywords
weakly connected components
CR
MapReduce
XRIME
-
分类号
O157.5
[理学—基础数学]
TP301.6
[自动化与计算机技术—计算机系统结构]
-