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, Güney Kore, 15 - 18 Aralık 2013, ss.69-77 identifier identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Doi Numarası: 10.1109/icpads.2013.22
  • Basıldığı Şehir: Seoul
  • Basıldığı Ülke: Güney Kore
  • Sayfa Sayıları: ss.69-77
  • Hacettepe Üniversitesi Adresli: Hayır

Özet

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.