MajorK: Majority Based <i>k</i>mer Matching in Commodity DRAM
Zuher Jahshan, Leonid Yavits
Abstract
Fast parallel search capabilities on large datasets are required across multiple application domains. One such domain is genome analysis, which requires high-performance kmer matching in large genome databases. Recently proposed solutions implemented kmer matching in DRAM, utilizing its sheer capacity and parallelism. However, their operation is essentially bit-serial, which ultimately limits the performance, especially when matching long strings, as customary in genome analysis pipelines. The proposed solution, MajorK, enables bit-parallel majority based kmer matching in an unmodified commodity DRAM. MajorK employs multiple DRAM row activation, where the search patterns (query kmers) are coded into DRAM addresses. We evaluate MajorK on viral genome kmer matching and show that it can achieve up to 2.7 X higher performance while providing a better matching accuracy compared to state-of-the-art DRAM based kmer matching accelerators.