Advcomparch

advcomparch@lists.cslab.ece.ntua.gr

1109 discussions

Απορίες
by George Matikas 01 Jul '13

01 Jul '13

Ευχαριστώ πολύ για την άμεση απάντηση στο προηγούμενο mail μου! Καθώς συνέχιζα το διάβασμα μου προέκυψαν μερικές απορίες ακόμη. Τις παραθέτω εδώ, ώστε αν βρείτε χρόνο να με βοηθήσετε και με αυτές: 1) Στις διαφάνειες "Lec1-overview-13" στη σελίδα 41, αναφέρει ότι υπάρχει το ενδεχόμενο να εμφανιστεί structural hazard λόγω ταυτόχρονης εγγραφής του register file στο στάδιο WB. Ωστόσο, πιστεύω ότι αυτό δεν είναι εφικτό, αφού πάντα πριν το στάδιο WB βρίσκεται στο pipeline του παραδείγματος το στάδιο MEM. Άρα θα έχουμε εκεί structural hazard και επομένως stall και δεν θα συμπέσουν ποτέ 2 WB στάδια. 2) Απλά επειδή θέλω να βεβαιωθώ ότι το έχω καταλάβει σωστά, capacity misses έχουμε μόνο σε fully-associative cache, ενώ σε direct-mapped και 2/4-way set- associative caches έχουμε μόνο conflict misses, έτσι; (εννοώ πέραν των compulsory και coherence misses). 3) Στο θέμα 1Β του Ιουλίου 2012 αναφέρει στη λύση ότι ο μέγιστος αριθμός physical register πρέπει να είναι <= Ν+Κ. Στις διαφάνειες όμως αναφέρει, επίσης, ότι θα πρέπει να έχουμε τουλάχιστον τόσα Reservation Stations όσοι οι φυσικοί καταχωρητές ("Lec5-dynamic-13" σελίδα 15). Οπότε δεν θα έπρεπε να λάβουμε υπόψην μας και αυτό; Πχ κάτι της μορφής: physical registers <= min( N+K , M ); Ευχαριστώ και πάλι, Ματίκας Γεώργιος

2 1

Re: [Advcomparch] Relaxed models και αναδιάταξη εντολών.
by Konstantinos Nikas 01 Jul '13

01 Jul '13

