Κεφάλαιο 2 | Ενότητα 5 | Ερωτήσεις επισκόπησης | Προηγούμενο | Επόμενο| Λεξικό όρων

Παραδείγματα πάνω στην τεχνική του Tomasulo



Παράδειγμα 1oΠαράδειγμα 1o

Υποθέστε πως για τις λειτουργικές μονάδες κινητής υποδιαστολής έχουμε τις επόμενες καθυστερήσεις μετρημένες σε κύκλους ρολογιού. Η πρόσθεση έχει 2 κύκλους ρολογιού, ο πολλαπλασιασμός 10 κύκλους ρολογιού και η διαίρεση 40. Για ένα στιγμιότυπο του παρακάτω κώδικα δείξτε πώς γίνονται οι πίνακες καταστάσεων όταν η εντολή MULTD είναι έτοιμη να γράψει το αποτέλεσμά της.

LD F6,34(R2)
LD F2, 45(R3)
MULTD F0, F2, F4
SUBD F8, F6, F2
DIVD F10, F0, F6
ADDD F6, F8, F2
Απάντηση
Τμήμα κατάστασης εντολής

Αντίθετα με το αντίστοιχο παράδειγμα του πίνακα αποτελεσμάτων, η εντολή ADDD έχει ολοκληρωθεί, αφού οι τελεστέοι της εντολής DIVD έχουν αντιγραφεί, ξεπερνώντας έτσι τον WAR κίνδυνο. Παρατηρήστε ότι ακόμα και αν καθυστερούσε η φόρτωση του F6, η πρόσθεση στον F6 θα μπορούσε να εκτελεστεί χωρίς να ενεργοποιηθεί WAW κίνδυνος. Οι εντολές MULTD και DIVD δεν έχουν γράψει το αποτέλεσμά τους. Αυτή η περίπτωση διαφέρει από την αντίστοιχη του πίνακα αποτελεσμάτων, μια και η εξάλειψη των WAR κινδύνων επέτρεψε στην εντολή ADDD να τελειώσει ακριβώς μετά την εντολή SUBD με την οποία είχε εξάρτηση.


    


ΠαράδειγμαΠαράδειγμα 2o

Στην παρακάτω ακολουθία εντολών του αρχικού παραδείγματος έχουμε διευθετήσει και την εντολή DIVD και την εντολή ADDD, παρόλο που υπάρχει ένας WAR κίνδυνος λόγω της παρουσίας του καταχωρητή F6. Παρακάτω φαίνεται πως εξαλείφεται ο κίνδυνος.

LD F6,34(R2)
LD F2, 45(R3)
MULTD F0, F2, F4
SUBD F8, F6, F2
DIVD F10, F0, F6
ADDD F6, F8, F2
Απάντηση





Αν η εντολή που δίνει την τιμή για την εντολή DIVD έχει ολοκληρωθεί, τότε ο Vk θα αποθηκεύσει το αποτέλεσμα, επιτρέποντας στην εντολή DIVD να εκτελεστεί ανεξάρτητα από την εντολή ADDD. Αυτή είναι και η περίπτωση που φαίνεται στο αρχικό παράδειγμα.

Από την άλλη, αν η εντολή LD δεν είχε ολοκληρωθεί, η Qk θα έδειχνε στο Load1 και η εντολή DIVD θα ήταν ανεξάρτητη από την εντολή ADDD. 'Ετσι, η εντολή ADDD μπορεί να διευθετηθεί και να ξεκινήσει την εκτέλεσή της. Οποιεσδήποτε χρήσεις του αποτελέσματος της εντολής MULTD θα έδειχναν στο σταθμό κράτησης επιτρέποντας στην εντολή ADDD να ολοκληρώσει την εκτέλεσή της και να αποθηκεύσει την τιμή της στους καταχωρητές χωρίς να επηρεάζει την εντολή DIVD.


    


ΠαράδειγμαΠαράδειγμα 3o

Το παρακάτω σχήμα δίνει τα βήματα που πρέπει να περάσει κάθε εντολή.

