Περίληψη Θεμάτων Γλώσσας Μηχανής του MIPS:

Εσωτερικά, ο υπολογιστής λειτουργεί μόνο με δυαδικές τιμές και σύμβολα. Ετσι, γιά να μπορέσει να εκτελεστεί ένα πρόγραμμα Assembly πρέπει να μεταφραστεί σε "Γλώσσα Μηχανής", δηλ. σε δυαδικά σύμβολα. Τη μετάφραση αυτή κάνει ένα πρόγραμμα, ο Assembler.

Ολες οι εντολές του MIPS, όπως και των άλλων υπολογιστών στυλ RISC, έχουν σταθερό μέγεθος 32 bits. Μέσα τους περιέχουν από 2 έως 6 πεδία (fields). Υπάρχουν 3 διαφορετικές μορφές που οι εντολές μπορεί να έχουν. Η μορφή (format) της κάθε εντολής καθορίζεται από το πρώτο πεδίο της εντολής, που ονομάζεται op, έχει μέγεθος 6 bits, και είναι πάντα στην ίδια θέση (MS bits) γιά όλες τις εντολές. Φυσικά, με τα 6 bits που έχει, το πεδίο αυτό καθορίζει, εκτός από το format της εντολής, και ένα μέρος ή και ολόκληρο το opcode της εντολής, δηλαδή το τι πράξη ή ενέργεια πρέπει να εκτελέσει αυτή η εντολή. Οι τρείς μορφές εντολών είναι:

R-format:

Αυτό φαίνεται στη σελίδα 118 του βιβλίου (επάνω), και αποτελείται, μετά το πεδίο op, από τρία πεδία των 5 bits καθένα που επιλέγουν έναν από τους 32 καταχωρητές καθένα, ένα πεδίο των 5 bits που δεν θα το χρησιμοποιήσουμε εμείς στο υποσύνολο των εντολών που θα μελετήσουμε, και ένα πεδίο μεγέθους 6 bits που αποτελεί επέκταση του op και λέγεται funct (function code).

I-format:

Αυτό φαίνεται στη σελίδα 118 του βιβλίου (κάτω), και αποτελείται, μετά το πεδίο op, από δύο πεδία των 5 bits καθένα που επιλέγουν έναν από τους 32 καταχωρητές καθένα, και ένα πεδίο μεγέθους 16 bits που λέγεται imm (immediate, ή offset, ή constant, ή address) και που περιέχει μία "άμεση" σταθερή ποσότητα.

J-format:

Αυτό φαίνεται στη σελίδα 148 του βιβλίου (επάνω), και περίεχει, μετά το πεδίο op, ένα πεδίο "target" μεγέθους 26 bits που προσδιορίζει μεγάλο μέρος μιάς πλήρους διεύθυνσης μνήμης.

Ασκηση 3.1: Γλώσσα Μηχανής και Κώδικες Μεταβλητού Μήκους

Σ' αυτή την άσκηση θα μελετήσετε τον τρόπο που το format και το opcode στον MIPS καθορίζονται από τα πεδία op και funct με μιά κωδικοποίηση μεταβλητού μεγέθους. Γιά να μην παιδευόμαστε όμως με μεγάλο πλήθος εντολών, θα χρησιμοποιήσουμε ένα δικό μας, φανταστικό format εντολών, ενός φανταστικού υπολογιστή, του MIPS_8. Ολες οι εντολές του MIPS_8 έχουν μέγεθος 8 bits. Ο MIPS_8 έχει μόνο 8 καταχωρητές, τους $0, $1, ..., $7, και οι σταθερές του ποσότητες (immediates) μπορούν να είναι μόνο οι 32 μη-αρνητικοί ακέραιοι 0, 1, 2, ..., 31. Οι εντολές του MIPS_8 έχουμ μόνον έναν τελεστέο --είτε καταχωρητή, είτε σταθερή ποσότητα immediate-- και έχουν μόνο δύο format, τα εξής:

