[Advcomparch] Ερωτήσεις συνδυασμού Tomasulo με ROB, cache

[Konstantinos Nikas]

Καλησπέρα,

1) Ναι οι προσβάσεις στη μνήμη γίνονται overlapped.

2) Ναι, επικαλύπτονται. Στον τελευταίο κύκλο του κάθε miss, το block
αποθηκεύεται στην cache και η λέξη που έχει ζητηθεί δίνεται στον
επεξεργαστή.

3) Το update της LRU το πραγματοποιεί η κάθε cache με βάση τις
προσβάσεις που γίνονται σε αυτή, όταν πραγματοποιείται η κάθε
πρόσβαση. Αν η πρόσβαση είναι hit, το update γίνεται εκείνη τη στιγμή,
διαφορετικά σε περίπτωση miss, όταν έρχεται το καινούργιο block
εισάγεται στη cache και ενημερώνεται ως MRU block.

4) Είναι write-allocate. Γενικά μπορείτε να θεωρήσετε ότι αν δεν
αναφέρετε κάτι στην άσκηση/θέμα, η cache είναι write-allocate. Αν
ισχύει κάτι άλλο, θα έχουμε φροντίσει να το δώσουμε στην εκφώνηση.

5) Flush σε περίπτωση misprediction κάνει μόνο ο επεξεργαστής και όχι
η ιεραρχία μνήμης.

Θα μπορούσε να σχεδιάσει κάποιος να κάνει και η cache, αλλά το κόστος
σε hardware θα ήταν πολύ μεγάλο (ανάγκη για logging, διόρθωση τιμών
κτλ), οπότε προφανώς και δεν αξίζει. Για το λόγο αυτό και στις οοο
αρχιτεκτονικής η εγγραφή στη μνήμη πραγματοποιείται στο Commit στάδιο
και όχι πιο πριν.

Στο πλαίσιο των ασκήσεων που εξετάζουμε στο μάθημα κάνουμε την
παραδοχή ότι η πρόσβαση στη cache πραγματοποιείται στο EX και για
loads και για stores (άρα και τα hits και misses) και η τιμή γράφεται
στο CMT στάδιο. Αυτό είναι μια παραδοχή για λόγους ευκολίας και
εκτέλεσης της άσκησης και όχι κάτι που συμβαίνει στην πραγματικότητα.

Store queues χρειάζονται για το ίδιο λόγο που χρειάζονται και load
queues και reservation stations :-)

6) Και πάλι για λόγους "ευκολίας" στις ασκήσεις μας θεωρούμε ότι το
branch prediction πραγματοποιείται ταυτόχρονα με το issue των εντολών
(μιας και αγνοούμε τα προηγούμενα στάδια). Με βάση το assumption
αυτών, σε μια superscalar αρχιτεκτονική μπορείτε να υποθέσετε ότι το
prediction είναι διαθέσιμο τόσο γρήγορα που να επιτρέπει και τη
φόρτωση predicted εντολών μαζί με το branch στον ίδιο κύκλο.

Στην πραγματικότητα, το prediction γίνεται πολύ νωρίτερα στο pipeline
και στο μάθημα έχουμε δει και συζητήσει διάφορες λύσεις που έχουν
προταθεί και προσφέρουν τη δυνατότητα αυτή ακόμα και στο IF στάδιο.

Κ.

