Για να διατηρήσουμε την σωλήνωση πλήρη βρίσκουμε ακολουθίες εντολών ασυσχέτιστων μεταξύ τους, οι οποίες μπορούν να επικαλυφθούν. Για να αποφύγουμε καθυστερήσεις στην σωλήνωση, διαχωρίζουμε κάθε εξαρτώμενη εντολή από την πηγαία εντολή, σε απόσταση, ίση με την καθυστέρηση της πηγαίας εντολής στην σωλήνωση, μετρημένη σε κύκλους ρολογιού.
Η δυνατότητα του μεταγλωττιστή να εκτελέσει τον προγραμματισμό σωλήνωσης εξαρτάται από:
Υποθέτουμε ότι διαθέτουμε:
Στο παρακάτω σχήμα δίνονται οι καθυστερήσεις για τις λειτουργίες κινητής υποδιαστολής (FP) :
Σχήμα 2.1.1 - Στην πρώτη στήλη φαίνεται ο τύπος της πηγαίας εντολής, στην δεύτερη στήλη ο τύπος της εντολής που εξαρτάται από το αποτέλεσμα, ενώ στην τρίτη φαίνεται η καθυστέρηση σε κύκλους ρολογιού, που είναι αναγκαία για την αποφυγή της κατάστασης κινδύνου.
ΠαράδειγμαΠαράδειγμα απλού βρόχου, που προσθέτει μία βαθμωτή τιμή σε έναν πίνακα, στην μνήμη.
for (i=1; i 1000; i++)
x[i]=x[i]+s;
Απάντηση:
Παρατηρούμε ότι το κύριο μέρος κάθε επανάληψης είναι ανεξάρτητο και άρα ο βρόχος είναι παράλληλος. Τώρα θα εξετάσουμε πώς μπορούμε να χρησιμοποιήσουμε αυτήν την ιδιότητα, για να βελτιώσουμε την παραλληλία στον DLX, χρησιμοποιώντας τις καθυστερήσεις που αναφέραμε στο σχήμα 2.1.1.
Μεταφράζουμε το βρόχο σε γλώσσα Assembly. Στο τμήμα κώδικα που ακολουθεί, το οποίο δεν είναι ειδικά προγραμματισμένο για σωλήνωση, ο R1 περιέχει αρχικά τη διεύθυνση του στοιχείου στον πίνακα με την μεγαλύτερη διεύθυνση και o F2 περιέχει τη βαθμωτή τιμή s. Υποθέτουμε ότι η χαμηλότερη διεύθυνση είναι στο 0, γιατί διαφορετικά, ο βρόχος θα απαιτούσε μία παραπάνω εντολή που θα εκτελούσε την σύγκριση με τον R1. 'Εχουμε, λοιπόν :
ΔΡΑΣΤΗΡΙΟΤΗΤΑ 2
Στο παράδειγμα που ακολουθεί εξετάζουμε πόσο γρήγορα θα εκτελεστεί ο παραπάνω βρόχος σε απλή σωλήνωση του DLX, λαμβάνοντας υπόψη τις καθυστερήσεις που αναφέρθηκαν στο σχήμα 2.1.1.
ΠαράδειγμαΔείξτε, πώς ο παραπάνω βρόχος θα ήταν για τον DLX, χωρίς προγραμματισμό και με προγραμματισμό, περικλείοντας τις καθυστερήσεις που προκύπτουν ή τους αδρανείς κύκλους ρολογιού. Ο προγραμματισμός να γίνει και για τις καθυστερήσεις που προκύπτουν από εφαρμογές κινητής υποδιαστολής αλλά και από καθυστερημένες διακλαδώσεις.
Απάντηση:
Χωρίς προγραμματισμό, ο βρόχος θα εκτελεστεί ως εξής:
Παρατηρούμε ότι χρειάζονται 10 κύκλοι ρολογιού, ανά επανάληψη:
Με προγραμματισμό έχουμε:
Ο χρόνος εκτέλεσης μειώθηκε από 10 σε 6 κύκλους ρολογιού. Η καθυστέρηση μετά την εντολή ADDD χρειάζεται λόγω της χρήσης του F4 από την εντολή SD.
Για τον προγραμματισμό της καθυστερημένης διακλάδωσης, ο μεταγλωττιστής καθορίζει την ανταλλαγή των εντολών SUBI και SD, αλλάζοντας και τη διεύθυνση που η SD αποθηκεύει το αποτέλεσμα της από 0 (R1) σε 8 (R1). Οι περισσότεροι μεταγλωττιστές, γνωρίζουν ότι η εντολή SD εξαρτάται από την εντολή SUBI και δεν υλοποιούν την ανταλλαγή αυτή. Η αλυσίδα των εξαρτημένων εντολών, από την εντολή LD στην ADDD και μετά στην SD, καθορίζει το πλήθος κύκλων ρολογιού του βρόχου.
Σε κάθε επανάληψη αποθηκεύουμε ένα στοιχείο του πίνακα, κάθε 6 κύκλους ρολογιού, αλλά ο πραγματικός χρόνος είναι 3 μόνο κύκλοι από τους 6, για LD, ADD, SD. Οι υπόλοιποι τρεις, διατίθενται για τις εντολές BNEZ, SUBI και stall. Για να εξαλείψουμε αυτούς τους τρεις τελευταίους κύκλους ρολογιού, θα χρειαστεί να υλοποιήσουμε περισσότερες εντολές μέσα στο κύριο μέρος του βρόχου ως προς την εντολή διακλάδωσης (BNEZ R1, loop) και την εντολή επιβάρυνσης (SUBI R1, R1, #8).
Ανάπτυξη βρόχου , είναι ένα απλό σχήμα, για την αύξηση του αριθμού των εντολών που σχετίζονται με την εντολή διακλάδωσης και την εντολή επιβάρυνσης.
Επιτυγχάνεται με την επανάληψη του κυρίως μέρους του βρόχου και με προσαρμογή των εντολών που τελειώνουν το βρόχο (BNEZ, SUBI).
Η ανάπτυξη του βρόχου βελτιώνει επίσης τον προγραμματισμό, περιορίζοντας την εντολή διακλάδωσης και ομαδοποιώντας εντολές από διαφορετικές επαναλήψεις.
ΔΡΑΣΤΗΡΙΟΤΗΤΑ 3
ΑΠΑΝΤΗΣΗ ΔΡΑΣΤΗΡΙΟΤΗΤΑΣ 3
Παράδειγμα
ΔΡΑΣΤΗΡΙΟΤΗΤΑ 4
ΑΠΑΝΤΗΣΗ ΔΡΑΣΤΗΡΙΟΤΗΤΑΣ 4 ΔΡΑΣΤΗΡΙΟΤΗΤΑ 5
|
|