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

Η τεχνική του πίνακα αποτελεσμάτων SCOREBOARDING

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

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

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

Έχουμε δύο είδη επεξεργαστών, τον CDC 6600 και τον DLX. Και οι δύο είναι κατασκευασμένοι σύμφωνα με την αρχιτεκτονική φόρτωσης-αποθήκευσης. Έτσι, οι τεχνικές που χρησιμοποιούν είναι σχεδόν ταυτόσημες.Οι λειτουργικές μονάδες που χρησιμοποιούν οι δύο αυτοί επεξεργαστές για την υλοποίηση του δυναμικού προγραμματισμού απεικονίζονται στο σχήμα 2.4.1.



ΥπολογιστήςΛειτουργικές μονάδες
CDC66004 FP: 2 mult, 1 add, 1 div
7 μονάδες μνήμης: 5 load, 2 store
7 μονάδες ακεραίων: add,shift, logical, κλπ.
DLX4 FP: 2 mult, 1 add, 1 div
1 μονάδα ακεραίων: integer

Σχήμα 2.4.1 – Οι λειτουργικές μονάδες των CDC6600 και DLX για την υλοποίηση του δυναμικού προγραμματισμού.

Κάθε εντολή κατά την εκτέλεση της ακολουθεί τέσσερα βήματα, που αντικαθιστούν τα ID, EX και WB στάδια στη βασική DLX σωλήνωση:

  1. Διευθέτηση - Εάν μια λειτουργική μονάδα είναι ελεύθερη τότε ο πίνακας αποτελεσμάτων διευθετεί την εντολή, με την προϋπόθεση ότι καμιά άλλη ενεργή εντολή δεν έχει τον ίδιο καταχωρητή προορισμού. Εξασφαλίζοντας ότι καμία άλλη ενεργή λειτουργική μονάδα δε θέλει να γράψει το αποτέλεσμά της στον καταχωρητή προορισμού, αποφεύγουμε τους WAW κινδύνους. Εάν υπάρχει ένας κατασκευαστικός ή WAW κίνδυνος, τότε η διευθέτηση της εντολής καθυστερεί και καμιά από τις επόμενες εντολές δε διευθετείται μέχρι οι κίνδυνοι να εξαλειφθούν. Αυτό το βήμα αντικαθιστά μέρος του ID βήματος στη DLX σωλήνωση.

  2. Διάβασμα τελεστέων - Ο πίνακας αποτελεσμάτων ελέγχει τη διαθεσιμότητα των πηγαίων τελεστέων. Ένας πηγαίος τελεστέος είναι διαθέσιμος σε δύο περιπτώσεις:

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

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

Τα βήματα ένα και δύο αντικαθιστούν το ID στάδιο της απλής DLX σωλήνωσης.

  1. Εκτέλεση - Η λειτουργική μονάδα αρχίζει την εκτέλεση με τη λήψη των τελεστέων. Όταν το αποτέλεσμα είναι έτοιμο, γνωστοποιεί στον πίνακα αποτελεσμάτων ότι έχει ολοκληρώσει την εκτέλεση. Το βήμα αυτό αντικαθιστά το EX στάδιο της απλής DLX σωλήνωσης.
  2. Εγγραφή αποτελέσματος - Μόλις ο πίνακας αποτελεσμάτων ενημερωθεί ότι η λειτουργική μονάδα έχει ολοκληρώσει την εκτέλεση, ελέγχει για WAR κινδύνους και αν είναι απαραίτητο καθυστερεί την εντολή προς ολοκλήρωση.

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

Μπορείτε να απαριθμήσετε τα βήματα για την εκτέλεση μιας εντολής με την τεχνική του πίνακα αποτελεσμάτων και να περιγράψετε τις λειτουργίες που επιτελούνται σε κάθε ένα;
Ποια στάδια της βασικής σωλήνωσης του DLX αντικαθιστούν τα βήματα αυτά;
Μπορείτε να σχεδιάσετε ένα σχήμα το οποίο να απεικονίζει την εκτέλεση των εντολών με τη χρήση της τεχνικής του πίνακα αποτελεσμάτων; Να συγκρίνετε την απάντησή σας με το σχήμα που ακολουθεί (σχήμα 2.4.2).

Σχήμα 2.4.2 – Η εκτέλεση των εντολών με τη χρήση της τεχνικής του πίνακα αποτελεσμάτων.

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

Έστω το τμήμα κώδικα:

DIVD F0 , F2 , F4
ADDD F10 , F0 , F8
SUBD F8 , F8 , F14

