Advanced search
Start date
Betweenand
Related content
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

Finding exact hitting set solutions for systems biology applications using heterogeneous GPU clusters

Full text
Author(s):
Carastan-Santos, Danilo ; de Camargo, Raphael Y. ; Martins, Jr., David C. ; Song, Siang W. ; Rozante, Luiz C. S.
Total Authors: 5
Document type: Journal article
Source: FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE; v. 67, p. 418-429, FEB 2017.
Web of Science Citations: 2
Abstract

The Systems Biology field presents several complex combinatorial problems that can be in part reduced to an instance of the Hitting Set Problem (HSP), which is NP-Hard. These reduced problems often come with a large amount of data that needs to be processed, such as gene expression profiles, resulting in prohibitive computational costs for finding the exact solutions. There are some proposals to obtain exact solutions for HSP, including an approach which uses GPUs. However, such an approach is not scalable for real input sizes (thousands of variables). We propose a novel algorithm for solving HSP instances with thousands of variables by using: (i) clause sorting, which enables the efficient discarding of non-solution candidates, (ii) parallel generation and evaluation of candidate solutions through the use of GPUs, and (iii) support for multiple GPUs. To permit the execution on heterogeneous clusters, we determine the minimum kernel size that does not incur extra overhead and distribute tasks among available GPUs on demand. Our experimental results show that the combination of these techniques results in a speedup of 118.5, when using eight NVIDIA Tesla K20c in comparison with a ten-core Intel Xeon E5-2690 processor. Consequently, our algorithm can enable the usage of exact algorithms for solving the Hitting Set problem and applying it to real world problems. (C) 2016 Elsevier B.V. All rights reserved. (AU)

FAPESP's process: 13/26644-1 - Algorithms and programming models for efficient execution of parallel applications in heterogeneous clusters
Grantee:Raphael Yokoingawa de Camargo
Support Opportunities: Regular Research Grants