Résumé
Electronic design automation toolchains require solving various circuit manipulation problems, such as floor planning, placement and routing. These circuits may be implemented using either Very Large-Scale Integration (VLSI) or Field Programmable Gate Arrays (FPGAs). However, with the ever-increasing size of circuits, now up to billions of gates, straightforward approaches to these problems do not scale well. A possible approach to reduce circuit complexity is to cluster circuits. In this work, we consider the problem of clustering combinatorial circuits, without cell replication. We propose a dedicated clustering algorithm based on binary search and study and improve the existing parameterized approximation ratio from M² + M (with M being the maximum size of each cluster) to M under specific hypothesis. We present an extension of the weighting schemes to model path length more accurately. This weighting scheme is combined with clustering methods based on a recursive matching algorithm. We evaluate and compare our approximation algorithm and recursive matching on several circuit instances and we obtain better results for a large number of instances with our algorithm than recursive matching.