Parallel algorithm design and implementation of regular/irregular problems: an in-depth performance study on graphics processing units

Simple item page
dc.contributor.authorSolomon, Steven
dc.contributor.examiningcommitteeDomaratzki, Michael (Computer Science) Lui, Shaun (Mathematics)en_US
dc.contributor.supervisorThulasiraman, Parimala (Computer Science)en_US
dc.date.accessioned2012-01-17T00:17:36Z
dc.date.available2012-01-17T00:17:36Z
dc.date.issued2012-01-16
dc.degree.disciplineComputer Scienceen_US
dc.degree.levelMaster of Science (M.Sc.)en_US
dc.description.abstractRecently, interest in the Graphics Processing Unit (GPU) for general purpose parallel applications development and research has grown. Much of the current research on the GPU focuses on the acceleration of regular problems, as irregular problems typically do not provide the same level of performance on the hardware. We explore the potential of the GPU by investigating four problems on the GPU with regular and/or irregular properties: lookback option pricing (regular), single-source shortest path (irregular), maximum flow (irregular), and the task matching problem using multi-swarm particle swarm optimization (regular with elements of irregularity). We investigate the design, implementation, optimization, and performance of these algorithms on the GPU, and compare the results. Our results show that the regular problem achieves greater performance and requires less development effort than the irregular problems. However, we find the GPU to still be capable of providing high levels of acceleration for irregular problems.en_US
dc.description.noteFebruary 2012en_US
dc.identifier.urihttp://hdl.handle.net/1993/5098
dc.language.isoengen_US
dc.rightsopen accessen_US
dc.subjectParallel Computingen_US
dc.subjectGPUen_US
dc.subjectCUDAen_US
dc.subjectCombinatorial Optimizationen_US
dc.subjectRegular/Irregular Problemsen_US
dc.subjectOption Pricingen_US
dc.subjectParticle Swarm Optimizationen_US
dc.titleParallel algorithm design and implementation of regular/irregular problems: an in-depth performance study on graphics processing unitsen_US
dc.typemaster thesisen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
solomon_steven.pdf
Size:
2.98 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
2.25 KB
Format:
Item-specific license agreed to upon submission
Description:
Download
Collections
FGS - Electronic Theses and Practica