Back to search

Michigan Technological University

Analysis and performance of a UPC implementation of a parallel longest common subsequence algorithm

Abstract

dc:description.abstract

An important problem in computational biology is finding the longest common subsequence (LCS) of two nucleotide sequences. This paper examines the correctness and performance of a recently proposed parallel LCS algorithm that uses successor tables and pruning rules to construct a list of sets from which an LCS can be easily reconstructed. Counterexamples are given for two pruning rules that were given with the original algorithm. Because of these errors, performance measurements originally reported cannot be validated. The work presented here shows that speedup can be reliably achieved by an implementation in Unified Parallel C that runs on an Infiniband cluster. This performance is partly facilitated by exploiting the software cache of the MuPC runtime system. In addition, this implementation achieved speedup without bulk memory copy operations and the associated programming complexity of message passing.

Degree

thesis:*
Name thesis:degree_name
Master of Science in Computer Science (MS)
Level thesis:degree_level
Master's Thesis
Discipline thesis:degree_discipline
Department of Computer Science

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Franklin, Bryan M.
Contributors dc:contributor
  • Steven R Seidel

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Michigan Technological University
Base URL
digitalcommons.mtu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Franklin, Bryan M.. Analysis and performance of a UPC implementation of a parallel longest common subsequence algorithm. Master's Thesis thesis, https://doi.org/10.37099/mtu.dc.etds/184