随着复杂网络和大数据的蓬勃发展,三角形计数在重要角色识别、垃圾邮件检测、社区发现和生物检测等领域得到了广泛的应用。三角形计数算法主要用于计算相邻列表的交点数来识别图中的三角形,三角形数量在计算网络聚类系数和传递性方面起着重要的作用。传统的三角形计数算法遍历图中的每个顶点或边,找到两个列表的交集,一旦找到一个公共的邻接顶点,就找到一个三角形。随着大数据时代的到来,研究人员所研究的图结构数据数量级随着指数增长,拥有上百亿的节点的网络甚至都出现在现实的社会和工程实际中。近年来,利用GPU加速图数据三角形计数受到越来越多研究人员的关注。如何充分利用GPU内存,利用GPU的计算特性来设计三角形计数方案成了研究的重点,本文给出两种基于GPU的图三角计数方案,并在大量数据集上进行实验验证,性能提升良好。本文主要研究内容和取得的成果如下:(1)提出基于CSR的图分割算法。该算法通过将大规模图的三角形计数整个任务划分为多个子任务,从而保证能够将数据送入GPU显存中进行计算或者是在多个GPU之间平衡工作负载分配。(2)提出一种基于GPU的负载均衡三角形计数方案。扩展基于合并的集合求交算法,将其移植到GPU上,提出基于SIMD的集合求交算法,使用一个邻居列表作为查询列表,另一个作为比较列表,多个GPU核心根据查询列表检查比较列表的值。该算法能够解了传统算法的分支发散和内存访问效率低的问题。在并行化过程中,传统的三角形计数算法是将节点平均分配到GPU的线程,由于节点的度大小不同,不同线程的工作负载也不同,这会降低并行计算的性能,为此,我们设计一个负载均衡算法来动态调度GPU的工作负载,提高并行效率。(3)提出基于二分搜索的集合求交三角形计数算法。针对基于二分搜索的串行集合求交算法的不足之处,在并行化过程中提出可行的解决方案,包括合并的内存访问、负载均衡和GPU共享内存优化等。通过分析基于合并的集合求交算法和基于二分搜索的集合求交算法的内存复杂度,得出在并行运算时基于二分搜索的集合求交算法的性能会比基于合并的集合求交算法更好的结论,并且在GPU上实现基于二分搜索的集合求交三角形计数算法。(4)在大量数据集上进行实验验证,实验结果表明,同传统的基于CPU图三角计数算法相比,基于GPU的性能有大幅提升,与其他并行算法相比,本文提出的算法具有较大的运行效率优势。