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

Γλώσσα Μηχανής, Διακλαδώσεις στον MIPS

Προθεσμία έως Τετάρτη 28 Φεβρουαρίου (βδομάδα 4)


Περίληψη Θεμάτων Γλώσσας Μηχανής του 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 που προσδιορίζει μεγάλο μέρος μιάς πλήρους διεύθυνσης μνήμης.
Οι εντολές του MIPS, το format τους, και τα opcodes τους φαίνονται στις σελίδες A-53 έως A-75 του παραρτήματος Α του βιβλίου. Ο τρόπος που το format και το opcode καθορίζονται από τα πεδία op και funct με μιά κωδικοποίηση μεταβλητού μεγέθους αποτελεί αντικείμενο της άσκησης 3.1.

Ασκηση 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:
I-format:

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 μιάς εντολής και να παράγει σαν εξόδους:

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), και συγκρίσεις δύο καταχωρητών μόνο γιά ισότητα ή ανισότητα και όχι γιά άλλων μορφών σχέσεις (μικρότερος, μεγαλύτερος, κλπ). Οι εντολές αυτές είναι:

Στη γλώσσα Assembly, η διεύθυνση προορισμού της διακλάδωσης δηλώνεται απλά με μία "ταμπέλα" (label), και αναλαμβάνει ο Assembler να υπολογίσει και να βάλει τη σωστή δυαδική τιμή. Στη γλώσσα μηχανής, οι εντολές διακλάδωσης ακολουθούν το I-format, και η διεύθυνση προορισμού προκύπτει ως εξής:
PC_new := (PC_br + 4) + 4 * ImmOffset
όπου PC_br είναι η διεύθυνση της ίδιας της εντολής διακλάδωσης, ImmOffset είναι η σταθερή ποσότητα των 16 bits του I-format θεωρούμενη ως προσημασμένος αριθμός σε συμπλήρωμα ως προς 2 (δηλαδή sign-extended), και PC_new είναι η διεύθυνση της εντολής προορισμού σε περίπτωση επιτυχίας της διακλάδωσης. Η αύξηση (PC_br+4) γίνεται γιά λόγους ευκολίας του hardware (όλες οι εντολές αυξάνουν τον PC κατά 4). Ο πολλαπλασιασμός του ImmOffset επί 4 γίνεται γιά να εκμεταλλευτούμε το γεγονός ότι η διεύθυνση όλων των εντολών του MIPS είναι ακέραιο πολλαπλάσιο του 4, κι έτσι να αυξήσουμε το "βεληνεκές" των διακλαδώσεων στο τετραπλάσιο --με άλλα λόγια, ο αριθμός ImmOffset μετράει πλήθος εντολών μπροστά (θετικός) ή πίσω (αρνητικός), αντί να μετρά πλήθος bytes μπροστά ή πίσω. (Σημείωση: στην πραγματικότητα, ο MIPS έχει "καθυστερημένες διακλαδώσεις" (delayed branches), γιά λόγους καλύτερης εκμετάλλευσης της ομοχειρίας (pipelining) του hardware, αλλά εμείς, σε αυτό το μάθημα, θα το αγνοήσουμε --ελάτε στο ΗΥ-425 γιά την πλήρη ιστορία).

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

Ασκηση 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;
          } 
Ομως, μόνον οι εξαιρετικά απλοϊκοί compilers θα έφτιαχναν τέτοιο κώδικα. Ξαναγράψτε το βρόχο σε Assembly, ούτως ώστε μόνο ένα branch ή jump να εκτελείται σε κάθε ανακύκλωση. Έστω ότι ο βρόχος εκτελείται 10 φορές. Πόσες εντολές συνολικά εκτελούνταν με τον παλαιό κώδικα, και πόσες συνολικά με τον νέο; Παραδώστε την απάντησή σας σε χαρτί.

Ασκηση 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 να δείχνουν σε αυτόν τον κόμβο (να περιέχουν τη διεύθυνσή του). Μετά, μπείτε στο βρόχο ανάγνωσης στοιχείων και κατασκευής της λίστας. Σε κάθε ανακύκλωση αυτού του βρόχου:

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

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

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

Τις ασκήσεις που ζητιόνται σε χαρτί μπορείτε να τις παραδώσετε είτε σε χαρτί στο μάθημα, είτε σε αρχείο κειμένου on-line μαζί με την άσκηση 3.5. Τα δύο αρχεία της άσκησης 3.5, συν όποιο άλλο αρχείο τυχόν παραδίδετε on-line, βάλτε τα στο αρχείο "ask3.tar.gz", και στη συνέχεια εκτελέστε, από το directory όπου βρίσκεται αυτό το αρχείο: "~hy225/bin/submit 3", δηλαδή συνολικά:
        tar -cvf ask3.tar arxeio1 arxeio2 arxeio3
        gzip ask3.tar
        ~hy225/bin/submit 3


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