David A. Bader
IEEE Fellow
AAAS Fellow
Professor
College of Computing
Georgia Tech
Atlanta, GA 30332


 
 

 

On Accelerating Iterative Algorithms with CUDA: A Case Study on Conditional Random Fields Training Algorithm for Biological Sequence Alignment

The accuracy of Conditional Random Fields (CRF) is achieved at the cost of huge amount of computation to train model. In this paper we designed the parallelized algorithm for the Gradient Ascent based CRF training methods for biological sequence alignment. Our contribution is mainly on two aspects: 1) We flexibly parallelized the different iterative computation patterns, and the according optimization methods are presented. 2) As for the Gibbs Sampling based training method, we designed a way to automatically predict the iteration round, so that the parallel algorithm could be run in a more efficient manner. In the experiment, these parallel algorithms achieved valuable accelerations comparing to the serial version.

Publication History

Versions of this paper appeared as:
  1. Z. Du, Z. Yin, W. Liu, and D.A. Bader, ``On Accelerating Iterative Algorithms with CUDA: A Case Study on Conditional Random Fields Training Algorithm for Biological Sequence Alignment,'' IEEE International Conference on Bioinformatics & Biomedicine, Workshop on Data-Mining of Next Generation Sequencing Data (NGS2010), Hong Kong, December 20, 2010.

Download this report in Adobe PDF


 
 

Last updated: June 1, 2012

 




Computational Biology



Parallel Computing



Combinatorics