Περίληψη ορισμένων Θεμάτων Προσπελάσεων Μνήμης στον MIPS

Αντιγραφή μιάς 32-μπιτης λέξης από τη μνήμη σ' ένα καταχωρητή ("φόρτωμα στον καταχωρητή") γίνεται με την εντολή "lw $rd, imm($rx)" (load word), όπου $rd είναι ο καταχωρητής προορισμού, και $rx είναι ένας καταχωρητής που περιέχει μιά διεύθυνση μνήμης στην οποία προστίθεται ο σταθερός αριθμός imm και το αποτέλεσμα της πρόσθεσης είναι η τελική διεύθυνση μνήμης απ' όπου γίνεται η αντιγραφή στον $rd. Αντίστροφα, αντιγραφή από τον καταχωρητή $rs στη θέση μνήμης με διεύθυνση imm+$rx ("M[imm+$rx]"), δηλαδή "αποθήκευση", γίνεται με την εντολή "sw $rs, imm($rx)" (store word).

Οι διευθύνσεις μνήμης στον MIPS, όπως και σχεδόν σε όλους τους μοντέρνους επεξεργαστές, αναφέρονται σε Bytes στη μνήμη, δηλαδή ο MIPS είναι "Byte Addressable". Ετσι, μιά 32-μπιτη λέξη (π.χ. ένας ακέραιος) καταλαμβάνει 4 "θέσεις μνήμης" (4 bytes). Κατά συνέπεια, ένας πίνακας (array) μεγέθους 100 ακεραίων "πιάνει" 400 (συνεχόμενες) διευθύνσεις (θέσεις) στη μνήμη. Σ' ένα τέτοιο πίνακα, η διεύθυνση του κάθε ακέραιου διαφέρει από αυτήν του διπλανού του κατά 4. Εαν A0 είναι η διεύθυνση του "πρώτου" (μηδενικού) στοιχείου, a[0], ενός πίνακα ακεραίων της C, τότε το στοιχείο a[i] του πίνακα αυτού θα βρίσκεται στη διεύθυνση A0+4*i. Αν ο πίνακας αυτός ήταν πίνακας χαρακτήρων (char), τότε το στοιχείο a[i] θα ήταν στη διεύθυνση A0+i.

Τα 4 bytes που αποτελούν έναν ακέραιο έχουν διευθύνσεις που είναι συνεχόμενοι αριθμοί. Διεύθυνση του ακεραίου είναι η διεύθυνση εκείνου από τα 4 bytes του που έχει τη μικρότερη ("πρώτη") από τις 4 διευθύνσεις. Ο MIPS επιβάλει περιορισμούς ευθυγράμμισης (alignment) στις ποσότητες που προσπελαύνουν οι εντολές load και store στη μνήμη: μία ποσότητα μεγέθους N bytes επιβάλεται να έχει διεύθυνση που είναι ακέραιο πολλαπλάσιο του N. Ετσι, όταν το N είναι δύναμη του 2, η διεύθυνση κάθε τέτοιας ποσότητας τελειώνει σ' ένα αντίστοιχο πλήθος μηδενικών, και η διεύθυνση των υπολοίπων bytes της ποσότητας διαφέρει μόνο σε αυτά τα λιγότερο σημαντικά (least significant) bits. Λόγω αυτού του περιορισμού, όταν η φυσική μνήμη έχει πλάτος N bytes, αρκεί μία μόνο προσπέλαση σε αυτήν γιά κάθε πρόσβαση σε ποσότητα μεγέθους N bytes.

