Advcomparch July 2015

advcomparch@lists.cslab.ece.ntua.gr

9 participants
14 discussions

Απορία επί του Tomasulo / Double Load στο ίδιο block
by Εμμανουήλ Βλατάκης-Γκαραγκού νης 07 Jul '15

07 Jul '15

Με αφορμή τις εκφωνήσεις στα διαγωνίσματα μου δημιουργήθηκαν κάποιες απορίες γενικού ενδιαφέροντος. Ειδικότερα με απασχολεί η superscalar περίπτωση και η pipeline διαχείριση των Load & Stores *SCENARIO* Ας πούμε ότι είμαστε σε απλή non-superscalar αρχιτεκτονική και θέλουμε να εκτελέσουμε τις ακόλουθες δύο εντολές με αλγόριθμο Tomasulo: ld r1, 0 (address) ld r2, 1 (address) Ας υποθέσουμε ότι: 1) το cache block χωραει από [address+0]...[address+7] 2) το block δεν βρίσκεται στην cache, συνεπώς έχουμε miss. 5) Hit time = 2, Miss time = 5 A) Υποθέτω ότι αν είναι non-pipelined το function unit που χρησιμοποιεί το load τότε αναγκαστικά θα τρέξει μόνο η πρώτη εντολή το EXECUTE και θα κάνει miss ενώ η δεύτερη θα περιμένει και στην συνέχεια θα κάνει hit B) Αν τώρα υποθέσουμε ότι είναι pipelined το function unit , η ερώτηση μου είναι τότε η πρώτη και πάλι θα δει miss, και θα διαρκέσει από το 2ο εως τον 7ο γύρο αλλά η δεύτερη δεν θα δει επίσης το block να βρίσκεται στην cache και εκείνη θα κάνει και εκείνη miss ή στις caches υπάρχει κάποιο πρωτόκολλο στην περίπτωση που προσπαθήσεις να κάνεις read κάτι που βρίσκεται σε διαδικασία μεταφοράς? Γιατί αν παράδειγμα : από το 2ο εως το 7ο τρέχει η 1η load από το 3ο εως το 8ο τρέχει 2η load Αρχίζω να αναρωτιέμαι διάφορα πράγματα για το consistency της διαδικασίας... Γ) Επίσης σε περίπτωση που έχουμε superscalar αρχιτεκτονική και έχουμε ας πούμε δύο cdb, γράφουν ταυτόχρονα στην cache? Δ) Τέλος κάτι ίσως προφανέστερο των παραπάνω. Αν έχουμε 2- superscalar αρχιτεκτονική π.χ και έχουμε δύο data bus, αλλά η μνήμη μας παρέχει ένα port, τότε υποθέτω ότι έχουμε bottleneck και θα αναγκαστεί η μία εκ των δύο load ακόμα και αν είναι για ανεξάρτητα block να περιμένει σωστά? Ευχαριστώ πολύ προκαταβολικά Μανόλης.

1 2

Re: [Advcomparch] Απορίες για το MESI protocol
by Konstantinos Nikas 07 Jul '15

07 Jul '15

