Parallel Algorithms for Counting Problems on Graphs Using Graphics Processing Units

Simple item page
dc.contributor.advisorRadhakrishnan, Sridhar
dc.contributor.authorChatterjee, Amlan
dc.contributor.committeeMemberKarabuk, Suleyman
dc.contributor.committeeMemberAntonio, John K.
dc.contributor.committeeMemberDhall, Sudarshan
dc.contributor.committeeMemberLakshmivarahan, Sivaramakrishnan
dc.date.accessioned2014-12-09T19:31:36Z
dc.date.available2014-12-09T19:31:36Z
dc.date.issued2014-12
dc.date.manuscript2014-12
dc.description.abstractThe availability of Graphics Processing Units (GPUs) with multicore architecture have enabled parallel computations using extensive multi-threading. Recent advancements in computer hardware have led to the usage of graphics processors for solving general purpose problems. Using GPUs for computation is a highly efficient and low-cost alternative as compared to currently available multicore Central Processing Units (CPUs). Also, in the past decade there has been tremendous growth in the World Wide Web and Online Social Networks. Social networking sites such as Facebook, Twitter and LinkedIn, with millions of users are a huge source of data. These data sets can be used for research in the fields of anthropology, social psychology, economics among others. Our research focuses on converting real-world problems into graph theoretic problems and using GPUs to solve them. The graph problems that we focus on in our research involve counting the number of subgraphs that satisfy a given property. For example, given a graph G=(V,E) and an integer k<=|V|, we provide algorithms to count the number of: a) connected subgraphs of size k; b) cliques of size k; and c) independent sets of size k, and other similar problems. Also, properties that are affected by the dynamic nature of the graphs i.e., addition or removal of edges or nodes, for example change in the number of triangles and connected components in the graph, are also studied. Sequential access to global memory and contention at the size-limited shared memory have been main impediments to fully exploiting potential performance in GPUs. Therefore, we propose novel memory storage and retrieval methods, based on using search techniques on graphs and converting it into trees, that enable parallel graph computations to overcome the above issues. We also analyze and utilize primitives such as memory access coalescing and avoiding partition camping that offset the increase in access latency of using a slower but larger global memory. In addition, we introduce graph compression techniques that further reduce memory requirements and overheads. Our experimental results for the GPU implementation show a significant speedup over the CPU counterpart for the problems described above.en_US
dc.identifier.urihttp://hdl.handle.net/11244/13860
dc.languageenen_US
dc.subjectGPUen_US
dc.subjectCUDAen_US
dc.subjectGraph Problemsen_US
dc.subjectParallel Algorithmsen_US
dc.subjectCounting Problemsen_US
dc.thesis.degreePh.D.en_US
dc.titleParallel Algorithms for Counting Problems on Graphs Using Graphics Processing Unitsen_US
ou.groupCollege of Engineering::School of Computer Scienceen_US

Files

Original bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
2014_Chatterjee_Amlan_Dissertation.pdf
Size:
2.61 MB
Format:
Adobe Portable Document Format
Description:
Complete Dissertation
Download
No Thumbnail Available
Name:
2014_Chatterjee_Amlan_Dissertation_NativeFormat.zip
Size:
8.74 MB
Format:
Unknown data format
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.72 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

OU - Dissertations