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

Δυναμικά σχήματα πρόβλεψης για το αποτέλεσμα διακλάδωσης.

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

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

Η αποτελεσματικότητα ενός σχήματος πρόβλεψης διακλάδωσης εξαρτάται όχι μόνο από την ακρίβεια πρόβλεψης αλλά και από το κόστος μιας διακλάδωσης, όταν η πρόβλεψη είναι σωστή και όταν είναι λάθος.

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

Θυμάστε τι είναι η ποινή διακλάδωσης; Να αναφέρετε τι είναι οι ποινές διακλάδωσης και από τι εξαρτώνται. Για περισσότερες λεπτομέρειες καλό θα ήταν να ανατρέξετε στο 1ο κεφάλαιο και συγκεκριμένα στην 6η ενότητα: «Κίνδυνοι Ελέγχου».

 

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



Το πιο απλό σχήμα πρόβλεψης διακλάδωσης είναι ο προσωρινός καταχωρητής πρόβλεψης διακλαδώσεων ή πίνακας ιστορικού των διακλαδώσεων.

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

Παράδειγμα
Έστω μία εντολή διακλάδωσης μέσα σε ένα βρόχο, η οποία ακολουθείται εννέα φορές στη σειρά, ενώ τη δέκατη δεν ακολουθείται. Ποια είναι η ακρίβεια πρόβλεψης για αυτή τη διακλάδωση, αν υποθέσουμε ότι το bit πρόβλεψης παραμένει στον προσωρινό καταχωρητή πρόβλεψης;

Απάντηση:
Θα προκύψει λάθος πρόβλεψη κατά την πρώτη και τη δέκατη επανάληψη του βρόχου. Η λάθος πρόβλεψη κατά την πρώτη επανάληψη συμβαίνει, διότι το bit είναι ανάποδα από την προηγούμενη εκτέλεση της τελευταίας επανάληψης του βρόχου, η οποία δεν είχε ακολουθηθεί (ήταν η δέκατη στην σειρά). Η πρόβλεψη κατά τη δέκατη επανάληψη θα είναι σίγουρα λάθος, αφού το bit πρόβλεψης θα δείχνει ότι η διακλάδωση ακολουθείται, ενώ είναι γνωστό ότι τη δέκατη φορά δεν ακολουθείται. Ακόμα και αν μία διακλάδωση ακολουθείται σχεδόν πάντα, όταν μία φορά δεν ακολουθηθεί, τότε κάνουμε δύο φορές λάθος πρόβλεψη αντί για μία. 'Ετσι, μία διακλάδωση η οποία ακολουθείται με συχνότητα 90%, έχει ακρίβεια πρόβλεψης μόνο 80% (δύο λάθος προβλέψεις και οκτώ σωστές). Γενικά, για τις διακλαδώσεις που συνηθίζουν να σχηματίζουν βρόχους, δηλαδή μία διακλάδωση ακολουθείται πολλές φορές στη σειρά, ενώ δεν ακολουθείται μία, το σχήμα πρόβλεψης του ενός bit θα κάνει λάθος δύο φορές ότι η διακλάδωση δεν ακολουθείται. Θεωρητικά, η ακρίβεια του σχήματος πρόβλεψης θα ήταν ίση με τη συχνότητα με την οποία ακολουθείται η διακλάδωση.

