Circuit partitioning with path delay-based minimization

Julien Rodriguez (1) , François Galea (1) , François Pellegrini (2) , Lilia Zaourar (1)

1 LECA - Laboratoire Environnement de Conception & Architecture
2 Inria Bordeaux - Sud-Ouest

Hypergraph partitioning has been used in several areas including circuit partitioning for VLSI design since the 1970s. The process of evaluating and verifying a System on a Chip (SoC) involves using Field-Programmable-Gate-Arrays (FPGAs). Nowadays, the increasing size of Integer Circuits (IC) requires partitioning them in several sub-circuits. Each one is then mapped onto a multi-FPGA platform while respecting some constraints. This work focuses on the minimization of the maximum path delay. There are several tools that allow hypergraph partitioning, like hMETIS, PaToH and KaHyPar. These solvers minimize a "min-cut" objective function based on individual penalties for each of the cut hyperedges. The minimization problems for "min-cut" are NP-hard. Even though this function tries to minimize the number of hyperedges (nets) between parts (vertex set), it does not solve the path delay minimization. There exist some previous works that deal with the timing constraint with good results (40 % delay improvement) but the main objective function remains min-cut. In this paper, we devise a mathematical moel for the problem of IC partitioning with path-delay-based minimization that takes into account various constraints. We propose a way to derive the classical multilevel approach for graph/hypergraph min-cut methods to adapt it to our specific problem.

Domains: Data Structures and Algorithms [cs.DS]; Operations Research [cs.RO]

Julien Rodriguez, François Galea, François Pellegrini, Lilia Zaourar. Circuit partitioning with path delay-based minimization. EURO 2021 - 31st European conference on operational research, Jul 2021, Athènes, Greece. ⟨cea-03616446⟩