high performance computing on graphics processing units: hgpu.org

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.