公开(公告)号：CN109741421B

公开(公告)日：2023-04-14

申请号：CN201910062804.7

申请日：2019-01-23

Applicant: 东北大学

Inventor： 谷峪 ,  宛长义 ,  杨莹 ,  李传文 ,  于戈

IPC: G06T11/40

Abstract: 本发明提出一种基于GPU的动态图着色方法，步骤为：将原始无向图转化成定向图；批量进行删除、插入操作进行后批量合并更新定向图；用压缩稀疏行CSR方式存储定向图的外邻信息，压缩稀疏列CSC方式存储定向图的内邻信息，并将外邻信息与内邻信息分别传输到GPU全局内存上；判断队列是否为空或低于阈值，若否，则利用贪婪着色方法对待更新结点构成的子图进行分区，把分区结果传输至GPU端；若是，则交由CPU端处理；根据分区结果并行地对每个区内的结点进行RC‑Hybrid着色；本发明方法可以充分利用GPU并行的处理能力、对待结点进行混合分块设计提高了并发性并保证着色结果的正确性与一致性。

公开(公告)号：CN109741421A

公开(公告)日：2019-05-10

申请号：CN201910062804.7

申请日：2019-01-23

Applicant: 东北大学

Inventor： 谷峪 ,  宛长义 ,  杨莹 ,  李传文 ,  于戈

IPC: G06T11/40

Abstract: 本发明提出一种基于GPU的动态图着色方法，步骤为：将原始无向图转化成定向图；批量进行删除、插入操作进行后批量合并更新定向图；用压缩稀疏行CSR方式存储定向图的外邻信息，压缩稀疏列CSC方式存储定向图的内邻信息，并将外邻信息与内邻信息分别传输到GPU全局内存上；判断队列是否为空或低于阈值，若否，则利用贪婪着色方法对待更新结点构成的子图进行分区，把分区结果传输至GPU端；若是，则交由CPU端处理；根据分区结果并行地对每个区内的结点进行RC-Hybrid着色；本发明方法可以充分利用GPU并行的处理能力、对待结点进行混合分块设计提高了并发性并保证着色结果的正确性与一致性。