一种基于索引定位的图计算系统的外存访问方法

    公开(公告)号:CN109522428A

    公开(公告)日:2019-03-26

    申请号:CN201811082365.8

    申请日:2018-09-17

    Abstract: 本发明公开了一种基于索引定位的图计算系统的外存访问方法,包括:将完整的图数据分割成多个子图;对各个子图的边分别按照源顶点编号和目标顶点编号进行排序;将排序后的各个子图写入外存文件中,并分别为源顶点编号和目标顶点编号建立索引;从索引定位的载入方式和访问完整数据的载入方式中选择最优载入方式;以最优载入方式,将外存中各个子图载入内存。本发明对外存数据结构重新设计,改进数据加载方式,使系统能够在载入之前分析外存中的有效数据,显著减少I/O数据量和随机访问次数;分析访问完整数据方式与索引定位方式的时间开销,动态判断系统的最优数据载入方式,降低数据加载的时间开销。

    一种基于多外存设备多队列的I/O管理方法

    公开(公告)号:CN109343943A

    公开(公告)日:2019-02-15

    申请号:CN201811040593.9

    申请日:2018-09-07

    Abstract: 本发明公开了一种基于多外存设备多队列的I/O管理方法,包括:将边块文件划分成大小相等的条带单元,条带单元以递增的顺序循环地条带化到条带化文件中;采用上述条带化方式,对原始I/O请求进行地址映射;判断原始I/O请求是否需要分解,如果是,将其分解成对齐条带单元边界的多个新I/O请求;否则,直接将其映射成等长的新I/O请求;对新I/O请求进行预取合并;将新I/O请求分派到对应外存设备的相应的I/O任务队列。本发明通过基于多外设多队列的I/O管理,确保每个I/O请求只由一个外存设备服务,每个应用I/O线程专用于一个外存设备,通过对新I/O请求的预取合并,将多个小的请求合并成一个大的I/O请求,有效地减少了对外存设备的访问次数,使得多外存I/O性能充分发挥。

    一种基于I/O调度的多任务外存模式图处理方法

    公开(公告)号:CN109522102B

    公开(公告)日:2022-12-02

    申请号:CN201811053424.9

    申请日:2018-09-11

    Abstract: 本发明公开了一种基于I/O调度的多任务外存模式图处理方法,包括:将图数据进行流式分区得到图分区,将图分区均衡地置于多个外存设备中,基于I/O调度从多个外存设备中选取目标外存设备,并将目标外存设备中图处理任务尚未访问的图分区作为指定分区;根据指定分区的同步字段判断其是否未被映射到内存中,若是,则将指定分区从外存设备映射到内存中,并更新指定分区的同步字段;否则,直接通过指定分区映射到内存的地址信息进行图分区数据的访问。本发明通过I/O调度,选择任务数最少的外存设备访问,以此控制访问外存图分区数据的顺序,平衡I/O压力;通过设置同步字段实现图分区数据的共享,减少相同图分区的重复加载,以此减少I/O总带宽量,提升I/O效率。

    一种基于BFS森林的社交网络中的知识图谱数据布局方法

    公开(公告)号:CN109271478B

    公开(公告)日:2021-07-27

    申请号:CN201811082264.0

    申请日:2018-09-17

    Abstract: 本发明公开了一种基于BFS森林的社交网络中的知识图谱数据布局方法,包括:对社交网络中的知识图谱进行一次全图的全局BFS遍历,得到全局BFS序列;将当前限长BFS子树的起始点初始化为全局BFS序列的起始序号;从起始点出发,使用限长BFS遍历社交网络中的知识图谱,直至图中所有节点都被遍历,最终得到BFS森林序列;利用所述BFS森林序列对社交网络中的知识图谱的节点进行更新,知识图谱数据布局结束。本发明使用BFS森林去遍历全图,限长BFS子树的局部性已经符合限长图遍历算法需求;以全局BFS序列作为“BFS森林”起始点选择依据,使BFS子树起始点的选择更加符合限长图遍历的需求,使多个BFS子树组成的序列满足整体顺序性,提高了算法执行效率。

    一种基于索引定位的图计算系统的外存访问方法

    公开(公告)号:CN109522428B

    公开(公告)日:2020-11-24

    申请号:CN201811082365.8

    申请日:2018-09-17

    Abstract: 本发明公开了一种基于索引定位的图计算系统的外存访问方法,包括:将完整的图数据分割成多个子图;对各个子图的边分别按照源顶点编号和目标顶点编号进行排序;将排序后的各个子图写入外存文件中,并分别为源顶点编号和目标顶点编号建立索引;从索引定位的载入方式和访问完整数据的载入方式中选择最优载入方式;以最优载入方式,将外存中各个子图载入内存。本发明对外存数据结构重新设计,改进数据加载方式,使系统能够在载入之前分析外存中的有效数据,显著减少I/O数据量和随机访问次数;分析访问完整数据方式与索引定位方式的时间开销,动态判断系统的最优数据载入方式,降低数据加载的时间开销。

    一种基于BFS森林的社交网络中的知识图谱数据布局方法

    公开(公告)号:CN109271478A

    公开(公告)日:2019-01-25

    申请号:CN201811082264.0

    申请日:2018-09-17

    Abstract: 本发明公开了一种基于BFS森林的社交网络中的知识图谱数据布局方法,包括:对社交网络中的知识图谱进行一次全图的全局BFS遍历,得到全局BFS序列;将当前限长BFS子树的起始点初始化为全局BFS序列的起始序号;从起始点出发,使用限长BFS遍历社交网络中的知识图谱,直至图中所有节点都被遍历,最终得到BFS森林序列;利用所述BFS森林序列对社交网络中的知识图谱的节点进行更新,知识图谱数据布局结束。本发明使用BFS森林去遍历全图,限长BFS子树的局部性已经符合限长图遍历算法需求;以全局BFS序列作为“BFS森林”起始点选择依据,使BFS子树起始点的选择更加符合限长图遍历的需求,使多个BFS子树组成的序列满足整体顺序性,提高了算法执行效率。

    匹配顺序大I/O负载特征的粗粒度条带化方法及系统

    公开(公告)号:CN109508234B

    公开(公告)日:2023-03-10

    申请号:CN201811053421.5

    申请日:2018-09-11

    Abstract: 本发明公开了一种匹配顺序大I/O负载特征的粗粒度条带化方法及系统,其中,该方法包括:图数据的分区;条带深度的确定;边块文件的条带化。本发明提出的匹配顺序大I/O负载特征的粗粒度条带化方法,将经过图分区处理后的所有边块文件,以匹配图数据访问特征的粗粒度条带深度,按照更新顺序条带化到一对一存储在多个外存设备的多个条带化文件中,在应用层实现图数据的多盘粗粒度条带化分布。本发明能保证每盘的顺序访问和减少设备I/O次数进而有效提高每个盘的I/O吞吐量,并为实现应用层高效I/O管理和发挥多盘并行I/O能力提供基础。

    一种基于多外存设备多队列的I/O管理方法

    公开(公告)号:CN109343943B

    公开(公告)日:2021-08-03

    申请号:CN201811040593.9

    申请日:2018-09-07

    Abstract: 本发明公开了一种基于多外存设备多队列的I/O管理方法,包括:将边块文件划分成大小相等的条带单元,条带单元以递增的顺序循环地条带化到条带化文件中;采用上述条带化方式,对原始I/O请求进行地址映射;判断原始I/O请求是否需要分解,如果是,将其分解成对齐条带单元边界的多个新I/O请求;否则,直接将其映射成等长的新I/O请求;对新I/O请求进行预取合并;将新I/O请求分派到对应外存设备的相应的I/O任务队列。本发明通过基于多外设多队列的I/O管理,确保每个I/O请求只由一个外存设备服务,每个应用I/O线程专用于一个外存设备,通过对新I/O请求的预取合并,将多个小的请求合并成一个大的I/O请求,有效地减少了对外存设备的访问次数,使得多外存I/O性能充分发挥。

    匹配顺序大I/O负载特征的粗粒度条带化方法及系统

    公开(公告)号:CN109508234A

    公开(公告)日:2019-03-22

    申请号:CN201811053421.5

    申请日:2018-09-11

    Abstract: 本发明公开了一种匹配顺序大I/O负载特征的粗粒度条带化方法及系统,其中,该方法包括:图数据的分区;条带深度的确定;边块文件的条带化。本发明提出的匹配顺序大I/O负载特征的粗粒度条带化方法,将经过图分区处理后的所有边块文件,以匹配图数据访问特征的粗粒度条带深度,按照更新顺序条带化到一对一存储在多个外存设备的多个条带化文件中,在应用层实现图数据的多盘粗粒度条带化分布。本发明能保证每盘的顺序访问和减少设备I/O次数进而有效提高每个盘的I/O吞吐量,并为实现应用层高效I/O管理和发挥多盘并行I/O能力提供基础。

    一种基于I/O调度的多任务外存模式图处理方法

    公开(公告)号:CN109522102A

    公开(公告)日:2019-03-26

    申请号:CN201811053424.9

    申请日:2018-09-11

    Abstract: 本发明公开了一种基于I/O调度的多任务外存模式图处理方法,包括:将图数据进行流式分区得到图分区,将图分区均衡地置于多个外存设备中,基于I/O调度从多个外存设备中选取目标外存设备,并将目标外存设备中图处理任务尚未访问的图分区作为指定分区;根据指定分区的同步字段判断其是否未被映射到内存中,若是,则将指定分区从外存设备映射到内存中,并更新指定分区的同步字段;否则,直接通过指定分区映射到内存的地址信息进行图分区数据的访问。本发明通过I/O调度,选择任务数最少的外存设备访问,以此控制访问外存图分区数据的顺序,平衡I/O压力;通过设置同步字段实现图分区数据的共享,减少相同图分区的重复加载,以此减少I/O总带宽量,提升I/O效率。

Patent Agency Ranking