Partitionnement de circuits

Sujets

• Safiatou Thiam
• Partition héraldique
• Sommet des Amériques
• Banque d'Estonie
• SimulacreS
• Coupesarte

Informations

• Publié par: Siem
• Nombre de lectures: 61
• Langue: Français
• Poids de l'ouvrage: 1 Mo

Extrait

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 safi[e-mail] 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 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 circuits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. I Partitionnement : op´eration sur les graphes et hypergraphes. Safia Kedad-Sidhoum Partitionnement de circuits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. I Peut apparaˆıtre pour des probl`emes de routage. Safia Kedad-Sidhoum Partitionnement de circuitsI 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 circuits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. I Graphe ou Hypergraphe G = (V,E)≡ circuit. Safia Kedad-Sidhoum Partitionnement de circuits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. I V- Ensemble de sommets≡ ´el´ements du circuit. Safia Kedad-Sidhoum Partitionnement de circuits