Καλησπέρα, πουθενά στο μάθημα ή στις διαφάνειες δεν αφήνουμε να εννοηθεί ότι επιτρέπονται και αναδιατάξεις οι οποίες δε σέβονται τα data dependencies. Επαναλαμβάνω και την αντιστοιχία με έναν out-of-order επεξεργαστή και το πότε επιτρέπεται το out-of-order execution των εντολών μνήμης. Σε καμία περίπτωση δε χρειάζεται barrier για να εκτελέσει σωστά ένα thread το flag=1 print flag που αναφέρεις. Τα barriers δίνονται ως εργαλεία τα οποία διασφαλίζουν ότι όλα τα threads θα δουν τις εγγραφές με τη σειρά που επιθυμεί ο προγραμματιστής και όχι με κάποια άλλη. Tα relaxed memory order models έχουν σα σκοπό να μειώσουν τα miss latencies, επιτρέποντας να εκτελεστούν εκτός σειράς εντολές μνήμης όσο εξυπηρετείται κάποιο miss. Διατηρώντας όμως πάντα τα data dependencies. K. 2013/7/1 el09004 <el09004(a)mail.ntua.gr>: > On Mon, 1 Jul 2013 17:08:26 +0300, Konstantinos Nikas wrote: >> >> Καλησπέρα, >> >> από ότι καταλαβαίνω έχει δημιουργηθεί >> μια παρεξήγηση όσον αφορά την >> αναδιάταξη των εντολών. >> >> Η αναδιάταξη λοιπόν των εντολών >> μνήμης επιτρέπεται καταρχάς εφόσον >> δεν επηρεάζονται τα data dependencies. Για να >> κατανοήσετε καλύτερα το τί γίνεται, >> φανταστείτε έναν out-of-order επεξεργαστή, >> στα LD/ST queues του οποίου μπαίνουν οι >> αντίστοιχες εντολές μνήμης. Είναι >> προφανές, ότι τυχόν αναδιάταξη μπορεί >> να αφορά μόνο εντολές που είναι >> έτοιμες να εκτελεστούν (να πάνε στη >> μνήμη)! Έτσι στην περίπτωση: >> >> lw r4, 0(r8) >> sw r4, 0(r9) >> >> η 2η εντολή ποτέ δε θα είναι έτοιμη >> πριν εκτελεστεί η πρώτη και άρα δεν >> πρόκειται να αναδιαταχθεί. Για τις >> εντολές τώρα που είναι έτοιμες να πάνε >> στη μνήμη, η αναδιάταξη επιτρέπεται >> μόνο μεταξύ αυτών που πηγαίνουν σε >> διαφορετική θέση της μνήμης. Δηλαδή >> στον κώδικα: >> >> sw r1, 0(r8) >> sw r2, 0(r8) >> >> δεν επιτρέπεται η αναδιάταξη. >> >> Όσον αφορά τα control dependencies τα πράγματα >> δεν είναι απόλυτα ξεκάθαρα, μιας και >> δεν εξαρτώνται από το memory model αλλά από >> την υλοποίηση σε κάθε επεξεργαστή. π.χ. >> για τον κώδικα: >> >> while (flag == 0) continue; >> assert (x == 1); >> >> o Power επεξεργαστής σέβεται το control >> dependence και δεν επιτρέπει την >> αναδιάταξη (βάζοντας ένα implicit barrier >> ανάμεσα στις 2 εντολές) ενώ ο ARM δεν το >> σέβεται και μπορεί να αναδιατάξει τις >> εντολές (κάτι που ισχύει και στα >> περισσότερα σύγχρονα συστήματα). >> Εμείς γενικά θεωρούμε ότι ισχύει το 2ο, >> δηλαδή στον κώδικα >> >> while (flag == 0) ; >> print A; >> >> μπορεί να υπάρξει αναδιάταξη. >> Σκεφτείτε το πάλι ως εξής. Έχετε έναν >> οut-of-order processor, ο οποίος κάνει branch predicition >> και "τυχαίνει" το prediction να λέει ότι το >> branch θα είναι NT (δε θα εκτελεστεί δηλαδή >> ξανά το loop). Αυτό έχει σαν αποτέλεσμα >> να μπαίνουν κάθε φορά στο LD queue τα load >> flag, load A τα οποία και μπορούν να >> αναδιαταχθούν μιας και πάνε σε >> διαφορετικές διευθύνσεις. Προφανώς σε >> κάθε λάθος prediction, κάνεις flush το LD queue, >> όταν όμως το prediction στο τελευταίο iteration >> θα είναι σωστό, τότε μπορεί να έχει >> διαβαστεί το A πριν να διαβάσεις ότι >> flag!=0. >> >> Κ. >> >> 2013/7/1 Σαρρής θεόδωρος >> >>> Γεια σας. Με ποιο τρόπο σέβεται ο >>> επεξεργαστής τα data και control dependecies; >>> Γιατί αν σέβεται τα data hazards πρέπει σε >>> ένα (1a)A=1 (1b)Print A να μην θεωρούμε εφικτό >>> 1b->1a γιατί είναι RAW hazard. Ομοίως για τα >>> control dependecies (1a)While (A==0) ; (1b)Print A πρέπει να >>> μην θεωρούμε εφικτό 1b->1a. Από τις >>> διαφάνειες και τα παλιά θέματα εγώ >>> έχω καταλάβει ότι στα δύο >>> παραδείγματα που ανέφερα το RMO >>> επιτρέπει αυτές τις αναδιατάξεις. >>> Ευχαριστώ, >>> Σαρρής Θεόδωρος >>> >>> On Mon, 1 Jul 2013 15:04:40 +0300, Konstantinos Nikas wrote: >>> >>>> Καλησπέρα, >>>> >>>> Στο συγκεκριμένο παράδειγμα που >>>> αναφέρεις, το block παραμένει στο Ι >>>> παρά >>>> το PrWr γιατί η cache είναι write-no-allocate. >>>> Δηλαδή αν κάνει write miss, δεν κάνει >>>> allocate >>>> το block στην cache. >>>> >>>> Για το δεύτερο ερώτημα, καταρχάς >>>> αναφερόμαστε σε κάποιο από τα >>>> μοντέλα >>>> που παρουσιάστηκαν στο μάθημα. Κατά >>>> δεύτερον, τα consistency models ασχολούνται >>>> μόνο με τη σειρά των memory εντολών. Οι >>>> τυχόν αναδιατάξεις των υπόλοιπων >>>> εντολών είναι θέμα του επεξεργαστή >>>> και δεν έχει σχέση με το >>>> coherence/consistency. >>>> >>>> Βέβαια, ακόμα και το πλέον relaxed memory >>>> order, >>>> δε σημαίνει ότι επιτρέπονται όλες >>>> οι >>>> πιθανές αναδιατάξεις. Μη ξεχνάτε >>>> ότι ο >>>> επεξεργαστής εξακολουθεί και >>>> σέβεται >>>> τα data και control dependencies! >>>> >>>> Κ. >>>> >>>> 2013/6/29 Ανδρέας Παντελόπουλος >>>> >>>>> Καλησπέρα,στο FSM του simple V/I protocol >>>>> (διαφ.30) παρατηρώ ότι με PrWr στην Ι >>>>> ξαναγυρνάει στην κατάσταση Ι. >>>>> Κανονικά δεν θα έπρεπε να γίνεται >>>>> μετάβαση στην κατάσταση V ? >>>>> >>>>> Επίσης,στην θεωρητική άσκηση της >>>>> 3ης >>>>> σειράς αναφέρεστε στο "πλέον relaxed >>>>> memory >>>>> order".Τι σημαίνει αυτό ακριβώς? Στην >>>>> ουσία οποιαδήποτε αναδιάταξη >>>>> εντολών ή αναδιάταξη εντολών που >>>>> επιτελούν λειτουργίες μνήμης ? >>>>> >>>>> Ευχαριστώ πολύ. >>>>> _______________________________________________ >>>>> Advcomparch mailing list >>>>> Advcomparch(a)lists.cslab.ece.ntua.gr [1] [1] >>>>> http://lists.cslab.ece.ntua.gr/mailman/listinfo/advcomparch [2] >>>>> [2] >>>> >>>> >>>> -- >>>> Dr. Konstantinos Nikas >>>> Computing Systems Laboratory >>>> School of Electrical and Computer Engineering >>>> National Technical University of Athens >>>> >>>> Tel: +30-210-7724159 [3] >>>> e-mail: knikas(a)cslab.ece.ntua.gr [4] [4] >>>> http://www.cslab.ece.ntua.gr/~knikas [5] [5] >>>> >>>> Links: >>>> ------ >>>> [1] mailto:Advcomparch@lists.cslab.ece.ntua.gr [6] >>>> [2] http://lists.cslab.ece.ntua.gr/mailman/listinfo/advcomparch >>>> [7] >>>> [3] mailto:padelopoulos@gmail.com [8] >>>> [4] mailto:knikas@cslab.ece.ntua.gr [9] >>>> [5] http://www.cslab.ece.ntua.gr/~knikas [10] >>> >>> >>> _______________________________________________ >>> Advcomparch mailing list >>> Advcomparch(a)lists.cslab.ece.ntua.gr [11] >>> http://lists.cslab.ece.ntua.gr/mailman/listinfo/advcomparch [12] >> >> >> -- >> Dr. Konstantinos Nikas >> Computing Systems Laboratory >> School of Electrical and Computer Engineering >> National Technical University of Athens >> >> Tel: +30-210-7724159 >> e-mail: knikas(a)cslab.ece.ntua.gr [14] >> http://www.cslab.ece.ntua.gr/~knikas [15] >> >> Links: >> ------ >> [1] mailto:Advcomparch@lists.cslab.ece.ntua.gr >> [2] http://lists.cslab.ece.ntua.gr/mailman/listinfo/advcomparch >> [3] http://webmail.ntua.gr/tel:%2B30-210-7724159 >> [4] mailto:knikas@cslab.ece.ntua.gr >> [5] http://www.cslab.ece.ntua.gr/~knikas >> [6] mailto:Advcomparch@lists.cslab.ece.ntua.gr >> [7] http://lists.cslab.ece.ntua.gr/mailman/listinfo/advcomparch >> [8] mailto:padelopoulos@gmail.com >> [9] mailto:knikas@cslab.ece.ntua.gr >> [10] http://www.cslab.ece.ntua.gr/~knikas >> [11] mailto:Advcomparch@lists.cslab.ece.ntua.gr >> [12] http://lists.cslab.ece.ntua.gr/mailman/listinfo/advcomparch >> [13] mailto:el09148@mail.ntua.gr >> [14] mailto:knikas@cslab.ece.ntua.gr >> [15] http://www.cslab.ece.ntua.gr/~knikas > > > > Αν κατάλαβα καλά, αυτό που λέτε είναι ότι απαγορεύεται η αναδιάταξη όταν > έχουμε RAW hazard και όταν έχουμε WAW dependency στην ίδια θέση μνήμης. Όμως > η όλη λογική των weak ordering models δεν είναι να τα επιτρέπουν όλα αυτά > και απλά να περνάνε το βάρος στο προγραμματιστή ώστε να βάζει τα κατάλληλα > barriers? > > Παράδειγμα, αν έχουμε > flag = 1; > print flag; > που είναι read after write και έχουμε και το πλέον relaxed memory model, οι > εντολές δεν μπορούν να αναδιαταχθούν? > Ευχαριστώ! > > -- > Δανασής Παναγιώτης > Εθνικό Μετσόβιο Πολυτεχνείο > Σχολή Ηλεκτρολόγων Μηχανικών Και Μηχανικών Υπολογιστών > _______________________________________________ > Advcomparch mailing list > Advcomparch(a)lists.cslab.ece.ntua.gr > http://lists.cslab.ece.ntua.gr/mailman/listinfo/advcomparch -- Dr. Konstantinos Nikas Computing Systems Laboratory School of Electrical and Computer Engineering National Technical University of Athens Tel: +30-210-7724159 e-mail: knikas(a)cslab.ece.ntua.gr http://www.cslab.ece.ntua.gr/~knikas