Το σχήμα πρόβλεψης των δύο bit, αποτελεί μία βελτιωμένη μορφή σχήματος πρόβλεψης. Σε ένα τέτοιο σχήμα, μία πρόβλεψη θα πρέπει να αποτύχει δύο φορές πριν αλλαχθεί. Το σχήμα πρόβλεψης των δύο bit είναι μια εξειδικευμένη μορφή ενός πιο γενικού σχήματος πρόβλεψης των n-bit.
Το σχήμα πρόβλεψης των n-bit έχει έναν n-bit μετρητή για κάθε καταχώρηση στον προσωρινό καταχωρητή πρόβλεψης διακλαδώσεων. Όταν ο μετρητής είναι μεγαλύτερος ή ίσος από το μισό της μέγιστης τιμής (2n-1), προβλέπεται ότι η διακλάδωση ακολουθείται, διαφορετικά ότι δεν ακολουθείται. Στο σχήμα πρόβλεψης των δύο bit ο μετρητής αυξάνει όταν η διακλάδωση ακολουθείται, ενώ μειώνεται όταν η διακλάδωση δεν ακολουθείται. Τα σχήματα πρόβλεψης των δύο bit λειτουργούν εξίσου καλά με αυτά των n-bit και για αυτό και χρησιμοποιούνται στα περισσότερα συστήματα.
Στο παρακάτω σχήμα φαίνονται οι καταστάσεις ενός σχήματος πρόβλεψης των δύο bit. Χρησιμοποιώντας δύο bit αντί για ένα, η διακλάδωση θα προβλεφθεί λάθος μόνο μία φορά. Τα δύο bit χρησιμοποιούνται για να κωδικοποιήσουν τις τέσσερις καταστάσεις ενός συστήματος.



Σχήμα 2.6.1- Οι καταστάσεις ενός σχήματος πρόβλεψης των δύο bit.

Παράδειγμα
Τι ακρίβεια μπορούμε να περιμένουμε από έναν προσωρινό καταχωρητή πρόβλεψης διακλαδώσεων ο οποίος χρησιμοποιεί δύο bit για κάθε καταχώρηση;

Απάντηση:
Για το πρόγραμμα δοκιμής με όνομα SPEC89 ένας προσωρινός καταχωρητής πρόβλεψης διακλαδώσεων με 4096 καταχωρήσεις μπορεί να επιτύχει ακρίβεια πρόβλεψης από 82% έως και πάνω από 99% ή ρυθμό λάθος πρόβλεψης από 1% ως 18%.

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

Θεωρείτε πως η ακρίβεια πρόβλεψης των εντολών διακλάδωσης με συνθήκη είναι αρκετή για να καθοριστεί η απόδοση των εντολών αυτών; Να αιτιολογήσετε την απάντησή σας.

 

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



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

Παράδειγμα
Δίνεται το παρακάτω τμήμα κώδικα:
SUBI R3, R1, #2
BNEZ R3, L1 ; Διακλάδωση b1
ADD R1, R0, R0 ;
L1: SUBI R3, R2, #2
BNEZ R3, L2 ; Διακλάδωση b2
ADD R2, R0, R0 ;
L2: SUB R3, R1, R2 ;
BEQZ R3, L3 ; Διακλάδωση b3
Απάντηση:
Στο παραπάνω τμήμα κώδικα υπάρχουν τρεις διακλαδώσεις, b1, b2 και b3. Η βασική παρατήρηση είναι ότι η συμπεριφορά της διακλάδωσης b3 εξαρτάται από τις συμπεριφορές των άλλων δύο διακλαδώσεων. Συγκεκριμένα αν καμιά από τις διακλαδώσεις b1 και b2 δεν ακολουθείται, τότε η διακλάδωση b3 ακολουθείται. Ένα σχήμα πρόβλεψης που χρησιμοποιεί αποκλειστικά και μόνο τη συμπεριφορά μιας διακλάδωσης για να προβλέψει το αποτέλεσμά της, δεν μπορεί ποτέ να αποκτήσει αυτή τη συμπεριφορά.

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

Παράδειγμα
Θεωρούμε το παρακάτω τμήμα κώδικα:
    if (d = = 0)
     d=1;
    if (d = = 1)
Απάντηση:
Εάν θεωρήσουμε ότι το d κρατείται στον καταχωρητή R1, τότε ο αντίστοιχος κώδικας που εκτελείται σε μία DLX σωλήνωση θα είναι ο παρακάτω:
BNEZ R1, L1 ; Διακλάδωση b1 (d!=0)
ADDI R1, R0, #1; d = = 0, άρα d=1
L1: SUBI R3, R1, #1;
BNEZ R3, L2 ; Διακλάδωση b2 (d!=1)
.....
L2:

