Web of Science: 1 citas, Scopus: 1 citas, Google Scholar: citas
Coalition structure generation problems : optimization and parallelization of the IDP algorithm in multicore systems
Cruz Mencía, Francisco (Artificial Intelligence Research Institute)
Cerquides Bueno, Jesús (Artificial Intelligence Research Institute)
Rodríguez-Aguilar, Juan A. (Juan Antonio) (Artificial Intelligence Research Institute)
Espinosa Morales, Antonio Miguel (Universitat Autònoma de Barcelona. Departament d'Arquitectura de Computadors i Sistemes Operatius)
Moure López, Juan Carlos (Universitat Autònoma de Barcelona. Departament d'Arquitectura de Computadors i Sistemes Operatius)
Ramchurn, Sarvapali D. (University of Southampton)
Svensson, Kim (University of Southampton)

Fecha: 2017
Resumen: The coalition structure generation problem is well known in the area of multi-agent systems. Its goal is to establish coalitions between agents while maximizing the global welfare. Among the existing different algorithms designed to solve the coalition structure generation problem, DP and IDP are the ones with smaller temporal complexity. After analyzing the operation of the dynamic programming and improved dynamic programming algorithms, we have identified which are the most frequent operations and propose an optimized method. In addition, we study and implement a method for dividing the work into different threads. To describe incremental improvements of the algorithm design, we first compare performance of an improved single central processing unit core version where we obtain speedups ranging from 7 × to 11 × . Then, we describe the best resource use in a multi-thread optimized version where we obtain an additional 7. 5 × speedup running in a 12-core machine.
Nota: Número d'acord de subvenció MICINN/TIN2014-53234-C2-1-R
Nota: Número d'acord de subvenció MICINN/TIN2015-66863-C2-1-R
Nota: Número d'acord de subvenció AGAUR/2014/SGR-576
Nota: Número d'acord de subvenció AGAUR/2014/SGR-118
Derechos: Tots els drets reservats
Lengua: Anglès.
Documento: article ; recerca ; acceptedVersion
Materia: Dynamic programming ; Multi agent systems ; Multi-core systems ; Set partitioning problem
Publicado en: Concurrency and Computation : Practice and Experience, Vol. 29, Issue 5 (March 2017) , art. e3969, ISSN 1532-0626

DOI: 10.1002/cpe.3969


Postprint
21 p, 1.3 MB

El registro aparece en las colecciones:
Artículos > Artículos de investigación
Artículos > Artículos publicados

 Registro creado el 2019-03-05, última modificación el 2019-04-04



   Favorit i Compartir