A Block-Based Systolic Array on an HBM2 FPGA for DNA Sequence Alignment
A Block-Based Systolic Array on an HBM2 FPGA for DNA Sequence Alignment
复制标题
HBM2 FPGA 上基于块的脉动阵列用于 DNA 序列比对
DOI：
10.1007/978-3-030-44534-8_23
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Ben Abdelhamid Riadh and Yamaguchi Yoshiki
中科院分区：
文献类型：
--
作者：
Ben Abdelhamid Riadh and Yamaguchi Yoshiki
揭示一对基因组序列之间的最佳局部相似性是生物信息学中最基本的问题之一。史密斯-沃特曼算法就是为此特定目的而开发的一种方法。随着计算机领域的不断进步，该方法得到了广泛的应用，甚至在网络数据包检测和模式匹配等领域也得到了广泛的应用。该算法基于动态规划，保证找到两个碱基对之间最优的局部序列比对。计算复杂度为0 (mn)，其中需求分别定义为查询和数据库序列的元素数量。研究人员已经研究了几种使用CPU、GPU、Cell b.e.和FPGA加速计算的方法。他们中的大多数人都提出了数据重用方法，因为Smith-Waterman算法具有相当高的“每次操作字节数”；换句话说，史密斯-沃特曼算法需要很大的内存带宽。在本文中，我们试图通过实现基于块的收缩阵列方法来最小化内存带宽瓶颈的影响，该方法可以最大限度地利用HBM2（高带宽内存）中的内存库。与以前报道的最佳案例之一相比，所提出的方法在GCUPS （Giga Cell Update Per Second）方面表现出更高的性能，并且在功率效率方面也取得了显着改善。例如，我们的实现可以达到429.39 GCUPS，同时实现7.68 GCUPS/W的功率效率。在不同的配置下，它可以达到316.73 GCUPS，峰值功率效率为8.86 GCUPS/W。
Revealing the optimal local similarity between a pair of genomic sequences is one of the most fundamental issues in bioinformatics. The Smith-Waterman algorithm is a method that was developed for that specific purpose. With the continuous advances in the computer field, this method becomes widely used to an extent where it expanded its reach to cover a broad range of applications, even in areas such as network packet inspections and pattern matching. This algorithm is based on Dynamic Programming and is guaranteed to find the optimal local sequence alignment between two base pairs. The computational complexity is O(mn), wheremandnare defined as the number of the elements of a query and a database sequence, respectively. Researchers have investigated several manners to accelerate the calculation using CPU, GPU, Cell B.E., and FPGA. Most of them have proposed a data-reuse approach because the Smith-Waterman algorithm has rather high “bytes per operation”; in other words, the Smith-Waterman algorithm requires large memory bandwidth. In this paper, we try to minimize the impact of the memory bandwidth bottleneck through the implementation of a block-based systolic array approach that maximizes the usage of memory banks in HBM2 (High Bandwidth Memory). The proposed approach demonstrates a higher performance in terms of GCUPS (Giga Cell Update Per Second) compared to one of the best cases reported in previous works, and also achieves a significant improvement in power efficiency. For example, our implementation could reach 429.39 GCUPS while achieving a power efficiency of 7.68 GCUPS/W. With a different configuration, it could reach 316.73 GCUPS while hitting a peak power efficiency of 8.86 GCUPS/W.