1 0

Relaxed models και αναδιάταξη εντολών.
by Konstantinos Nikas 01 Jul '13

01 Jul '13

Καλησπέρα, από ότι καταλαβαίνω έχει δημιουργηθεί μια παρεξήγηση όσον αφορά την αναδιάταξη των εντολών. Η αναδιάταξη λοιπόν των εντολών μνήμης επιτρέπεται καταρχάς εφόσον δεν επηρεάζονται τα data dependencies. Για να κατανοήσετε καλύτερα το τί γίνεται, φανταστείτε έναν out-of-order επεξεργαστή, στα LD/ST queues του οποίου μπαίνουν οι αντίστοιχες εντολές μνήμης. Είναι προφανές, ότι τυχόν αναδιάταξη μπορεί να αφορά μόνο εντολές που είναι έτοιμες να εκτελεστούν (να πάνε στη μνήμη)! Έτσι στην περίπτωση: lw r4, 0(r8) sw r4, 0(r9) η 2η εντολή ποτέ δε θα είναι έτοιμη πριν εκτελεστεί η πρώτη και άρα δεν πρόκειται να αναδιαταχθεί. Για τις εντολές τώρα που είναι έτοιμες να πάνε στη μνήμη, η αναδιάταξη επιτρέπεται μόνο μεταξύ αυτών που πηγαίνουν σε διαφορετική θέση της μνήμης. Δηλαδή στον κώδικα: sw r1, 0(r8) sw r2, 0(r8) δεν επιτρέπεται η αναδιάταξη. Όσον αφορά τα control dependencies τα πράγματα δεν είναι απόλυτα ξεκάθαρα, μιας και δεν εξαρτώνται από το memory model αλλά από την υλοποίηση σε κάθε επεξεργαστή. π.χ. για τον κώδικα: while (flag == 0) continue; assert (x == 1); o Power επεξεργαστής σέβεται το control dependence και δεν επιτρέπει την αναδιάταξη (βάζοντας ένα implicit barrier ανάμεσα στις 2 εντολές) ενώ ο ARM δεν το σέβεται και μπορεί να αναδιατάξει τις εντολές (κάτι που ισχύει και στα περισσότερα σύγχρονα συστήματα). Εμείς γενικά θεωρούμε ότι ισχύει το 2ο, δηλαδή στον κώδικα while (flag == 0) ; print A; μπορεί να υπάρξει αναδιάταξη. Σκεφτείτε το πάλι ως εξής. Έχετε έναν οut-of-order processor, ο οποίος κάνει branch predicition και "τυχαίνει" το prediction να λέει ότι το branch θα είναι NT (δε θα εκτελεστεί δηλαδή ξανά το loop). Αυτό έχει σαν αποτέλεσμα να μπαίνουν κάθε φορά στο LD queue τα load flag, load A τα οποία και μπορούν να αναδιαταχθούν μιας και πάνε σε διαφορετικές διευθύνσεις. Προφανώς σε κάθε λάθος prediction, κάνεις flush το LD queue, όταν όμως το prediction στο τελευταίο iteration θα είναι σωστό, τότε μπορεί να έχει διαβαστεί το A πριν να διαβάσεις ότι flag!=0. Κ. 2013/7/1 Σαρρής θεόδωρος <el09148(a)mail.ntua.gr> > Γεια σας. Με ποιο τρόπο σέβεται ο επεξεργαστής τα data και control > dependecies; Γιατί αν σέβεται τα data hazards πρέπει σε ένα (1a)A=1 > (1b)Print A να μην θεωρούμε εφικτό 1b->1a γιατί είναι RAW hazard. Ομοίως > για τα control dependecies (1a)While (A==0) ; (1b)Print A πρέπει να μην > θεωρούμε εφικτό 1b->1a. Από τις διαφάνειες και τα παλιά θέματα εγώ έχω > καταλάβει ότι στα δύο παραδείγματα που ανέφερα το RMO επιτρέπει αυτές τις > αναδιατάξεις. > Ευχαριστώ, > Σαρρής Θεόδωρος > > > On Mon, 1 Jul 2013 15:04:40 +0300, Konstantinos Nikas wrote: > >> Καλησπέρα, >> >> Στο συγκεκριμένο παράδειγμα που >> αναφέρεις, το block παραμένει στο Ι παρά >> το PrWr γιατί η cache είναι write-no-allocate. >> Δηλαδή αν κάνει write miss, δεν κάνει allocate >> το block στην cache. >> >> Για το δεύτερο ερώτημα, καταρχάς >> αναφερόμαστε σε κάποιο από τα μοντέλα >> που παρουσιάστηκαν στο μάθημα. Κατά >> δεύτερον, τα consistency models ασχολούνται >> μόνο με τη σειρά των memory εντολών. Οι >> τυχόν αναδιατάξεις των υπόλοιπων >> εντολών είναι θέμα του επεξεργαστή >> και δεν έχει σχέση με το coherence/consistency. >> >> Βέβαια, ακόμα και το πλέον relaxed memory order, >> δε σημαίνει ότι επιτρέπονται όλες οι >> πιθανές αναδιατάξεις. Μη ξεχνάτε ότι ο >> επεξεργαστής εξακολουθεί και σέβεται >> τα data και control dependencies! >> >> Κ. >> >> 2013/6/29 Ανδρέας Παντελόπουλος >> >> Καλησπέρα,στο FSM του simple V/I protocol >>> (διαφ.30) παρατηρώ ότι με PrWr στην Ι >>> ξαναγυρνάει στην κατάσταση Ι. >>> Κανονικά δεν θα έπρεπε να γίνεται >>> μετάβαση στην κατάσταση V ? >>> >>> Επίσης,στην θεωρητική άσκηση της 3ης >>> σειράς αναφέρεστε στο "πλέον relaxed memory >>> order".Τι σημαίνει αυτό ακριβώς? Στην >>> ουσία οποιαδήποτε αναδιάταξη >>> εντολών ή αναδιάταξη εντολών που >>> επιτελούν λειτουργίες μνήμης ? >>> >>> Ευχαριστώ πολύ. >>> ______________________________**_________________ >>> Advcomparch mailing list >>> Advcomparch(a)lists.cslab.ece.**ntua.gr<Advcomparch(a)lists.cslab.ece.ntua.gr>[1] >>> http://lists.cslab.ece.ntua.**gr/mailman/listinfo/**advcomparch<http://lists.cslab.ece.ntua.gr/mailman/listinfo/advcomparch>[2] >>> >> >> -- >> Dr. Konstantinos Nikas >> Computing Systems Laboratory >> School of Electrical and Computer Engineering >> National Technical University of Athens >> >> Tel: +30-210-7724159 >> e-mail: knikas(a)cslab.ece.ntua.gr [4] >> http://www.cslab.ece.ntua.gr/~**knikas<http://www.cslab.ece.ntua.gr/~knikas>[5] >> >> Links: >> ------ >> [1] mailto:Advcomparch@lists.**cslab.ece.ntua.gr<Advcomparch(a)lists.cslab.ece.ntua.gr> >> [2] http://lists.cslab.ece.ntua.**gr/mailman/listinfo/**advcomparch<http://lists.cslab.ece.ntua.gr/mailman/listinfo/advcomparch> >> [3] mailto:padelopoulos@gmail.com >> [4] mailto:knikas@cslab.ece.ntua.**gr <knikas(a)cslab.ece.ntua.gr> >> [5] http://www.cslab.ece.ntua.gr/~**knikas<http://www.cslab.ece.ntua.gr/~knikas> >> > > ______________________________**_________________ > Advcomparch mailing list > Advcomparch(a)lists.cslab.ece.**ntua.gr<Advcomparch(a)lists.cslab.ece.ntua.gr> > http://lists.cslab.ece.ntua.**gr/mailman/listinfo/**advcomparch<http://lists.cslab.ece.ntua.gr/mailman/listinfo/advcomparch> > -- Dr. Konstantinos Nikas Computing Systems Laboratory School of Electrical and Computer Engineering National Technical University of Athens Tel: +30-210-7724159 e-mail: knikas(a)cslab.ece.ntua.gr http://www.cslab.ece.ntua.gr/~knikas

