ΗΥ-225: Οργάνωση Υπολογιστών
Ανοιξη 2001		 Τμ. Επ. Υπολογιστών
Πανεπιστήμιο Κρήτης
Σειρά Ασκήσεων 4:

Κάλεσμα Διαδικασιών στον MIPS

Προθεσμία έως Τετάρτη 7 Μαρτίου (βδομάδα 5)


Περίληψη Υπολοίπων Εντολών Μεταφοράς Ελέγχου του MIPS:

Εκτός από τις εντολές διακλάδωσης υπό συνθήκη, που είδαμε στην 3η σειρά ασκήσεων, το υποσύνολο εντολών του MIPS που χρησιμοποιούμε στο μάθημα περιλαμβάνει και τις παρακάτω άλλες εντολές μεταφοράς ελέγχου (CTI, control transfer instructions):
j target
Αλμα (jump) χωρίς συνθήκη: επόμενη προς εκτέλεση εντολή είναι η εντολή στη διεύθυνση target. Χρησιμοποιεί το J-format, το οποίο φαίνεται στη σελίδα 148 του βιβλίου (επάνω). Η τελική διεύθυνση προορισμού (32 bits) προκύπτει από τα 4 παλαιά MS bits του PC, τα 26 bits του πεδίου προορισμού της εντολής, και από 2 μηδενικά LS bits, όπως εξηγείται στη σελίδα 150 του βιβλίου (κάτω).
jal target
Αλμα και Σύνδεση (jump and link) -- κάλεσμα διαδικασίας: έχει το ίδιο format με την εντολή jump, και κάνει τα ίδια με εκείνην (ίδια διεύθυνση προορισμού), συν, επιπλέον, αποθηκεύει τη διεύθυνση της επόμενής της εντολής (παλαιό PC συν 4) στον καταχωρητή 31 ($ra, ή $31). Χρησιμοποιείται γιά κάλεσμα διαδικασίας, όπως περιγράφεται στις σελίδες 132-133 του βιβλίου. Η διεύθυνση που αποθηκεύεται μπορεί στη συνέχεια να χρησιμοποιηθεί γιά επιστροφή από τη διαδικασία, μέσω της εντολής jr $ra. Η διεύθυνση επιστροφής αποθηκεύεται πάντα στον $ra ($31) --το "31" δεν φαίνεται πουθενά μέσα στην εντολή jal, απλώς το βάζει το hardware αυτόματα.
jr $rs
Αλμα σε προορισμό που καθορίζεται από καταχωρητή (jump register): επόμενη προς εκτέλεση εντολή είναι η εντολή στη διεύθυνση που περιέχεται στον καταχωρητή rs (με άλλα λόγια, ο $rs περιέχει τη διεύθυνση προορισμού, δηλαδή έναν pointer στην επόμενη προς εκτέλεση εντολή). Η εντολή αυτή μας επιτρέπει να μεταφέρουμε τον έλεγχο (την εκτέλεση του προγράμματος) σε αυθαίρετη θέση μνήμης, η οποία μπορεί και να ποικίλει κατά την εκτέλεση του προγράμματος (run-time variable) και πιθανόν να εξαρτάται και από τα δεδομένα (data dependent). Χρησιμοποιείται γιά επιστροφή από διαδικασία, όπως είπαμε παραπάνω, γιά μετάφραση του switch statement, όπως περιγράφεται στις σελίδες 129-130 του βιβλίου, και γιά μεταφορά του ελέγχου οσοδήποτε μακριά, όπως αναφέρεται στη σελίδα 150 του βιβλίου (κάτω).

Τίνος Ευθύνη είναι το Σώσιμο των Καταχωρητών:

