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

A hybrid CPU-GPU-MIC algorithm for minimal hitting set enumeration

Full text
Carastan-Santos, Danilo [1, 2] ; Martins-, Jr., David C. [1] ; Song, Siang W. [3] ; Rozante, Luiz C. S. [1] ; de Camargo, Raphael Y. [1]
Total Authors: 5
[1] Univ Fed ABC, Ctr Math Comp & Cognit, Santo Andre - Brazil
[2] Univ Grenoble Alpes, CNRS, INRIA, Grenoble INP, LIG, Grenoble - France
[3] Univ Sao Paulo, Inst Matemat & Estat, Sao Paulo - Brazil
Total Affiliations: 3
Document type: Journal article
Web of Science Citations: 1

We present a hybrid exact algorithm for the Minimal Hitting Set (MHS) Enumeration Problem for highly heterogeneous CPU-GPU-MIC platforms. With several techniques that permit an efficient exploitation of each architecture, low communication cost, and effective load balancing, we were able to enumerate MHSs for large instances in reasonable time, achieving good performance and scalability. We obtained speedups of up to 25.32 in comparison with using two six-core CPUs and we also enumerated MHSs for instances with tens of thousands of variables in less than 5 hours. We also evaluated our algorithm with a real-world driven dataset, and with a large CPU-GPU cluster, we unprecedentedly enumerated in parallel large minimal hitting sets of this dataset in less than 8 hours. These results reinforce the statement that heterogeneous clusters of CPUs, GPUs, and MICs can be used efficiently for high-performance computing. (AU)

FAPESP's process: 14/50937-1 - INCT 2014: from the Internet of the Future
Grantee:Fabio Kon
Support type: Research Projects - Thematic Grants
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 type: Regular Research Grants
FAPESP's process: 15/01587-0 - Storage, modeling and analysis of dynamical systems for e-Science applications
Grantee:João Eduardo Ferreira
Support type: Research Grants - eScience and Data Science Program - Thematic Grants
FAPESP's process: 15/24485-9 - Future internet for smart cities
Grantee:Fabio Kon
Support type: Research Projects - Thematic Grants