GPU에서 CUDA를 이용한 그래프 유사도 측정을 위한 병렬 알고리즘

국문 초록 (Abstract)

두 그래프의 유사도를 측정하는 문제는 다양한 응용분야에서 그래프 문제를 해결하기 위한 기본적인 도구 중 하나이다. 대부분 그래프 알고리즘들은 정점과 간선의 개수를 기반으로 한 시간 복잡도를 가진다. 최근 GPU는 낮은 가격 대비 높은 계산 능력을 제공하기 때문에 그래프 응용에서 수행 시간을 개선하기 위해 널리 활용되고 있다. 본 논문에서는 GPU 환경에서 CUDA를 사용하여 그래프의 유사도를 측정하기 위한 효율적인 병렬 알고리즘을 제안한다. 제안된 알고리즘의 평가를 위해 CPU 기반 알고리즘과 비교하였으며 실험적 결과를 통하여 제안된 방법이 성능과 효율성에서 상당한 개선이 있음을 보인다. 또한 그래프의 크기가 클수록 제안된 알고리즘의 성능이 더 개선됨을 보인다.

다국어 초록 (Multilingual Abstract)

Measuring the similarity of two graphs is a basic tool to solve graph problems in various applications. Most graph algorithms have a high time complexity according to the number of vertices and edges. Because Graphics Processing Units (GPUs) have a high computational power and can be obtained at a low cost, these have been widely used in graph applications to improve execution time. This paper proposes an efficient parallel algorithm to measure graph similarity using the CUDA on a GPU environment. The experimental results show that the proposed approach brings a considerable improvement in performance and efficiency when compared to CPU-based results. Our results also show that the performance is improved significantly as the size of the graph increases.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. GPU와 CUDA
• 3. 관련 연구
• 4. 그래프와 유사도 행렬
• 5. 그래프 유사도 측정 병렬 알고리즘 제안
• 6. 실험
• 7. 결론
• References

참고문헌 (Reference)

1 Y. Shinano, "Solving the maximum clique problem using PUBB" 326-332, 1998

2 S. Melnik, "Similarity flooding: A versatile graph matching algorithm and its application to schema matching" 117-128, 2002

3 G. Jeh, "SimRank : a measure of structural-context similarity" 538-543, 2002

4 D. Merrill, "Scalable GPU graph traversal" 47 (47): 117-128, 2012

5 P. J. Narayanan, "Processor Autonomy on SIMD Architectures" 127-136, 1993

6 Guoming He, "Parallel SimRank computation on large graphs with iterative aggregation" 543-552, 2010

7 R. A. Horn, "Matrix analysis" Cambridge university press 2012

8 P. Harish, "Large Graph Algorithms for Massively Multithreaded Architectures"

9 R. Singh, "Global alignment of multiple protein interaction networks with application to functional orthology detection" 105 (105): 12763-12768, 2008

10 K. Matsumoto, "Blocked all-pairs shortest paths algorithm for hybrid CPU-GPU system" 145-152, 2011

11 C. Silverstein, "Beyond market baskets : Generalizing association rules to dependence rules" 2 (2): 39-68, 1998

12 J. M. Kleinberg, "Authoritative sources in a hyperlinked environment" 46 (46): 604-632, 1999

13 P. M. Pardalos, "An exact parallel algorithm for the maximum clique problem"

14 M.-Y. Son, "An Efficient parallel Algorithm for Graph Isomorphism on GPU using CUDA" 7 (7): 1840-1848, 2015

15 G. J. Katz, "All-pairs shortestpaths for large graphs on the GPU" 47-55, 2008

16 R. Allen, "A parallel algorithm for graph matching and its MasPar implementation" 8 (8): 490-501, 1997

17 V. D. Blondel, "A measure of similarity between graph vertices : Applications to synonym extraction and web searching" 46 (46): 647-666, 2004