版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
一种基于局部性感知的核外图随机游走处本发明公开了一种基于局部性感知的核外于时空局部性对已划分的子图进行更细粒度的将前90%walkers游走过程中最常访问的前1%节对walkers所在子图进行更精细的动态划分,每造是由SmartSSD7完成,随机游走的过程在CPU22.根据权利要求1所述的方法,其特征在于,所述将前90%采用归并排序对图节点按照访问次数从高到低进行排序,归并排序是一种分治算法,需使用哈希数组来建立子图顶点ID与索引0至n_1之间的着,为每个节点ID与索引0到n_1之间建立一一对应的哈希映射关系,生成哈希数组hash_array,offset_array,edges_子图中walkers所在的节点标记为活动节点,然后从每个活动节点开始执行两层广度优先1%高访问频率的节点构成一个子图的方法进行构建子图,同时主机上的随机游走过程与图时,除了需要从活动节点出发通过两层BFS获取的所有节点外,还需要包含这些子图中3在一阶段随机游走过程中,当主机端正在执行随机游走时,从在二阶段随机游走过程中,当主机端正在执行随机游走时,从7.根据权利要求5所述的方法,其特征在于,每次需要将已经划分好的子图调入到8.一种基于局部性感知的核外图随机游走处理系统,其特要求1_7任一项所述的一种基于局部性感知的核外图随机游走处理方法,具体包括如下内所述主机CPU处理随机游走过程以及对子图中walkers数量进所述SmartSSD一方面需要存储游走过程所需要的所有已划分好的子图和所有9.根据权利要求8所述的系统,其特征在于,所述主机C前90%的walkers游走过程完全在主机CPU中执行,后10%walke进行更新,同时,累加单元在随机游走过程中记录每个节点的访问次数,直至前90%的4在前90%walkers完成游走后,顶点排序核心首先根据节点在前当本轮随机游走完成后,对于一阶段随机游走,子图调度核心将从SSD中选取包含5荐技术等多个领域都有着广泛的应用。它不仅帮助我们理解和模拟自然界中的随机过程,方式的一阶段随机游走模型以及异步方式的二阶段随机游走[0005]基于同步方式的一阶段随机游走模型首先将整个图划分为若干子图并存储在磁6中。在内存中,对该子图中的活动节点采用异步方式进行游走,即每个活动节点上的[0008]基于异步模式的二阶段随机游走模型首先将整个图划分为若干子图并存储在磁时间的60%至90%主要集中在不足10%的活动节点上7首先,提取前90%游走过程中访问频率最高的前1%节点,并将这些节点按顺序排将每个节点的所有边提取并构成一个边数组edges_array,因此,子图的最终表示形式为[hash_array,offset_array,edges_并将子图中walkers所在的节点标记为活动节点,然后从每个活动节点开始执行两层广度与SmartSSD7中FPGA的两层BFS过图数据量小于N,则继续从磁盘中调入已划分好的子图至FPGA中进行进一步的动态子图构8所述主机CPU处理随机游走过程以及对子图中walkers数量进所述SmartSSD一方面需要存储游走过程所需要的所有已划分好的子图和所有[0019]进一步地,所述主机CPU处理随机游走过程以及对子图中wal程中所有已划分的子图以及所有walkers的状态信息;FPGA加速器则负责动态子图的划分对于二阶段随机游走,子图调度核心从SSD中选取包含walkers数量最多的4个子图中选取walkers数量最多的4个子图进行下一步动态子图的构建,从而确保主机CPU与9分总执行时间,I/O成为了核外随机游走的瓶颈。其实I/O大部执行时间是由最后10%用动态子图划分加速器对剩下walkers游走过程所需要的子图进行动态划分,子图的划分过程和随机游走过程并发进行。在动态子图划分加速器中主要是利用空间局部性对[0029]当前90%walkers游走完成后,需要系统能够识别出被访问[0031]首先提取在前90%walkers游走过程中访问频率最高的前1%节点,并对其按顺序排列。接着,将每个节点的ID与0到n_1之间的连续编号建立一一对应的哈希映射hash_[hash_array,offset_array,edg[0032]在完成对前90%walkers访问最频繁的前1%节点构成的子图的一次随机游走之其关联的边构建为下一轮随机游走所需的子图。该子图的构建方式与前90%walkers访问[0034]二阶段随机游走过程与一阶段随机游走主要区别在于:每次需要将4个子图同时的子图中选择4个walkers数量最多的子图加载进SmartSSD7的FPGA中进行动态子图的构的前1%节点构建子图。主机CPU1将首先在该子图上进行一轮随机游走。对于剩余的子图的数据量大小小于N时,则需要继续将SSD8中已划分好的子图调入FPGA中进行更细粒[0040]一种基于局部性感知的核外图随机游走处理系统整体架构如图1所示,整体架构[0041]主机CPU1主要处理随机游走过程以及对已划分好地子图中walkers数量进行更[0042]SmartSSD7一方面需要存储游走过程中的整张图和所有walkers状态,另一方面[0044]当前90%walkers随机游走完成后,在最后10%walkers游走过程中,需要SmartSSD8中取出walkers数量最多的一个已划分好的子图,然后送入BFS计算核心14进行两层取walkers第二多的已划分好的子图进行动态子图的构造,使得每次主机CPU1和Smart[0048]如果是二阶段随机游走,加速器子图调度核心13从SSD8中取出walkers数量最多[0049]SmartSSD7的结构如图2所示,一种基于局部性感知的核外图随机游走处理方法及系统能够成功解决核外随机游走后期I/O所带来的长尾问题的一个关键所在就是利用了速器11之间采用P2P的方式直接通信而无需借助主机CPU1,因此已划分好的子图可以直接[0051]所述两层BFS计算核心14实现如图3所示,本发明的两层BFS采用五阶段流水线结[0054]两层BFS操作的输入是子图中walkers所在的活动节点,输出是经过两层BFS后所[0056]子图的输入是经过两层BFS操作得到的最终需要构造子图的节点,在子图构造的节点邻居以及构建好的哈希表对子图进行构造,子图采用三元组的形式进行表示hash_[0057]子图构造操作的输入是经过两层BFS后的节点ID,输出是采用三原组(hash_开始位置,offsetm+1表示该节点m对应邻居的结束位置,在blk1中,3号节点有2条边,先从hash_array结构中发现3号节点对应offset_array数组中的0号位置,说明3号节点的邻居在edges_array数组中的对应应offset_array数组中的2号位置,说明3号节点的邻居在edges_array数组中的对应的位[0061]本实施例是对基于局部性感知的核外图随机游走处理方法及系统的一个具体实入内存中,从9号节点出发的walkers有两个,由blk1中跳入的walker的游走轨迹为9→2,此时blk1和blk2中walker的数量都为0,blk0中walkers的数量为3,2号节点上有2个[0066]本实施例是对基于局部性的二阶段核外随机游走动态块划分方法的一个具体实[0067]图7是对二阶段核外随机游走动态划分实例示意说明,二阶段核外随机游走和一阶段核外随机游走都采用了三个阶段完成,这里仍然详细介绍二阶段随机游走的第三阶如果加载blk1和blk2,有效walkers只有两个,分别是5号节点上的walker和9号节点上的blk0和blk1力。0号节点上的walker的游走轨迹为0→1→3点上walkers的上一跳分别是7号节点和8号节点,因此应该将blk1和blk2从SSD8中加载进节点,这时需要blk0和blk2加载进FPGA中
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026事业单位工勤技能-浙江-浙江广播电视天线工三级(高级工)历年参考题库含答案详解
- 2026事业单位工勤技能-河南-河南理疗技术员三级(高级工)历年参考题库含答案详解
- 2026事业单位工勤技能-河南-河南房管员三级(高级工)历年参考题库含答案详解
- 2026事业单位工勤技能-河北-河北理疗技术员一级(高级技师)历年参考题库含答案详解
- 2026事业单位工勤技能-河北-河北工程测量工四级(中级工)历年参考题库含答案详解
- 2026事业单位工勤技能-河北-河北保育员三级(高级工)历年参考题库含答案详解
- 2026事业单位工勤技能-江西-江西环境监测工五级(初级工)历年参考题库含答案详解
- 2026事业单位工勤技能-江西-江西房管员二级(技师)历年参考题库含答案详解
- 2026事业单位工勤技能-江苏-江苏收银员二级(技师)历年参考题库含答案详解
- 药品营销与推广策略考点题库及答案
- YY/T 0493-2026牙科学弹性体印模和咬合记录材料
- (2026)发展对象考试测试题库附参考答案
- 2026客服面试题及参考答案
- T/GDNSA 011-2025成人机械通气雾化吸入技术规范
- 人教版四年级(上)英语1-6单元语法专项训练
- 第6课 人民当家作主 第1课时 课件(内嵌视频)2026-2027学年道德与法治五年级上册统编版
- 药品经营和使用质量监督管理办法培训试题及答案
- 港口陆域形成施工方案
- 食材配送中心仓储管理操作手册
- 《新能源汽车电工电子技术》课程标准
- 中医胆囊结石护理要点说课
评论
0/150
提交评论