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

Krishnan Spt, Liang Sim, Veeravalli, Veeravalli Bharadwaj

Description

RNA 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. Methods In 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. Results Our 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. Conclusion The 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.

Informations

• Publié par: biomed
• Publié le: 01 janvier 2010
• Nombre de lectures: 5
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

BMC Bioinformatics

Research Towards high performance computing for molecular structure prediction using IBM Cell Broadband Engine  an implementation perspective 1 22 SPT Krishnan*, Sim Sze Liangand Bharadwaj Veeravalli

BioMedCentral

Open Access

1 2 Addresses: Institutefor Infocomm Research, 1 Fusionopolis Way, #2101, Connexis South Tower, Singapore 138632 andDepartment of Electrical and Computer Engineering, National University of Singapore, 4 Engineering Drive 3, Singapore 117576 Email: SPT Krishnan*  krishnan@i2r.astar.edu.sg; Sim Sze Liang  [e-mail]; Bharadwaj Veeravalli  [e-mail] *Corresponding author

fromThe Eighth Asia Pacific Bioinformatics Conference (APBC 2010) Bangalore, India 1821 January 2010

Published: 18 January 2010 BMC Bioinformatics2010,11(Suppl 1):S36

doi: 10.1186/1471210511S1S36

This article is available from: http://www.biomedcentral.com/14712105/11/S1/S36 ©2010 Krishnan et al; licensee BioMed Central Ltd. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract Background:RNA 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. Methods:In 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. Results:Our 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. Conclusion:The 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.

Page 1 of 12 (page number not for citation purposes)