Mapping – BWA-MEM
Mapping is a fundamental task in genomics. BWA-MEM is an implementation based on the FM-index data structure which used the Burrows-Wheeler transform (BWT). BWA-MEM is commonly used in many bioinformatics pipelines. The study showed that BWA-MEM’s data structure, the FM-index, is not adapted to PIM architecture.
Bloom Filters and Graph Algorithms
De Bruijn graphs are a central data structure to process genomic reads. To handle huge volumes of reads more easily and perform computational analyses faster, libraries may rely on efficient compact structures, such as Bloom filters, to build this graph. To improve further these processes, it is critical to understand the shortcomings of current approaches. Therefore, we investigate the performances of Bloom filters and several de Bruijn graph algorithms that use them. In particular, our analysis aims at identifying their memory footprint.
Study report
https://gitlab.inria.fr/pim/pim-analysis
https://gitlab.inria.fr/pim/gatb-core
Mapping – Minimap2
This work focus on profiling the widely used program Minimap2 to understand its bottlenecks and evaluate whether it could benefit from processing-in-memory (PIM) accelerators. We showed that the Minimap2 chaining stage becomes the most prevalent bottleneck when mapping reads with low divergence from the reference genome due to sequential constraints. Besides, the micro-instruction pipeline does not exhibit particular stalls regarding memory management. We conclude that the Minimap2 seed-chain-align paradigm may not be the best fit for an implementation on the UPMEM PIM architecture.
Study report
https://github.com/fdemoor2/minimap2-instrument
Genome matching – COBS
As bacterial databases are growing exponentially, finding genes or mutations require efficient and fast algorithms to perform approximate pattern matching of a query against a set of genomes. It is thus essential to assess the potential of modern processors and hardware accelerators for such task. We devise a proof-of-concept implementation on the UPMEM PiM architecture and compare it to a CPU-only equivalent that uses SIMD instructions. Our evaluation shows that the PiM program scales better as the database size increases, but suffers from the lack of vectorized instructions and fails to achieve significant speed-ups.
