EXMA: A Genomics Accelerator for Exact-Matching
EXMA: A Genomics Accelerator for Exact-Matching
复制标题
DOI：
10.1109/hpca51647.2021.00041
复制
发表时间：
2021-01
期刊：
影响因子：
--
通讯作者：
Lei Jiang;Farzaneh Zokaee
中科院分区：
文献类型：
--
作者：
Lei Jiang;Farzaneh Zokaee
基因组学是精准医疗、全球粮食安全和病毒监测的基础。精确匹配是基因组学中最重要的操作之一，广泛应用于基因组学的每一步，如比对、组装、注释和压缩。现代基因组学采用Ferragina-Manzini指数（FMIndex）增强空间效率的Burrows-Wheeler变换（BWT）和额外的数据结构，以实现超快速的精确匹配操作。然而，FM-Index的空间局部性差和随机存储器访问模式是臭名昭著的。先前的工作创建了基于GPU、FPGA、ASIC甚至内存中进程（PIM）的加速器来提高FM-Index搜索吞吐量。虽然它们实现了最先进的FM-Index搜索吞吐量，但与所有先前的传统加速器一样，FM-Index pim在每个DRAM行激活后只处理一个DNA符号，因此内存带宽利用率很低。在本文中，我们提出了一个硬件加速器EXMA，以提高FM-Index的搜索吞吐量。我们首先使用基于多任务学习（MTL）的索引创建一个新的EXMA表，以便在每个DRAM行激活时处理多个DNA符号。然后我们构建一个加速器来搜索EXMA表。为了提高加速器的缓存命中率，我们提出了两阶段调度。为了提高DRAM主存的行缓冲区命中率，我们引入了动态页面策略。我们还提出了CHAIN压缩来减少EXMA表的数据结构大小。与最先进的FM-Index pim相比，EXMA将搜索吞吐量提高了4.9倍，并将每瓦特的搜索吞吐量提高了4.8倍。
Genomics is the foundation of precision medicine, global food security and virus surveillance. Exact-match is one of the most essential operations widely used in almost every step of genomics such as alignment, assembly, annotation, and compression. Modern genomics adopts Ferragina-Manzini Index (FMIndex) augmenting space-efficient Burrows-Wheeler transform (BWT) with additional data structures to permit ultra-fast exact-match operations. However, FM-Index is notorious for its poor spatial locality and random memory access pattern. Prior works create GPU-, FPGA-, ASIC- and even process-in-memory (PIM)based accelerators to boost FM-Index search throughput. Though they achieve the state-of-the-art FM-Index search throughput, the same as all prior conventional accelerators, FM-Index PIMs process only one DNA symbol after each DRAM row activation, thereby suffering from poor memory bandwidth utilization. In this paper, we propose a hardware accelerator, EXMA, to enhance FM-Index search throughput. We first create a novel EXMA table with a multi-task-learning (MTL)-based index to process multiple DNA symbols with each DRAM row activation. We then build an accelerator to search over an EXMA table. We propose 2-stage scheduling to increase the cache hit rate of our accelerator. We introduce dynamic page policy to improve the row buffer hit rate of DRAM main memory. We also present CHAIN compression to reduce the data structure size of EXMA tables. Compared to state-of-the-art FM-Index PIMs, EXMA improves search throughput by $4.9 \times$, and enhances search throughput per Watt by $4.8 \times$.