Οταν διάφορες διαδικασίες χρησιμοποιούν τον ίδιο καταχωρητή γιά διαφορετικούς σκοπούς η καθεμία, σε τρόπο που να καταστρέφεται η προηγούμενη τιμή του καταχωρητή --την οποία όμως δεν θέλουμε να χάσουμε, τότε καποιος πρέπει να "σώσει" (αντιγράψει) την προηγούμενη τιμή σε ασφαλές μέρος (στη μνήμη) και αργότερα να την επαναφέρει στον καταχωρητή. Γιά να ελαχιστοποιηθεί το κόστος αυτής της εργασίας (δηλαδή το πόσο συχνά πρέπει αυτή να γίνεται), οι compilers του MIPS ακολουθούν τις παρακάτω συμβάσεις. (Οι συμβάσεις αυτές είναι αρκούντως συντηρητικές ώστε να επιτρέπουν χωριστή μετάφραση (separate compilation) των διαδικασιών). Εστω ότι μιά διαδικασία Α καλεί μιάν άλλη διαδικασία Β (ή η ενεργοποίηση (instance) Α μιάς αναδρομικής διαδικασίας καλεί την ενεργοποίηση Β του εαυτού της). Θα ονομάζουμε την:

Προσωρινοί Καταχωρητές $t0 - $t9 ($8-$15 και $24-$25): Η τιμή των καταχωρητών αυτών δεν διατηρείται μετά από ένα κάλεσμα διαδικασίας (not preserved across call), δηλαδή η καλούμενη διαδικασία (ή άλλες που τυχόν καλιούνται από αυτήν) επιτρέπεται να μεταβάλει την τιμή αυτών των καταχωρητών χωρίς προηγουμένως να σώσει την τιμή που τυχόν είχε μείνει εκεί από την καλούσα διαδικασία, επομένως και χωρίς να επαναφέρει την παλαιά εκείνη τιμή προ της επιστροφής στην καλούσα διαδικασία. Αρα, αν η καλούσα διαδικασία έχει κάτι χρήσιμο μέσα σε έναν τέτοιο καταχωρητή ενώ ετοιμάζεται να καλέσει μιάν άλλη διαδικασία, το οποίο χρήσιμο επιθυμεί να το ξαναβρεί στη θέση του μετά την επιστροφή του καλέσματος, είναι ευθύνη της καλούσας διαδικασίας να σώσει την χρήσιμη τιμή πριν το κάλεσμα ("caller-saved"), και να την επαναφέρει αμέσως μετά από αυτό (δηλ. μετά την επιστροφή του). Προσωρινές τιμές των οποίων η διάρκεια ζωής (lifetime) δεν περιλαμβάνει καλέσματα διαδικασιών συμφέρει να τοποθετούνται σε τέτοιους καταχωρητές, διότι δεν χρειάζεται να σώσουμε τα παλαιά περιεχόμενα (από αυτόν που μας κάλεσε) αυτών των καταχωρητών πριν τους χρησιμοποιήσουμε.

