An Approximation Algorithm for Hypergraph Disjoint Clustering Problem with Path-length awareness
Julien Rodriguez  1@  , François Galea  2@  , François Pellegrini  3, 4@  , Lilia Zaourar  2@  
1 : Laboratoire d'Intégration des Systèmes et des Technologies
Commissariat à l'énergie atomique et aux énergies alternatives : DRT/LIST, Université de Bordeaux (Bordeaux, France)
2 : Laboratoire dÍntégration des Systèmes et des Technologies
Direction de Recherche Technologique (CEA), Direction de Recherche Technologique (CEA) : DRT/LIST
3 : BACCHUS  (INRIA Bordeaux - Sud-Ouest)
CNRS : UMR5800, CNRS : UMR5251, PRES Université de Bordeaux, INRIA
4 : Laboratoire Bordelais de Recherche en Informatique  (LaBRI)
Université Sciences et Technologies - Bordeaux I, CNRS : UMR5800, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université Victor Segalen - Bordeaux II
Domaine Universitaire 351, cours de la Libération 33405 Talence Cedex -  France

Circuit partitioning is a usual process in very large-scale integrated (VLSI) design, because many of the classic methods (placement of logic cells on the silicon surface or resource mapping on a FPGA) do not scale well with ever-increasing circuit sizes.
Circuit sizes typically vary from millions to billions, making such methods challenging.One possible approach is to cluster the circuit to reduce its size, while trying to maintain a good level of locality in the clusters.
Even for combinatorial circuits, there are several models for the clustering problem. In particular, we consider the problem of clustering without replication in combinatorial circuits with minimizing the overall delay. This problem is well recently studied from an algorithmic and complexity point of view. We extend the problem to cluster a set of connected directed acyclic hypergraphs (DAH) and propose a designed approximation algorithm.


Personnes connectées : 2 Vie privée
Chargement...