Μέσα σ' έναν ακέραιο αριθμό, τα bits εκείνα που πολλαπλασιάζονται επί τις μεγαλύτερες δυνάμεις του 2 γιά να μας δώσουν την αριθμητική τιμή του ακεραίου λέγονται "περισσότερο σημαντικά" (MS - most significant) bits, και αυτά που πολλαπλασιάζονται επί τις μικρότερες δυνάμεις του 2 λέγονται "λιγότερο σημαντικά" (LS - least significant) bits. Το byte που περιέχει τα MS bits λέγεται MS byte, και εκείνο που περιέχει τα LS bits λέγεται LS byte. Όποτε σχεδιάζουμε έναν ακέραιο στο χαρτί, οριζόντια, θα βάζουμε πάντα τα MS bits και byte αριστερά, και τα LS bits και byte δεξιά, δηλαδή όπως και στους δεκαδικούς αριθμούς (αυτό αφορά μόνο τους ανθρώπους, και όχι τους υπολογιστές...).

• Big-Endian: Σε πολλούς υπολογιστές, το MS byte του κάθε ακεραίου έχει τη μικρότερη διεύθυνση, και οι διευθύνσεις των bytes του αυξάνουν (προχωρούν) καθώς προχωράμε "δεξιά", προς το LS byte του. Αυτοί οι υπολογιστές λέγονται "big-endian" διότι η αρίθμιση των bytes τους ξεκινά από το "big end", δηλαδή το MS byte τους.
• Little-Endian: Σε άλλους υπολογιστές, το LS byte του κάθε ακεραίου έχει τη μικρότερη διεύθυνση, και οι διευθύνσεις των bytes του αυξάνουν (προχωρούν) καθώς προχωράμε "αριστερά", προς το MS byte του. Αυτοί οι υπολογιστές λέγονται "little-endian" διότι η αρίθμιση των bytes τους ξεκινά από το "little end", δηλαδή το LS byte τους.

Ασκηση 2.1: Πίνακας Ακεραίων

• Ξεκινήστε με όσα μάθατε στην πρώτη σειρά ασκήσεων, αλλά εδώ θα χρειαστεί να χρησιμοποιήσετε και τις νέες εντολές προσπέλασης ακεραίων στη μνήμη "lw" και "sw".
• Χρησιμοποιήστε τις οδηγίες ".data", ".align", και ".space" του Assembler του SPIM (σελίδες A-51, A-52 του παραρτήματος του βιβλίου) γιά να κρατήστε χώρο στη μνήμη δεδομένων (data segment) γιά τον πίνακα "a[ ]" μεγέθους 10 ακεραίων. Τοποθετήστε κατάλληλα το label "a" ώστε να μπορείτε πιό κάτω να αναφερθείτε στη διεύθυνση όπου αρχίζει ο χώρος που κρατήσατε.
• Στην αρχή του προγράμματός σας, τοποθετήστε τη διεύθυνση όπου αρχίζει ο πίνακας a[ ] σε έναν καταχωρητή. Τη διεύθυνση αυτή την ξέρει ο Assembler, αλλά εσείς πιθανότατα όχι (εκτός αν την είχατε δώσει σαν argument στην οδηγία .data). Επίσης, δεν ξέρετε αν η διεύθυνση αυτή χωρά σε 16 bits (ένα immediate) ή όχι. Σε όλα αυτά έρχεται να σας βοηθήσει η ψεύδοεντολή (pseudoinstruction) "la $rDest, label" του Assembler του SPIM: αυτή λέει στον Assembler να γεννήσει μία ή δύο πραγματικές εντολές που τοποθετούν την πραγματική διεύθυνση του label στον $rDest (μία εντολή αν η διεύθυνση χωρά σε 16 bits, δύο εντολές αλλοιώς). Παράδειγμα χρήσης της ψευδοεντολής "la" θα βρείτε στην πρώτη σειρά ασκήσεων, εκεί που ετοιμάζαμε τα ορίσματα γιά τις εκτυπώσεις strings.
• Στη συνέχεια, τυπώστε ένα prompt που να ζητά 10 ακεραίους σε 10 γραμμές.
• Μετά, μπείτε σ' ένα βρόγχο που θα επαναληφθεί 10 φορές, και που κάθε φορά θα διαβάζει έναν αριθμό (μέσω καλέσματος συστήματος) και θα τον αποθηκεύει στην επόμενη θέση του πίνακα a[ ]. Επισημάνσεις: (i) Οι εντολές "beq" και "bne" γιά τη δημιουργία του βρόγχου δέχονται μόνο καταχωρητές σαν τελεστέους, και όχι σταθερές ποσότητες (immediates). (ii) Η μοναδική διευθυνσιοδότηση (addressing mode) του MIPS είναι "σταθερή ποσότητα (immediate) + καταχωρητής" --μην χρησιμοποιήστε τις ψεύδοδιευθυνσιοδοτήσεις του SPIM (σελίδες A-49 έως A-51).
• Αφού βγείτε από τον προηγούμενο βρόγχο, τυπώστε μιά διαχωριστική γραμμή, και μπείτε σ'έναν άλλο βρόγχο, που θα επαναληφθεί και αυτός 10 φορές, και που θα επισκεφθεί τα στοιχεία του πίνακα "a[ ]" αλλά κατ' αντίστροφη σειρά. Γιά κάθε στοιχείο, θα το διαβάζει από τη μνήμη, θα το διπλασιάζει (χωρίς να πειράξει την τιμή στη μνήμη), και θα τυπώνει αυτό το διπλάσιο, στην ίδια γραμμή αλλά όχι "κολλητά" με το προηγούμενό του.
• Τέλος, ξαναγυρίστε στην αρχή (όπως και στην πρώτη σειρά ασκήσεων), ώστε η ίδια δουλειά να επαναλαμβάνεται επ' αόριστο.

