Circuit partitioning with path delay-based minimization - CEA - Commissariat à l’énergie atomique et aux énergies alternatives Access content directly
Conference Papers Year : 2021

Circuit partitioning with path delay-based minimization


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.
Fichier principal
Vignette du fichier
Euro21_abstract.pdf (62.38 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

cea-03616446 , version 1 (22-03-2022)


  • 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⟩
55 View
17 Download


Gmail Facebook Twitter LinkedIn More