کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950561 | 1440647 | 2017 | 27 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Finding exact hitting set solutions for systems biology applications using heterogeneous GPU clusters
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Finding exact hitting set solutions for systems biology applications using heterogeneous GPU clusters Finding exact hitting set solutions for systems biology applications using heterogeneous GPU clusters](/preview/png/4950561.png)
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Future Generation Computer Systems - Volume 67, February 2017, Pages 418-429
Journal: Future Generation Computer Systems - Volume 67, February 2017, Pages 418-429
نویسندگان
Danilo Carastan-Santos, Raphael Y. de Camargo, David C. Jr., Siang W. Song, Luiz C.S. Rozante,