Καλησπέρα, δε χρειάζεται να σκέφτεστε πολύπλοκα, οι απαντήσεις είναι συνήθως απλές. Όταν κάποιος θέλει να κάνει write, προφανώς και απαιτείται να λάβει τα up-to-date δεδομένα, καθώς το coherence protocol δουλεύει σε επίπεδο cache block, ενώ οι εγγραφές από τον επεξεργαστή γίνονται σε επίπεδο word, half word ή byte. Όσον αφορά τα misses, βλέπεις με λάθος τρόπο τη διαδικασία. Την ερώτηση "είναι miss ή όχι" την κάνει ο επεξεργαστής που ζητάει τo block και την απάντηση τη δίνει η δική του cache με βάση το αν το block υπάρχει μέσα της στο κατάλληλο state. Αν λοιπόν το block δεν υπάρχει ή υπάρχει αλλά όχι στο κατάλληλο state, τότε έχουμε miss και η ίδια cache διαπιστώνει και τον τύπο του miss (απαντώντας ουσιαστικά στην ερώτηση "γιατί δεν έχω τα δεδομένα που πρέπει;"). Κ. 2015-07-07 0:54 GMT+03:00 Εμμανουήλ Βλατάκης-Γκαραγκούνης <tetraktida42(a)gmail.com>: >> > Α) >> >> Έστω ο ορισμός που δώσατε στο Flush, δηλαδή """παρέχει τα data στον >> επεξεργαστή που τα ζήτησε""".Να ρωτήσω κάτι και στο MSI, MESI γιατί όταν έχω >> στο E/M το block και ο άλλος θέλει να γράψει κάτι σε αυτό πρέπει εγώ να του >> στείλω με Flush αυτό που έχω. Αφού έτσι και αλλιώς σκοπεύει να το >> τροποποιήσει. >> Άρα τι νόημα έχει να κάνω Flush, αφού την πληροφορία μου θα την πετάξει, >> αφού σκοπεύει να κάνει WRITE? >> >> Τι συμβαίνει σε αυτή την λεπτομέρεια. > > > Το μόνο που συμβαίνει και μπορώ να φανταστώ εγώ είναι αν χρησιμοποιούσαμε > π.χ σε πιο upper level το MESI, πρωτόκολλο π.χ για DataBase Coherence. Τότε > κάνοντας flush στο BusWRITE demand κάποιου άλλου, αφήνεις τον άλλο να λάβει > το exclusiveness αλλά έχοντας δώσει την πληροφορία σου στο bus, μπορείς την > μνήμη [global database] να την ενημερώσεις για τα δικά σου αποτελέσματα. Η > μνήμη θα παραμείνει invalid γιατί κάποια ακόμα πιο νέα πληροφορία θα > γραφτεί, αλλά θα έχει προχωρήσει τουλάχιστον στο ιστορικό, πράγμα που σε > επίπεδο ας πούμε βάσης δεδομένων θα το θέλαμε. > > Β) > Ένα συναφές ζήτημα με τις συνολικές απορίες είναι το cache coherence miss > σύστημα. > Θα μου φαινόταν λογικό να έπρεπε να θεωρώ ότι εμφανίστηκε miss κάθε φορά που > θα χρειαστεί να γράψω για κάποιο λόγο στο bus. Κάτι τέτοιο όμως δεν > επαληθεύεται στις λύσεις στο θέμα του Ιουλίου του 2012. > Π.χ > +) όταν γίνονται από exclusive shared πράγματα δεν έχω coherence miss. > [πρώτα 6 miss] > +)Επίσης αν τύχει κάποιος άλλος να έχει exclusive και εγώ να το παίρνω για > πρώτη φορά το block και θέλω να γράψω έχω μόνο compulsory, ενώ σίγουρα > κάποιον μόλις τον έκανα invalid [7o με 10ο miss Μεταξυ P0,P1] > +) Ενώ στον αντίποδα αν ακριβώς έχει συμβεί για δεύτερη φορά αυτό [19ο με > 21ο miss, Μεταξυ P0,P1] > > Αν μπορείτε δώστε μας ένα clarification σε αυτό το ζήτημα > > > > Στις 2 Ιουλίου 2015 - 12:36 π.μ., ο χρήστης Βασίλειος Χαρισόπουλος > <el10046(a)central.ntua.gr> έγραψε: >> >> -----BEGIN PGP SIGNED MESSAGE----- >> Hash: SHA256 >> >> Καλησπέρα, >> >> έχω 2 απορίες για την συμπεριφορά του πρωτοκόλλου MESI που έχουν να κάνουν >> με τα flushes. >> Συγκεκριμένα, έστω τα 2 ακόλουθα σενάρια για σύστημα με 2 επεξεργαστές, ο >> καθένας με τη δικιά του cache, αναφερόμενος πάντα στο ίδιο block. >> >> 1) Έστω ότι σε κάποια φάση βρισκόμαστε στην κατάσταση (Modified, Invalid) >> και ο P2 κάνει read. Ο P1 θα παρατηρήσει το BusRd και θα κάνει flush. Τα >> δεδομένα που θα κάνει flush "πάνε" μόνο στην κύρια μνήμη ή και στον P2? >> Δηλαδή ο P2 θα χρειαστεί να περιμένει την μεταφορά από P1 -> cache και >> έπειτα cache -> P2 ή θεωρούμε πως ένα flush ενημερώνει και τον επεξεργαστή >> που το ζήτησε; >> >> Εάν η απάντηση είναι ότι το flush ενημερώνει μονάχα την κύρια μνήμη και >> δεν κάνει κάποιο cache-to-cache transfer, προκύπτει η εξής απορία: >> >> 2) Έστω ότι είμαστε στην κατάσταση (Exclusive, Invalid) και ο P2 κάνει >> Read. Για ποιο λόγο -όπως φαίνεται στο FSM του MESI- ο P1 να κάνει απλό >> flush (άρα να ενημερώσει την κύρια μνημη και ο P2 να πρέπει να περιμένει για >> αυτή την ενημέρωση) και όχι flush' (που αφορά μονάχα cache-to-cache >> transfers) εφόσον το αντίγραφο που διαθέτει δεν διαφέρει από αυτό της κύριας >> μνήμης? >> >> Ευχαριστώ προκαταβολικά. >> >> >> - -- >> “The method of doubt must be applied to civilization; we must doubt its >> necessity, its excellence, and its permanence.” >> - -Charles Fourier >> -----BEGIN PGP SIGNATURE----- >> Version: GnuPG v2 >> >> iQIcBAEBCAAGBQJVlF1gAAoJEIdZW/3eEQLNBc8P/i1bAr19LQ/wWm3erEctSvOA >> tO5oCp9EnN/zsZzVY1U6i4jEYfPVzku77DLqtCM9rKF9n2N4QAv4qz7hQzqrR1In >> XD2IP+9zwDzAgnQ3OfOY6CFQJLIe9ySuLhUfLlBf1rcfStWkkYu+ER9JCryKyEgA >> pCzVHSc3O3njXx6NrPGM8JGgArxMECAvJDrEDp1P/+26JH6CY6CgI+Hnn/ESHPhN >> IW+31Y8l/lZFRR5TGof9J5YpHAoU0KFjtIGc6FkBYfvnuZMNGfhPq50it2/T25EU >> hUsYO95JrtwzHlMpeu8llcBVap/nDV+b+eHx1FYoeMZSDPItHlvFeZu9ho69OP/J >> H/wmHl0f5wWCoDDGPTa8NZIjj7+NjjBJnklVXQUpn64CtqrxihSanqkV9NnWk9Eu >> 2C9B/573h/wA74HwyM9azO/uZhc+dgnsSsFvGwiL8IRENLWaupiJrUkkRoAJxa2w >> 2Eyui0GFyc/VVokL+sHYx+xtvi3+frazNDpricJUdHPpsu15XsPu+bQEU/mDSMTZ >> +kn4DwTCjQIZwsq+5qg/26SXdfYSepKvv6lpfoJx/tqLx42XcBWuprPMVmN/fKm5 >> xyfpN6wBzPEtDlfanEILQYw6iqYdWpx5EkTW8t/OUdXcH2zqh7b+OERAxfNn7Ohl >> 0C/U48hc3JTucddOjjzK >> =r9Tj >> -----END PGP SIGNATURE----- >> _______________________________________________ >> Advcomparch mailing list >> Advcomparch(a)lists.cslab.ece.ntua.gr >> http://lists.cslab.ece.ntua.gr/mailman/listinfo/advcomparch > > > > _______________________________________________ > 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

