Achieving TeraCUPS on Longest Common Subsequence Problem using GPGPUs

Ozsoy A., CHAUHAN A., Swany M.

19th IEEE International Conference on Parallel and Distributed Systems (ICPADS), Seoul, South Korea, 15 - 18 December 2013, pp.69-77, (Full Text) identifier identifier

  • Publication Type: Conference Paper / Full Text
  • Doi Number: 10.1109/icpads.2013.22
  • City: Seoul
  • Country: South Korea
  • Page Numbers: pp.69-77
  • Hacettepe University Affiliated: No

Abstract

In this paper, we describe a novel technique to optimize longest common subsequence (LCS) algorithm for one-to-many matching problem on GPUs by transforming the computation into bit-wise operations and a post-processing step. The former can be highly optimized and achieves more than a trillion operations (cell updates) per second (CUPS)-a first for LCS algorithms. The latter is more efficiently done on CPUs, in a fraction of the bit-wise computation time. The bit-wise step promises to be a foundational step and a fundamentally new approach to developing algorithms for increasingly popular heterogeneous environments that could dramatically increase the applicability of hybrid CPU-GPU environments.