hLCS. A Hybrid GPGPU Approach for Solving Multiple Short and Unbalanced LCS Problems
hLCS. A Hybrid GPGPU Approach for Solving Multiple Short and Unbalanced LCS Problems
复制标题
DOI：
10.1007/978-3-319-09153-2_8
复制
发表时间：
2014-06
期刊：
影响因子：
--
通讯作者：
Pedro Valero-Lara
中科院分区：
文献类型：
--
作者：
Pedro Valero-Lara
“最长公共子序列”是相似性搜索界中使用最广泛和众所周知的方法之一，适用于广泛的领域。目前，基于现代多核 CPU 和 GPU 的系统提供了令人印象深刻的性价比，并且是一个有吸引力的测试平台，可以加快响应时间并增加每秒解决的问题数量。使用 GPU 进行序列比对已广泛应用于生物信息学应用。然而，我们专注于将该算法应用于其他问题，这需要一种新的、不同的方法。特别是，最重要的差异在于序列的模式。一方面，生物序列的大小较大且相似，另一方面，其他应用中的序列较短且不平衡。此外，这项工作的目标是使用一个多核 CPU 和 GPU 系统同时计算多个问题，而不是只计算一个问题。这项工作的主要贡献是一种新的混合方法，它将两种经典的并行技术结合起来解决我们在两个不同阶段的问题。对于我们的特定问题，即解决短序列和不平衡序列上的多个“最长公共子序列”问题，每秒解决问题的比例很高，就加速而言，这种新实现分别比顺序和多核对应物快了 80 倍和 25 倍。
The “Longest Common Subsequence” is one of the most widely used and well-known methods within the similarity search community, applicable to a wide range of fields. Currently, modern multicore CPU and GPU-based systems offer an impressive cost/performance ratio and are an attractive test platform to accelerate response time and increase the number of problems solved per second. The use of GPUs for carrying out sequences alignment is widely extended for bioinformatics applications. However, we focus on the use of this algorithm applied to other problems which supposes a new and different approach. In particular, the most important difference is found in the pattern of the sequences. While, on one hand, the size of the biological sequences are large and similar, on the other hand, the sequences in other applications are short and unbalanced. Furthermore, this work aims to use one multicore CPU and GPU system for computing multiple problems simultaneously instead of computing only one. The main contribution of this work is a new hybrid approach which combines the two classical parallel techniques for our problem in two different phases. This new implementation is up to 80× and 25× faster, in terms of speedup, over the sequential and multicore counterpart respectively for our particular problem, that is, solving multiple “Longest Common Subsequence” problems on short and unbalanced sequences with a high ratio of problems solved per second.