Διατηρούμενοι Καταχωρητές $s0 - $s7 ($16-$23): Η τιμή των καταχωρητών αυτών διατηρείται μετά από ένα κάλεσμα διαδικασίας (preserved across call), δηλαδή είναι ευθύνη της καλούμενης διαδικασίας να σώσει την παλαιά τιμή κάθε τέτοιου καταχωρητή πριν την χαλάσει (callee-saved"), και να την επαναφέρει στη θέση της πριν επιστρέψει στην καλούσα διαδικασία. Αρα, η καλούσα διαδικασία μπορεί να αφήνει χρήσιμες τιμές σε αυτούς τους καταχωρητές, πριν καλέσει άλλες διαδικασίες, και να τις ξαναβρίσκει μετά την επιστροφή από αυτές, χωρίς να χρειάζεται --η καλούσα διαδικασία-- να κάνει κάτι ιδιαίτερο γι' αυτό. Μεταβλητές και τιμές των οποίων η διάρκεια ζωής (lifetime) περιλαμβάνει πολλά καλέσματα διαδικασιών, με επανειλημμένη χρήση της παλαιάς τιμής τους μεταξύ των καλεσμάτων, συμφέρει να τοποθετούνται σε τέτοιους καταχωρητές, διότι, αν οι καλούμενες διαδικασίες (και οι τυχόν δικοί τους απόγονοι) δεν χρησιμοποιούν αυτούς τους καταχωρητές, γλιτώνουμε τα πολλαπλά σωσίματα και επαναφορές (σώζουμε και επαναφέρουμε μόνο μία φορά την τιμή που είχε αφήσει εκεί η διαδικασία που κάλεσε εμάς τους ίδιους).

Αλλοι Καταχωρητές:

Πού Σώζονται οι Καταχωρητές. Αν οι διαδικασίες δεν ήταν αναδρομικές, δηλαδή αν απαγορεύονταν να καλέσει μιά διαδικασία τον εαυτό της --είτε άμεσα είτε έμμεσα μέσω άλλων που αυτή καλεί, τότε θα αρκούσε μιά συγκεκριμένη περιοχή στη μνήμη γιά κάθε διαδικασία, όπου αυτή να φυλάει τις τιμές των καταχωρητών που πρέπει να σώσει και αργότερα να επαναφέρει. Ομως, οι σημερινές γλώσσες προγραμματισμού επιτρέπεουν την αναδρομή (επανενεργοποιούμενες διαδικασίες, re-entrant procedures), κι έτσι μιά τέτοια λύση δεν θα δούλευε. Δεδομένου ότι τα κλέσματα και οι επιστροφές διαδικασιών λειτουργούν με τρόπο "last in first out" (LIFO), η φυσική δομή δεδομένων γιά δυναμική παραχώρηση και απελευθέρωση μνήμης στις διαδικασίες και από τις διαδικασίες είναι η στοίβα (stack).

Η στοίβα (χρήστη) στον MIPS ξεκινάει από τη διεύθυνση 7f.ff.ff.ff (δεκαεξαδικό), δηλαδή από τη μέση της μνήμης, και μεγαλώνει προς τις μικρότερες διευθύνσεις (προς τη διεύθυνση 0). Ο $sp δείχνει στην τελευταία χρησιμοποιούμενη λέξη της στοίβας. Πριν αποθηκεύσουμε Ν νέες λέξεις στη στοίβα πρέπει να ελαττώσουμε τον $sp κατά 4Ν, πράγμα που ισοδυναμεί με την δήλωση από πλευράς του προγράμματός μας (προς το λειτουργικό σύστημα, σε περίπτωση διακοπής (interrupt)) ότι τώρα η στοίβα μας είναι μεγλύτερη κατά Ν λέξεις. Η αντίστροφη πράξη (αύξηση του $sp κατά 4Ν --απελευθέρωση μνήμης) πρέπει να γίνει αφού πάρουμε τις αποθηκευμένες λέξεις και δεν τις χρειαζόμαστε άλλο πιά στη στοίβα. Οι τιμές που βρίσκονται αποθηκευμένες στη στοίβα προσπελάυνονται συνήθως μέσω εντολών load και store με διευθυνσιοδότηση σχετικά με τον $sp. Καθώς ο $sp αυξομειώνεται λόγω παραχώρησης/απελευθέρωσης μνήμης, η απόσταση των αποθηκευμένων τιμών στη στοίβα από τον $sp αλλάζει, αλλά παραμένει πάντοτε γνωστή στον compiler/προγραμματιστή (εκτός των περιπτώσεων δυναμικής παραχώρησης μνήμης στη στοίβα --πράγμα σπάνιο στις γλώσσες προγραμματισμού-- οπότε και απαιτείται η χρήση του $fp).

Ασκηση 4: Αναδρομική Διαδικασία Fibonacci

Γράψτε σε Assembly του MIPS και τρέξτε στο προσομοιωτή SPIM μιά αναδρομική διαδικασία η οποία θα υλοποιεί τη συνάρτηση του Fibonacci:

f(n) = f(n-1) + f(n-2)
με αρχικές τιμές: f(0)=0, και f(1)=1. Γιά αρνητικούς αριθμούς, neg<0, η συνάρτηση f(neg)=-1.

Το κυρίως πρόγραμμά σας θα είναι ένας άπειρος βρόχος ο οποίος θα αρχικοποιεί τις γενικές (global) μεταβλητές, θα ζητά και θα διαβάζει έναν ακέραιο αριθμό n, θα καλεί τη διαδικασία f(n), θα τυπώνει το αποτέλεσμα που αυτή επέστρεψε --καθώς και το συνολικό πλήθος των λέξεων που "σώθηκαν" στη στοίβα (βλ. παρακάτω)-- και μετά θα ξαναρχίζει πάλι από την αρχή.

Το πρόγραμμά σας θα διατηρεί τρείς γενικές (global) μεταβλητές: το αρχικό n που δόθηκε από το χρήστη, το παρόν βάθος της αναδρομής, και το συνολικό πλήθος των λέξεων που "σώθηκαν" στη στοίβα. Το παρόν βάθος της αναδρομής είναι 0 μέσα στην ενεργοποίηση της f(n) που καλέστηκε από το κυρίως πρόγραμμα, είναι 1 μέσα στις ενεργοποιήσεις f(n-1) και f(n-2) που αυτή καλεί, κ.ο.κ. Το πλήθος των λέξεων που σώθηκαν στη στοίβα μετράει όλες τις λέξεις που οι ενεργοποιήσεις της διαδικασίας σας γράφουν στη στοίβα με σκοπό να τις επαναφέρουν αργότερα (περιλαμβανόμενης και της διεύθυνσης επιστροφής). Κάθε λέξη που αποθηκεύετε τη μετράτε μία φορά, όταν την αποθηκεύετε --δεν την ξαναμετράτε όταν την επαναφέρετε. Κρατήστε τις τρείς αυτές γενικές μεταβλητές σε τρείς κατάλληλους καταχωρητές (σύμφωνα με τις παραπάνω συμβάσεις χρήσης των καταχωρητών --αν και συνήθως οι compilers αποφεύγουν να κρατούν γενικές μεταβλητές σε καταχωρητές) --προσοχή: τις γενικές μεταβλητές δεν τις σώζουμε στη στοίβα, ούτε επαναφέρουμε ποτέ παλαιές τιμές τους....

Γράψτε την αναδρομική διαδικασία σας σεβόμενοι τις παραπάνω συμβάσεις χρήσης των καταχωρητών, δηλαδή χωρίς να εκμεταλλεύεστε το γεγονός ότι ξέρετε το εσωτερικό της καλούμενης διαδικασίας. Οργανώστε τη στοίβα σας όπως φαίνεται στο σχήμα 3.10 του βιβλίου (σελ. 135) --αλλά προφανώς αποθηκεύοντας μόνο όσους καταχωρητές πρέπει να αποθηκεύσετε βάσει των παραπάνω συμβάσεων-- ή όπως στο σχήμα 3.12 (σελ. 139) αλλά χωρίς τον $fp. Προσπαθείστε να ελαττώστε το συνολικό πλήθος των λέξεων που σώζονται στη στοίβα γιά δεδομένη τιμή του n --πειραματιστείτε λίγο με διαφορετικές μορφές του κώδικα γιά να δείτε πώς αυτό επηρεάζεται. Μην κάνετε βελτιστοποιήσεις που εκμεταλλεύονται γνωστές τιμές της f(i) γιά μικρά i: κάθε ενεργοποίηση της f(i) γιά i>1 θα κάνει δύο καλέσματα, στις f(i-1) και f(i-2) παρά το γεγονός ότι ενδέχεται τα f(i-2) ή/και f(i-1) να είναι τα γνωστά f(0) ή f(1). (Επίσης, μην βάλετε την f(i) να επιστρέφει και την τιμή f(i-1) που τυχαίνει να έχει επίσης ζητήσει/υπολογίσει...).

Στην αρχή της αναδρομικής διαδικασίας σας, αφού κάνετε αριθμητικούς ελέγχους στο όρισμα σας αλλά πριν καλέσετε άλλη ενεργοποίηση της διαδικασίας, και μόνον εάν πρόκειται να καλέσετε άλλη τέτοια ενεργοποίηση, θα τυπώνετε ένα string της μορφής "    enter f(5)\n", όπου το πλήθος των κενών χαρακτήρων (spaces) στην αρχή της γραμμής ισούται με το παρόν βάθος της αναδρομής (απο τη σχετική γενική μεταβλητή), ο δε αριθμός μέσα στις παρενθέσεις είναι το παρόν όρισμα με το οποίο μας καλέσανε.

Παραδώστε, όπως και στις προηγούμενες ασκήσεις, τον κώδικά σας και ένα στιγμιότυπο της εκτέλεσής του στον SPIM, πακεταρισμένα στο αρχείο "ask4.tar.gz", μέσω: 

        tar -cvf ask4.tar askisi4.s snapshot4.jpg
        gzip ask4.tar
        ~hy225/bin/submit 4

Up to the Home Page of CS-225
 		 © copyright University of Crete, Greece.
Last updated: 27 Feb. 2001, by M. Katevenis.