Comprehensive Branch Elimination for GPU Accelerated Biomedical Applications
Lucas John Vespa, Alex Bauman · 2014
Biomedical application speed requirements have made general purpose graphics processing unit (GPU) acceleration of Biomedical and Bioinformat-ics a lucrative area of study. SIMD design of GPUs means that most Biomedical applications are either not suitable for acceleration on GPUs, or cannot reach their full acceleration potential due to thread divergence. Also, many Biomedical applications are decision heavy and experience intense thread diver-gence on GPUs. Previous research has addressed the issue of reducing branch code, but none of this work aims to entirely eliminate branches, because the methods required for complete branch elimination are a drastic de-optimization for CPU and MPU. We present a de-optimization for CPU which completely eliminates branches, and results in a significant op-timization for GPU accelerated Biomedical applica-tions which: • Eliminates thread divergence • Substantially decreases execution time • Allows implementation of Biomedical algorithms on GPU which previously do not fully utilize GPU capability Our optimization removes branches from Biomedical algorithms using a reduced equation. The equation evaluates all branches simultaneously using arith-metic operations. We call our method Algorithm Flattening (AF). We test AF using two DNA Align-ment methods [1, 2]. AF achieves up to a 3x speedup of already GPU accelerated implementations. 1