2 1

Υλοποίηση lock
by Lambros Flokas 01 Jul '13

01 Jul '13

Έχω μια απορία για την υλοποίηση της lock.Δυστυχώς μετά από αρκετές προσομοιώσεις κατάλαβα ότι κάτι πήγαινε λάθος με την υλοποίηση μου και το επιβεβαίωσα με το DDEBUG του locks_scalability.Το πρόβλημα είναι ότι ακόμα δεν είμαι σίγουρος γιατί είναι λάθος η υλοποίηση και δεν μπορώ πλέον να αντιληφθώ πως θα κάνουμε χρήση της compare and swap (προσπάθησα να βρω εναλλακτικές εντολές του gcc αλλά αν και δούλευαν στο debug έλεγαν ότι έχουν κάποιους περιορισμούς οπότε τις άφησα) Η υλοποίηση μου βασιζόταν στο εξής : Η compare and swap κάνει swap μόνο όταν το lock είναι oldval αλλά εμείς στο test and set θέλουμε να κάνουμε set κάθε φορά έτσι κι αλλιώς οπότε σκέφτηκα να του δώσω σαν oldval την ίδια την τιμή του lock δηλαδή *lock. Το μόνο που μπορώ να σκεφτώ είναι ότι το *lock παίρνει την τιμή από την cache ή κάποια μη τρέχουσα τιμή(αν και αμφιβάλλω αφού δηλώνουμε το lock volatile) και συγκρίνεται με την πρόσφατη τιμή στη μνήμη που είναι διαφορετική.Τότε αν είναι locked στην cache και unlocked στη μνήμη τότε τερματίζει η acquire lock αλλά δεν κλειδώνουμε με αποτέλεσμα ο επόμενος να το βρίσκει ξεκλείδωτο οπότε να μπαίνει και αυτός στην κρίσιμη περιοχή. Δεν ξέρω αν η παραπάνω είναι η σωστή εξήγηση οπότε μια επιβεβαίωση/διόρθωση είναι ευπρόσδεκτη. Αυτό που δεν καταλαβαίνω είναι πώς θα μετατρέψω την compare and swap σε μια απλή ατομική εντολή set.Ίσως μπορεί κάποιος να δώσει καμιά ιδέα Επίσης μια ακόμη ερώτηση είναι αν το release πρέπει να γίνει και αυτό ατομικά ή όχι και αν ναι γιατί; Ευχαριστώ πολύ εκ των προτέρων, Λάμπρος Φλόκας

