文章基本信息

标题：AN ALGORITHM FOR DETECTING CYCLES IN UNDIRECTED GRAPHS USING CUDA TECHNOLOGY
本地全文：下载
作者：Maytham Safar ; Fahad Mahdi ; Khaled Mahdi 等
期刊名称：International Journal of New Computer Architectures and their Applications
印刷版ISSN：2220-9085
出版年度：2012
卷号：2
期号：1
页码：193-212
出版社：Society of Digital Information and Wireless Communications
摘要：Cycles count in a graph is an NP-complete problem. This work minimizes the execution time to solve the problem compared to the other traditional serial, CPU based one. It reduces the hardware resources needed to a single commodity GPU. We developed an algorithm to approximate counting the number of cycles in an undirected graph, by utilizing a modern parallel computing paradigm called CUDA (Compute Unified Device Architecture) from nVIDIA, using the capabilities of the massively parallel multi-threaded specialized processor called Graphics Processing Unit (GPU). The algorithm views the graph from combinatorial perspective rather than the traditional adjacency matrix/list view. The design philosophy of the algorithm shows that each thread will perform simple computation procedures in finite loop iterations to be executed in polynomial time. The algorithm is divided into two stages, the first stage is to extract a unique number of vertices combinations for a given cycle length using combinatorial formulas, and then examine whether given combination can for a cycle or not. The second stage is to approximate the number of exchanges (swaps) between vertices for each thread to check the possibility of cycle existence. An experiment was conducted to compare the results between the proposed algorithm and another distributed serial based algorithm based on the Donald Johnson backtracking algorithm.
关键词：Approximation algorithms; graph cycles; ; GPU programming; CUDA parallel ; algorithms; multi-threaded applications