Partitionnement de circuits

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 circuitsIntroduction
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 circuitsIntroduction
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 circuits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.
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 circuitsI Partitionnement : op´eration sur les graphes et hypergraphes.
I Peut ...