2 2

Re: [Advcomparch] Απορία για προτεραιότητα αντικατάστασης ενός Invalid Block
by Konstantinos Nikas 01 Jul '13

01 Jul '13

Καλησπέρα, γενικά στην υλοποίηση της LRU (αλλά και των υπόλοιπων πολιτικών αντικατάστασης) πρέπει να δίνεται προτεραιότητα στα invalid blocks. Δηλαδή, όταν ψάχνουμε να διώξουμε κάποιο block για να φέρουμε ένα καινούριο πρώτα κοιτάμε αν υπάρχει κάποιο άδειο (invalid) και αν δε βρούμε ψάχνουμε το LRU (ή όποιο ορίζει η πολιτική). Στο συγκεκριμένο θέμα που αναφέρεις, επειδή δεν είχε εξηγηθεί και δημιουργήθηκε μπέρδεμα, θεωρήθηκε τελικά ότι η πολιτική δεν ψάχνει τα invalid αλλά κοιτά μόνο τα LRU. Προφανώς, εσείς μπορείτει να κοιτάτε πρώτα για invalid. Κ. 2013/7/1 Dimitris <tartoufo1973(a)gmail.com>: > Έχω την εξής απορία για την περίπτωση του MESI cache coherence protocol με > associative cache. Όταν ένα μπλοκ γίνεται Invalid, η LRU προτεραιότητά του > αλλάζει ή όχι. Δηλαδή ένα invalid block είναι το πρώτο υποψήφιο προς > αντικατάσταση σε κάποιο conflict; > > Παράδειγμα: Θέματα εξετάσεων Ιουλίου 2012, Θέμα 4ο: > > Στην αίτηση του P0 για s[0].x το block της cache του P1 που περιέχει > s[0].x....s[1].x γίνεται invalid. Το ίδιο set περιέχει επιπλέον το > b[0]...b[3] > Παρακάτω στην αίτηση του P1 για a[1] ποιο block θα αντικατασταθεί; (αν το > invalid block είναι το πρώτο υποψήφιο θα αντικατασταθεί αυτό). > Πιο κάτω ο P1 κάνει αίτηση για το b[1]. Έχουμε hit ή miss; (αν > αντικαταστάθηκε όντως το invalid block θα έχουμε hit). > > > Ευχαριστώ. > > _______________________________________________ > Advcomparch mailing list > Advcomparch(a)lists.cslab.ece.ntua.gr > http://lists.cslab.ece.ntua.gr/mailman/listinfo/advcomparch > -- Dr. Konstantinos Nikas Computing Systems Laboratory School of Electrical and Computer Engineering National Technical University of Athens Tel: +30-210-7724159 e-mail: knikas(a)cslab.ece.ntua.gr http://www.cslab.ece.ntua.gr/~knikas