Απορίες για το MESI protocol
by Βασίλειος Χαρισόπουλος 06 Jul '15

06 Jul '15

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 Καλησπέρα, έχω 2 απορίες για την συμπεριφορά του πρωτοκόλλου MESI που έχουν να κάνουν με τα flushes. Συγκεκριμένα, έστω τα 2 ακόλουθα σενάρια για σύστημα με 2 επεξεργαστές, ο καθένας με τη δικιά του cache, αναφερόμενος πάντα στο ίδιο block. 1) Έστω ότι σε κάποια φάση βρισκόμαστε στην κατάσταση (Modified, Invalid) και ο P2 κάνει read. Ο P1 θα παρατηρήσει το BusRd και θα κάνει flush. Τα δεδομένα που θα κάνει flush "πάνε" μόνο στην κύρια μνήμη ή και στον P2? Δηλαδή ο P2 θα χρειαστεί να περιμένει την μεταφορά από P1 -> cache και έπειτα cache -> P2 ή θεωρούμε πως ένα flush ενημερώνει και τον επεξεργαστή που το ζήτησε; Εάν η απάντηση είναι ότι το flush ενημερώνει μονάχα την κύρια μνήμη και δεν κάνει κάποιο cache-to-cache transfer, προκύπτει η εξής απορία: 2) Έστω ότι είμαστε στην κατάσταση (Exclusive, Invalid) και ο P2 κάνει Read. Για ποιο λόγο -όπως φαίνεται στο FSM του MESI- ο P1 να κάνει απλό flush (άρα να ενημερώσει την κύρια μνημη και ο P2 να πρέπει να περιμένει για αυτή την ενημέρωση) και όχι flush' (που αφορά μονάχα cache-to-cache transfers) εφόσον το αντίγραφο που διαθέτει δεν διαφέρει από αυτό της κύριας μνήμης? Ευχαριστώ προκαταβολικά. - -- “The method of doubt must be applied to civilization; we must doubt its necessity, its excellence, and its permanence.” - -Charles Fourier -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 iQIcBAEBCAAGBQJVlF1gAAoJEIdZW/3eEQLNBc8P/i1bAr19LQ/wWm3erEctSvOA tO5oCp9EnN/zsZzVY1U6i4jEYfPVzku77DLqtCM9rKF9n2N4QAv4qz7hQzqrR1In XD2IP+9zwDzAgnQ3OfOY6CFQJLIe9ySuLhUfLlBf1rcfStWkkYu+ER9JCryKyEgA pCzVHSc3O3njXx6NrPGM8JGgArxMECAvJDrEDp1P/+26JH6CY6CgI+Hnn/ESHPhN IW+31Y8l/lZFRR5TGof9J5YpHAoU0KFjtIGc6FkBYfvnuZMNGfhPq50it2/T25EU hUsYO95JrtwzHlMpeu8llcBVap/nDV+b+eHx1FYoeMZSDPItHlvFeZu9ho69OP/J H/wmHl0f5wWCoDDGPTa8NZIjj7+NjjBJnklVXQUpn64CtqrxihSanqkV9NnWk9Eu 2C9B/573h/wA74HwyM9azO/uZhc+dgnsSsFvGwiL8IRENLWaupiJrUkkRoAJxa2w 2Eyui0GFyc/VVokL+sHYx+xtvi3+frazNDpricJUdHPpsu15XsPu+bQEU/mDSMTZ +kn4DwTCjQIZwsq+5qg/26SXdfYSepKvv6lpfoJx/tqLx42XcBWuprPMVmN/fKm5 xyfpN6wBzPEtDlfanEILQYw6iqYdWpx5EkTW8t/OUdXcH2zqh7b+OERAxfNn7Ohl 0C/U48hc3JTucddOjjzK =r9Tj -----END PGP SIGNATURE-----

