The Coalition Structure Generation (CSG) problem is wellknown in the area of Multi-Agent Systems. Its goal is to establish coalitions between agents while maximizing the global welfare. Between the existing dierent algorithms designed to solve the CSG problem, DP and IDP are the ones with smaller temporal complexity. After analyzing the operation of the DP and IDP algorithms, we identify which are the most frequent operations and propose an optimized method. Then, we analyze the memory access pattern and nd that its irregular behavior represents a potential performance bottleneck. In addition, we study and implement a method for dividing the work in dierent 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. With this, we are able to solve a CSG problem of 27 agents using our multi-core computer in 1.2 hours.

This research has been supported by MICINN-Spain under contracts TIN2011-28689-C02-01, TIN2012-38876-C02-01 and the Generalitat of Catalunya (2009-SGR-1434)

Peer Reviewed