-
公开(公告)号：CN110264392A
公开(公告)日：2019-09-20
申请号：CN201910371236.9
申请日：2019-05-06
Applicant: 中国科学院信息工程研究所
Abstract: 本发明提出一种基于多GPU的强连通图检测方法，包括以下步骤：加载图数据并统一存储格式；对图数据进行预处理，包括按照分区个数进行图分割并进行分区保存，对相互链接的处于不同分区的顶点进行复制顶点处理；将预处理好的数据存入多个GPU中，以复制顶点为中心进行广度优先遍历并记录复制边信息；将复制边传回CPU，检测强连通图并标记属于同一个强连通图的顶点；将标记的顶点传回上述多个GPU中，进行强连通图检测。
-
公开(公告)号：CN112257865A
公开(公告)日：2021-01-22
申请号：CN202010940174.1
申请日：2020-09-09
Applicant: 中国科学院信息工程研究所
Abstract: 本发明公开了一种GPU上的基于着色优化的置信传播方法。本发明通过使用信息残差大的顶点对信息残差小的顶点进行固定步长的着色操作，在整个图模型上形成多个以信息残差大的顶点为中心的分区，将该顶点命名为中心点；在每个分区中，按照最远顶点到中心点以及中心点到最远点的顺序对边上的信息进行更新操作，以完成每次迭代的置信传播计算。本发明能够保证置信传播方法在短时间内收敛大多数顶点。
-
公开(公告)号：CN111754383A
公开(公告)日：2020-10-09
申请号：CN202010403115.0
申请日：2020-05-13
Applicant: 中国科学院信息工程研究所
Abstract: 本发明提出一种基于GPU加速的优化线程调度与分区的强连通图检测方法，为使用异构系统进行强连通图检测的方法，通过将每个warp分成多个虚拟warp并分配多个顶点任务、使用着色分区替换传统的WCC分区等方法平衡了线程分配、增加了每次迭代产生的强连通图数目，从而达到提升算法运行效率的目的。
-
公开(公告)号：CN112257866B
公开(公告)日：2024-09-27
申请号：CN202010940904.8
申请日：2020-09-09
Applicant: 中国科学院信息工程研究所
Abstract: 本发明公开了一种GPU上的基于边着色与信息更新率优化的置信传播方法。本方法针对在全局都有较高收敛速度的计算需求，直接使用信息残差大的边对信息残差小的边进行一次着色操作，则信息残差大的边会对与其相连的所有边进行着色，只更新这些信息残差大的边上的信息，降低了每次迭代置信传播的计算量，提升了置信传播算法在整个计算过程中的收敛速度。以及针对在算法稳定后有较高收敛度的计算需求，提出通过逐步降低未收敛信息的更新率，使得算法在整个计算过程中都保持较高的收敛速度，并且算法稳定时有较高的收敛度。本发明提升了置信传播方法整体的运行效率。
-
公开(公告)号：CN111754383B
公开(公告)日：2023-03-10
申请号：CN202010403115.0
申请日：2020-05-13
Applicant: 中国科学院信息工程研究所
Abstract: 本发明提出一种基于GPU加速的优化线程调度与分区的强连通图检测方法，为使用异构系统进行强连通图检测的方法，通过将每个warp分成多个虚拟warp并分配多个顶点任务、使用着色分区替换传统的WCC分区等方法平衡了线程分配、增加了每次迭代产生的强连通图数目，从而达到提升算法运行效率的目的。
-
Patent Agency Ranking
公开(公告)号：CN110288507B
公开(公告)日：2021-03-09
申请号：CN201910371230.1
申请日：2019-05-06
Applicant: 中国科学院信息工程研究所
IPC: G06T1/20 , G06F16/901
Abstract: 本发明提出一种基于GPU的多分区强连通图检测方法，包括以下步骤：加载图数据并统一存储格式；在图数据上基于GPU进行第一剪枝操作，检测出1‑SCC；在除1‑SCC外的部分上选取中心点，从中心点开始并行地前向和后向遍历，更新状态得到SCC和多个分区；在未被检测的图数据上基于GPU进行第二剪枝操作，检测出2‑SCC；在未被检测的图数据上检测弱连通区域，并在弱连通区域上每个选取中心点，从中心点开始前向遍历；在弱连通区域的中未被前向遍历到的区域随机选取保存的最后一个顶点做为副中心点，从中心点与副中心点开始后向遍历，再进行第一剪枝操作，再次更新状态得到SCC和分区；通过上述步骤获得全部的SCC。
-
公开(公告)号：CN112257866A
公开(公告)日：2021-01-22
申请号：CN202010940904.8
申请日：2020-09-09
Applicant: 中国科学院信息工程研究所
Abstract: 本发明公开了一种GPU上的基于边着色与信息更新率优化的置信传播方法。本方法针对在全局都有较高收敛速度的计算需求，直接使用信息残差大的边对信息残差小的边进行一次着色操作，则信息残差大的边会对与其相连的所有边进行着色，只更新这些信息残差大的边上的信息，降低了每次迭代置信传播的计算量，提升了置信传播算法在整个计算过程中的收敛速度。以及针对在算法稳定后有较高收敛度的计算需求，提出通过逐步降低未收敛信息的更新率，使得算法在整个计算过程中都保持较高的收敛速度，并且算法稳定时有较高的收敛度。本发明提升了置信传播方法整体的运行效率。
-
公开(公告)号：CN112257865B
公开(公告)日：2023-11-03
申请号：CN202010940174.1
申请日：2020-09-09
Applicant: 中国科学院信息工程研究所
Abstract: 本发明公开了一种GPU上的基于着色优化的置信传播方法。本发明通过使用信息残差大的顶点对信息残差小的顶点进行固定步长的着色操作，在整个图模型上形成多个以信息残差大的顶点为中心的分区，将该顶点命名为中心点；在每个分区中，按照最远顶点到中心点以及中心点到最远点的顺序对边上的信息进行更新操作，以完成每次迭代的置信传播计算。本发明能够保证置信传播方法在短时间内收敛大多数顶点。
-
公开(公告)号：CN110264392B
公开(公告)日：2021-05-04
申请号：CN201910371236.9
申请日：2019-05-06
Applicant: 中国科学院信息工程研究所
Abstract: 本发明提出一种基于多GPU的强连通图检测方法，包括以下步骤：加载图数据并统一存储格式；对图数据进行预处理，包括按照分区个数进行图分割并进行分区保存，对相互链接的处于不同分区的顶点进行复制顶点处理；将预处理好的数据存入多个GPU中，以复制顶点为中心进行广度优先遍历并记录复制边信息；将复制边传回CPU，检测强连通图并标记属于同一个强连通图的顶点；将标记的顶点传回上述多个GPU中，进行强连通图检测。
-
公开(公告)号：CN110288507A
公开(公告)日：2019-09-27
申请号：CN201910371230.1
申请日：2019-05-06
Applicant: 中国科学院信息工程研究所
IPC: G06T1/20 , G06F16/901
Abstract: 本发明提出一种基于GPU的多分区强连通图检测方法，包括以下步骤：加载图数据并统一存储格式；在图数据上基于GPU进行第一剪枝操作，检测出1-SCC；在除1-SCC外的部分上选取中心点，从中心点开始并行地前向和后向遍历，更新状态得到SCC和多个分区；在未被检测的图数据上基于GPU进行第二剪枝操作，检测出2-SCC；在未被检测的图数据上检测弱连通区域，并在弱连通区域上每个选取中心点，从中心点开始前向遍历；在弱连通区域的中未被前向遍历到的区域随机选取保存的最后一个顶点做为副中心点，从中心点与副中心点开始后向遍历，再进行第一剪枝操作，再次更新状态得到SCC和分区；通过上述步骤获得全部的SCC。
-
-
-
-
-
-
-
-
-
Search Results
10
records
(took 0.034 seconds)
