Fine-grain acceleration of graph algorithms on a heterogeneous chip

dc.contributor.advisorErez, Mattan
dc.creatorEryilmaz, Cagri
dc.date.accessioned2017-07-14T22:08:48Z
dc.date.available2017-07-14T22:08:48Z
dc.date.issued2017-05
dc.date.submittedMay 2017
dc.date.updated2017-07-14T22:08:48Z
dc.description.abstractWith the rise of heterogeneous chips available in the market, where integrated GPU cores and CPU cores reside in the same chip and share a unified memory, it is possible to have better execution schemes for many graph algorithms. Graph algorithms can exhibit producer-consumer behavior, a varying amount of parallelism during execution, and irregularity which results in inefficiency. The inefficiency problem could be solved by exploiting heterogeneity between cores. In this work, I provide an understanding of the executions of some graph algorithms in heterogeneous chips and accelerate their executions by using fine-grain software optimization techniques. To achieve this, I introduce two different fine-grain execution techniques to accelerate the Maximal Independent Set and Preflow-push graph algorithms, and present an evaluation of the techniques on a heterogeneous chip. My techniques, namely Overlapping Threads with Hot-Vertices and Task Switcher, provide 1.3x to 16x speedup over CPU-only execution depending on the input and the algorithm.
dc.description.departmentElectrical and Computer Engineering
dc.format.mimetypeapplication/pdf
dc.identifierdoi:10.15781/T2H98ZV0N
dc.identifier.urihttp://hdl.handle.net/2152/60447
dc.language.isoen
dc.subjectFine-grain
dc.subjectCPU
dc.subjectGPU
dc.subjectHeterogeneous
dc.subjectAPU
dc.subjectFine-grain acceleration
dc.subjectHeterogeneous chip
dc.titleFine-grain acceleration of graph algorithms on a heterogeneous chip
dc.typeThesis
dc.type.materialtext
thesis.degree.departmentElectrical and Computer Engineering
thesis.degree.disciplineElectrical and Computer Engineering
thesis.degree.grantorThe University of Texas at Austin
thesis.degree.levelMasters
thesis.degree.nameMaster of Science in Engineering

Access full-text files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
ERYILMAZ-THESIS-2017.pdf
Size:
1.4 MB
Format:
Adobe Portable Document Format

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
PROQUEST_LICENSE.txt
Size:
4.45 KB
Format:
Plain Text
Description:
No Thumbnail Available
Name:
LICENSE.txt
Size:
1.84 KB
Format:
Plain Text
Description: