Changes between Version 35 and Version 36 of CaoCourseTme8

Timestamp:

May 20, 2009, 4:23:03 PM (16 years ago)

Author:

alain

Comment:

--

CaoCourseTme8

@@ -11 +11 @@
 la méthode Min-Cut, dont le principe a été présenté en cours. Cet algorithme est fortement
 inspiré de la méthode publiée par Fiduccia et Mattheyses en 1982.
+Cet algorithme est souvent utilisé en CAO micro-électronique pour résoudre des problèmes de
+placement : Les noeuds du graphe représentent des cellules précaractérisèes à placer dans un plan, 
+et l'existence d'une arête entre deux noeuds i et j représente l'existence d'une connection entre 
+les deux deux cellules i et j.
 
 = A) Introduction = 
@@ -22 +26 @@
 équilibrée si |L| = |R| = N/2
 
-Pour ce qui nous concerne, on s'intéresse à une net-list de cellules
+Dans le contexte du placement de cellules, on part d'une net-list de cellules
 précaractérisées, et on cherche à partitionner l'ensemble des cellules
 en deux sous-ensembles L et R tels que le nombre de signaux traversant la
@@ -91 +95 @@
 On calcule la variation de la fonction de coût associé à l'échange i <-> j, et on accepte le mouvement
 tant que celui-ci n'entraîne pas une augmentation de la fonction de coût.
-
-Accepter un mouvement consiste à effectuer les actions suivantes:
- * On transfère la première cellule i de la liste ordonnée GAIN_R vers L, on met à jour les gains des cellules adjacentes à i, ainsi que l'ordre des listes GAIN_L et GAIN_R. La cellule i transférée dans L n'est pas rangée dans GAIN_L, car elle n'est plus autorisée à bouger.
- * On transfère la première cellule j de la liste ordonnée GAIN_L vers R, on met à jour les gains des cellules adjacentes à j, ainsi que l'ordre des listes GAIN_L et GAIN_R. La cellule j transférée dans R n'est pas rangée dans GAIN_R, car elle n'est plus autorisée à bouger.
 
 = C) Structures de données =
@@ -297 +297 @@
        de la structure de donnée move_manager'', et les gains de toutes les cellules adjacentes à i et j doivent
        être mis à jour.
+Accepter un mouvement consiste à effectuer les actions suivantes:
+ * On transfère la première cellule i de la liste ordonnée GAIN_R vers L, on met à jour les gains des cellules adjacentes à i, ainsi que l'ordre des listes GAIN_L et GAIN_R. La cellule i transférée dans L n'est pas rangée dans GAIN_L, car elle n'est plus autorisée à bouger.
+ * On transfère la première cellule j de la liste ordonnée GAIN_L vers R, on met à jour les gains des cellules adjacentes à j, ainsi que l'ordre des listes GAIN_L et GAIN_R. La cellule j transférée dans R n'est pas rangée dans GAIN_R, car elle n'est plus autorisée à bouger.
 
 '''4. Ecriture des autres fonctions d'accès'''::