R-format:

• op (3 bits): πρώτο μέρος του opcode,
• R (3 bits): ο καταχωρητής - τελεστέος,
• funct (2 bits): δεύτερο μέρος του opcode.

I-format:

• op (3 bits): ο (μοναδικός) opcode,
• Imm (5 bits): η σταθερά - τελεστέος.

3.1.1: Εστω ότι "ξοδεύουμε" και τους οκτώ (8) διαθέσιμους συνδυασμούς του πεδίου op γιά 8 εντολές I-format, τις εντολές ai, bi, ci, di, ei, fi, gi, hi. Σ' αυτή την περίπτωση, μπορούμε να έχουμε καμία εντολή R-format; Γιατί όχι; Εστω πως επιμέναμε να έχουμε την εντολή R-format "BBB" με op=001 και funct=10. Τότε, η εντολή "BBB $5" με ποιάν άλλη εντολή I-format (και με τι τελεστέο) θα ήταν ίδια κι απαράλλακτη, με συνέπεια να μην μπορούμε να τις έχουμε και τις δύο στον MIPS_8; Αποδείξτε εν συντομία αλλά με "μαθηματική" ακρίβεια και σαφήνεια ότι το ίδιο θα ίσχυε γιά οιαδήποτε άλλη δυνατή εντολή R-format.

3.1.2: Εστω τώρα ότι "ξοδεύουμε" μόνο τους 7 από τους 8 διαθέσιμους συνδυασμούς του πεδίου op --τους 001, 010, 011, 100, 101, 110, 111-- γιά 7 εντολές I-format --τις bi, ci, di, ei, fi, gi, hi. Σ' αυτή την περίπτωση, πόσες εντολές R-format μπορούμε να έχουμε; Τι κώδικες op και funct θα έχει καθεμιά τους; Γιατί δεν μπορούμε να έχουμε περισσότερες από τόσες εντολές R-format;

3.1.3: Γιά την περίπτωση 3.1.2, σχεδιάστε ένα συνδυαστικό κύκλωμα, χρησιμοποιώντας πύλες AND, OR, NOT, που να δέχεται σαν εισόδους τα 8 bits μιάς εντολής και να παράγει σαν εξόδους:

• ένα σήμα I που ανάβει όταν και μόνον όταν η εντολή είναι I-format,
• ένα σήμα R που ανάβει όταν και μόνον όταν η εντολή είναι R-format,
• 7 σήματα, ένα γιά καθε εντολή I-format, που να ανάβει όταν και μόνον όταν βλέπει τη συγκεκριμένη εντολή, και
• ένα σήμα γιά καθε εντολή R-format, που να ανάβει όταν και μόνον όταν βλέπει τη συγκεκριμένη εντολή.