2 1

MESI protocol
by Konstantinos Nikas 06 Jul '15

06 Jul '15

Καλησπέρα, σχετικά με διάφορες ερωτήσεις που έχουν γίνει στη λίστα ή και εκτός αυτής για το MESI protocol: 1. Γενικότερα έχουν προταθεί και υλοποιηθεί διάφορες εκδόσεις του MESI. Εμείς στο μάθημα χρησιμοποιούμε την αρχική έκδοση, όπως αυτή περιγράφηκε από τους ερευνητές στο University of Illinois και η οποία είναι γνωστή ως Illinois protocol. Από εκεί είναι και το FSM που δίνουμε στις διαφάνειες. 2. Στο Illinois protocol χρησιμοποιούνται όπου είναι δυνατό cache-to-cache transfers. Για αυτό το λόγο όταν μια cache έχει το block σε E/M, τότε σε περίιπτωση που ζητηθεί από κάποια άλλη κάνει Flush, δηλαδή παρέχει τα data στον επεξεργαστή που τα ζήτησε. Αν το block είναι σε S, σημαίνει ότι το αντίγραφο βρίσκεται σε πολλές caches. Στην περίπτωση αυτή, πρέπει τα data να τα δώσει μόνο ένας επεξεργαστής ενώ οι υπόλοιποι πραγματοποιούν μόνο την μετάβαση που προβλέπεται από το FSM χωρίς να μεταδώσουν δεδομένα (δηλ. Flush' = μόνο 1 επεξεργαστής δίνει data). 3. Όσον αφορά την ενημέρωση της κύριας μνήμης (ή πιο γενικά του επόμενου επιπέδου της ιεραρχίας) είναι νομίζω προφανές ότι το πιο εύκολο είναι να πραγματοποιείται σε κάθε flush. Κάθε φορά δηλαδή που κάποιος επεξεργαστής βάζει data στο bus (είτε κάνει Flush είτε Flush'), η κύρια μνήμη τα διαβάζει και αυτή και ενημερώνεται (όλες οι caches και η μνήμη βρίσκονται πάνω στο ίδιο bus). Με αυτό τον τρόπο διασφαλίζεται ότι όταν ένα block είναι σε κατάσταση S η μνήμη είναι up-to-date και επομένως δε χρειάζεται να κάνουμε WB όταν κάνουμε evict ένα S block. K. -- 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

2026

2025

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

Advcomparch July 2015