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

[Ιάσων Μηλι]

Καλησπέρα σας,

Με αφορμή το Μέρος Β' της 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, καταλαβαίνω ότι το παραπάνω δεν μπορεί να γίνει, σωστά;

Σας ευχαριστώ πολύ εκ των προτέρων για τον χρόνο σας,
Ιάσων