Abstract
In computational biology, biological database search has been playing a very important role. Since the COVID-19 outbreak, it has provided significant help in identifying common characteristics of viruses and developing vaccines and drugs. Sequence alignment, a method finding similarity, homology and other information between gene/protein sequences, is the usual tool in the database search. With the explosive growth of biological databases, the search process has become extremely time-consuming. However, existing parallel sequence alignment algorithms cannot deliver efficient database search due to low utilization of the resources such as cache memory and performance issues such as load imbalance and high communication overhead. In this paper, we propose an efficient sequence alignment algorithm on Sunway TaihuLight, called ESA, for biological database search. ESA adopts a novel hybrid alignment algorithm combining local and global alignments, which has higher accuracy than other sequence alignment algorithms. Further, ESA has several optimizations including cache-aware sequence alignment, capacity-aware load balancing and bandwidth-aware data transfer. They are implemented in a heterogeneous processor SW26010 adopted in the world’s 6th fastest supercomputer, Sunway TaihuLight. The implementation of ESA is evaluated with the Swiss-Prot database on Sunway TaihuLight and other platforms. Our experimental results show that ESA has a speedup of 34.5 on a single core group (with 65 cores) of Sunway TaihuLight. The strong and weak scalabilities of ESA are tested with 1 to 1024 core groups of Sunway TaihuLight. The results show that ESA has linear weak scalability and very impressive strong scalability. For strong scalability, ESA achieves a speedup of 338.04 with 1024 core groups compared with a single core group. We also show that our proposed optimizations are also applicable to GPU, Intel multicore processors, and heterogeneous computing platforms.
•In this paper, we propose and implement an efficient sequence alignment algorithm, ESA, for biological database search on SW26010 heterogeneous processors. This algorithm adopts both local and global alignments for biological database search with several optimizations. ESA achieves high computational performance without sacrificing accuracy. To the best of our knowledge, this is the first attempt to parallelize hybrid sequence alignment on Sunway TaihuLight using multi-level optimizations.•We propose three optimization strategies in ESA: cache-aware sequence alignment, capacity-aware load balancing and bandwidth-aware data transfer. Cache-aware sequence alignment effectively reduces the size of the data structure for sequence alignment and fully utilizes the vectorization of the slave cores of SW26010. With capacity-aware load balancing, we distribute the workload evenly among the cores of SW26010. With bandwidth-aware data transfer, ESA reduces the communication overhead by using asynchronous DMA transmission and RLC.•We evaluate the performance of ESA using the Swiss-Prot database on Sunway TaihuLight. Our experimental results show that ESA achieves a speedup of 34.5 times on a single CG over the manager core. Compared with a serial implementation on Intel (R) Xeon (R) CPU E5-2620 v4 processor, ESA achieves a speedup of 21.6 on a single CG. We also demonstrate that ESA has linear weak scalability and very competitive strong scalability. Finally, we compare ESA with mainstream algorithms on the CPU+GPU platform and achieve the highest GCUPS of 228.91.