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

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

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

Η μονάδα ελέγχου μιας μηχανής πεπερασμένων καταστάσεων ανταποκρίνεται στα πέντε βήματα της εκτέλεσης των εντολών. Κάθε κατάσταση της μηχανής θα καταλαμβάνει έναν κύκλο ρολογιού. Η μηχανή πεπερασμένων καταστάσεων αποτελείται από διάφορα μέρη. Αφού τα δύο πρώτα βήματα είναι ίδια για όλες τις εντολές, οι δύο αρχικές καταστάσεις της μηχανής θα είναι κοινές για όλες τις εντολές. Τα βήματα 3 έως 5 διαφέρουν ανάλογα με τον κωδικό λειτουργίας. Μετά την εκτέλεση του τελευταίου βήματος, για ένα συγκεκριμένο τύπο εντολής, η μηχανή πεπερασμένων καταστάσεων επιστρέφει στην αρχική κατάσταση για να ξεκινήσει την ανάκληση της επόμενης εντολής. Το σχήμα 3.2.35 απεικονίζει μια αναπαράσταση της μηχανής πεπερασμένων καταστάσεων. Στη συνέχεια θα αναπτύξουμε το τμήμα ανάκλησης της εντολής και το τμήμα της αποκωδικοποίησης και μετά θα δούμε τις καταστάσεις (και τις λειτουργίες τους) για τους διαφορετικούς τύπους εντολών.

Σχήμα 3.2.35 - Μια εικόνα του υψηλού επιπέδου της μονάδας ελέγχου της μηχανής πεπερασμένων καταστάσεων. Κάθε κουτί σε αυτό το σχήμα μπορεί να είναι από μία έως πολλές καταστάσεις. Το βέλος 'Αρχή' δείχνει την αρχική κατάσταση, στην οποία γίνεται ανάκληση της πρώτης εντολής.

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

Τα σήματα που είναι ενεργά σε κάθε κατάσταση φαίνονται στο σχήμα μέσα στην κατάσταση. Τα βέλη μεταξύ των καταστάσεων καθορίζουν την επόμενη κατάσταση και έχουν πάνω τους τις συνθήκες οι οποίες προσδιορίζουν την επόμενη κατάσταση, όταν περισσότερες από μία καταστάσεις είναι πιθανές. Μετά την κατάσταση 1, η ενεργοποίηση των σημάτων εξαρτάται από τον τύπο της εντολής. Έτσι η μηχανή του σχήματος 3.2.36 έχει τέσσερα βέλη να εξέρχονται από την κατάσταση 1, που ανταποκρίνονται στους τέσσερις διαφορετικούς τύπους των εντολών: εντολές αναφοράς στη μνήμη, τύπου R, διακλάδωσης και μεταπήδησης. Η κατάσταση αυτή ονομάζεται αποκωδικοποίηση και επομένως οι ενέργειες που ακολουθούν εξαρτώνται από τον τύπο της εντολής.

Σχήμα 3.2.36 - Η ανάκληση της εντολής και το τμήμα της αποκωδικοποίησης είναι ίδια για όλες τις εντολές. Οι καταστάσεις αυτές ανταποκρίνονται στο κουτί που βρίσκεται στην κορυφή του σχήματος 3.2.35. Στην πρώτη κατάσταση ενεργοποιούμε κάποια σήματα για να διαβαστεί μια εντολή από τη μνήμη και να εγγραφεί στον καταχωρητή εντολών (MemRead και MemWrite), και θέτουμε το IorD=0 για την επιλογή του απαριθμητή προγράμματος ως την πηγή της διεύθυνσης. Τα σήματα PCWrite, PCSourse, ALUSrcA, ALUOp και ALUSrcB είναι ενεργοποιημένα για τον υπολογισμό του PC+4 και την αποθήκευσή αυτής της τιμής στον απαριθμητή προγράμματος. Στην επόμενη κατάσταση, υπολογίζουμε την διεύθυνση του στόχου διακλάδωσης θέτοντας το ALUSrcB=11 (για να προκαλέσουμε την αποστολή των 16 λιγότερο σημαντικών ψηφίων του IR μετά από επέκταση προσήμου και ολίσθηση, στην ALU). Επίσης θέτουμε τα σήματα ALUSrcA=0 και ALUOp=00 και αποθηκεύουμε το αποτέλεσμα στον καταχωρητή Στόχο (χρησιμοποιώντας το TargetWrite). Μετά υπάρχουν τέσσερις διαφορετικές καταστάσεις που εξαρτώνται από τον τύπο της εντολής, ο οποίος είναι γνωστός κατά την διάρκεια αυτού του βήματος. Εάν έχουμε εντολή φόρτωσης ή αποθήκευσης πηγαίνουμε σε μία κατάσταση, ενώ τα άλλα βέλη ασχολούνται με τους κωδικούς λειτουργίας μίας εντολής. Η είσοδος της μονάδας ελέγχου, που ονομάζεται op, χρησιμοποιείται για να καθορίσει ποιο από αυτά τα βέλη πρέπει να ακολουθήσουμε, δηλαδή ποια πρέπει να είναι η επόμενη κατάσταση (ένα από τα σχήματα: 3.2.37, 3.2.38, 3.2.39, 3.2.40).

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

• Εντολές αναφοράς στη μνήμη
• Εντολές τύπου R
• Εντολές διακλάδωσης με συνθήκη
• Εντολές μεταπήδησης

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

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

Να ενώσετε κατάλληλα τα σχήματα 3.2.36, 3.2.37, 3.2.38, 3.2.39, 3.2.40, έτσι ώστε να σχεδιάσετε την ολοκληρωμένη μηχανή πεπερασμένων καταστάσεων της μονάδας ελέγχου του υπολογιστή MIPS. Να συγκρίνετε το σχήμα που σχεδιάσατε με το σχήμα που ακολουθεί (σχήμα 3.2.41).

Σχήμα 3.2.41 - Η ολοκληρωμένη μηχανή πεπερασμένων καταστάσεων της μονάδας ελέγχου για την δίοδο δεδομένων του σχήματος 3.2.33. Στα βέλη υπάρχουν συνθήκες οι οποίες ελέγχονται για να καθορίσουν την επόμενη κατάσταση. Όταν για την επόμενη κατάσταση δεν υπάρχει συνθήκη, δεν υπάρχει ετικέτα στο βέλος. Οι ετικέτες μέσα στους κόμβους καθορίζουν τα σήματα εξόδου που είναι ενεργοποιημένα κατά την διάρκεια μιας κατάστασης. Η ενεργοποίηση του σήματος ελέγχου ενός πολυπλέκτη καθορίζεται πάντα εάν χρειάζεται σε κάποια από τις λειτουργίες. Έτσι σε μερικές καταστάσεις η είσοδος ελέγχου του πολυπλέκτη είναι ενεργοποιημένη στο 0.

Παράδειγμα

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

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

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

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

Η μηχανή πεπερασμένων καταστάσεων του σχήματος 3.2.41 ονομάζεται μηχανή Moore (από τον Edward Moore). Το χαρακτηριστικό της είναι ότι η έξοδος εξαρτάται μόνο από την παρούσα κατάσταση. Ένας διαφορετικός τύπος είναι οι μηχανή Mealy (από τον George Mealy). Στη μηχανή Mealy η έξοδος καθορίζεται και από την είσοδο και από την παρούσα κατάσταση.