Ασκηση 2.2: Υπολογιστές Big-Endian και Little-Endian

1. Χρησιμοποιήστε τον SPIM γιά να βρείτε τον δυαδικό (δεκαεξαδικό) κώδικα εσωτερικής αναπαράστασης (κώδικα ASCII) των χαρακτήρων του Λατινικού αλφαβήτου, a, b, ..., z, A, ..., Z, και των αριθμητικών χαρακτήρων, 0, 1, ..., 9. Γιά να το πετύχετε, ορίστε σταθερές τύπου string όπως στην πρώτη σειρά ασκήσεων, και στη συνέχεια μπείτε στον SPIM και μελετήστε τα περιεχόμενα της μνήμης δεδομένων στο παράθυρο "Data Segments". Δώστε τις διαπιστώσεις σας σ' έναν πίνακα σε χαρτί, με 3 στήλες: χαρακτήρας, κώδικας ASCII στο δεκαεξαδικό, κώδικας ASCII στο δυαδικό.
2. Εστω ότι αποθηκεύουμε το null-terminated string "abc" σε μία λέξη ενός 32-μπιτου υπολογιστή, και στη συνέχεια διαβάζουμε αυτή τη λέξη σαν να είναι (32-μπιτος) ακέραιος. Υπολογίστε με αριθμητικές πράξεις ποιόν ακέραιο θα διαβάσουμε (α) σε μιά μηχανή big-endian, και (β) σε μιά μηχανή little-endian. Δώστε την απάντησή σας, μαζί με τις αριθμητικές πράξεις που κάνατε, σε χαρτί (στο δεκαδικό).
3. Επαληθεύστε την απάντησή σας μ' ένα μικρό πρόγραμμα στον SPIM: Ζητήστε από τον Assembler να βάλει το string στη μνήμη δεδομένων, και μέσα από το πρόγραμμά σας αντιγράψτε εκείνη τη λέξη (ολόκληρη!) σ' ένα καταχωρητή και ζητήστε να τυπωθεί (μ' ένα κάλεσμα συστήματος) σαν ακέραιος. Ο SPIM συμπεριφέρεται σαν big-endian ή σαν little-endian ανάλογα σε ποιόν υπολογιστή τρέχει! Σε τι υπολογιστή τον τρέξατε τον SPIM; Τι έβγαλε; Αν τον τρέξτε σε άλλο τύπο υπολογιστή, με επεξεργαστή άλλης εταιρείας, θα βγάλει άλλα; Παραδώστε το πρόγραμμά σας (πηγαίος κώδικας) και τα συμπεράσματά σας σε χαρτί.