An FM-index Based High-Throughput Memory-Efficient FPGA Accelerator for Paired-end Short-read Mapping

Chung Hsuan Yang, Yi Chung Wu, Yen Lung Chen, Chao Hsi Lee, Jui Hung Hung, Chia Hsiang Yang

研究成果: Article同行評審

1 引文 斯高帕斯(Scopus)


This paper presents an Ferragina-Manzini index (FM-index) based paired-end short-read mapping hardware accelerator. Four techniques are proposed to significantly reduce the number of memory accesses and operations to improve the throughput. First, an interleaved data structure is proposed to reduce the processing time by 51.8% by leveraging the data locality. Second, the boundaries of possible mapping location candidates can be retrieved within only one memory access by constructing a lookup table along with the FM-index. This reduces the number of DRAM accesses by 60% with only a 64MB memory overhead. Third, an additional step is added to skip the time-consuming repetitive location candidates filtering conditionally, avoiding unnecessary operations. Lastly, an early termination method is proposed to terminate the mapping process if any location candidate with a high enough alignment score is detected, greatly decreasing the execution time. Overall, the computation time is reduced by 92.6% with only a 2% memory overhead in DRAM. The proposed methods are realized on a Xilinx Alveo U250 FPGA. The proposed FPGA accelerator processes 1,085,812,766 short-reads from the U.S. Food and Drug Administration (FDA) dataset within 35.4 minutes at 200MHz. It achieves a 1.7-to-18.6× higher throughput and the highest 99.3% accuracy by exploiting the paired-end short-read mapping, compared to state-of-the-art FPGA-based designs.

頁(從 - 到)1-11
期刊IEEE Transactions on Biomedical Circuits and Systems
出版狀態Accepted/In press - 2023


深入研究「An FM-index Based High-Throughput Memory-Efficient FPGA Accelerator for Paired-end Short-read Mapping」主題。共同形成了獨特的指紋。