Parallel Longest Common Subsequence using Graphics Hardware

Simple item page
dc.contributor.authorKloetzli, Johnen_US
dc.contributor.authorStrege, Brianen_US
dc.contributor.authorDecker, Jonathanen_US
dc.contributor.authorOlano, Marcen_US
dc.contributor.editorJean M. Favre and Kwan-Liu Maen_US
dc.date.accessioned2014-01-26T16:43:25Z
dc.date.available2014-01-26T16:43:25Z
dc.date.issued2008en_US
dc.description.abstractWe 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.en_US
dc.description.seriesinformationEurographics Symposium on Parallel Graphics and Visualizationen_US
dc.identifier.isbn978-3-905674-04-0en_US
dc.identifier.issn1727-348Xen_US
dc.identifier.urihttps://doi.org/10.2312/EGPGV/EGPGV08/057-064en_US
dc.publisherThe Eurographics Associationen_US
dc.titleParallel Longest Common Subsequence using Graphics Hardwareen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
057-064.pdf
Size:
317.74 KB
Format:
Adobe Portable Document Format
Download
Collections
EGPGV08: Eurographics Symposium on Parallel Graphics and Visualization