6517

An Algorithm for Detecting Cycles in Undirected Graphs using CUDA Technology

Maytham Safar, Fahad Mahdi, Khaled Mahdi
Computer Engineering Department, Kuwait University, Kuwait
International Journal on New Computer Architectures and Their Applications (IJNCAA) 2(1): 194-213, 2012

@article{safar2012algorithm,

   title={An Algorithm for Detecting Cycles in Undirected Graphs using CUDA Technology},

   author={Safar, M. and Mahdi, F. and Mahdi, K.},

   year={2012}

}

Download Download (PDF)   View View   Source Source   

829

views

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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: