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

Πολλαπλή διευθέτηση εντολών με δυναμικό προγραμματισμό

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

ΔΡΑΣΤΗΡΙΟΤΗΤΑ 3

Θυμάστε τι ποια είναι η χρησιμότητα των σταθμών κράτησης στην υλοποίηση της τεχνικής Tomasulo; Για περισσότερες λεπτομέρειες καλό θα ήταν να ανατρέξετε στην 5η ενότητα αυτού του κεφαλαίου: «Η μέθοδος Tomasulo».

 

ΑΠΑΝΤΗΣΗ ΔΡΑΣΤΗΡΙΟΤΗΤΑΣ 3



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

Υπάρχουν δύο προσεγγίσεις ώστε να επιτύχουμε διπλή διευθέτηση:

  • Η πρώτη είναι να σωληνώσουμε το τμήμα διευθέτησης εντολών ώστε να τρέχει με το διπλάσιο του βασικού ρυθμού ρολογιού. Αυτό επιτρέπει την ενημέρωση των πινάκων πριν επεξεργαστούμε την επόμενη εντολή και έτσι οι δύο εντολές μπορούν να αρχίσουν την εκτέλεσή τους στον ίδιο κύκλο ρολογιού.
  • Η δεύτερη υποθέτει, ότι σύμφωνα με τους περιορισμούς που έχουν ληφθεί, μόνο οι εντολές φορτώσεων και μετακινήσεων, από τους καταχωρητές ακεραίων (GP) στους καταχωρητές κινητής υποδιαστολής (FP), θα δημιουργήσουν εξαρτήσεις ανάμεσα σε εντολές που θα διευθετήσουμε μαζί.

Η ανάγκη πινάκων που καταγράφουν τα αποτελέσματα των σταθμών κράτησης εξαλείφεται, χρησιμοποιώντας ουρές για το αποτέλεσμα μιας εντολής φόρτωσης ή μετακίνησης. Επίσης χρησιμοποιούνται και για μια εντολή αποθήκευσης, ώστε να διευθετηθεί νωρίτερα και να περιμένει για τους τελεστέους της.
Αφού ο δυναμικός προγραμματισμός είναι περισσότερο αποτελεσματικός στις μετακινήσεις δεδομένων, μπορούμε να χρησιμοποιήσουμε στατικό προγραμματισμό για να εξαλείψουμε τελείως τους σταθμούς κράτησης και να βασιστούμε μόνο στις ουρές.
Αυτός ο τρόπος οργάνωσης του επεξεργαστή, όπου οι μονάδες φόρτωσης-αποθήκευσης έχουν ουρές που επιτρέπουν σύνδεση με άλλες λειτουργικές μονάδες, ονομάζεται μη συζευγμένη αρχιτεκτονική.
Ένας επεξεργαστής που προγραμματίζει δυναμικά τις εντολές φόρτωσης και αποθήκευσης, μπορεί να προκαλέσει αναδιάταξη αυτών των εντολών. Η αναδιάταξη μπορεί να οδηγήσει στην παραβίαση μιας εξάρτησης δεδομένων και να προκύψει κίνδυνος. Για να ανιχνεύσουμε τέτοιους κινδύνους ελέγχουμε δυναμικά αν η διεύθυνση μνήμης των πηγαίων τελεστέων μιας εντολής φόρτωσης είναι η ίδια με τη διεύθυνση προορισμού μιας μη ολοκληρωμένης εντολής αποθήκευσης. Αν είναι ίδια, τότε καθυστερούμε την εντολή φόρτωσης μέχρι να ολοκληρωθεί η εντολή αποθήκευσης. Αφού υπολογιστεί η διεύθυνση προορισμού της εντολής αποθήκευσης, τοποθετείται στον προσωρινό καταχωρητή αποθήκευσης. Υπάρχει επίσης η πιθανότητα WAW και WAR κινδύνων μέσω μνήμης.

Παράδειγμα

