| Texto completo | |
| Autor(es): |
Curtis, V. V.
;
Sanches, C. A. A.
Número total de Autores: 2
|
| Tipo de documento: | Artigo Científico |
| Fonte: | Computers & Operations Research; v. 83, p. 120-124, JUL 2017. |
| Citações Web of Science: | 1 |
| Resumo | |
We present a highly scalable parallel solution for the Subset-Sum Problem on Graphics Processing Units (GPUs) that substantially reduces the memory access by the device and, consequently, decreases the total runtime. We test this algorithm only on hard instances, which require the exhaustion of the entire search space, instead of simple random benchmarks. On a GPU with only 1.2 GB of global memory, we address hard instances with 100,000 items limited to 10(6) and 200 items limited to 10(8). Our algorithm achieves excellent runtimes outperforming the best-known practical and parallel algorithms, reaching speed-ups higher than 1000 in the best case compared to its sequential version. (C) 2017 Elsevier Ltd. All rights reserved. (AU) | |
| Processo FAPESP: | 15/18164-5 - Resoluções paralelas de problemas intratáveis em processos industriais |
| Beneficiário: | Carlos Alberto Alonso Sanches |
| Modalidade de apoio: | Auxílio à Pesquisa - Regular |