Parallel Longest Common Subsequence using Graphics Hardware

Kloetzli, John; Strege, Brian; Decker, Jonathan; Olano, Marc

Parallel Longest Common Subsequence using Graphics Hardware

Files

057-064.pdf (317.74 KB)

Date

2008

Authors

Kloetzli, John
Strege, Brian
Decker, Jonathan
Olano, Marc

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.

        @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
}
}