Parallel Longest Common SubSequence Analysis In Chapel

Soroush Vahidi, Baruch Schieber, Zhihui Du, David A. Bader

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

One of the most critical problems in the field of string algorithms is the longest common subsequence problem (LCS). The problem is NP-hard for an arbitrary number of strings but can be solved in polynomial time for a fixed number of strings. In this paper, we select a typical parallel LCS algorithm and integrate it into our large-scale string analysis algorithm library to support different types of large string analysis. Specifically, we take advantage of the high-level parallel language, Chapel, to integrate Lu and Liu's parallel LCS algorithm into Arkouda, an open-source framework. Through Arkouda, data scientists can easily handle large string analytics on the back-end high-performance computing resources from the front-end Python interface. The Chapel-enabled parallel LCS algorithm can identify the longest common subsequences of two strings, and experimental results are given to show how the number of parallel resources and the length of input strings can affect the algorithm's performance.

Original languageEnglish (US)
Title of host publication2023 IEEE High Performance Extreme Computing Conference, HPEC 2023
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9798350308600
DOIs
StatePublished - 2023
Event2023 IEEE High Performance Extreme Computing Conference, HPEC 2023 - Virtual, Online, United States
Duration: Sep 25 2023Sep 29 2023

Publication series

Name2023 IEEE High Performance Extreme Computing Conference, HPEC 2023

Conference

Conference2023 IEEE High Performance Extreme Computing Conference, HPEC 2023
Country/TerritoryUnited States
CityVirtual, Online
Period9/25/239/29/23

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Modeling and Simulation
  • Artificial Intelligence
  • Computer Science Applications
  • Software
  • Media Technology
  • Computational Mathematics

Keywords

  • Chapel programming language
  • parallel computing
  • string algorithms

Fingerprint

Dive into the research topics of 'Parallel Longest Common SubSequence Analysis In Chapel'. Together they form a unique fingerprint.

Cite this