Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

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

Texto completo
Autor(es):
Carastan-Santos, Danilo [1, 2] ; Martins-, Jr., David C. [1] ; Song, Siang W. [3] ; Rozante, Luiz C. S. [1] ; de Camargo, Raphael Y. [1]
Número total de Autores: 5
Afiliação do(s) autor(es):
[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
Número total de Afiliações: 3
Tipo de documento: Artigo Científico
Fonte: CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE; v. 31, n. 18, SI SEP 25 2019.
Citações Web of Science: 1
Resumo

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)

Processo FAPESP: 15/24485-9 - Internet do futuro aplicada a cidades inteligentes
Beneficiário:Fabio Kon
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 13/26644-1 - Modelos de programação e algoritmos para a execução eficiente de aplicações paralelas em aglomerados heterogêneos
Beneficiário:Raphael Yokoingawa de Camargo
Linha de fomento: Auxílio à Pesquisa - Regular
Processo FAPESP: 14/50937-1 - INCT 2014: da Internet do Futuro
Beneficiário:Fabio Kon
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 15/01587-0 - Armazenagem, modelagem e análise de sistemas dinâmicos para aplicações em e-Science
Beneficiário:João Eduardo Ferreira
Linha de fomento: Auxílio à Pesquisa - Programa eScience e Data Science - Temático