Thread-cooperative, bit-parallel computation of levenshtein distance on GPU
Alejandro Chacón, Santiago Marco‐Sola, Antonio Espinosa, Paolo Ribeca, Juan Carlos Moure · 2014
Approximate string matching is a very important problem in computational biology; it requires the fast computation of string distance as one of its essential components. Myers' bit-parallel algorithm improves the classical dynamic programming approach to Levenshtein distance computation, and offers competitive performance on CPUs. The main challenge when designing an efficient GPU implementation is to expose enough SIMD parallelism while at the same time keeping a relatively small working set for each thread.