Σχεδόν σε οποιοδήποτε πρόγραμμα υπολογιστή, υπάρχουν τμήματα του κώδικα που διακλαδίζονται σε ξεχωριστές διαδρομές. Για παράδειγμα, μια δήλωση αν-τότε-άλλο έχει δύο πιθανά αποτελέσματα. Αυτές οι δηλώσεις δεν παρουσιάζουν κανένα πρόβλημα στους διαδοχικούς επεξεργαστές, καθώς η CPU επεξεργάζεται κάθε εντολή με τη σειρά. Οι κλάδοι παρουσιάζουν μεγάλο πρόβλημα για τους επεξεργαστές με σωλήνωση, καθώς πολλαπλές εντολές εκτελούνται ταυτόχρονα.
Το Σενάριο
Στην περίπτωση ενός προγράμματος με δήλωση διακλάδωσης με δύο πιθανά αποτελέσματα, οι δύο πιθανές διαδρομές κώδικα δεν μπορούν να βρίσκονται στην ίδια θέση. Η επεξεργασία που απαιτείται για την ολοκλήρωση μιας επιλογής θα είναι διαφορετική. Διαφορετικά, το πρόγραμμα δεν θα διακλαδωθεί. Πιθανότατα θα υπάρχει ένας αρκετά μεγάλος αριθμός δηλώσεων διακλάδωσης που λαμβάνονται μόνο μία φορά, όπως μια δήλωση εάν.
Υπάρχουν επίσης εντολές διακλάδωσης που σχηματίζουν βρόχο. Ενώ αυτές μπορεί να μην είναι τόσο κοινές αριθμητικά όσο οι δηλώσεις μιας χρήσης, γενικά επαναλαμβάνονται στατιστικά. Μπορούμε να υποθέσουμε ότι είναι πιο πιθανό ένας κλάδος να σας οδηγήσει πίσω σε έναν βρόχο παρά όχι.
Γιατί είναι αυτό ένα πρόβλημα;
Δεν έχει σημασία πώς διατυπώνεται αυτό το πρόβλημα σε έναν πλήρως διαδοχικό επεξεργαστή. Απλώς δεν είναι πρόβλημα. Ποιος κλάδος θα ληφθεί είναι γνωστός πριν από την επεξεργασία του πρώτου μέρους της ακόλουθης εντολής.
Σε έναν επεξεργαστή με διοχέτευση, ωστόσο, οι ακόλουθες οδηγίες βρίσκονται στην ουρά. Ήδη υποβάλλονται σε επεξεργασία όταν ο επεξεργαστής γνωρίζει ποιο κλάδο έχει ληφθεί. Πώς πρέπει λοιπόν ο επεξεργαστής να χειριστεί αυτό το σενάριο; Υπάρχουν μερικές επιλογές. Το χειρότερο είναι απλώς να περιμένεις και να αφήσεις τον αγωγό σε αδράνεια ενώ περιμένει την απάντηση για το ποιο κλάδο να πάρει. Αυτό θα σήμαινε ότι κάθε φορά που έχετε μια δήλωση διακλάδωσης, θα χάνετε πάντα τουλάχιστον τόσους κύκλους χρόνου επεξεργαστή όσοι έχετε στάδια σε εξέλιξη.
Εναλλακτικά, θα μπορούσατε να δοκιμάσετε να εκτελέσετε και τις δύο επιλογές σε εξέλιξη και να απορρίψετε τη λάθος επιλογή. Αυτό θα είχε τη μισή ποινή να μην κάνεις τίποτα, αλλά να επιφέρει ποινή απόδοσης σε κάθε δήλωση διακλάδωσης. Δεδομένου ότι οι σύγχρονες CPU μπορούν επίσης να εκτελούν οδηγίες εκτός λειτουργίας, θα μπορούσατε ενδεχομένως να προσπαθήσετε να εκτελέσετε κάθε εντολή διακλάδωσης το συντομότερο δυνατό. Άρα το αποτέλεσμά του είναι γνωστό πριν χρειαστεί. Αυτή η επιλογή θα μπορούσε να είναι χρήσιμη, εκτός από το ότι δεν είναι επεκτάσιμη. Ας υποθέσουμε ότι έχετε μια σχετικά υψηλή πυκνότητα δηλώσεων διακλάδωσης. Σε αυτήν την περίπτωση, απλά δεν θα μπορείτε να τα εκτελέσετε όλα νωρίς χωρίς να έχετε χρόνο αδράνειας.
Πώς αντιμετωπίζεται πραγματικά αυτό το ζήτημα
Στην πραγματικότητα, ο επεξεργαστής περιλαμβάνει έναν προγνωστικό κλάδου. Η πρόβλεψη διακλάδωσης επιχειρεί να μαντέψει ποιο αποτέλεσμα μιας επιλογής διακλάδωσης θα ληφθεί. Στη συνέχεια, ο επεξεργαστής υποθέτει ότι η πρόβλεψη είναι σωστή και προγραμματίζει οδηγίες. Εάν η πρόβλεψη διακλάδωσης είναι ακριβής, δεν υπάρχει ποινή απόδοσης.
Εάν το πρόγραμμα πρόβλεψης διακλάδωσης κάνει λάθος, πρέπει να ξεπλύνετε τον αγωγό και να ξεκινήσετε την επεξεργασία του πραγματικού αποτελέσματος. Αυτό έχει ως αποτέλεσμα μια ελαφρώς χειρότερη ποινή απόδοσης από το να μην έχετε κάνει τίποτα και απλώς να περιμένετε το αποτέλεσμα. Για να έχετε την καλύτερη απόδοση, είναι σημαντικό να διασφαλίσετε ότι η πρόβλεψη διακλάδωσης είναι όσο το δυνατόν ακριβέστερη. Υπάρχει μια σειρά από διαφορετικές προσεγγίσεις σε αυτό.
Κωδικός αντιστοίχισης
Στον κώδικα μηχανής, ένας κλάδος είναι πάντα μια επιλογή μεταξύ ανάγνωσης της επόμενης εντολής ή μετάβασης σε ένα σύνολο εντολών αλλού. Μερικές πρώιμες εφαρμογές πρόβλεψης διακλαδώσεων απλώς υπέθεσαν ότι όλοι οι κλάδοι θα λαμβάνονταν πάντα ή ποτέ δεν θα λαμβάνονταν. Αυτή η υλοποίηση μπορεί να έχει ένα εκπληκτικά καλό ποσοστό επιτυχίας εάν οι μεταγλωττιστές γνωρίζουν αυτήν τη συμπεριφορά και γνωρίζουν έχει σχεδιαστεί για να προσαρμόζει τον κώδικα του μηχανήματος έτσι ώστε το πιο πιθανό αποτέλεσμα να ευθυγραμμίζεται με το γενικό του επεξεργαστή υπόθεση. Αυτό απαιτεί πολύ συντονισμό και προσαρμογή των συνηθειών ανάπτυξης λογισμικού.
Μια άλλη εναλλακτική ήταν να μάθουμε από το στατιστικό ότι οι βρόχοι λαμβάνονται γενικά και πάντα πηδούν εάν ο κλάδος πηγαίνει προς τα πίσω στο ροή εντολών και μην πηδήξετε ποτέ εάν το άλμα είναι προς τα εμπρός, επειδή αυτή θα ήταν κανονικά η στατιστικά λιγότερο πιθανή κατάσταση να αφήσετε ένα βρόχος. Αυτοί είναι και οι δύο τύποι πρόβλεψης στατικής διακλάδωσης, όπου το αποτέλεσμα ενός κλάδου προβλέπεται κατά το χρόνο μεταγλώττισης.
Δυναμικοί Προγνωστικοί Κλάδος
Οι σύγχρονοι μηχανισμοί πρόβλεψης υποκαταστημάτων είναι δυναμικοί, χρησιμοποιώντας στατιστικά από το τρέχον πρόγραμμα που εκτελείται για να επιτύχουν καλύτερα ποσοστά επιτυχίας προβλέψεων. Ένας μετρητής κορεσμού είναι μια βάση για όλους τους τρέχοντες προγνωστικούς κλάδους. Η πρώτη εικασία αποφασίζεται στατικά ή τυχαία. Μόλις ληφθεί ή όχι ένας κλάδος, αυτό το αποτέλεσμα αποθηκεύεται σε ένα τμήμα της μνήμης. Την επόμενη φορά που θα εμφανιστεί ο ίδιος κλάδος, ο προγνωστικός κλάδος προβλέπει το ίδιο αποτέλεσμα όπως πριν.
Αυτό έχει φυσικά ως αποτέλεσμα καλούς ρυθμούς πρόβλεψης για βρόχους. Υπάρχουν δύο εκδοχές αυτού. Οι πρώτες εκδόσεις χρησιμοποιούσαν απλώς ένα μόνο κομμάτι δεδομένων για να υποδείξουν εάν η διακλάδωση είχε ληφθεί ή όχι. Οι νεότερες εκδόσεις χρησιμοποιούν δύο bit για να υποδείξουν μια ασθενώς ή έντονα επιλεγμένη ή μη επιλεγμένη επιλογή. Αυτή η ρύθμιση εξακολουθεί να μπορεί να προβλέψει το αποτέλεσμα της λήψης ενός βρόχου εάν το πρόγραμμα επιστρέψει σε αυτό, αυξάνοντας γενικά τα ποσοστά επιτυχίας.
Μοτίβα παρακολούθησης
Για την παρακολούθηση μοτίβων, ορισμένοι προγνωστικοί κλάδοι παρακολουθούν ένα ιστορικό των επιλογών που έγιναν. Για παράδειγμα, ας υποθέσουμε ότι ένας βρόχος καλείται συνεχώς, αλλά κάνει βρόχους μόνο τέσσερις φορές πριν βγει από τον βρόχο. Σε αυτήν την περίπτωση, ένας προσαρμοστικός προγνωστικός παράγοντας δύο επιπέδων μπορεί να αναγνωρίσει αυτό το μοτίβο και να προβλέψει ότι θα συμβεί ξανά. Αυτό αυξάνει ακόμη περισσότερο τα ποσοστά επιτυχίας σε σχέση με έναν απλό κορεσμένο μετρητή. Οι σύγχρονοι προγνωστικοί κλάδοι βασίζονται σε αυτό περαιτέρω χρησιμοποιώντας ένα νευρωνικό δίκτυο για να εντοπίσουν και να προβλέψουν μοτίβα.
Ορισμένοι προγνωστικοί κλάδοι χρησιμοποιούν πολλαπλούς αλγόριθμους και στη συνέχεια συγκρίνουν τα αποτελέσματα για να αποφασίσουν ποια πρόβλεψη θα χρησιμοποιήσουν. Ορισμένα συστήματα παρακολουθούν κάθε εντολή διακλάδωσης ξεχωριστά σε αυτό που ονομάζεται πρόβλεψη τοπικού κλάδου. Άλλοι χρησιμοποιούν ένα παγκόσμιο σύστημα πρόβλεψης διακλάδωσης για να παρακολουθούν όλες τις πρόσφατες οδηγίες διακλάδωσης. Και τα δύο έχουν τις χρήσεις και τα μειονεκτήματά τους.
συμπέρασμα
Ένας δείκτης πρόβλεψης διακλάδωσης είναι ένα ειδικό μέρος μιας CPU με διοχέτευση. Προσπαθεί να προβλέψει το αποτέλεσμα μιας εντολής διακλάδωσης πριν από την επεξεργασία της πραγματικής εντολής. Αυτή είναι μια βασική συνάρτηση μιας CPU με διοχέτευση, καθώς επιτρέπει στην CPU να διατηρεί κορεσμένη τη διοχέτευση, ακόμα κι αν δεν είναι σίγουρο ποιες οδηγίες πρέπει να εκτελεστούν. Δεν προσφέρουν καμία μείωση στην απόδοση όταν είναι σωστά. Οι σύγχρονοι αλγόριθμοι μπορούν να είναι ακριβείς σε σχετικά προβλέψιμους φόρτους εργασίας έως και το 97% του χρόνου.
Δεν υπάρχει τέλεια μέθοδος πρόβλεψης, επομένως οι υλοποιήσεις ποικίλλουν. Ο αντίκτυπος στην απόδοση μιας λανθασμένης πρόβλεψης εξαρτάται από το μήκος του αγωγού. Συγκεκριμένα, το μήκος του αγωγού πριν μπορεί να προσδιοριστεί εάν η πρόβλεψη ήταν λάθος. Εξαρτάται επίσης από το πόσες οδηγίες υπάρχουν σε κάθε στάδιο του αγωγού. Οι σύγχρονοι επιτραπέζιοι επεξεργαστές υψηλής τεχνολογίας έχουν περίπου 19 στάδια διοχέτευσης και μπορούν να εκτελούν τουλάχιστον τέσσερις εντολές ταυτόχρονα σε κάθε στάδιο.