3.1.4: Ανάλογη ερώτηση με την 3.1.2, αλλά έστω ότι τώρα έχουμε μόνο 6 εντολές I-format. Πόσες εντολές R-format μπορούμε να έχουμε; Γράψτε τα opcodes όλων των εντολών, και των δύο format. Προσπαθήστε να επιλέξτε τα opcodes έτσι ώστε να απλοποιείται η αποκωδικοποίηση των σημάτων I και R (κατ' αναλογία προς την ερώτηση 3.1.3). Δώστε όλες τις απαντήσεις σας σε χαρτί.

 

Περίληψη Θεμάτων Συγκρίσεων και Διακλαδώσεων στον MIPS

Οι εντολές μεταφοράς ελέγχου (CTI, control transfer instructions) καθορίζουν να εκτελεστεί σαν επόμενη εντολή --πάντοτε ή υπό ορισμένες συνθήκες μόνο-- μιά έντολη άλλη από την "επόμενη από κάτω" τους εντολή. Οταν η μεταφορά ελέγχου γίνεται υπό συνθήκη, οι εντολές συνήθως ονομάζονται διακλαδώσεις (branch). Οταν η μεταφορά γίνεται πάντοτε, οι εντολές συνήθως λέγονται άλματα (jump). Επίσης υπάρχουν καλέσματα διαδικασιών, λειτουργικού συστήματος, και επιστροφές από αυτά.

Στον MIPS, η συνθήκη διακλάδωσης μπορεί να έχει περιορισμένες μόνο μορφές, γιά λόγους ταχύτητας. Οι μόνες συνθήκες διακλαδώσεων που υπάρχουν αφορούν συγκρίσεις ενός καταχωρητή με το μηδέν (δεν θα ασχοληθούμε με αυτές στο "δικό μας" υποσύνολο του MIPS), και συγκρίσεις δύο καταχωρητών μόνο γιά ισότητα ή ανισότητα και όχι γιά άλλων μορφών σχέσεις (μικρότερος, μεγαλύτερος, κλπ). Οι εντολές αυτές είναι:

• beq $rs, $rt, label   # διακλάδωση εάν $rs == $rt
• bne $rs, $rt, label   # διακλάδωση εάν $rs != $rt

Οι υπόλοιπες μορφές συγκρίσεων, που δεν γίνονται μέσα στις εντολές διακλάδωσης, υλοποιούνται με ειδικές, ξεχωριστές, αριθμητικές εντολές σύγκρισης. Πρόκειται γιά εντολές ανάλογες προς την πρόσθεση ή την αφαίρεση, μόνο που το αποτέλεσμά τους είναι τύπου Boolean αντί τύπου ακέραιος. Τέτοια αποτελέσματα τύπου Boolean έχουν δύο μόνο δυνατές τιμές: 0 γιά ψευδές, και 1 γιά αληθές. Τα αποτελέσματα αυτά γράφονται στους γνωστούς μας, κανονικούς (32μπιτους) καταχωρητές, σαν οι ακέραιοι 0 ή 1, δηλαδή στο LS bit του καταχωρητή, με όλα τα υπόλοιπα bits του καταχωρητή μηδενικά. Οι εντολές σύγκρισης που εμείς θα έχουμε στο δικό μας υποσύνολο του MIPS είναι οι:

• slt  $rd, $rs, $rt  # set less than --αριθμητική σύγκριση των καταχωρητών: $rs < $rt. Το αποτέλεσμα, τύπου Boolean, γράφεται στον καταχωρητή $rd.
• slti $rd, $rs, imm  # set less than immediate --αριθμητική σύγκριση καταχωρητή και προσημασμένης (sign-extended) σταθερής ποσότητας imm: $rs < imm. Το αποτέλεσμα, τύπου Boolean, γράφεται στον καταχωρητή $rd.

Ασκηση 3.2: Διακλάδωση με Σύγκριση Καταχωρητή-Σταθεράς

Είπαμε ότι, γιά λόγους ταχύτητας, οι μόνες συνθήκες διακλάδωσης του MIPS που αφορούν δύο αυθαίρετους αριθμούς (όχι έναν αριθμό και το μηδέν) είναι συγκρίσεις ισότητας/ανισότητας και όχι συγκρίσεις μεγαλύτερος/μικρότερος. Ομως, επίσης, οι εντολές αυτές (beq, bne) υπάρχουν μόνο στη μορφή που δέχεται δύο καταχωρητές σαν τελεστέους, και δεν μπορούν να συγκρίνουν καταχωρητή με σταθερή ποσότητα (immediate). Ο λόγος δεν μπορεί να έχει να κάνει με ταχύτητα, αφού η σύγκριση ισότητας/ανισότητας καταχωρητή-σταθεράς είναι τουλάχιστο το ίδιο γρήγορη με την αντίστοιχη σύγκριση δύο καταχωρητών. Γιατί λοιπόν πιστεύετε ότι δεν υπάρχουν τέτοιες εντολές "beqi" και "bnei" στον MIPS; Δώστε την απάντησή σας σε χαρτί και εξηγήστε.

Ασκηση 3.3: Εντολές Σύγκρισης και Διακλάδωσης

Εστω ότι η μεταβλητή i βρίσκεται στον καταχωρητή $17, η μεταβλητή j στον καταχωρητή $21, και ότι CONST σημαίνει μια αυθαίρετη προσημασμένη σταθερή ποσότητα μέχρι και 16 bits. Συνθέστε τις παρακάτω περιπτώσεις κώδικα χρησιμοποιώντας αποκλειστικά και μόνο τις εντολές beq, bne, slt, slti, addi. Οπου χρειάζεστε προσωρινό καταχωρητή, χρησιμοποιήστε τον $at (Assembler temporary) ο οποίος είναι ο $1 (αυτόν χρησιμοποιεί ο Assembler γιά να συνθέτει τις ψευδοεντολές του). Δώστε τις απαντήσεις σας σε χαρτί. Υπόδειξη: παίξτε με τη σειρά που βάζετε τους 2 τελεστέους πηγής στην εντολή σύγκρισης, με τον καταχωρητή $0 που περιέχει πάντα μηδέν (ή "ψευδές"), με το είδος της διακλάδωσης (ίσο/άνισο ή ψευδές/αληθές), με τις σταθερές CONST, CONST+1, CONST-1, -CONST, και με τους (πολλούς) συνδυασμούς όλων αυτών. Θα εκτιμήστε το πόσα πολλά μπορεί να κάνει το software, εκμεταλλευόμενο λίγους, προσεκτικά επιλεγμένους δομικούς λίθους από πλευράς hardware, χωρίς απώλεια ταχύτητας!

1. if ( i == j ) goto L1; (ίσο)
2. if ( i != j ) goto L1; (διάφορο)
3. if ( i <  j ) goto L1; (μικρότερο)
4. if ( i <= j ) goto L1; (μικρότερο ή ίσο)
5. if ( i >  j ) goto L1; (μεγαλύτερο)
6. if ( i >= j ) goto L1; (μεγαλύτερο ή ίσο)
7. if ( i == CONST ) goto L1; (ίσο)
8. if ( i != CONST ) goto L1; (διάφορο)
9. if ( i <  CONST ) goto L1; (μικρότερο)
10. if ( i <= CONST ) goto L1; (μικρότερο ή ίσο)
11. if ( i >  CONST ) goto L1; (μεγαλύτερο)
12. if ( i >= CONST ) goto L1; (μεγαλύτερο ή ίσο)

Ασκηση 3.4: Μετάφραση Βρόχου "While"

Στην παράγραφο 3.5, είδαμε τον παρακάτω βρόχο μεταφρασμένο σε Assembly κατά τέτοιο τρόπο ώστε σε κάθε ανακύκλωση να εκτελείται τόσο μία διακλάδωση υπό συνθήκη (branch), όσο και ένα πήδημα χωρίς συνθήκη (jump).

          while (save[i] == k) {
              i = i+j;
          } 

Ασκηση 3.5: Κατασκευή και Σάρωση Συνδεδεμένης Λίστας

Γράψτε και τρέξτε στον SPIM, σε Assembly του MIPS, ένα πρόγραμμα που πρώτα θα κατασκευάζει και θα γεμίζει με θετικούς ακέραιους αριθμούς μία συνδεδεμένη λίστα (linked list), και στη συνέχεια θα την σαρώνει επαναληπτικά, τυπώνοντας κάθε φορά ένα διαφορετικό υποσύνολο των στοιχείων της --συγκεκριμένα: όσα στοιχεία της είναι μεγαλύτερα από δοθείσα τιμή.

Data Structures: Θα χρησιμοποιήσουμε μία δομή δεδομένων (structure) που θα αποτελεί έναν κόμβο της λίστας. Κάθε κόμβος (δομή δεδομένων) μας θα αποτελείται από δύο λέξεις (των 32 bits καθεμία): έναν ακέραιο "data" που θα περιέχει την "πληροφορία χρήστη", κι έναν δείκτη σύνδεσης (pointer) "nxtPtr" που θα περιέχει τη διεύθυνση του επόμενου κόμβου στη λίστα (στον τελευταίο κόμβο της λίστας, nxtPtr=0). Τα δύο στοιχεία (λέξεις) της δομής μας θα βρίσκονται σε διαδοχικές θέσεις (λέξεις) της μνήμης. Επομένως, κάθε δομή (κόμβος) μας θα έχει μέγεθος 2x4=8 bytes. Διεύθυνση μιάς δομής είναι η διεύθυνση του πρώτου στοιχείου της, δηλαδή του στοιχείου με "μηδενικό offset", που γιά μας είναι το "data". Αρα, το δεύτερο στοιχείο της δομής μας, ο "nxtPtr", βρίσκεται στη διεύθυνση που προκύπτει προσθέτοντας 4x1=4 στη διεύθυνση της δομής (κόμβου).

Dynamic Memory Allocation: Το πρόγραμμά σας θα ζητάει και θα παίρνει δομές (κόμβους) από το λειτουργικό σύστημα "δυναμικά", την ώρα που τρέχει (σε run-time). Γιά το σκοπό αυτό θα χρησιμοποιήστε το κάλεσμα συστήματος (system call) "sbrk" (set break). Το κάλεσμα αυτό "σπρώχνει" πιό πέρα (προς αύξουσες διευθύνσεις μνήμης) το σημείο "break", το όριο δηλαδή πριν από το οποίο οι διευθύνσεις μνήμης που γεννά το πρόγραμμα είναι νόμιμες, ενώ μετά από το οποίο (και μέχρι την αρχή της στοίβας) οι διευθύνσεις είναι παράνομες και τυχόν χρήση τους προκαλεί το γνωστό από την C "segmentation violation - core dumped". Το κάλεσμα συστήματος "sbrk" περιγράφεται στη σελίδα Α-49 του βιβλίου, και λειτουργεί κατ' αναλογία με τα άλλα καλέσματα συστήματος (εκτύπωσης και ανάγνωσης) που χρησιμοποιήσατε στις προηγούμενες ασκήσεις. Πριν το καλέσετε, θέτετε τον καταχωρητή $a0 ($4) να περιέχει το πλήθος των νέων bytes που επιθυμείτε (ένας αριθμός). Μετά την επιστροφή του, ο καταχωρητής $v0 ($2) περιέχει τη διεύθυνση του νέου block μνήμης, του ζητηθέντος μεγέθους, που το σύστημα δίνει στο πρόγραμμά σας (έναν pointer). Η επιστρεφόμενη διεύθυνση μνήμης είναι πάντα διάφορη του μηδενός (εκτός --πιθανότατα-- όταν γεμίσει όλη η μνήμη, αλλά δεν χρειάζεται εσείς εδώ να ελέγχετε κάτι τέτοιο), και είναι πάντα ευθυγραμμισμένη σε όρια λέξεων (πολλαπλάσιο του 4) (τουλάχιστο στη δική μας περίπτωση, που ζητάμε πάντα blocks μεγέθους πολλαπλάσιου του 4, αλλά --πιστεύω-- και σε κάθε περίπτωση).

Το πρόγραμμά σας θα κρατάει στον καταχωρητή $s0 (δηλαδή τον $16) τον pointer στην αρχή (στον πρώτο κόμβο) της λίστας, και θα αποτελείται από δύο κομμάτια:

3.5.1: Κατασκευή της Λίστας. Χρησιμοποιήστε τον καταχωρητή $s1 ($17) σαν pointer στην ουρά (στον τελευταίο κόμβο) της λίστας. Γιά διευκόλυνση του βρόχου κατασκευής της λίστας (επειδή η εισαγωγή σε κενή λίστα διαφέρει από την εισαγωγή σε μη κενή λίστα), αρχικοποιήστε τη λίστα να περιέχει ένα αδιάφορο ("dummy") κόμβο: ένα κόμβο με data=0 (αφού όλοι οι κόμβοι θα περιέχουν θετικούς αριθμούς, και αφού θα τυπώνουμε μόνο τις τιμές που θα είναι μεγαλύτερες από δοθέντα μη αρνητικό αριθμό, ο κόμβος αυτός ποτέ δεν θα τυπώνεται, κι έτσι θα είναι σαν να μην υπάρχει). Η αρχικοποίηση γίνεται ζητώντας και παίρνοντας ένα κόμβο από το λειτουργικό σύστημα, γράφοντας data=0 και nxtPtr=0 (τελευταίος κόμβος) σε αυτόν, και κάνοντας τους $s0 και $s1 να δείχνουν σε αυτόν τον κόμβο (να περιέχουν τη διεύθυνσή του). Μετά, μπείτε στο βρόχο ανάγνωσης στοιχείων και κατασκευής της λίστας. Σε κάθε ανακύκλωση αυτού του βρόχου:

• Διαβάζουμε έναν ακέραιο αριθμό από την κονσόλα.
• Εάν ο αριθμός αυτός είναι μηδέν, βγαίνουμε από το βρόχο.
• Ζητάμε έναν νέο κόμβο από το λειτουργικό σύστημα (memory allocation).
• Τοποθετούμε τον αριθμό που διαβάσαμε στο πεδίο "data" του κόμβου.
• Συνδέουμε το νέο κόμβο στην ουρά της λίστας.

3.5.2: Σάρωση της Λίστας. Το δεύτερο μέρος του προγράμματος θα διαβάζει έναν μη αρνητικό αριθμό, και θα τυπώνει, με τη σειρά από την αρχή μέχρι το τέλος, όσα στοιχεία της λίστας είναι μεγαλύτερα από αυτόν τον αριθμό. Μην χρησιμοποιήστε τον pointer στον τελευταίο κόμβο της λίστας (από την παλιά τιμή του καταχωρητή $s1 ($17)) γιά να βρίσκετε πού τελειώνει η λίστα --χρησιμοποιήστε τον nxtPtr κάθε κόμβου γιά να ξέρετε αν υπάρχει ή όχι επόμενος κόμβος στη λίστα. Το μέρος αυτό του προγράμματος κάνει τα εξής:

• Διαβάζει έναν ακέραιο αριθμό από την κονσόλα και τον φυλάει στον καταχωρητή $s1 ($17) (υποτίθεται ότι αυτός είναι μη αρνητικός αριθμός, αλλά δεν χρειάζεται εσείς να το ελέγχετε).
• Αρχικοποιεί τον καταχωρητή $s2 ($18) σαν δείκτη (pointer) σάρωσης, να δείχνει στον πρώτο κόμβο της λίστας (τον ξέρουμε από τον $s0 ($16)).
• Μπαίνει σ' ένα βρόχο, σε κάθε ανακύκλωση του οποίου: (α) ελέγχει αν τα "data" του κόμβου όπου δείχνει ο $s2 ($18) είναι ή όχι μεγαλύτερα από τον $s1 ($17), (β) αν είναι μεγαλύτερα τα τυπώνει, (γ) ελέγχει αν υπάρχει ή όχι επόμενος κόμβος στη λίστα, (δ) αν δεν υπάρχει βγαίνει από το βρόγχο, (ε) αν υπάρχει, προχωρεί τον $s2 ($18) να δείξει σε αυτόν τον επόμενο κόμβο και επιστρέφει στην αρχή του βρόχου.
• Μετά την έξοδο του βρόχου, επιστρέφει (πάντα) στην αρχή του δεύτερου μέρους του προγράμματος, γιά να ζητήσει μιά νέα τιμή και να ξανατυπώσει τα μεγαλύτερα από αυτή στοιχεία.

Τρόπος Παράδοσης των Ασκήσεων

        tar -cvf ask3.tar arxeio1 arxeio2 arxeio3
        gzip ask3.tar
        ~hy225/bin/submit 3