Coalition structure generation problems: optimization and parallelization of the IDP algorithm in multicore systems
Coalition structure generation problems: optimization and parallelization of the IDP algorithm in multicore systems
复制标题
DOI：
10.1002/cpe.3969
复制
发表时间：
2017-03
期刊：
影响因子：
--
通讯作者：
Francisco Cruz-Mencia;Antonio Espinosa;J. Moure;J. Cerquides;J. Rodríguez-Aguilar;Kim Svensson;S. Ramchurn
中科院分区：
文献类型：
--
作者：
Francisco Cruz-Mencia;Antonio Espinosa;J. Moure;J. Cerquides;J. Rodríguez-Aguilar;Kim Svensson;S. Ramchurn
联盟结构生成问题在多智能体系统领域是众所周知的。它的目标是在代理人之间建立联盟，同时最大化全球福利。在现有的联盟结构生成算法中，DP和IDP是时间复杂度较小的算法。通过对动态规划和改进的动态规划算法的运算分析，找出了最常见的运算，并提出了优化方法。此外，我们还研究并实现了一种将工作划分到不同线程的方法。为了描述算法设计的增量改进，我们首先比较了改进的单中央处理器核心版本的性能，其中我们获得了7倍到11倍的加速比。然后，我们描述了多线程优化版本中的最佳资源使用，其中我们在12核机器上获得了额外的7.5倍加速。
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.