Show simple item record

dc.contributor.advisorBader, David A.
dc.contributor.authorMcLaughlin, Adam
dc.date.accessioned2016-01-07T17:24:46Z
dc.date.available2016-01-07T17:24:46Z
dc.date.created2015-12
dc.date.issued2015-09-29
dc.date.submittedDecember 2015
dc.identifier.urihttp://hdl.handle.net/1853/54374
dc.description.abstractThe stagnant performance of single core processors, increasing size of data sets, and variety of structure in information has made the domain of parallel and high-performance computing especially crucial. Graphics Processing Units (GPUs) have recently become an exciting alternative to traditional CPU architectures for applications in this domain. Although GPUs are designed for rendering graphics, research has found that the GPU architecture is well-suited to algorithms that search and analyze unstructured, graph-based data, offering up to an order of magnitude greater memory bandwidth over their CPU counterparts. This thesis focuses on GPU graph analysis from the perspective that algorithms should be efficient on as many classes of graphs as possible, rather than being specialized to a specific class, such as social networks or road networks. Using betweenness centrality, a popular analytic used to find prominent entities of a network, as a motivating example, we show how parallelism, distributed computing, hybrid and on-line algorithms, and dynamic algorithms can all contribute to substantial improvements in the performance and energy-efficiency of these computations. We further generalize this approach and provide an abstraction that can be applied to a whole class of graph algorithms that require many simultaneous breadth-first searches. Finally, to show that our findings can be applied in real-world scenarios, we apply these techniques to the problem of verifying that a multiprocessor complies with its memory consistency model.
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technology
dc.subjectParallel algorithms
dc.subjectGPUs
dc.subjectGraph algorithms
dc.subjectMemory consistency verification
dc.subjectEnergy-efficiency
dc.subjectHigh performance computing
dc.titleMapping parallel graph algorithms to throughput-oriented architectures
dc.typeDissertation
dc.description.degreePh.D.
dc.contributor.departmentElectrical and Computer Engineering
thesis.degree.levelDoctoral
dc.contributor.committeeMemberYalamanchili, Sudhakar
dc.contributor.committeeMemberLanterman, Aaron
dc.contributor.committeeMemberVuduc, Richard
dc.contributor.committeeMemberClements, Mark
dc.date.updated2016-01-07T17:24:46Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record