Performance improvement of BWA MEM algorithm using data-parallel with concurrent parallelization

摘要

Burrows-Wheeler Transform (BWT) is the widely used data compression technique in the next-generation sequencing (NGS) analysis. Due to the advancement in the NGS technology, the genome data size was increased rapidly and these higher volumes of genome data need to be processed by empirical parallelism. Generally, these NGS data will be processed by traditional parallel processing approaches like (i) thread parallelization (ii) Data parallelization and (iii) Concurrent parallelization, which are their own performance bottlenecks in, thread scalability, scattering/gathering of data and memory bandwidth limitations respectively. To eliminate these drawbacks, we introduced the hybrid parallelization approach called “data-parallel with concurrent parallelization” to process our genome alignment. We used BWA MEM algorithm for aligning human genome sequence, which are dominated by huge memory intensive operations and the performance is limited due to cache/TLB misses. To eliminate the cache/TLB miss, the genome data is partitioned into multiple pieces (i.e., reducing the read size) using data parallelization and concurrently processing these multiple pieces of genome data within the same cache/memory hierarchy. Hence, the performance of proposed data-parallel with concurrent parallelization is 45% better than traditional parallelization approaches. Additionally, we provided proof of concept to process higher volume of genome data using BWA MEM algorithm on the high-end desktop machines.