Extremal optimization approach to 3D design of integrated circuits layouts

Computer-aided 3D ICs layout design is an NP-hard problem in which an important step is the graph partitioning task. If speed is the dominant requirement, the commonly applied Fiduccia-Mattheyses partitioning algorithm is superior to any other local search method. However, taking into account other cost function, it often fails to obtain a quasi-optimal solution in 3D spaces. This paper presents an original 3D layout graph partitioning heuristics implemented with the use of extremal optimization method. The preliminary results show very good performance and stimulate further research.