An Efficient Connected Components Algorithm for Massively-Parallel Devices

Simple item page
dc.contributor.advisorBurtscher, Martin
dc.contributor.authorJaiganesh, Jayadharini
dc.contributor.committeeMemberQasem, Apan
dc.contributor.committeeMemberMetsis, Vangelis
dc.date.accessioned2017-05-16T13:21:18Z
dc.date.available2017-05-16T13:21:18Z
dc.date.issued2017-05
dc.description.abstractMassively-parallel devices such as GPUs are best suited for accelerating regular algorithms. Since the memory access patterns and control flow of irregular algorithms are data dependent, such programs are more difficult to parallelize in general and a direct parallelization may not yield good performance, on GPUs in particular. However, by carefully studying the underlying problem, it may be possible to derive new algorithms that are more suitable for massively-parallel accelerators. This thesis involves studying and analyzing such an irregular algorithm, called Connected Components, and proposes an efficient algorithm, called ECL, which is faster than the existing CC algorithms on most tested inputs. Though atomic operations are fast, they can represent a bottleneck as these operations run serially and might hinder performance in the future parallel devices. This thesis also proposes a synchronous and atomic-free algorithm, called ECLaf, whose performance is comparable to the fastest existing CC algorithm.
dc.description.departmentComputer Science
dc.formatText
dc.format.extent66 pages
dc.format.medium1 file (.pdf)
dc.identifier.citationJaiganesh, J. (2017). <i>An efficient connected components algorithm for massively-parallel devices</i> (Unpublished thesis). Texas State University, San Marcos, Texas.
dc.identifier.urihttps://hdl.handle.net/10877/6570
dc.language.isoen
dc.subjectGPU
dc.subjectConnected components
dc.subjectIrregular algorithm
dc.subjectParallel processing
dc.subject.lcshComputer scienceen_US
dc.subject.lcshParallel processing (Electronic computers)en_US
dc.titleAn Efficient Connected Components Algorithm for Massively-Parallel Devices
dc.typeThesis
thesis.degree.departmentComputer Science
thesis.degree.disciplineComputer Scienceen_US
thesis.degree.grantorTexas State Universityen_US
thesis.degree.levelMasters
thesis.degree.nameMaster of Science

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
JAIGANESH-THESIS-2017.pdf
Size:
1.87 MB
Format:
Adobe Portable Document Format
Download

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
LICENSE.txt
Size:
2.13 KB
Format:
Plain Text
Description:
Download

Collections

Graduate Theses and Dissertations