Hypergraph Clustering with Path-Length Awareness

EasyChair Preprint 13273

Abstract

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, to reduce their apparent size for critical processing operations, while preserving their topological properties (e.g., connection locality).

Several models have been proposed to tackle the clustering problem. In this work, we consider the problem of clustering combinatorial circuits, without cell replication. Our main objective is to minimize the overall delay, which conditions the circuit operating frequency. We propose a dedicated clustering algorithm based on binary search and study and improve the existing parameterized approximation ratio from M^2+M (with M being the maximum size of each cluster) to M under specific hypothesis. We present an extension of the weighting schemes introduced 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.

Keyphrases: Clustering, Digital electronic circuit, hypergraph

@booklet{EasyChair:13273,
  author    = {Julien Rodriguez and Francois Galea and François Pellegrini and Lilia Zaourar},
  title     = {Hypergraph Clustering with Path-Length Awareness},
  howpublished = {EasyChair Preprint 13273},
  year      = {EasyChair, 2024}}