Partitioning a given circuit targeting multiple FPGAs

Our approach to the problem of partitioning the design (represented as a hypergraph) into Multi-FPGAs uses a bi-level approach by initially clustering the design and then applying the bipartitioning technique iteratively. Each partition generated by the iterative bipartitioning technique should meet the constraints given by the FPGAs input-output and number of CLBs. The traditional FM partitioning can be applied to partition the circuit into multiple FPGAs. FM partitioning aims to minimize the number of interconnections but fails to group the nodes with maximum interconnections into one partition. Thus FM algorithm looks at the partitioning problem with a global viewpoint, abandoning the details. The proposed algorithm adds another level of optimization to the partitioning heuristic. By clustering the nodes that are connected very closely in a netlist before partitioning, local optimization property is added to the FM algorithm. This clustered circuit is then partitioned to implement the design in multiple FPGAs. Bipartitioning using the Fiduccia Mattheyses algorithm is applied. (Abstract shortened by UMI.)...