1 0

Απορία για προτεραιότητα αντικατάστασης ενός Invalid Block
by Dimitris 01 Jul '13

01 Jul '13

Έχω την εξής απορία για την περίπτωση του MESI cache coherence protocol με associative cache. Όταν ένα μπλοκ γίνεται Invalid, η LRU προτεραιότητά του αλλάζει ή όχι. Δηλαδή ένα invalid block είναι το πρώτο υποψήφιο προς αντικατάσταση σε κάποιο conflict; Παράδειγμα: Θέματα εξετάσεων Ιουλίου 2012, Θέμα 4ο:<http://www.cslab.ece.ntua.gr/courses/advcomparch/2012/files/exams/adv_ca-Ju…> - Στην αίτηση του P0 για s[0].x το block της cache του P1 που περιέχει s[0].x....s[1].x γίνεται invalid. Το ίδιο set περιέχει επιπλέον το b[0]...b[3] - Παρακάτω *στην αίτηση του P1 για a[1] ποιο block θα αντικατασταθεί*; (αν το invalid block είναι το πρώτο υποψήφιο θα αντικατασταθεί αυτό). - Πιο κάτω *ο P1 κάνει αίτηση για το b[1]. Έχουμε hit ή miss*; (αν αντικαταστάθηκε όντως το invalid block θα έχουμε hit). Ευχαριστώ.

