MSpace - DSpace at UofM >
Faculty of Graduate Studies (Electronic Theses and Dissertations) >
FGS - Electronic Theses & Dissertations (Public) >

Please use this identifier to cite or link to this item:

Title: Parallel algorithm design and implementation of regular/irregular problems: an in-depth performance study on graphics processing units
Authors: Solomon, Steven
Supervisor: Thulasiraman, Parimala (Computer Science)
Examining Committee: Domaratzki, Michael (Computer Science) Lui, Shaun (Mathematics)
Graduation Date: February 2012
Keywords: Parallel Computing
Combinatorial Optimization
Regular/Irregular Problems
Option Pricing
Particle Swarm Optimization
Issue Date: 16-Jan-2012
Abstract: Recently, 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.
Appears in Collection(s):FGS - Electronic Theses & Dissertations (Public)

Files in This Item:

File Description SizeFormat
solomon_steven.pdf3.04 MBAdobe PDFView/Open
View Statistics

Items in MSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! MSpace Software Copyright © 2002-2010  Duraspace - Feedback