Για το παραδειγμα με τον αλγοριθμο Fiduccia-Muttheyses (FM) pdf Διαχωρισμός_κυκλωμάτω σελιδα 24 εχουμε και λεμε
FS(a) = ο αριθμός των κομμένων nets TE(a) = ο αριθμός των μη κομμένων nets
Δg(a) = FS(a) - TE(a)
Αρχικά υπολογίζουμε τον περιορισμό r*area(V) - areamax(V) <= area(V) <= r*area(V) + areamax(V)
area(V) = Το άθροισμα όλων τον επιφανίων για κάθε cell = 16 areamax(V) = το cell με την μέγιστη επιφάνεια = 5 ( το cell e)
Για το net N2 είναι υπερκομβος. I = 1 Υπολογίζουμε όλα τα FS , TE για κάθε κομβο που δεν είναι fixed
a: FS(a) = 2 ( N2, N3) TE(a) = 1(N1) Δg1(a)= 1 b: FS(b) = 0 TE(b) = 1 ( N1) Δg1(b)= -1 c: FS(c) =1 (N2) TE(c) = 1(N5) Δg1(c)= 0 d: FS(d) = 1 (N3) TE(d) = 1(N5) Δg1(d)= 0 e: FS(e) = 1 (N4) TE(e) = 0 Δg1(e)= 1
Για να διαλέξουμε πιο κελί θα αλλάξει partition επιλέγουμε εκείνα με το μεγαλύτερο κέρδος Αρα για το cell a έχουμε: area(A) = area(b) = 4 ικανοποιεί το κτήριο για το κελί e έχουμε area(A) = area(a)+area(b)+area(e) = 2 + 4 +5 = 11.
Επιλέγουμε το α (όπως το παράδειγμα) αρα εχουμε A = {b} , B = {a,c,d,e}, Fixed = {a}
i = 2 Υπολογίζουμε όλα τα FS , TE για κάθε κομβο που δεν είναι fixed
b: FS(b) = 2 TE(b) = 0 Δg2(b)= 2 c: FS(c) = 0 TE(c) = 1 Δg2(c)= -1 d: FS(d) = 0 TE(d) = 2 Δg2(d)= -2 e: FS(e) = 0 TE(e) = 1 Δg2](e)= -1
Αν επιλέξουμε το b τότε area(A) = 0 αλλά επιτρέπεται τουλάχιστον 1 οπότε δεν το αλλάζουμε. Η επόμενες επιλογές είναι το c,e έστω ότι επιλέγουμε την c A = {b,c} , B = {a,d,e}, Fixed = {a,c}
i = 3
b: FS(b) = 2 TE(b) = 1 Δg3(b)= 1 d: FS(d) = 1 TE(d) = 1 Δg3(d)= 0 e: FS(e) = 0 TE(e) = 1 Δg3](e)= -1
Έστω ότι επιλέγουμε το b τοτε area(A) = 1
A = {c} , B = {a,b,d,e}, Fixed = {a,c,b}
i = 4
d: FS(d) = 1 TE(d) = 1 Δg3(d)= 0 e: FS(e) = 0 TE(e) = 1 Δg3](e)= -1
Τώρα επιλέγουμε το d area(A) = 1 + 4 = 5 A = {c,d} , B = {a,b,e}, Fixed = {a,c,b,d}
i = 5
e: FS(e) = 0 TE(e) = 1 Δg3](e)= -1 area(A) = 5+5 = 10 A = {c,d,e} , B = {a,b}, Fixed = {a,c,b,d,e} STOP όλα είναι fixed Ποιο όμως θα επιλέξουμε σαν τελικό? G1 = 1 G2 = 0 G3 = 1 G4 = 1 G5 = 0 αποδεχτά είναι εκείνα με το μεγαλύτερο κέρδος στην περίπτωση μας ένα από τα G1,G3,G4 αλλά ως καλύτερο θεωρητικά το G4 γιατί έχει καλύτερο balance μεταξύ των 2 partitions στην επιφάνεια
|