[Ψηφιακά Ολοκληρωμένα Κυκλώματα VLSI-ASIC] Ανακοινώσεις - Επικαιρότητα 2022-2023

[Thmmy.gr portal]

  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Elearning
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Instagram @thmmy.gr
   mTHMMY
  
  Φοιτητικές Ομάδες
   ACM
   Aristurtle
   ART
   ASAT
   BEAM
   BEST Thessaloniki
   EESTEC LC Thessaloniki
   EΜΒ Auth
   IAESTE Thessaloniki
   IEEE φοιτητικό παράρτημα ΑΠΘ
   SpaceDot
   VROOM
   Panther
  

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

[Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads]

Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ. Βοήθεια για τους καινούργιους μέσω χάρτη.

Κατεβάστε εδώ το Android Application για εύκολη πρόσβαση στο forum.

Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads με προσοχή στα ονόματα των αρχείων!

[Πληροφορίες Καθηγητών]

Πληροφορίες Καθηγητών

[Caterpillar]

Ο Παυλίδης είπε θα λείπει από βδομάδα;

To μάθημα την Δευτέρα θα γίνει. Την τριτη δεν θα γίνει το αναλογικό

[Black Velvet]

Στον αλγόριθμο FM, το FS είναι οι διασυνδέσεις που κόβονται και TE αυτές που δεν κόβονται;
Επίσης (π.χ. διαφάνεια 4 σελ. 23), όταν μία διασύνδεση συνδέει τρεις κόμβους (η Ν2 εδώ), μετράει και στους τρεις; Γιατί σ' αυτό το παράδειγμα την Ν2 δεν την μετράει στον κόμβο a

[Caterpillar]

Στον αλγόριθμο FM, το FS είναι οι διασυνδέσεις που κόβονται και TE αυτές που δεν κόβονται;
Επίσης (π.χ. διαφάνεια 4 σελ. 23), όταν μία διασύνδεση συνδέει τρεις κόμβους (η Ν2 εδώ), μετράει και στους τρεις; Γιατί σ' αυτό το παράδειγμα την Ν2 δεν την μετράει στον κόμβο a

Δεν θυμάμαι τις ονομασίες και ούτε θα τις θυμάμαι ποτέ αλλά για το κέρδος μετακίνησης το λεν? τέλος πάντων κατάλαβες όπως και να το λεν είναι: διασυνδέσεις που κόβονται μειον αυτές που δεν κόβονται  είτε είσαι στον FM είται στον άλλον
 
Ούτε εγώ το έχω καταλάβει αυτό να πω την αλήθεια, ίσως το μόνο που δεν έχω καταλάβει από το μάθημα.

Βασικά κάτσε, κάνε όπισθεν στην σελίδα 21 διαβάσε την, χόνεψέ την και αν καταλάβεις τι γίνεται πες μου και εμένα. γιατί συμφωνα με αυτήν το A(net) = 2 στην περίπτωση μας, αλλά το B(net) = 1, άρα είναι κρισίμη ή δεν είναι? Μας ενδιαφέρει το A(net ) ή το B(net)? Μάλλον το παίρνει μη κρίσιμο, αλλά γιατί αφού  B(νετ) = 1 δεν είναι κρίσιμο?

[Nickgian]

Για το παραδειγμα με τον αλγοριθμο Fiduccia-Muttheyses (FM) pdf Διαχωρισμός_κυκλωμάτω σελιδα 24 εχουμε και λεμε

FS(a) = ο αριθμός των κομμένων nets
TE(a) = ο αριθμός των μη κομμένων nets

Δg(a) = FS(a) - TE(a)

Αρχικά υπολογίζουμε τον περιορισμό
r*area(V) - area_max(V) <= area(V) <= r*area(V) + area_max(V)

