Introduction Multiway partition Bi-partitionnement Heuristiques d’am´elioration it´erative Algorithme de recuit simul´e Partitionnement de circuits Safia Kedad-Sidhoum LIP6 - Universit´e Paris 6 safia.kedad-sidhoum@lip6.fr DEA-ASIME, Mars 2004 Safia Kedad-Sidhoum Partitionnement de circuitsIntroduction Multiway partition Bi-partitionnement Heuristiques d’am´elioration it´erative Algorithme de recuit simul´e Introduction Objet D´efinition Multiway partition D´efinition Instance Configuration Solution - Optimale Complexit´e Applications Bi-partitionnement D´efinition Complexit´e Hypergraphes Heuristiques d’am´elioration it´erative Objectifs Safia Kedad-Sidhoum Partitionnement de circuitsIntroduction Multiway partition Bi-partitionnement Heuristiques d’am´elioration it´erative Algorithme de recuit simul´e Heuristique de Kernighan-Lin Heu de Fiduccia-Mattheyes Conclusion Algorithme de recuit simul´e Principes g´en´eraux Probl`eme de bi-partitionnement Safia Kedad-Sidhoum Partitionnement de circuitsI Aspect important des probl`emes de Layout. I Partitionnement : op´eration sur les graphes et hypergraphes. I Peut apparaˆıtre pour des probl`emes de routage. Introduction Multiway partition Objet Bi-partitionnement D´efinition Heuristiques d’am´elioration it´erative Algorithme de recuit simul´e Notion de partitionnement I Diviser un circuit en petites parties. Safia Kedad-Sidhoum Partitionnement de circuitsI Partitionnement : op´eration sur les graphes et hypergraphes. I Peut ...
Introduction
Multiway partition
Bi-partitionnement
Heuristiques d’am´elioration it´erative
Algorithme de recuit simul´e
Partitionnement de circuits
Safia Kedad-Sidhoum
LIP6 - Universit´e Paris 6
safia.kedad-sidhoum@lip6.fr
DEA-ASIME, Mars 2004
Safia Kedad-Sidhoum Partitionnement de circuitsIntroduction
Multiway partition
Bi-partitionnement
Heuristiques d’am´elioration it´erative
Algorithme de recuit simul´e
Introduction
Objet
D´efinition
Multiway partition
D´efinition
Instance
Configuration
Solution - Optimale
Complexit´e
Applications
Bi-partitionnement
D´efinition
Complexit´e
Hypergraphes
Heuristiques d’am´elioration it´erative
Objectifs
Safia Kedad-Sidhoum Partitionnement de circuitsIntroduction
Multiway partition
Bi-partitionnement
Heuristiques d’am´elioration it´erative
Algorithme de recuit simul´e
Heuristique de Kernighan-Lin
Heu de Fiduccia-Mattheyes
Conclusion
Algorithme de recuit simul´e
Principes g´en´eraux
Probl`eme de bi-partitionnement
Safia Kedad-Sidhoum Partitionnement de circuitsI Aspect important des probl`emes de Layout.
I Partitionnement : op´eration sur les graphes et hypergraphes.
I Peut apparaˆıtre pour des probl`emes de routage.
Introduction
Multiway partition
Objet
Bi-partitionnement
D´efinition
Heuristiques d’am´elioration it´erative
Algorithme de recuit simul´e
Notion de partitionnement
I Diviser un circuit en petites parties.
Safia Kedad-Sidhoum Partitionnement de circuitsI Partitionnement : op´eration sur les graphes et hypergraphes.
I Peut apparaˆıtre pour des probl`emes de routage.
Introduction
Multiway partition
Objet
Bi-partitionnement
D´efinition
Heuristiques d’am´elioration it´erative
Algorithme de recuit simul´e
Notion de partitionnement
I Diviser un circuit en petites parties.
I Aspect important des probl`emes de Layout.
Safia Kedad-Sidhoum Partitionnement de circuitsI Peut apparaˆıtre pour des probl`emes de routage.
Introduction
Multiway partition
Objet
Bi-partitionnement
D´efinition
Heuristiques d’am´elioration it´erative
Algorithme de recuit simul´e
Notion de partitionnement
I Diviser un circuit en petites parties.
I Aspect important des probl`emes de Layout.
I Partitionnement : op´eration sur les graphes et hypergraphes.
Safia Kedad-Sidhoum Partitionnement de circuitsIntroduction
Multiway partition
Objet
Bi-partitionnement
D´efinition
Heuristiques d’am´elioration it´erative
Algorithme de recuit simul´e
Notion de partitionnement
I Diviser un circuit en petites parties.
I Aspect important des probl`emes de Layout.
I Partitionnement : op´eration sur les graphes et hypergraphes.
I Peut apparaˆıtre pour des probl`emes de routage.
Safia Kedad-Sidhoum Partitionnement de circuitsI Graphe ou Hypergraphe G = (V,E)≡ circuit.
I V- Ensemble de sommets≡ ´el´ements du circuit.
I E- Ensemble des arˆetes ou hyper-arˆetes≡ fils du circuit.
I Graphe de routage : E- canaux et V Switch boxes.
I Un partitionnement peut ˆetre obtenu en supprimant les arˆetes
(ou hyper-arˆetes) ou les sommets (et les arˆetes incidentes)
(probl`eme de s´eparation).
I Le coutˆ d’une partition est la somme pond´er´ee des ´el´ements
supprim´es du graphe.
I Contraintes additionnelles : taille des composants...
Introduction
Multiway partition
Objet
Bi-partitionnement
D´efinition
Heuristiques d’am´elioration it´erative
Algorithme de recuit simul´e
D´efinition du partitionnement
I Diviser un graphe ou un hypergraphe en plusieurs composants
d´econnect´ees.
Safia Kedad-Sidhoum Partitionnement de circuitsI V- Ensemble de sommets≡ ´el´ements du circuit.
I E- Ensemble des arˆetes ou hyper-arˆetes≡ fils du circuit.
I Graphe de routage : E- canaux et V Switch boxes.
I Un partitionnement peut ˆetre obtenu en supprimant les arˆetes
(ou hyper-arˆetes) ou les sommets (et les arˆetes incidentes)
(probl`eme de s´eparation).
I Le coutˆ d’une partition est la somme pond´er´ee des ´el´ements
supprim´es du graphe.
I Contraintes additionnelles : taille des composants...
Introduction
Multiway partition
Objet
Bi-partitionnement
D´efinition
Heuristiques d’am´elioration it´erative
Algorithme de recuit simul´e
D´efinition du partitionnement
I Diviser un graphe ou un hypergraphe en plusieurs composants
d´econnect´ees.
I Graphe ou Hypergraphe G = (V,E)≡ circuit.
Safia Kedad-Sidhoum Partitionnement de circuitsI E- Ensemble des arˆetes ou hyper-arˆetes≡ fils du circuit.
I Graphe de routage : E- canaux et V Switch boxes.
I Un partitionnement peut ˆetre obtenu en supprimant les arˆetes
(ou hyper-arˆetes) ou les sommets (et les arˆetes incidentes)
(probl`eme de s´eparation).
I Le coutˆ d’une partition est la somme pond´er´ee des ´el´ements
supprim´es du graphe.
I Contraintes additionnelles : taille des composants...
Introduction
Multiway partition
Objet
Bi-partitionnement
D´efinition
Heuristiques d’am´elioration it´erative
Algorithme de recuit simul´e
D´efinition du partitionnement
I Diviser un graphe ou un hypergraphe en plusieurs composants
d´econnect´ees.
I Graphe ou Hypergraphe G = (V,E)≡ circuit.
I V- Ensemble de sommets≡ ´el´ements du circuit.
Safia Kedad-Sidhoum Partitionnement de circuits