Skip to Main content Skip to Navigation
Conference papers

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
Université Paris-Saclay, DSCIN - Département Systèmes et Circuits Intégrés Numériques : DRT/LIST/DSCIN
Abstract : 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.
Complete list of metadata
Contributor : Contributeur MAP CEA Connect in order to contact the contributor
Submitted on : Tuesday, March 22, 2022 - 3:15:56 PM
Last modification on : Friday, April 1, 2022 - 3:34:18 AM
Long-term archiving on: : Thursday, June 23, 2022 - 7:32:29 PM


Files produced by the author(s)


  • HAL Id : cea-03616446, version 1


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⟩



Record views


Files downloads