Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

A dynamic programming model to solve optimisation problems using GPUs

O'Connell, Jonathan F. 2017. A dynamic programming model to solve optimisation problems using GPUs. PhD Thesis, Cardiff University.
Item availability restricted.

[img]
Preview
PDF - Accepted Post-Print Version
Download (8MB) | Preview
[img] PDF - Supplemental Material
Restricted to Repository staff only

Download (5MB)

Abstract

This thesis presents a parallel, dynamic programming based model which is deployed on the GPU of a system to accelerate the solving of optimisation problems. This is achieved by simultaneously running GPU based computations, and memory transactions, allowing computation to never pause, and overcoming the memory constraints of solving large problem instances. Due to this some optimisation problems, which are currently not solved in an exact manner for real world sized instances due to their complexity, are moved into the solvable realm. The model is implemented to solve, a range of different test problems, where artificially constructed test data is used to ensure good performance even in the worst cases. Through this extensive testing, we can be confident the model will perform well when used to solve real world test cases. Testing of the model was carried out using a range of different implementation parameters in relation to deployment on the GPU, in order to identify both optimal implementation parameters, and how the model will operate when running on different systems. All problems, when implemented in parallel using the model, show run-time improvements compared to the sequential implementations, in some instances up to hundreds of times faster, but more importantly also show high efficiency metrics for the utilisation of GPU resources. Throughout testing emphasis has been placed on GPU based metrics to ensure the wider generic applicability of the model. Finally, the parallel model allows for new problems to be defined through the use of a simple file format, enabling wider usage of the model.

Item Type: Thesis (PhD)
Status: Unpublished
Schools: Computer Science & Informatics
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Uncontrolled Keywords: gpu, nvidia cuda, dynamic programming, optimisation problems, exact methods
Date of First Compliant Deposit: 1 February 2017
Last Modified: 04 Jun 2017 09:39
URI: http://orca-mwe.cf.ac.uk/id/eprint/97930

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics