一种面向大图计算高效图划分方法与系统
专利类型：发明专利
语 言：中文
申 请 号：CN201711375929.2
申 请 日：20171219
申 请 人：重庆大学
申请人地址：400044 重庆市沙坪坝区沙正街174号
公 开 日：20180424
公 开 号：CN107957962A
代 理 人：王丹
代理机构：重庆市前沿专利事务所(普通合伙) 50211
摘 要：本发明提出了一种面向大图计算高效图划分方法与系统，该方法将图数据划分成多个顶点，并将顶点随机排序转为队列；按照队列顺序对第一个顶点进行分区分配，即分配到处理单元，分配完后以该顶点的分区信息作为值，此顶点的邻点作为键，以字典条目的形式存储于DRAM或者NVM中；后续顶点，先判断DRAM或NVM中是否有以此顶点为键的条目，如存在，直接将此顶点的分区信息追加到DRAM或者NVM中对应的条目；如果不存在，则将该点分配到负载最小的处理单元。将每个分配完的顶点的分区信息作为值，此顶点的邻点作为键，以字典条目的形式存储于对应的缓存中。该方法每次可直接根据当前定点查找对应的以此点为键的条目，效率得到了提升。
主 权 项：一种面向大图计算高效图划分方法，其特征在于，包括以下步骤：S1，将图数据划分成多个顶点，并将顶点随机排序转为队列；S2，按照队列顺序对第一个顶点进行分区分配，即分配到处理单元，分配完后以该顶点的分区信息作为值，此顶点的邻点作为键，以字典条目的形式存储于DRAM中，如果DRAM的数据容量超过设定阈值则存储于NVM中；S3，对于队列中后续顶点，先判断DRAM或NVM中是否有以此顶点为键的条目，如果存在，直接将此顶点的分区信息追加到DRAM或者NVM中对应的条目，即依据该条目中的值，将该点分配到对应的处理单元，每分配完一个顶点，均以分配完成顶点的分区信息作为值，此顶点的邻点作为键，以字典条目的形式存储于对应缓存中；如果DRAM或NVM中不存在以此顶点为键的条目，则将该点分配到负载最小的处理单元，再将每个分配完的顶点的分区信息作为值，此顶点的邻点作为键，以字典条目的形式存储于DRAM中，如果DRAM的数据容量超过设定阈值则存储于NVM中，直至队列中所有点都分配完毕，其中，所述负载最小的处理单元为拥有顶点数量最少的分区。
关 键 词：分区信息;分配;条目;处理单元;字典条目;图计算;队列;存储;缓存;随机排序;图数据;分区;追加;查找
法律状态：公开
IPC专利分类号：G06F12/0871(2016.01)I