Finding Longest Common Subsequences by GPU-Based Parallel Ant Colony Optimization

David Markvica
Fakultat fur Informatik der Technischen Universitat Wien
Universitat Wien, 2014


   title={Finding Longest Common Subsequences by GPU-Based Parallel Ant Colony Optimization},

   author={Markvica, David},



Download Download (PDF)   View View   Source Source   



The longest common subsequence (LCS) problem is one of the classic problems in string processing. It is commonly used in file comparison, pattern recognition, and computational biology as a measure of sequence similarity. Given a set of strings, the LCS is the longest string that is a subsequence of every string in the set. For an arbitrary number of strings the LCS problem is NP-complete. Heuristic approaches are needed to process datasets of hundreds of sequences, each thousands of character in length, that are common place in computational biology. This master thesis presents a parallel hybrid metaheuristic combining an Ant Colony Optimization with a Local Search. The heuristic is designed from the ground up to exploit the capabilities of many-core processor architectures, such as Graphics Processing Units (GPUs). The Ant Colony Optimization constructs numerous solutions simultaneously and the Local Search employs a highly parallel enumeration to explore neighborhoods. The algorithm was implemented using OpenCL, a framework for parallel programming of heterogeneous systems. The result is a single program that is capable of running on two different processor architectures, on CPUs and on GPUs. A number of micro benchmarks are performed to highlight the different performance characteristics of the tested architectures and to show that the algorithm scales linearly with the number of processor cores used. Finally the implementation is benchmarked on a dataset commonly used in the LCS literature. It will be shown that the presented approach outperforms previously described methods based on Ant Colony Optimization in terms of solution quality.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2024 hgpu.org

All rights belong to the respective authors

Contact us: