一种面向GPU卡群的图遍历混合负载均衡方法

摘要

本发明公开了一种面向GPU卡群的图遍历混合负载均衡方法，用于解决大规模图数据处理中存在的负载不均衡问题，在图数据划分过程中，先对图数据中的顶点按照度进行排序并重编号，之后使用优化的静态shuffle方案进行划分，以保证划分后的子图节点和边所携带的信息量相近。在子图遍历过程中，Top‑Down算法中使用基于边粒度的动静混合负载划分方案，Bottom‑Up算法中使用度排序、顶点边表排序和度感知等方法，以解决图数据遍历中的数据不规则、局部性差、负载不均衡等问题。通过使用多种混合负载均衡方案，能够显著提升GPU卡群上图遍历的性能。