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 175
- Downloads 0
Object Removal Using Super-Resolution-Based In-Painting
Abstract: In-painting is the process of reconstructing lost or deteriorated part of images based on the background information. Image in-painting fills the missing or damaged region in an image, utilizing information of...
A Survey on Brute Force Attack on Open Functionality Secured
The project entitled as Brute Force Attack On Open Functionality Secured is to design and develop the application package for well secured dynamic application. A common threat web developer’s face is a password-guessing...
Automatic Text Extraction System for Complex Images
Abstract : The Intelligent text extraction system automatically identifies and extracts the text present in different types of images. The growth of digital world Detection and Extraction of text regions in an image are...
Utility Mining Algorithm for High Utility Item sets from Transactional Databases
The discovery of item sets with high utility like profits is referred by mining high utility item sets from a transactional database. Although in recent years a number of relevant algorithms have been proposed, for high...
Survey of Machine Learning Techniques in Textual Document Classification
Classification of Text Document points towards associating one or more predefined categories based on the likelihood expressed by the training set of labeled documents. Many machine learning algorithms plays &nbs...