Back to search

Clemson University

Analysis and Implementation of Room Assignment Problem and Cannon's Algorithm on General Purpose Programmable Graphical Processing Units with CUDA

Abstract

dc:description.abstract

General-purpose Graphics Processing Units (GP-GPU) has emerged as a popular computing paradigm for high-performance computing over the last few years. The increased interest in GP-GPUs for parallel computing mirrors the trend in general computing with the rise of multi-core processors as an alternative approach to increase processor performance. Many applications that were previously accelerated on distributed processing platforms with MPI or multithreaded techniques such as OpenMP are now being investigated to assess their performance on GP-GPU platforms. Since the GP-GPU platform is designed to give higher performance for parallel problems, applications on other parallel architectures are good candidates for performance studies on GP-GPUs. The first case study in this research is a GP-GPU implementation of a Simulated Annealing-based solution of the Room Assignment problem using CUDA. The Room Assignment problem attempts to arrange N people in N/2 rooms, taking into consideration each person's preference for a roommate. To evaluate the implementation, it was compared against the serial implementation for problem sizes 5000, 10000, 15000 and 20000 people. The GP-GPU implementation achieved as much as 78% higher improvement ratio than the serial version in comparable execution time. The second case study is a GP-GPU implementation of Cannon's Algorithm using CUDA. The GP-GPU implementation is compared with a serial implementation of a conventional matrix multiplication O(n3). The GP-GPU implementation achieved upto 6.2x speedup over the conventional serial multiplication. The results for both applications with varying problem sizes are presented and discussed.

Degree

thesis:*
Name thesis:degree_name
Master of Science (MS)
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Computer Engineering

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Dwivedi, Harsh vardhan
Contributors dc:contributor
  • Smith, Melissa C.
  • Ligon , Walter B.
  • Oehsen , J. Barr von

Subjects

dc:subject × 1

Identifiers

dc:identifier.*
Repository record dc:identifier
https://open.clemson.edu/all_theses/1234

Chain of custody

source
Harvested from
Clemson University
Base URL
open.clemson.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Dwivedi, Harsh vardhan. Analysis and Implementation of Room Assignment Problem and Cannon's Algorithm on General Purpose Programmable Graphical Processing Units with CUDA. Thesis thesis, https://open.clemson.edu/all_theses/1234