On Thu, 11 Jun 2020 at 19:22, Ιάσων Μηλιώνης <el16014 at central.ntua.gr> wrote:
>
> Καλησπέρα σας,
>
> Με αφορμή το Μέρος Β' της 4ης άσκησης, αλλά και κάποια γενικότερα, μου
> γεννήθηκαν οι εξής απορίες σχετικά με τον συνδυασμό Tomasulo με ROB,
> cache, branch prediction και άλλα:
>
> 1) Στην εκφώνηση αναφέρεται ότι "Οι εντολές χρησιμοποιούν ένα ξεχωριστό
> pipelined functional unit για τον υπολογισμό της διεύθυνσης". Αυτό αφορά
> και την ίδια την μνήμη φαντάζομαι, έτσι; Δηλαδή, γνωρίζουμε ότι η μνήμη
> έχει οργανωθεί σε παράλληλα banks, το bus είναι κατάλληλο κλπ, ώστε να
> έχουμε pipelined πρόσβαση και στην ίδια τη μνήμη;
>
> 2) Πάνω στο προηγούμενο, και επεκτείνοντας, εάν είχαμε την ίδια εκφώνηση
> με έναν άλλο κώδικα όπου πραγματοποιούνται 4 διαδοχικά LD (τα οποία
> φορτώνουν αντίστοιχα 4 floating point αριθμούς) που όλα αναφέρονται σε
> διαφορετικά μεταξύ τους blocks με miss και στα 4 blocks (άρα 4
> διαφορετικά blocks) χωρίς καμία εξάρτηση μεταξύ τους, άρα εν ολίγοις
> όταν δεν χωρούν στο σύνολο της cache, μπορούμε και πάλι να επικαλύψουμε
> τις προσβάσεις τους στη μνήμη, δηλαδή τα στάδια EX (με τα 4 LD, τα
> στάδια EX τους να ήταν πχ 20-23, 21-24, 22-25, 23-26) ή όχι; Και αν όχι,
> τι ακριβώς να κάνουμε σε μια τέτοια περίπτωση;
>
> 3) Σχετικά με την πολιτική LRU (της άσκησης), η σειρά με την οποία
> γίνονται indicate τα recent blocks, ποια είναι ακριβώς; Μπορώ να σκεφτώ
> πολλαπλές: βάσει του program order ποια εντολή έγινε issue τελευταία,
> βάσει του ποια εντολή ολοκλήρωσε την πρόσβαση στη μνήμη τελευταία, ή
> βάσει του ποια εντολή ξεκίνησε την πρόσβαση στη μνήμη τελευταία.
> Εξηγώντας, φαντάζομαι πως επειδή η cache είναι που καθορίζει τα LRU-bits
> η ίδια, και δεν μπορεί να γνωρίζει το program order ή την in-order σειρά
> που γίνονται issue οι εντολές από τον επεξεργαστή, μόνο με βάση το
> στάδιο της πρόσβασης στη μνήμη (EX εδώ) θα καθορίζεται, αλλά παραμένει
> το ερώτημα αν πιο πρόσφατο block γίνεται εκείνο που **ολοκλήρωσε** την
> πρόσβαση τελευταίο, ή εκείνο που **άρχισε** την πρόσβαση τελευταίο. Αυτά
> τα δύο μπορεί να είναι εν γένει διαφορετικά: για παράδειγμα, εάν έχουμε
> δύο εντολές LD που αναφέρονται σε δύο διαφορετικά blocks όπου το ένα δεν
> υπάρχει (miss) και το άλλο υπάρχει (hit) στην cache, και έστω με τους
> εξής χρονισμούς σε κύκλους (μαζί με τον υπολογισμό της διεύθυνσης είναι
> αυτό βέβαια): για την πρώτη εντολή EX 23-26 (4 κύκλοι, miss), και για
> την δεύτερη εντολή 24-24 (1 κύκλος, hit), τότε πιο πρόσφατο block
> γίνεται indicate ποιο από τα δύο; Αν πιο πρόσφατο είναι εκείνο που
> αρχίζει την πρόσβαση τελευταίο, τότε το block που αναφέρεται στην εντολή
> LD με στάδιο EX 24-24 είναι πιο recent από το άλλο, ενώ αν πιο πρόσφατο
> είναι εκείνο που ολοκληρώνει την πρόσβαση τελευταίο, τότε το άλλο block
> (που αναφέρεται στην εντολή LD με στάδιο EX 23-26) είναι πιο recent.
>
> 4) Η cache της άσκησης είναι write-allocate ή no-write-allocate; Από την
> διάρκεια του σταδίου EX για την εντολή store σε περίπτωση miss, εικάζω
> ότι είναι write-allocate (και κατά πάσα πιθανότητα write-back), αλλά
> νομίζω ότι επηρεάζει τα τελικά contents της cache τι από τα δύο ισχύει.
>
> 5α) Όταν έχουν εκτελεστεί διάφορες προσβάσεις στη μνήμη, αλλά δεν έχουν
> γίνει commit ακόμη, και γίνουν flush μετέπειτα λόγω branch
> misprediction, εκείνες οι προσβάσεις στη μνήμη που έχουν γίνει έχουν
> αλλάξει τα LRU-bits (την ένδειξη του ποια blocks είναι πιο recent)
> μονίμως στην cache ακόμη και μετά το flush, έτσι; Αντίστοιχα, μπορεί να
> έχουν γίνει fetch διάφορα blocks στην cache, να έχουν αποχωρήσει άλλα
> που δεν χωρούσαν πλέον κλπ, οπότε γενικά το flush δεν δύναται να
> αναιρέσει καμία από αυτές τις αλλαγές, σωστά;
>
> 5β) Βάσει αυτού, αναφερόμενος τώρα σε μια πραγματική write-through cache
> (όχι στην άσκηση), σε μια Store εντολή δεν συμβαίνει τίποτε άλλο πέρα
> από τον υπολογισμό της διεύθυνσης στο στάδιο EX, και μετά παραμένει στο
> ROB για το τελικό commit (που θα γίνει στην μνήμη), άρα γιατί
> χρειαζόμαστε store queue πραγματικά; Επίσης, τότε, το στάδιο Commit
> καταλαβαίνω ότι δεν μπορεί να γίνει σε 1 κύκλο, αν έχουμε miss στην
> cache, οπότε τι θα έπρεπε να συμβεί; Δεν δημιουργεί προβλήματα ένα
> στάδιο Commit που δεν έχει σταθερή διάρκεια;
>
> 6α) Εάν είχαμε την ίδια εκφώνηση με έναν άλλο κώδικα όπου γίνεται Issue
> μία εντολή διακλάδωσης και υπάρχει η δυνατότητα στον ίδιο αυτό κύκλο να
> γίνει issue άλλη μία εντολή (2-wide superscalar), που καταλαβαίνω ότι θα
> πρέπει να είναι η predicted από τον branch predictor, η συνθήκη "Η
> πρόβλεψη για μια εντολή διακλάδωσης υπό συνθήκη γίνεται ταυτόχρονα με τη
> δρομολόγηση της εντολής" σημαίνει ότι μπορούν όντως να γίνουν issue μαζί
> η εντολή διακλάδωσης και η predicted εντολή στον ίδιο κύκλο, ή όχι;
>
> 6β) Σε πραγματικούς σύγχρονους επεξεργαστές, το branch prediction
> γίνεται σε προηγούμενο στάδιο του Issue? Αν όχι και γίνεται συνήθως στο
> Issue stage, καταλαβαίνω ότι το παραπάνω δεν μπορεί να γίνει, σωστά;
>
> Σας ευχαριστώ πολύ εκ των προτέρων για τον χρόνο σας,
> Ιάσων
> _______________________________________________
> Advcomparch mailing list
> Advcomparch at 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 at cslab.ece.ntua.gr
http://www.cslab.ece.ntua.gr/~knikas