Towards high performance computing for molecular structure prediction using IBM Cell Broadband Engine - an implementation perspective

BMC Bioinformatics

Research

Sim Sze Liang¹  Bharadwaj Veeravalli¹  SPT Krishnan² 

[1] Department of Electrical and Computer Engineering, National University of Singapore, 4 Engineering Drive 3, 117576, Singapore;Institute for Infocomm Research, 1 Fusionopolis Way, #21-01, 138632, Connexis South Tower, Singapore;

关键词: Virtual Machine;    Dynamic Programming Algorithm;    Scalar Implementation;    Parallelization Effort;    Dynamic Programming Solution;   

DOI  :  10.1186/1471-2105-11-S1-S36

来源: Springer

【 摘 要 】

BackgroundRNA structure prediction problem is a computationally complex task, especially with pseudo-knots. The problem is well-studied in existing literature and predominantly uses highly coupled Dynamic Programming (DP) solutions. The problem scale and complexity become embarrassingly humungous to handle as sequence size increases. This makes the case for parallelization. Parallelization can be achieved by way of networked platforms (clusters, grids, etc) as well as using modern day multi-core chips.MethodsIn this paper, we exploit the parallelism capabilities of the IBM Cell Broadband Engine to parallelize an existing Dynamic Programming (DP) algorithm for RNA secondary structure prediction. We design three different implementation strategies that exploit the inherent data, code and/or hybrid parallelism, referred to as C-Par, D-Par and H-Par, and analyze their performances. Our approach attempts to introduce parallelism in critical sections of the algorithm. We ran our experiments on SONY Play Station 3 (PS3), which is based on the IBM Cell chip.ResultsOur results suggest that introducing parallelism in DP algorithm allows it to easily handle longer sequences which otherwise would consume a large amount of time in single core computers. The results further demonstrate the speed-up gain achieved in exploiting the inherent parallelism in the problem and also elicits the advantages of using multi-core platforms towards designing more sophisticated methodologies for handling a fairly long sequence of RNA.ConclusionThe speed-up performance reported here is promising, especially when sequence length is long. To the best of our literature survey, the work reported in this paper is probably the first-of-its-kind to utilize the IBM Cell Broadband Engine (a heterogeneous multi-core chip) to implement a DP. The results also encourage using multi-core platforms towards designing more sophisticated methodologies for handling a fairly long sequence of RNA to predict its secondary structure.

【 授权许可】

CC BY   
© Krishnan et al; licensee BioMed Central Ltd. 2010