Path Length-Driven Hypergraph Partitioning: An Integer Programming Approach - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Annals of Computer Science and Information Systems Année : 2023

Path Length-Driven Hypergraph Partitioning: An Integer Programming Approach

Résumé

Circuit prototyping on multi-FPGA (Field Programmable Gate Arrays) platforms is a widely used technique in the VLSI (Very-Large-Scale Integration) context. Due to the ever-increasing size of circuits, it is necessary to use partitioning algorithms to place them on multi-FPGA platforms. Existing partitioning algorithms focus on minimizing the cut size but do not consider the critical path length, which can be degraded when mapping long paths to multiple FPGAs. However, recent studies try to consider the degradation of the critical path and the target topology but these works still use cutting minimization algorithms. In this work, we propose a mathematical model as an integer program (IP) based on the Red-Black Hypergraph model that considers the minimization of the critical path degradation and the target topology. We compare our partitioning results with KHMETIS, a min-cut algorithm, and show a better critical path for many circuit instances.
Fichier principal
Vignette du fichier
Path Length-Driven Hypergraph Partitioning_ An Integer Programming Approach.pdf (277.61 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-04379729 , version 1 (08-01-2024)

Identifiants

Citer

Julien Rodriguez, Francois Galea, François Pellegrini, Lilia Zaourar. Path Length-Driven Hypergraph Partitioning: An Integer Programming Approach. Annals of Computer Science and Information Systems, 2023, pp.1119-1123. ⟨10.15439/2023F592⟩. ⟨hal-04379729⟩
56 Consultations
16 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More