Για την διευθετούμενη εντολή, D είναι ο προορισμός, S1 και S2 οι πηγαίοι αριθμοί καταχωρητών και r ο σταθμός κράτησης ή ο προσωρινός καταχωρητής με τον οποίο ο D συσχετίζεται. RS είναι η δομή δεδομένων του σταθμού κράτησης. Η τιμή που επιστρέφεται από έναν σταθμό κράτησης ή από τη μονάδα φόρτωσης ονομάζεται result. Register είναι η δομή δεδομένων για τον καταχωρητή, ενώ Store είναι η δομή δεδομένων για τον προσωρινό καταχωρητή αποθήκευσης. Το Ri σημαίνει το όνομα του καταχωρητή Ri και όχι τα περιεχόμενά του. 'Οταν διευθετείται μία εντολή, ο καταχωρητής προορισμού έχει το Qi πεδίο του ρυθμισμένο στον αριθμό του προσωρινού καταχωρητή ή του σταθμού κράτησης στον οποίο διευθετείται η εντολή. Αν οι τελεστέοι είναι διαθέσιμοι στους καταχωρητές, αυτοί αποθηκεύονται στα V πεδία. Διαφορετικά, τα Q πεδία ρυθμίζονται για να δηλώσουν το σταθμό κράτησης που θα δώσει τις τιμές που είναι αναγκαίες ως πηγαίοι τελεστέοι. Η εντολή παραμένει στο σταθμό κράτησης μέχρι και οι δύο τελεστέοι της να είναι διαθέσιμοι, γεγονός που υποδηλώνεται από το μηδέν στα Q πεδία. Τα Q πεδία ρυθμίζονται στο μηδέν είτε όταν η συγκεκριμένη εντολή διευθετείτε, είτε όταν μία εντολή από την οποία εξαρτάται ολοκληρώνεται και γράφει το αποτέλεσμά της. 'Οταν μία εντολή έχει τελειώσει την εκτέλεσή της και η κοινή αρτηρία δεδομένων είναι διαθέσιμη, μπορεί να γράψει το αποτέλεσμά της. 'Ολοι οι προσωρινοί καταχωρητές, οι καταχωρητές και σταθμοί κράτησης που συμμετέχουν στη διαδικασία ολοκλήρωσης, ενημερώνουν τις τιμές τους από την κοινή αρτηρία δεδομένων και μαρκάρουν τα πεδία Q για να δηλώσουν ότι οι τιμές έχουν ληφθεί. 'Ετσι, η κοινή αρτηρία δεδομένων μπορεί να μεταδόσει το αποτέλεσμα σε πολλούς προορισμούς σε ένα μόνο κύκλο ρολογιού και αν οι εν αναμονή εντολές έχουν τους τελεστέους τους μπορούν όλες να αρχίσουν την εκτέλεση στον επόμενο κύκλο ρολογιού. Για απλότητα, υποθέτουμε ότι όλες οι ενέργειες αρχικοποίησης γίνονται σε ένα κύκλο.  



ΠαράδειγμαΠαράδειγμα 4o

Για να καταλάβουμε τη δυναμική της εξάλειψης WAR και WAW κινδύνων μέσω της δυναμικής μετονομασίας καταχωρητών, πρέπει να δούμε ένα βρόχο. Θεωρήστε την παρακάτω ακολουθία εντολών για τον πολλαπλασιασμό των στοιχείων ενός πίνακα με μια βαθμωτή ποσότητα του F2.

Απάντηση

Αν προβλέψουμε ότι οι διακλαδώσεις ακολουθούνται, η χρησιμοποίηση σταθμών κράτησης θα επιτρέψει σε πολλαπλές εκτελέσεις του βρόχου να προχωρήσουν αμέσως. Αυτό γίνεται χωρίς να αναπτύξουμε το βρόχο, μια και αναπτύσεται δυναμικά από το υλικό. Ο αλγόριθμος Tomasulo υποστηρίζει την επικαλυπτόμενη εκτέλεση πολλαπλών επαναλήψεων του βρόχου με τη χρήση ενός μικρού αριθμού καταχωρητών.

Ας υποθέσουμε ότι έχουμε διευθετήσει όλες τις εντολές σε δύο επιτυχημένες επαναλήψεις του βρόχου, αλλά καμία από τις κινητής υποδιαστολής φορτώσεις/αποθηκεύσεις ή λειτουργίες δεν έχει ολοκληρωθεί. Η κατάσταση των εντολών, οι σταθμοί κράτησης, η κατάσταση των καταχωρητών και των προσωρινών καταχωρητών φόρτωσης και αποθήκευσης φαίνονται στους παρακάτω πίνακες.

Αφού το σύστημα φτάσει σ' αυτή την κατάσταση δύο επαναλήψεις του βρόχου θα μπορούσαν να κρατηθούν σε ένα CPI πολύ κοντά στο 1, δεδομένου ότι οι πολλαπλασιασμοί θα μπορούσαν να ολοκληρωθούν σε τέσσερις κύκλους ρολογιού. Η εντολή φόρτωσης από την τελευταία επανάληψη του βρόχου μπορούσε εύκολα να ολοκληρωθεί πριν από την αποθήκευση της πρώτης επανάληψης, παρόλο που η κανονική σειριακή εξέλιξη είναι διαφορετική. Η φόρτωση και η αποθήκευση μπορούν να γίνουν με ασφάλεια σε διαφορετική σειρά, δεδομένου ότι έχουν πρόσβαση σε διαφορετικές διευθύνσεις. Αυτό ελέγχεται εξετάζοντας τις διευθύνσεις στον προσωρινό καταχωρητή αποθήκευσης όταν διευθετείται μία φόρτωση. Αν η διεύθυνση φόρτωσης συμπίπτει με τη διεύθυνση του προσωρινού καταχωρητή αποθήκευσης, πρέπει να σταματήσουμε και να περιμένουμε έως ότου ο προσωρινός καταχωρητής αποθήκευσης να πάρει τιμή. Μπορούμε τότε να έχουμε πρόσβαση σε αυτή ή να πάρουμε τιμή από τη μνήμη.