Ας υποθέσουμε ότι διευθετούμε δύο εντολές που είναι εξαρτώμενες αλλά χρησιμοποιούν διαφορετικές λειτουργικές μονάδες. Θεωρούμε την εκτέλεση του αρχικού βρόχου σε DLX σωλήνωση που έχει όμως επεκταθεί με τον αλγόριθμο Tomasulo και με την πολλαπλή διευθέτηση. Επίσης, θεωρούμε ότι η εντολή ADDD και η εντολή LD διευθετούνται μαζί σε κάθε κύκλο ρολογιού, ακόμα και αν υπάρχει μεταξύ τους εξάρτηση, με τη προϋπόθεση ότι η εντολή LD είναι πρώτη. Υποθέτουμε μία ακέραια λειτουργική μονάδα και μία ξεχωριστή λειτουργική μονάδα κινητής υποδιαστολής για κάθε λειτουργία. Ο αριθμός των κύκλων καθυστέρησης για κάθε εντολή είναι ο ίδιος. Υποθέτουμε ότι τα αποτελέσματα της διευθέτησης και της εγγραφής χρειάζονται ένα κύκλο ρολογιού το καθένα και ότι υπάρχει υλικό δυναμικής πρόβλεψης διακλάδωσης. Δημιουργήστε ένα πίνακα που να δείχνει πότε διευθετείται κάθε εντολή, πότε αρχίζει να εκτελείται και να γράφει το αποτέλεσμά της για τις δύο πρώτες επαναλήψεις του βρόχου. Δίνεται ο αρχικός βρόχος:

loop: LD F0, 0(R1) ; F0 = στοιχείο πίνακα
ADDD F4, F0, F2 ; πρόσθεση με το βαθμωτό μέγεθος του F2
SD 0(R1), F4 ; αποθήκευση του αποτελέσματος
SUBI R1, R1, #8 ; μείωση δείκτη 8 bytes (για κάθε DW)
BNEZ R1, loop ; διακλάδωση R1!= μηδέν

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

Το στάδιο εγγραφής αποτελέσματος δεν έχει τιμή για τις εντολές αποθήκευσης και διακλάδωσης, αφού δεν γράφουν σε καταχωρητές. Ο βρόχος τρέχει σε 7/2=3.5 κύκλους ρολογιού ανά αποτέλεσμα για 2 επαναλήψεις.
Υπάρχει η υπόθεση ότι κάθε αποτέλεσμα γράφεται στη CDB (common data bus) δηλαδή στη κοινή αρτηρία δεδομένων στο τέλος του κύκλου ρολογιού που είναι διαθέσιμο. Οπότε πρέπει να γίνουν οι αναγκαίες αλλαγές στον πίνακα. Ακόμα, για να εκτελεστεί η εντολή ADDD πρέπει να έχει τελειώσει η εγγραφή του αποτελέσματος (κοινή αρτηρία δεδομένων και μετά καταχωρητές ή σταθμοί κράτησης) της εντολής φόρτωσης ώστε να χρησιμοποιηθεί το αποτέλεσμά της.
Η εκτέλεση της εντολής αποθήκευσης αποτελέσματος πρέπει να εκτελεστεί μετά την εγγραφή του αποτελέσματος στην αρτηρία δεδομένων, οπότε η πρώτη εντολή SD θα έχει πρόσβαση στη μνήμη για να γράψει στον 7ο κύκλο του ρολογιού. Αυτό παρασύρει και την δεύτερη εντολή LD που πρέπει να εκτελεστεί αργότερα, οπότε και η δεύτερη ADDD πρέπει να εκτελεστεί ένα κύκλο αργότερα. Τέλος, η δεύτερη εντολή SD πρέπει να εκτελεστεί μετά το τέλος της ADDD για να αποθηκεύσει τη σωστή τιμή του F4 αφού θα έχει γίνει η πρόσθεση.
Ο αριθμός των διπλών διευθετήσεων είναι μικρός επειδή υπάρχει μία εντολή κινητής υποδιαστολής ανά επανάληψη. Αν ο επεξεργαστής ήταν ευρύτερος θα διευθετούσε περισσότερες εντολές ακεραίων ανά κύκλο ρολογιού.