Show simple item record

dc.contributor.advisorKim, Hyesoon
dc.contributor.authorBangalore Lakshminarayana, Nagesh
dc.date.accessioned2015-01-12T20:51:24Z
dc.date.available2015-01-12T20:51:24Z
dc.date.created2014-12
dc.date.issued2014-11-17
dc.date.submittedDecember 2014
dc.identifier.urihttp://hdl.handle.net/1853/53058
dc.description.abstractMechanisms for improving the execution efficiency of graph algorithms on Data-Parallel Architectures were proposed and identified. Execution of graph algorithms on GPGPU architectures, the prevalent data-parallel architectures was considered. Irregular and data dependent accesses in graph algorithms were found to cause significant idle cycles in GPGPU cores. A prefetching mechanism that reduced the amount of idle cycles by prefetching a data-dependent access pattern found in graph algorithms was proposed. Storing prefetches in unused spare registers in addition to storing them in the cache was shown to be more effective by the prefetching mechanism. The design of the cache hierarchy for graph algorithms was explored. First, an exclusive cache hierarchy was shown to be beneficial at the cost of increased traffic; a region based exclusive cache hierarchy was shown to be similar in performance to an exclusive cache hierarchy while reducing on-chip traffic. Second, bypassing cache blocks at both the level one and level two caches was shown to be beneficial. Third, the use of fine-grained memory accesses (or cache sub-blocking) was shown to be beneficial. The combination of cache bypassing and fine-grained memory accesses was shown to be more beneficial than applying the two mechanisms individually. Finally, the impact of different implementation strategies on algorithm performance was evaluated for the breadth first search algorithm using different input graphs and heuristics to identify the best performing implementation for a given input graph were also discussed.
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technology
dc.subjectGraph algorithms
dc.subjectData-parallel architectures
dc.subjectGPGPU architectures
dc.subjectPrefetching
dc.subjectCache hierarchy
dc.subjectInclusion property
dc.subjectCache bypass
dc.subjectFine-grained accesses
dc.subjectBFS characterization
dc.titleEfficient graph algorithm execution on data-parallel architectures
dc.typeDissertation
dc.description.degreePh.D.
dc.contributor.departmentComputer Science
thesis.degree.levelDoctoral
dc.contributor.committeeMemberPande, Santosh
dc.contributor.committeeMemberPrvulovic, Milos
dc.contributor.committeeMemberQureshi, Moinuddin K.
dc.contributor.committeeMemberVuduc, Richard W.
dc.date.updated2015-01-12T20:51:24Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record