1 0

Εκτέλεση σε πραγματικό σύστημα και πλήθος thread
by Lambros Flokas 01 Jul '13

01 Jul '13

Στην εκφώνηση λέτε να χρησιμοποιήσουμε τους ίδιους αριθμούς νημάτων με τις προσομοιώσεις.Παρατηρώ όμως ότι αν δοκιμάσω για περισσότερα νήματα από ότι πυρήνες στο vm μου βγάζει το ακόλουθο μήνυμα Error in pthread_setaffinity_np. Αυτό μου φαίνεται πολύ λογικό αφού η αντιστοίχιση νημάτων και πυρήνων γίνεται όπως λέει και η εκφώνηση 1 προς 1 . Απλά ρωτάω για επιβεβαίωση κυρίως, αν θα τρέξουμε τις προσομοιώσεις μέχρι το πλήθος πυρήνων του vm ή αν κάνω εγώ κάτι λάθος. Σας ευχαριστώ εκ των προτέρων Λάμπρος Φλόκας

2 3

Re: [Advcomparch] Απορίες
by Konstantinos Nikas 01 Jul '13

01 Jul '13

Καλησπέρα, 1α)Καταρχάς flush δε σημαίνει ότι ενημερώνω την κύρια μνήμη, αλλά ότι γράφω τα περιεχόμενα του block στο bus. Όπως εξήγησα και στο μάθημα έχει να κάνει με την υλοποίηση του MESI και το αν επιτρέπονται τα cache-to-cache transfers ή όχι. Αν δηλαδή όταν μια cache ζητήσει να διαβάσει/γράψει ένα block, τα δεδομένα θα έρθουν από την κύρια μνήμη ή μπορεί να τα δώσει και μια άλλη cache που έχει το block (σε Ε ή S). Αντίστοιχα, η διαφορά του flush με το flush' εντοπίζεται πάλι στην υλοποίηση και έχει να κάνει με το πότε ενημερώνεται η κύρια μνήμη. 1b) Όχι. Δεν προκύπτει από κάπου ότι ενημερώνεται η κύρια μνήμη. Για αυτό το λόγο υπάρχει και η SM κατάσταση, ώστε όταν η cache που έχει αυτό το block το κάνει evict να πάει να το γράψει και στην κύρια μνήμη. Κοινώς η κύρια μνήμη εδώ ενημερώνεται μόνο μέσω evicts. 2) Σε write-back caches ναι, σε write-through θα ήταν όπως είναι στη διαφάνεια. Έχεις δίκιο απλά είχε χρησιμοποιηθεί το σχήμα από τις αντίστοιχες διαφάνειες του coherence όπου υποθέταμε write-through caches. K. 2013/7/1 George Matikas <g_matikas(a)hotmail.com> > Γεια σας! > > Καθώς διάβαζα τις διαφάνειες για να προετοιμαστώ για την αυριανή εξέταση > μου γεννήθηκαν κάποιες απορίες. Θα μπορούσατε να με βοηθήσετε να λύσω τις > απορίες μου αυτές; > > 1α. Στις διαφάνειες "Lec8-coherence-13" στη σελίδα 39, που αναφέρει για το > πρωτόκολλο MESI, γιατί πρέπει να γίνει Flush στις μεταβάσεις Ε->S, Ε->Ι, > S->S, S->I; Δεν υποτίθεται ότι στις καταστάσεις Ε και S η κύρια μνήμη είναι > ήδη ενημερωμένη με τα δεδομένα της συγκεκριμένης cache; Άρα δεν υπάρχει > λόγος να γράψουμε τα ίδια δεδομένα πάλι... Επίσης, τι διαφορά έχει το > Flush' με το Flush; > 1β. Στις ίδιες διαφάνειες, στη σελίδα 44, που αναφέρει για το πρωτόκολλο, > όταν βρισκόμαστε στην κατάσταση SM και έρθει σήμα BusRd (οπότε γίνεται > Flush) για ποιο λόγο παραμένουμε στην ίδια κατάσταση; Δεν θα ήταν πιο σωστό > να μεταβούμε στην κατάσταση SC μιας και πλέον τα δεδομένα της κύριας μνήμης > είναι ενημερωμένα (και άρα τα δεδομένα της cache δεν είναι "modified" πια); > > 2. Στις διαφάνειες "Lec9-memory_consistency-13" στη σελίδα 29, στο > πινακάκι που δείχνει τις τιμές της κύριας μνήμης και των 2 caches, η τιμή > 400 θα έπρεπε να γραφτεί στην μνήμη στην τελευταία γραμμή αντί για την > προτελευταία, έτσι δεν είναι; > > Ευχαριστώ εκ των προτέρων, > Ματίκας Γεώργιος > > _______________________________________________ > Advcomparch mailing list > Advcomparch(a)lists.cslab.ece.ntua.gr > http://lists.cslab.ece.ntua.gr/mailman/listinfo/advcomparch > > -- Dr. Konstantinos Nikas Computing Systems Laboratory School of Electrical and Computer Engineering National Technical University of Athens Tel: +30-210-7724159 e-mail: knikas(a)cslab.ece.ntua.gr http://www.cslab.ece.ntua.gr/~knikas