area(V) = Το άθροισμα όλων τον επιφανίων για κάθε cell = 16
area_max(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 στην επιφάνεια

[Caterpillar]

i = 1
a: FS(a) = 2 ( N2, N3) TE(a) = 1(N1) Δ_g1(a)= 1

Mόνο που κάτσες και το γραψες όλο αυτό, θα σε πρωτείνω για μέλος του μήνα  

Αλλά το N4 που πήγε ?

To δε βιβλιο που χει πάρει το συγκεκριμένο παράδειγμα λέει αυτό, αλλά δεν έχει το Ν2 που πήγε το N2?

Nets N3 and N4 are cut: FS(a) = 2. Net N1 is connected to a but is not cut: TE(a) = 1.
Δg1(a) = 2 – 1 = 1. The cut size will be reduced if a moves from A to B.

[Caterpillar]

Τελικά η απάντηση για αυτό το katarameno το Ν2, είναι στην σελίδα 19, όπου λέει:

όπου FS(c) είναι ο αριθμός των διασυνδέσεων που συνδέονται στο c αλλά δε συνδέονται σε άλλα κελιά στο διαχωρισμό που ανήκει και TE(c) είναι ο αριθμός των «μη κομμένων» διασυνδέσεων που συνδέονται στο c.
Σε αυτό βέβαια έρχομαι να προσθέσv ότι άν η υπερακμή Ν2 συνδέεται στην περιοχη Α με 2 κόμβους, και ο 3ος είναι στην Β, τότε για τους κόμβους που βρίσκονται στην περιοχή α δεν την μετράμε, ενώ για τον κόμβο που βρίσκεται στην περιοχή Β την μετράμε.
Αν και οι 3 κόμβοι της υπερακμής είναι στο Α, τότε την μετράμε κανονικά (αυτό κατάλαβα τουλάχιστον μέσα από παραδείγματα που είδα).

Επίσης σε αυτό το βίντεο παίζει να τα λεει και έχει και τον ίδιο γράφο (δεν το είδα τελικά γτ μόλις το βρήκα και πήγα να το δω έπεσα  στην κατάλληλη διαφάνεια) https://www.youtube.com/watch?v=r48S44EwsU0

[Black Velvet]

Τελικά η απάντηση για αυτό το katarameno το Ν2, είναι στην σελίδα 19, όπου λέει:

όπου FS(c) είναι ο αριθμός των διασυνδέσεων που συνδέονται στο c αλλά δε συνδέονται σε άλλα κελιά στο διαχωρισμό που ανήκει και TE(c) είναι ο αριθμός των «μη κομμένων» διασυνδέσεων που συνδέονται στο c.
Σε αυτό βέβαια έρχομαι να προσθέσv ότι άν η υπερακμή Ν2 συνδέεται στην περιοχη Α με 2 κόμβους, και ο 3ος είναι στην Β, τότε για τους κόμβους που βρίσκονται στην περιοχή α δεν την μετράμε, ενώ για τον κόμβο που βρίσκεται στην περιοχή Β την μετράμε.
Αν και οι 3 κόμβοι της υπερακμής είναι στο Α, τότε την μετράμε κανονικά (αυτό κατάλαβα τουλάχιστον μέσα από παραδείγματα που είδα).

άρα λες το FS δεν είναι ο αριθμός των κομμένων ακμών, αλλά ο αριθμός των ακμών που ακουμπάνε το a αλλά όχι κάποιο άλλο στο partition A; Δηλαδή η ακμή Ν2 συνδέεται στο a, αλλά συνδέεται και στο b που ανήκει στο Α, άρα δεν την μετράμε στο FS;

[Caterpillar]

άρα λες το FS δεν είναι ο αριθμός των κομμένων ακμών, αλλά ο αριθμός των ακμών που ακουμπάνε το a αλλά όχι κάποιο άλλο στο partition A; Δηλαδή η ακμή Ν2 συνδέεται στο a, αλλά συνδέεται και στο b που ανήκει στο Α, άρα δεν την μετράμε στο FS;

Ναι.

Αν κάνεις 2ο πέρασμα στον αλγόριθμο, τότε σε κάποια φάση θα είναι και οι τρεις κόμβοι στο Α, τότε θα την μετρήσεις την Ν2 κανονικά σαν μην κομένη. Κάνε το 2ο πέρασμα (το χει σαν άλυτη άσκηση  στο βιβλιο που χρησιμοποιεί στις διαφάνειες για να το συγκρίνεις, οι λύσεις των ασκήσεων υπάρχουν στο τέλος του βιβλιου για καλή μας τύχη).

[Black Velvet]

Αν κάνεις 2ο πέρασμα στον αλγόριθμο, τότε σε κάποια φάση θα είναι και οι τρεις κόμβοι στο Α, τότε θα την μετρήσεις την Ν2 κανονικά σαν μην κομένη. Κάνε το 2ο πέρασμα (το χει σαν άλυτη άσκηση  στο βιβλιο που χρησιμοποιεί στις διαφάνειες για να το συγκρίνεις, οι λύσεις των ασκήσεων υπάρχουν στο τέλος του βιβλιου για καλή μας τύχη).

Στο δεύτερο πέρασμα το αποτέλεσμα είναι Α = {e} και B = {a, b, c, d};;;;

(Πάντως στο δεύτερο βήμα, αν ακολουθήσουμε τις οδηγίες απ'τις διαφάνειες, τον κόμβο e δεν θα έπρεπε να τον ανανεώσουμε, αφού δεν συνδέεται με κρίσιμη διασύνδεση με τον c που μετακινήσαμε στο προηγούμενο βήμα. Το λέω γιατί μου φαίνεται περίεργο. Εκτός αν σε κάποιο άλλο βήμα πιο κάτω ανανεώνεται ο e και καταλήγει στο Α.)

[Caterpillar]

Στο δεύτερο πέρασμα το αποτέλεσμα είναι Α = {e} και B = {a, b, c, d};;;;

Σωστά.

(Πάντως στο δεύτερο βήμα, αν ακολουθήσουμε τις οδηγίες απ'τις διαφάνειες, τον κόμβο e δεν θα έπρεπε να τον ανανεώσουμε, αφού δεν συνδέεται με κρίσιμη διασύνδεση με τον c που μετακινήσαμε στο προηγούμενο βήμα. Το λέω γιατί μου φαίνεται περίεργο. Εκτός αν σε κάποιο άλλο βήμα πιο κάτω ανανεώνεται ο e και καταλήγει στο Α.)

Ναι δεν το ενημερώνεις το e, αλλά και να το ενημερώσεις αλλάζει κάτι στο κέρδος μετακίνησης του e? Όχι, -1 ήταν -1 θα το βρεις πάλι.
Εγώ πάντως για να μην μπλέκω με όλα αυτά ενημερώνω κάθε φορά όλους τους μη κλειδωμένους κόμβους. (όσοι δεν χρειαζόταν ενημέρωση, το ίδιο κέρδος μετακίνησης θα έχουν πάλι_ )

[Caterpillar]

Επίσης τωρα που το βλεπω στο 2ο περασμα 2ο βήμα ο e μετακινείτε με κέρδος -1 γιατί αν φύγει από το A ο d που χει θετικο κερδος (2), τότε θα μείνει άδειο το Α.

[Black Velvet]

Επίσης τωρα που το βλεπω στο 2ο περασμα 2ο βήμα ο e μετακινείτε με κέρδος -1 γιατί αν φύγει από το A ο d που χει θετικο κερδος (2), τότε θα μείνει άδειο το Α.

ναι αυτό βασικά, αν δεν είχαμε ανανεώσει το κέρδος του δεν θα μετακινούταν και ίσως έβγαινε άλλο αποτέλεσμα. Οπότε ανανεώνουμε όλους τους κόμβους κανονικά;

Επίσης, στο floorplan, εκεί που βγάζει απ'τους γράφους τα S+ και S-. Πρέπει να είναι ίδια για το κάθετο και οριζόντιο; Επίσης π.χ. για το κάθετο, κόμβοι που είναι "δίπλα", έχει διαφορά με τι σειρά θα τους βάλουμε στα S;
Δηλαδή π.χ. στην σελ.21, αν το S+ ήταν abcde;

[Caterpillar]

ναι αυτό βασικά, αν δεν είχαμε ανανεώσει το κέρδος του δεν θα μετακινούταν και ίσως έβγαινε άλλο αποτέλεσμα. Οπότε ανανεώνουμε όλους τους κόμβους κανονικά;

Μα το e ήδη το ενημερώνεις μια φορά στο 1ο βήμα του 2ου περάσματος, και ειναι -1.  Στο 1ο βημα καθε περασματος τα εμημερωνουμε ολα. (καλά και σε καθε βημα αν τα ενημερωνεις ολα δεν εγινε και τπτ, το ιδιο κερδος θα χουν παλι οπως ειπα).
edit Επισης αν θυμάμαι καλα το σχημα, το e παιζει να ναι -1 ήδη απο το 1ο πέρασμα άρα να μην θέλει ενημέρωση. Αν και ειπαμε τα ενημενουμε ολα για να χουμε το κεφαλι μας ησυχο


Θα επανέλθω το απογευμα για το άλλο, αν θες νωριτερα ανεβασε φωτό.

[Caterpillar]

Επίσης, στο floorplan, εκεί που βγάζει απ'τους γράφους τα S+ και S-. Πρέπει να είναι ίδια για το κάθετο και οριζόντιο; Επίσης π.χ. για το κάθετο, κόμβοι που είναι "δίπλα", έχει διαφορά με τι σειρά θα τους βάλουμε στα S;
Δηλαδή π.χ. στην σελ.21, αν το S+ ήταν abcde;

Στην ουσία δεν τα βγάζεις από τους γραφους αυτα αλλά απο την κατοψη. Επομενως ναι αφου η κατοψη ειναι ίδια για τον οριζοντιο και καταγράφο γράφο ίδια θα ναι και αυτά.
Αυτο που λες θα ταν καπως ετσι

[Caterpillar]

Πολύ STA ρε παιδί μου, ούτε ένας γράφος