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

1. Ο πιο απλός τρόπος είναι να καθυστερήσουμε τη σωλήνωση έως ότου γίνει γνωστή η διεύθυνση στόχου διακλάδωσης κι αν αληθεύει η συνθήκη διακλάδωσης. Το σχήμα αυτό είναι αρκετά απλό σε ό,τι αφορά το υλικό και το λογισμικό και έχει απεικονιστεί στο σχήμα 1.6.1.
2. Ένα άλλο σχήμα είναι να προβλέψουμε ότι η διακλάδωση δεν πρόκειται να ακολουθηθεί, επιτρέποντας απλά στο υλικό να συνεχίσει σα να μην εκτελέστηκε η διακλάδωση. Στη σωλήνωση του DLX υπολογιστή, η μέθοδος αυτή ονομάζεται πρόβλεψη μη ακολούθησης. Υλοποιείται με την ανάκληση εντολών, σαν να ήταν η διακλάδωση μια απλή εντολή.
   Το σχήμα αυτό είναι λίγο πιο πολύπλοκο, αλλά καλύτερο σε επιδόσεις από το προηγούμενο.
   
   

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

   

   Σχήμα 1.6.3 Το σχήμα πρόβλεψης μη ακολούθησης και η ακολουθία σωλήνωσης όταν η διακλάδωση δεν ακολουθείται (στο πάνω σχήμα) και όταν ακολουθείται ( στο κάτω σχήμα). Όταν η διακλάδωση δεν ακολουθείται, γεγονός που καθορίζεται κατά τη διάρκεια του σταδίου ID, έχουμε καλέσει τη σωστή εντολή και απλώς συνεχίζουμε. Αν η διακλάδωση ακολουθείται τότε ξαναρχίζουμε την ανάκληση από το στόχο διακλάδωσης. Αυτό προκαλεί όλες τις εντολές, που ακολουθούν τη διακλάδωση, να καθυστερούν ένα κύκλο.
   
   
3. Το επόμενο σχήμα είναι η πρόβλεψη ότι η διακλάδωση ακολουθείται. Στη συνέχεια, κι ενώ η διακλάδωση έχει αποκωδικοποιηθεί και υπολογιστεί η διεύθυνση του στόχου, υποθέτουμε ότι η διακλάδωση ακολουθείται και αρχίζουμε να καλούμε και να εκτελούμε το στόχο. Η μέθοδος αυτή συνιστάται για υπολογιστές στους οποίους ο στόχος διακλάδωσης γίνεται γνωστός πριν από το αποτέλεσμα της διακλάδωσης.
   
   
4. Υπάρχουν υπολογιστές που έχουν χρησιμοποιήσει την τεχνική της καθυστέρησης διακλάδωσης. Η μέθοδος αυτή έχει χρησιμοποιηθεί σε πολλές μικροπρογραμματιζόμενες μονάδες ελέγχου. Σε μια καθυστέρηση διακλάδωσης, ο κύκλος εκτέλεσης με μια καθυστέρηση διακλάδωσης μήκους n είναι:

   εντολή διακλάδωσης
   διαδοχική επόμενη εντολή1
   διαδοχική επόμενη εντολή2
   . . .
   διαδοχική επόμενη εντολήn
   στόχος διακλάδωσης αν η διακλάδωση ακολουθείται
   

   Οι διαδοχικές επόμενες εντολές βρίσκονται στη σχισμή καθυστέρησης διακλάδωσης. Οι εντολές αυτές εκτελούνται είτε η διακλάδωση ακολουθείται είτε όχι. Στο σχήμα 1.6.4 φαίνεται η συμπεριφορά της σωλήνωσης στον DLX υπολογιστή για την περίπτωση αυτή, ενώ το σχήμα 1.6.5 δείχνει τους τρεις τρόπους με τους οποίους μια καθυστέρηση διακλάδωσης μπορεί να προγραμματιστεί.

   

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

   

   Σχήμα 1.6.5 Προγραμματισμός της σχισμής καθυστέρησης διακλάδωσης. Το πάνω σχήμα σε κάθε ζευγάρι δείχνει τον κώδικα πριν τον προγραμματισμό και το κάτω σχήμα δείχνει τον προγραμματισμένο κώδικα. Στο (a) η σχισμή καθυστέρησης προγραμματίζεται με μια ανεξάρτητη εντολή πριν τη διακλάδωση. Αυτή είναι η καλύτερη επιλογή. Οι στρατηγικές (b) και (c) χρησιμοποιούνται όταν η (a) είναι αδύνατη. Στις ακολουθίες κώδικα για τις (b) και (c) η χρήση του καταχωρητή R1 στη συνθήκη διακλάδωσης εμποδίζει την εντολή ADD(της οποίας προορισμός είναι ο R1) να μετακινηθεί μετά τη διακλάδωση. Στο (b) η σχισμή καθυστέρησης διακλάδωσης προγραμματίζεται από το στόχο διακλάδωσης. Συνήθως η εντολή στόχου θα χρειαστεί να αντιγραφεί γιατί μπορεί να προσεγγιστεί από ένα άλλο μονοπάτι. Η στρατηγική (b) προτιμάται όταν η διακλάδωση έχει υψηλή πιθανότητα να ακολουθηθεί, όπως μια διακλάδωση βρόχου. Τέλος, η διακλάδωση μπορεί να προγραμματιστεί από το τμήμα κώδικα που βρίσκεται ανάμεσα (fall through) στην εντολή διακλάδωσης και στο στόχο διακλάδωσης.

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

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

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

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

 

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