1 0

Απορίες
by George Matikas 01 Jul '13

01 Jul '13

Γεια σας! Καθώς διάβαζα τις διαφάνειες για να προετοιμαστώ για την αυριανή εξέταση μου γεννήθηκαν κάποιες απορίες. Θα μπορούσατε να με βοηθήσετε να λύσω τις απορίες μου αυτές; 1α. Στις διαφάνειες "Lec8-coherence-13" στη σελίδα 39, που αναφέρει για το πρωτόκολλο MESI, γιατί πρέπει να γίνει Flush στις μεταβάσεις Ε->S, Ε->Ι, S->S, S->I; Δεν υποτίθεται ότι στις καταστάσεις Ε και S η κύρια μνήμη είναι ήδη ενημερωμένη με τα δεδομένα της συγκεκριμένης cache; Άρα δεν υπάρχει λόγος να γράψουμε τα ίδια δεδομένα πάλι... Επίσης, τι διαφορά έχει το Flush' με το Flush;1β. Στις ίδιες διαφάνειες, στη σελίδα 44, που αναφέρει για το πρωτόκολλο, όταν βρισκόμαστε στην κατάσταση SM και έρθει σήμα BusRd (οπότε γίνεται Flush) για ποιο λόγο παραμένουμε στην ίδια κατάσταση; Δεν θα ήταν πιο σωστό να μεταβούμε στην κατάσταση SC μιας και πλέον τα δεδομένα της κύριας μνήμης είναι ενημερωμένα (και άρα τα δεδομένα της cache δεν είναι "modified" πια); 2. Στις διαφάνειες "Lec9-memory_consistency-13" στη σελίδα 29, στο πινακάκι που δείχνει τις τιμές της κύριας μνήμης και των 2 caches, η τιμή 400 θα έπρεπε να γραφτεί στην μνήμη στην τελευταία γραμμή αντί για την προτελευταία, έτσι δεν είναι; Ευχαριστώ εκ των προτέρων,Ματίκας Γεώργιος

1 0

Re: [Advcomparch] Σχετικά με V/I protocol και RMO.
by Konstantinos Nikas 01 Jul '13

01 Jul '13

Καλησπέρα, Στο συγκεκριμένο παράδειγμα που αναφέρεις, το block παραμένει στο Ι παρά το PrWr γιατί η cache είναι write-no-allocate. Δηλαδή αν κάνει write miss, δεν κάνει allocate το block στην cache. Για το δεύτερο ερώτημα, καταρχάς αναφερόμαστε σε κάποιο από τα μοντέλα που παρουσιάστηκαν στο μάθημα. Κατά δεύτερον, τα consistency models ασχολούνται μόνο με τη σειρά των memory εντολών. Οι τυχόν αναδιατάξεις των υπόλοιπων εντολών είναι θέμα του επεξεργαστή και δεν έχει σχέση με το coherence/consistency. Βέβαια, ακόμα και το πλέον relaxed memory order, δε σημαίνει ότι επιτρέπονται όλες οι πιθανές αναδιατάξεις. Μη ξεχνάτε ότι ο επεξεργαστής εξακολουθεί και σέβεται τα data και control dependencies! Κ. 2013/6/29 Ανδρέας Παντελόπουλος <padelopoulos(a)gmail.com> > Καλησπέρα,στο FSM του simple V/I protocol (διαφ.30) παρατηρώ ότι με PrWr > στην Ι ξαναγυρνάει στην κατάσταση Ι. Κανονικά δεν θα έπρεπε να γίνεται > μετάβαση στην κατάσταση V ? > > Επίσης,στην θεωρητική άσκηση της 3ης σειράς αναφέρεστε στο "πλέον relaxed > memory order".Τι σημαίνει αυτό ακριβώς? Στην ουσία οποιαδήποτε αναδιάταξη > εντολών ή αναδιάταξη εντολών που επιτελούν λειτουργίες μνήμης ? > > Ευχαριστώ πολύ. > > _______________________________________________ > Advcomparch mailing list > Advcomparch(a)lists.cslab.ece.ntua.gr > http://lists.cslab.ece.ntua.gr/mailman/listinfo/advcomparch > > -- Dr. Konstantinos Nikas Computing Systems Laboratory School of Electrical and Computer Engineering National Technical University of Athens Tel: +30-210-7724159 e-mail: knikas(a)cslab.ece.ntua.gr http://www.cslab.ece.ntua.gr/~knikas

2 1

Jump to page:

2026

2025

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

Advcomparch