Hypergraphs and extremal optimization in 3D integrated circuit design automation

The circuit design task poses an extremely difficult intellectual challenge. The solution has to meet a number of specific requirements and satisfy a variety of constraints. Efficient search of huge and discontinuous spaces requires new non-deterministic and heuristic algorithms. The goal of the research is to minimize the total wire-length of interconnects between sub-circuits. The paper presents a knowledge intensive 3D ICs layout hypergraph representation together with the elaborated neighborhood optimization heuristics. The results of the Extremal Optimization (EO) implementation applied to the MCNC set of benchmark circuits are reported.