Έστω b1 η πρώτη διακλάδωση και b2 η δεύτερη. Οι πιθανές ακολουθίες εκτέλεσης, για μία εκτέλεση του παραπάνω τμήματος του κώδικα, για τιμές d=0,1,2 παρουσιάζονται στον παρακάτω πίνακα.


Πίνακας 1

Από τον πίνακα 1 βλέπουμε ότι αν η διακλάδωση b1 δεν ακολουθείται, τότε και η διακλάδωση b2 δεν ακολουθείται. Αυτό, ένας συσχετισμένος προγνώστης μπορεί να το εκμεταλλευτεί, αλλά όχι ο τυπικός προγνώστης. Αντί να εξετάσουμε όλα τα πιθανά μονοπάτια διακλαδώσεων, θεωρούμε μια ακολουθία όπου το d μεταβάλλεται μεταξύ 2 και 0. 'Ενας προγνώστης ενός bit που ξεκινάει με την κατάσταση ότι δεν ακολουθείται, έχει τη συμπεριφορά του παρακάτω πίνακα.


Πίνακας 2 - To T σημαίνει ότι η διακλάδωση ακολουθείται, ενώ το NT σημαίνει ότι δεν ακολουθείται.

Όλες οι προβλέψεις των παραπάνω διακλαδώσεων είναι λάθος.

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



Πίνακας 3- Συνδυασμοί και σημασία των δύο bit πρόβλεψης ακολουθούμενης και μη ακολουθούμενης διακλάδωσης. Το T σημαίνει ακολουθούμενη, ενώ το NT σημαίνει μη ακολουθούμενη διακλάδωση.

Η δράση του προγνώστη ενός bit με ένα bit συσχέτισης, όταν εισάγεται το NT/NT παρουσιάζεται στο παρακάτω πίνακα.



Πίνακας 4- Η δράση του προγνώστη ενός bit με ένα bit συσχέτισης, όταν εισάγεται το NT/NT.

Σε αυτή την περίπτωση, η μόνη λάθος πρόβλεψη είναι στην πρώτη επανάληψη όταν d=2. Η σωστή πρόβλεψη του b1 γίνεται λόγω της επιλογής των τιμών για το d, μια και το b1 δεν είναι φανερά συσχετισμένο με την προηγούμενη πρόβλεψη του b2. Ωστόσο, η σωστή πρόβλεψη του b2 δείχνει το πλεονέκτημα των συσχετισμένων προγνωστών. Ακόμα και αν είχαμε επιλέξει διαφορετικές τιμές για το d, ο προγνώστης για το b2 θα προέβλεπε σωστά την περίπτωση που το b1 δεν ακολουθείται σε κάθε εκτέλεση του b2, μετά από μία αρχική αποτυχημένη πρόβλεψη.

Ο προγνώστης, που αφορά τους δύο τελευταίους πίνακες ονομάζεται προγνώστης (1,1), επειδή χρησιμοποιεί τη συμπεριφορά της τελευταίας διακλάδωσης για να επιλέξει ανάμεσα σε ένα ζευγάρι προγνωστών διακλαδώσεων του ενός bit. Στη γενική περίπτωση ένας προγνώστης (m, n), χρησιμοποιεί τη συμπεριφορά των τελευταίων m διακλαδώσεων για να επιλέξει ανάμεσα σε 2m προγνώστες διακλαδώσεων, ο καθένας από τους οποίους είναι ένας προγνώστης διακλάδωσης με n-bit.
Η μεγάλη σπουδαιότητα αυτού του είδους προγνώστη, είναι ότι μπορεί να επιτύχει πιο μεγάλη ακρίβεια πρόβλεψης, από ότι ένα σχήμα των δύο bit, ενώ απαιτεί μόνο ένα ασήμαντο επιπλέον ποσό υλικού.