Circuit partitioning is a usual process in very large-scale integrated (VLSI) design, because many of the classic methods (placement of logic cells on the silicon surface or resource mapping on a FPGA) do not scale well with ever-increasing circuit sizes.
Circuit sizes typically vary from millions to billions, making such methods challenging.One possible approach is to cluster the circuit to reduce its size, while trying to maintain a good level of locality in the clusters.
Even for combinatorial circuits, there are several models for the clustering problem. In particular, we consider the problem of clustering without replication in combinatorial circuits with minimizing the overall delay. This problem is well recently studied from an algorithmic and complexity point of view. We extend the problem to cluster a set of connected directed acyclic hypergraphs (DAH) and propose a designed approximation algorithm.