Por favor, use este identificador para citar o enlazar a este item:
http://hdl.handle.net/10261/183656
COMPARTIR / EXPORTAR:
SHARE CORE BASE | |
Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL | DATACITE | |
Título: | An Efficient Approach for Accelerating Bucket Elimination on GPUs |
Autor: | Bistaffa, Filippo CSIC ORCID ; Bombieri, Nicola; Farinelli, Alessandro | Palabras clave: | GPU Bucket elimination Constrainto optimisation problem Belief propagation Junction tree |
Fecha de publicación: | nov-2017 | Citación: | IEEE Transactions on Cybernetics Volume 47, Issue 11 | Resumen: | Bucket elimination (BE) is a framework that encompasses several algorithms, including belief propagation (BP) and variable elimination for constraint optimization problems (COPs). BE has significant computational requirements that can be addressed by using graphics processing units (GPUs) to parallelize its fundamental operations, i.e., composition and marginalization, which operate on functions represented by large tables. We propose a novel approach to parallelize these operations with GPUs, which optimizes the table layout so to achieve better performance in terms of increased speedup and scalability. Our approach allows us to process incomplete tables (i.e., tables with some missing variables assignments), which often occur in several practical applications (such as the ones we consider in our dataset). Finally, we can process tables that are larger than the GPU memory. Our approach outperforms the state-of-the-art technique to parallelize BP on GPUs, achieving better speedups (up to +466% with respect to such parallel technique). We test our method on a publicly available COP dataset, measuring a speedup up to 696.02× with respect to the sequential version. The ability of our technique to process large tables is crucial in this scenario, in which most of the instances generate tables larger than the GPU memory, and hence they cannot be solved with previous GPU techniques related to BE. | Versión del editor: | http://dx.doi.org/10.1109/TCYB.2016.2593773 | URI: | http://hdl.handle.net/10261/183656 | DOI: | 10.1109/TCYB.2016.2593773 |
Aparece en las colecciones: | (IIIA) Artículos |
Ficheros en este ítem:
Fichero | Descripción | Tamaño | Formato | |
---|---|---|---|---|
2016ieeecyb.pdf | 766,32 kB | Adobe PDF | Visualizar/Abrir |
CORE Recommender
SCOPUSTM
Citations
9
checked on 22-abr-2024
WEB OF SCIENCETM
Citations
6
checked on 21-feb-2024
Page view(s)
296
checked on 24-abr-2024
Download(s)
291
checked on 24-abr-2024
Google ScholarTM
Check
Altmetric
Altmetric
NOTA: Los ítems de Digital.CSIC están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.