GraphMat论文总结

爱被打了一巴掌 2022-06-17 00:08 187阅读 0赞

GraphMat 是用 c++ 写的

GraphMat 是利用vertexprogram来编程的，但是在后端把它们映射成了高效的稀疏矩阵操作。通过这样的方法，我们在高效地容易理解地编程的同时，又使得程序效率变得很高

由于GraphMat表现主要是依赖一些可扩展的容易理解的稀疏矩阵操作，因此，这个特点使得其能够随着硬件的效率的提升利用到很好的并行的特性

GraphMat在一个singlenode上面会比 目前的一些图计算框架要快， 比GraphLab 快5-7倍，比Galois要快1.2倍

在多核的情况下，提升的性能也会更多一点

GraphMat背后的思想是图分析算法（凭借vertex programming）的一般都可以通过稀疏矩阵操作来表示。特别一点的，这种方法适用于我们可以用邻接矩阵来表示图中的边。特别地，我们用到的概括来讲的思想如下，其中左边的是giraph的所采用的模型

在开始的时候，每个vertex都有着用户自己定义的特征向量，一些vertex被标记为active的，用户定义的func

SEND\_MESSAGE()读取vertexdata,然后将其生成为message object.

PROCESS\_MESSAGE()读取messageobject, edge data沿着message的，还有desvertex data然后为该edge生成message.

REDUCE()得到该vertex的message并且把其整合为一个value.

APPLY()利用REDUCE()的结果来更新vertex的值

SEND\_MESSAGE()用来沿着入边或者出边发送message

特别地，相比于传统的MATRIX框架来说，在PROCESS\_MESSAGE()中添加的destination vertex使得算法（比如triangle counting和CF）更容易实现。

GraphMat相比较其它matrix框架的优点是，基于vertex观点来编程的话更加方便了，一些其它的matrix-based 框架例如 CombBLAS和 PEGASUS，用户定义的PROCESS\_MESSAGE()函数 只能获取它自己的message和它作为入边的edge上的值，但是GraphMat的可以获得向其发送信息的vertex的特征向量

数据结构实现的具体细节

Sparse Matrix

Doubly Compressed Sparse Column形式来高效地存储稀疏矩阵,用四个数组来存储矩阵简单的解释一下: 一个数组来存储“行”的索引，是那些至少有一个非0元素的行， 第二个数组用来存储列的索引，是那些每一行的哪些列是按照第一个数组里的行一一对应下来的。第三个数组用来存储那些非0元素的值具体是多少，其与第二个数组是一一对应的，第四个数组用来表示每一行的起始对应于第2，3数组的哪个位置。

Sparse Vector

稀疏向量能用很多方式表达， 一种是可变长度的数组（index, value）,另一种则是用bitvector

由于bitvector能够被多线程共享，并且可以利用cache的有效性，所以其在并行性能上提高了很多。

发表评论取消回复

表情：

评论列表（有 0 条评论，187人围观）

还没有评论，来说两句吧...

相关阅读

相关历年系统架构师论文题目总结（2012-2018）

离2019年软考还剩下一个星期了，今天收集了2012-2018年系统架构师论文题目供大家参考。 2019年软考系统架构师论文论文内容预测： 1.架构风格 2.架构基础

亦凉/ 2023年10月08日 09:13/ 0 赞/ 73 阅读

相关论文笔记：Tree-LSTM结构的三篇论文总结

对于序列数据而言，从最早的 RNN 结构单元，后来衍生出了 LSTM 以及 GRU 等等变种，这些变种单元的功能更好，并且有效解决了RNN的梯度消失/爆炸问题。对于树结构信息来

Myth丶恋晨/ 2023年06月27日 11:08/ 0 赞/ 5 阅读

相关 CAP理论-论文/博客总结

前言最近看了关于CAP理论的一些资料，想着整理方便日后寻找论文 Harvest, yield, and scalable tolerant systems

约定不等于承诺〃/ 2023年02月23日 07:47/ 0 赞/ 15 阅读

相关【论文阅读】句向量总结、文本相似度计算

句向量不定长的句子用定长的向量表示，为NLP下游任务提供服务。对于word embedding，训练完以后每个词对应一个向量，可以直观地判断embedding的好

刺骨的言语ヽ痛彻心扉/ 2023年01月17日 08:52/ 0 赞/ 158 阅读

相关【latex】sci论文写作总结

文章目录一、前言二、Elsevier latex模板三、图表绘制绘制表格参考一、前言 latex基础操作参考: [

今天药忘吃喽~/ 2023年01月15日 08:03/ 0 赞/ 501 阅读

相关干货｜我的读论文经验总结！

Datawhale干货作者：胡来，Datawhale成员从入门到精通一个领域，绕不开文献阅读。本文是自己做科研的一些经验总结，，将论文阅读分为从小白到大师四个段位

红太狼/ 2022年09月10日 00:26/ 0 赞/ 227 阅读

相关总结和评价论文

from:[https://m.weibo.cn/status/4581221364933235?sourceType=weixin&from=10B7295010&wm=90

心已赠人/ 2022年08月31日 15:29/ 0 赞/ 155 阅读

相关【系分】论文案例、知识点总结

论文范文： https://wenku.baidu.com/view/3e83b7d126fff705cc170aa4?pn=1&pu=sz@1320\_320

左手的ㄟ右手/ 2022年07月03日 20:54/ 0 赞/ 161 阅读

相关 GraphMat论文总结

GraphMat 是用 c++ 写的 GraphMat 是利用vertexprogram来编程的，但是在后端把它们映射成了高效的稀疏矩阵操作。通过这样的方法，我们在高效地容易

爱被打了一巴掌/ 2022年06月17日 00:08/ 0 赞/ 188 阅读

相关 Alexnet总结/论文笔记

本文主要从如下几个方面分析深度学习Alexnet网络： 1. 为什么Alexnet能在图2012 ImageNet LSVRC-2012 像识别(分类) competiti

Myth丶恋晨/ 2022年05月16日 01:11/ 0 赞/ 160 阅读