Name
Abstract | ||
|---|---|---|
This paper proposes and evaluates a parallel strategy to execute the exact Smith-Waterman (SW) biological sequence comparison algorithm for huge DNA sequences in multi-GPU platforms. In our strategy, the computation of a single huge SW matrix is spread over multiple GPUs, which communicate border elements to the neighbour, using a circular buffer mechanism. We also provide a method to predict the execution time and speedup of a comparison, given the number of the GPUs and the sizes of the sequences. The results obtained with a large multi-GPU environment show that our solution is scalable when varying the sizes of the sequences and/or the number of GPUs and that our prediction method is accurate. With our proposal, we were able to compare the largest human chromosome with its homologous chimpanzee chromosome (249 Millions of Base Pairs (MBP) x 228 MBP) using 64 GPUs, achieving 1.7 TCUPS (Tera Cells Updated per Second). As far as we know, this is the largest comparison ever done using the Smith-Waterman algorithm. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/CCGrid.2014.18 | Cluster, Cloud and Grid Computing |
Keywords | Field | DocType |
DNA,biology computing,cellular biophysics,graphics processing units,matrix algebra,parallel architectures,CUDAlign 3.0,DNA sequence,GPU cluster,SW biological sequence comparison algorithm,Smith-Waterman algorithm,circular buffer mechanism,exact Smith-Waterman biological sequence comparison algorithm,homologous chimpanzee chromosome,human chromosome,multiGPU platform,parallel biological sequence comparison,parallel strategy,prediction method,single huge SW matrix,Biological Sequence Comparison,GPU,Smith-Waterman | Kernel (linear algebra),Instruction set,Computer science,Parallel computing,Circular buffer,Algorithm,Smith–Waterman algorithm,Tera-,Scalability,Distributed computing,Speedup,Computation | Conference |
ISSN | Citations | PageRank |
2376-4414 | 3 | 0.40 |
References | Authors | |
0 | 7 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| weigang | 1 | 22 | 2.61 |
| Guillermo Miranda | 2 | 26 | 1.62 |
| Alba Cristina Magalhaes Alves De Melo | 3 | 253 | 33.90 |
| Xavier Martorell | 4 | 1470 | 125.40 |
| Eduard Ayguadé | 5 | 2406 | 216.00 |
| De Sandes, E.F.O. | 6 | 3 | 0.40 |
| De Melo, A.C.M.A. | 7 | 38 | 2.85 |