· Μπορείτε να προσδιορίσετε τις εξαρτήσεις μεταξύ των εντολών;

 

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



Εντολές προς ολοκλήρωση ονομάζονται οι εντολές που είναι έτοιμες να γράψουν το αποτέλεσμά τους κατά το στάδιο εγγραφής αποτελέσματος.

Μία εντολή προς ολοκλήρωση δεν μπορεί να γράψει το αποτέλεσμα της όταν:

  • Υπάρχει μια εντολή που προηγείται και δεν έχει διαβάσει τους τελεστέους της. Για παράδειγμα, η εντολή SUBD δεν μπορεί να γράψει το αποτέλεσμά της αν η εντολή ADDD δεν έχει διαβάσει τους τελεστέους της.
  • Ένας από τους πηγαίους καταχωρητές είναι και καταχωρητής προορισμού. Για παράδειγμα, ο καταχωρητής F8 είναι και πηγαίος καταχωρητής και καταχωρητής προορισμού.

Εάν ο WAR κίνδυνος δεν υπάρχει ή έχει εξαλειφθεί, τότε ο πίνακας αποτελεσμάτων επιτρέπει στη λειτουργική μονάδα να αποθηκεύσει το αποτέλεσμά της στον καταχωρητή προορισμού.
Το βήμα εγγραφής αποτελέσματος αντικαθιστά το WB στάδιο της απλής DLX σωλήνωσης.

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

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

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

· Να εξηγήσετε τους κινδύνους που προκύπτουν από την εκτέλεση των εντολών.
· Μπορείτε να σχεδιάσετε το τμήμα κατάστασης εντολής, το τμήμα λειτουργικής μονάδας και το τμήμα κατάστασης καταχωρητή αποτελέσματος για την εκτέλεση του παραπάνω τμήμα κώδικα;
· Να συγκρίνετε την απάντησή σας με την απάντηση που ακολουθεί.




Στο παρακάτω πίνακα παρουσιάζονται οι απαιτούμενοι έλεγχοι και ενέργειες για κάθε βήμα κατά την εκτέλεση μιας εντολής.

Το FU συμβολίζει τη λειτουργική μονάδα που χρησιμοποιείται από την εντολή.Ο καταχωρητής D είναι ο καταχωρητής προορισμού, ενώ οι S1 και S2 είναι οι πηγαίοι καταχωρητές. Η Op είναι η λειτουργία που θα γίνει. Όταν η εγγραφή με όνομα Fj χρησιμοποιείται από τη λειτουργική μονάδα FU χρησιμοποιούμε το συμβολισμό Fj(FU). Η Result(D) είναι η τιμή του πεδίου αποτελέσματος καταχωρητή για τον καταχωρητή D. Η προσπάθεια εγγραφής αποτελέσματος αποτυγχάνει όταν υπάρχει ένας WAR κίνδυνος. Ο συμβολισμός Ri αφορά το όνομα του καταχωρητή Ri και όχι το περιεχόμενό του. Για απλότητα υποθέτουμε ότι όλες οι ενέργειες γίνονται σε ένα κύκλο ρολογιού.

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

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

2. Τον αριθμό των καταχωρήσεων στον πίνακα αποτελεσμάτων.
Ο αριθμός των καταχωρήσεων καθορίζει πόσο μακριά μπορεί να ψάξει η σωλήνωση για ανεξάρτητες εντολές. Το σύνολο των εντολών που εξετάζεται ως υποψήφιο για πιθανή εκτέλεση ονομάζεται παράθυρο. Το μέγεθος (αριθμός καταχωρήσεων) του πίνακα αποτελεσμάτων καθορίζει το μέγεθος του παραθύρου. Θεωρούμε ότι ένα παράθυρο δεν επεκτείνεται πέρα από μία διακλάδωση κι έτσι το παράθυρο και ο πίνακας αποτελεσμάτων περιέχουν πάντα κώδικα που εκτελείται σειριακά περιορισμένο σε ένα μονό βασικό μπλοκ.

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

4. Την παρουσία αντιεξαρτήσεων και εξαρτήσεων εξόδου.
Αυτές προκαλούν WAR και WAW κινδύνους, που με τη σειρά τους προκαλούν τις αντίστοιχες καθυστερήσεις.

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




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

Δίνεται το παρακάτω τμήμα κατάσταση εντολής, από τον πίνακα αποτελεσμάτων.



Να εξηγήσετε σε τι κατάσταση βρίσκεται η κάθε εντολή που περιέχεται στον πίνακα για το συγκεκριμένο στιγμιότυπο.

 

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