Παρουσιάζουμε τους περιορισμούς αυτούς συνοπτικά μαζί με τις καταστάσεις στις οποίες επικρατούν στο σχήμα 1.6.6 που ακολουθεί.

Σχήμα 1.6.6 Σχήματα προγραμματισμού καθυστερημένων διακλαδώσεων και οι απαιτήσεις τους. Η προέλευση της εντολής, που προγραμματίζεται στη σχισμή καθυστέρησης, καθορίζει τη στρατηγική προγραμματισμού. Ο μεταγλωττιστής εξετάζει τις εντολές που θα προγραμματίσουν τη σχισμή καθυστέρησης. Όταν η σχισμή δεν μπορεί να προγραμματιστεί, γεμίζει με εντολές no-op. Στη στρατηγική (β), αν ο στόχος διακλάδωσης είναι επίσης προσβάσιμος από ένα άλλο σημείο του προγράμματος – όπως αν ήταν η πρώτη εντολή του βρόχου – η εντολή στόχου πρέπει να αντιγραφεί κι όχι απλά να μετακινηθεί.

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

Σε μία ακυρωτική διακλάδωση, η εντολή περιλαμβάνει την κατεύθυνση, η οποία είχε προβλεφθεί πως θα ακολουθήσει η διακλάδωση. Όταν η διακλάδωση συμπεριφέρεται όπως είχε προβλεφθεί, η εντολή στη σχισμή καθυστέρησης διακλάδωσης απλά εκτελείται, όπως θα είχε κάνει σε μια καθυστέρηση διακλάδωσης. Όταν η διακλάδωση προβλέπεται λανθασμένα, η εντολή στη σχισμή καθυστέρησης διακλάδωσης τίθεται σε μια εντολή no-op. Στο σχήμα 1.6.7 φαίνεται η συμπεριφορά και για τις δύο περιπτώσεις.

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

Οι ακυρωτικές διακλαδώσεις έχουν το πλεονέκτημα ότι εξαλείφουν τις απαιτήσεις για την εντολή που τοποθετείται στη σχισμή καθυστέρησης, ενεργοποιώντας το μεταγλωττιστή ως προς τη χρήση των προγραμματιστικών μεθόδων (b) και (c) του σχήματος 1.6.5, παραβιάζοντας όμως τις απαιτήσεις που φαίνονται στο σχήμα 1.6.6 για τις αντίστοιχες μεθόδους.

Οι πιο πολλοί υπολογιστές με ακυρωτικές διακλαδώσεις διαθέτουν μία ακυρωτική και μία μη ακυρωτική φόρμα. Όμως, παρόλο που ο σχεδιασμός αυτός έχει πολλά πλεονεκτήματα, δεν επιτρέπει τη χρήση της προγραμματιστικής μεθόδου (c), εκτός και αν πληρούνται οι προϋποθέσεις του σχήματος 1.6.6.

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

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

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

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

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

 

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