Parallelizing Graph Algorithms on GPU for Optimization
Journal Title: IOSR Journals (IOSR Journal of Computer Engineering) - Year 2015, Vol 17, Issue 4
Abstract
Abstract: Many practical applications include image processing, space searching, network analysis, graphpartitioning etc. in that large graphs having a millions of vertices are commonly used and to process on thatvertices is difficult task. Using high-end computers practical-time implementations are reported but areaccessible only to a few. Efficient performance of those applications requires fast implementation of graphprocessing and hence Graphics Processing Units (GPUs) of today having a high computational power ofaccelerating capacity are deployed. The NVIDIA GPU can be treated as a SIMD processor array using theCUDA programming model. In this paper Breadth-First Search and All Pair shortest path and travelingsalesmen problem graph algorithms are performed on GPU capabilities. The algorithms are introduced tooptimize such that they can efficiently adopt GPU. Also an optimization technique that reduce data transfer rateCPU to GPU and reduce access of global memory is designed to reduce latency. Analysis of All pair shortestpath algorithm by performing on different memories of GPU which shows that using shared memory can reduceexecution time and increase speedup over CPU than global memory and coalescing access of data. TSPalgorithm shows that increasing number of blocks and iteration obtained optimized tour length.
Authors and Affiliations
Trupti R. Desale
Keywords
Related Articles
- EP ID EP89698
- DOI -
- Views 194
- Downloads 0
Online Password Guessing Attacks by Using Persuasive Click Point with Dynamic User Block
Abstract: The goal of knowledge-based authentication system is to guide the users in creating graphical passwords. User often creates memorable passwords that are easy for attackers to guess, but strong system assi...
An Adaptive approach to retrieve image affected by impulse noisefrom documents
Abstract: Impulsive noise is sometimes called salt-and-pepper noise or spike noise is most oftenly occuringimage detoriation. An image containing salt-and-pepper noise will have dark pixels in bright regions and brightpi...
Matlab Based Decimeter Design Analysis Wimax Appliacation
Abstract: A Digital down Converter (DDC), which is basically used to convert an intermediate frequency (IF) signal to its baseband form, forms an integral part of wireless receivers. The major functional blocks of a DDC...
Secured Employee Attendance Management System Using Fingerprint
In this paper an effective employee attendance management system using fingerprint is introduced. It is used to managed the attendance of employees in any organization. All organizations and institutions are &nbs...
Emergency Vehicle Priority Preference at Multiple Wireless Network Sensors (MWNS) Intelligent Road Traffic Signal Control System
Abstract: Traffic control management system has to be intelligent and equitable in signal allocation management system, especially priority order has to be given to emergency vehicles so as to prevent unforeseen...