Show simple item record

dc.contributor.advisorBurtscher, Martin
dc.contributor.authorJaiganesh, Jayadharini ( )
dc.date.accessioned2017-05-16T13:21:18Z
dc.date.available2017-05-16T13:21:18Z
dc.date.created2017-05
dc.date.issued2017-04-07
dc.identifier.urihttps://digital.library.txstate.edu/handle/10877/6570
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.formatText
dc.format.extent66 pages
dc.format.medium1 file (.pdf)
dc.language.isoen_US
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
txstate.documenttypeThesis
dc.contributor.committeeMemberQasem, Apan
dc.contributor.committeeMemberMetsis, Vangelis
thesis.degree.departmentComputer Science
thesis.degree.disciplineComputer Scienceen_US
thesis.degree.grantorTexas State Universityen_US
thesis.degree.levelMasters
thesis.degree.nameMaster of Science
txstate.departmentComputer Science


Download

Thumbnail

This item appears in the following Collection(s)

Show simple item record