ASW: Accelerating Smith-Waterman Algorithm on Coupled CPU-GPU Architecture

Huihui Zou, Shanjiang Tang, Ce Yu, Hao Fu, Yusen Li, Wenjie Tang
College of Intelligence and Computing, Tianjin University, Tianjin, China
The 15th Annual IFIP International Conference on Network and Parallel Computing (NPC), 2018


   title={ASW: Accelerating Smith–Waterman Algorithm on Coupled CPU–GPU Architecture},

   author={Zou, Huihui and Tang, Shanjiang and Yu, Ce and Fu, Hao and Li, Yusen and Tang, Wenjie},

   journal={International Journal of Parallel Programming},





Download Download (PDF)   View View   Source Source   



Smith-waterman algorithm (SW) is a popular dynamic programming algorithm widely used in Bioinformatics for local biological sequence alignment. Due to the O(n2) high time and space complexity of SW and growing size of biological data, it is crucial to accelerate SW for high performance. In view of the GPU high efficiency in science computation, many existing studies(e.g., CUDAlign, CUDASW++) speedup SW with GPU. However, the strong data dependency makes SW communication intensive, and the previous works fail to fully leverage the heterogeneous capabilities of the GPU machine for either the neglect of the CPU ability or the low bandwidth of PCI-e. In this paper, we propose ASW, which aims at accelerating SW algorithm with accelerated processing unit (APU), a heterogeneous processor integrates CPU and GPU in a single die and share the same memory. This coupled CPU-GPU architecture is more suitable for frequent data exchanging due to the elimination of PCI-e bus. For the full utilization of both CPU and GPU in APU system, ASW partitions the whole SW matrix into blocks and dynamically dispatches each block to CPU and GPU for the concurrent execution. A DAG-based dynamic scheduling method is presented to dispatch the workload automatically. Moreover, we also design a time cost model to determine the partition granularity in the matrix division phase. We have evaluated ASW on AMD A12 platform and our results show that ASW achieves a good performance of 7.2 GCUPS (gigacells update per second).
Rating: 1.0/5. From 1 vote.
Please wait...

* * *

* * *

* * *

HGPU group © 2010-2023 hgpu.org

All rights belong to the respective authors

Contact us: