English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/133773
logo share SHARE   Add this article to your Mendeley library MendeleyBASE
Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Exportar a otros formatos:


Optimizing Performance for Coalition Structure Generation Problems' IDP Algorithm

AuthorsCruz-Mencia, Francisco ; Cerquides, Jesús ; Espinosa, Antonio; Moure, Juan C.; Rodríguez-Aguilar, Juan Antonio
Issue Date22-Jul-2013
CitationParallel and Distributed Processing Techniques and Applications: The 2013 WorldComp International Conference Proceedings
AbstractThe Coalition Structure Generation (CSG) problem is well-known in the area of Multi-Agent Systems. Its goal is establishing coalitions between agents while maximizing the global welfare. Between the existing different algorithms designed to solve the CSG problem, DP and IDP are the ones with smaller temporal complexity. After analyzing the performance of the DP and IDP algorithms, we identify which is the most frequent operation and propose an optimized method. Then, we analyze the memory access pattern and find that its irregular behavior represents a potential performance bottleneck. In addition, we study and implement a method for dividing the work in different threads. We show that selecting the best algorithmic options can improve performance by 10x or more. Furthermore, the execution in a dual-socket, six-core processor computer may increase performance by an additional 5x-6x.
Identifiersisbn: 9781601322586
Appears in Collections:(IIIA) Comunicaciones congresos
Files in This Item:
File Description SizeFormat 
PDPTA2013_Optim..pdf840,97 kBAdobe PDFThumbnail
Show full item record
Review this work

WARNING: Items in Digital.CSIC are protected by copyright, with all rights reserved, unless otherwise indicated.