Parallel Longest Common SubSequence Analysis In Chapel
Parallel Longest Common SubSequence Analysis In Chapel
复制标题
DOI：
10.1109/hpec58863.2023.10363472
复制
发表时间：
2023-09
期刊：
影响因子：
--
通讯作者：
Soroush Vahidi;B. Schieber;Zhihui Du;David A. Bader
中科院分区：
文献类型：
--
作者：
Soroush Vahidi;B. Schieber;Zhihui Du;David A. Bader
字符串算法领域最关键的问题之一是最长公共子序列问题（LCS）。对于任意数量的字符串，该问题是 NP 困难的，但对于固定数量的字符串，可以在多项式时间内解决。在本文中，我们选择了一种典型的并行LCS算法，并将其集成到我们的大规模串分析算法库中，以支持不同类型的大串分析。具体来说，我们利用高级并行语言Chapel，将Lu和Liu的并行LCS算法集成到开源框架Arkouda中。通过Arkouda，数据科学家可以从前端Python接口轻松处理后端高性能计算资源上的大型字符串分析。 Chapel支持的并行LCS算法可以识别两个字符串的最长公共子序列，并给出实验结果来说明并行资源的数量和输入字符串的长度如何影响算法的性能。
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.