Adnan Ozsoy passed his Final Dissertation Defense for Ph.D. in Computer Science!

Title: Bit-vector Strategies for String Matching Algorithms on GPGPUs

Abstract: The use of general purpose graphic processing units (GPGPUs) in high performance computing and parallel programming has had a striking impact in many areas, such as medical fields, energy sciences, image/video processing, and finance. A popular method to utilize GPUs is to parallelize existing sequential algorithms. The main parallelization approach applied to many applications is to parallelize the best known sequential algorithm and then attempt to optimize the parallel version for GPUs. However, this approach generates solutions, which are only limited to a single application, and they often do not fully utilize the resources on a GPU.

String matching is one of the domains that has been explored for parallelization using GPGPUs. However, current solutions fail to achieve the performance potential of the current GPGPU hardware. This dissertation aims to address the effective use of GPUs in this domain through bit-parallelism. We rephrase string-matching algorithms using bit-vector operations. The resulting algorithms not only expose bit-level parallelism, more effectively utilizing the large number of light-weight GPU threads, but also exhibit significantly reduced control flow divergence, eliminating a major source of potential inefficiency on contemporary GPGPUs. The thesis of this dissertation is that several string-matching algorithms that are apparently not data-parallel can be made more conducive to data-parallel execution by rewriting those in terms of bit-vector operations. Such rewriting leads to easily identifiable highly data-parallel portions in the algorithms that are suitable for GPGPUs. High overall performance can then be achieved by a combination of GPGPUs and CPUs that corresponds naturally to the popular heterogeneous architectures of modern high performance computers. In order to support the thesis, this dissertation presents the decomposition of several string matching problems into bit parallel portions, provides GPU porting strategies for each problem, and analyzes algorithms in detail.

Congratulations, Adnan! Well done!

People: 
Date: 
Thursday, May 8, 2014
News media: 
Flag: 
News & Events
Personnel Ref: 
153
----------