Parallel Longest Common Subsequence using Graphics Hardware
Loading...
Date
2008
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association
Abstract
We present an algorithm for solving the Longest Common Subsequence problem using graphics hardware accel- eration. We identify a parallel memory access pattern which enables us to run efficiently on multiple layers of parallel hardware by matching each layer to the best sub-algorithm, which is determined using a mix of theoretical and experimental data including knowledge of the specific hardware and memory structure of each layer. We implement a linear-space, cache-coherent algorithm on the CPU, using a two-level algorithm on the GPU to com- pute subproblems quickly. The combination of all three running on a CPU/GPU pair is a fast, flexible and scalable solution to the Longest Common Subsequence problem. Our design method is applicable to other algorithms in the Gaussian Elimination Paradigm, and can be generalized to more levels of parallel computation such as GPU clusters.
Description
@inproceedings{10.2312:EGPGV/EGPGV08/057-064,
booktitle = {Eurographics Symposium on Parallel Graphics and Visualization},
editor = {Jean M. Favre and Kwan-Liu Ma},
title = {{Parallel Longest Common Subsequence using Graphics Hardware}},
author = {Kloetzli, John and Strege, Brian and Decker, Jonathan and Olano, Marc},
year = {2008},
publisher = {The Eurographics Association},
ISSN = {1727-348X},
ISBN = {978-3-905674-04-0},
DOI = {10.2312/EGPGV/EGPGV08/057-064}
}