| ΗΥ-225: Οργάνωση Υπολογιστών
Άνοιξη 2015 |
Τμ. Επ. Υπολογιστών © Πανεπιστήμιο Κρήτης |
|
[Up - Table of Contents] [Prev - 4. Instruction Formats] |
[printer version - PDF] [6. Procedure Call - Next] |
Βιβλίο: Διαβάστε την §2.7, σελίδες 145-151, καθώς και τις σελίδες 171-175.
Οι εντολές μεταφοράς ελέγχου (CTI, control transfer instructions) καθορίζουν να εκτελεστεί σαν επόμενη εντολή --πάντοτε ή υπό ορισμένες συνθήκες μόνο-- μια έντολη άλλη από την "επόμενη από κάτω" τους εντολή. Όταν η μεταφορά ελέγχου γίνεται υπό συνθήκη, οι εντολές συνήθως ονομάζονται διακλαδώσεις (branch). Όταν η μεταφορά γίνεται πάντοτε, οι εντολές συνήθως λέγονται άλματα (jump). Επίσης υπάρχουν καλέσματα διαδικασιών, λειτουργικού συστήματος, και επιστροφές από αυτά.
Στη γλώσσα Assembly, η διεύθυνση προορισμού της διακλάδωσης δηλώνεται απλά με μια ετικέτα (label), και αναλαμβάνει ο Assembler να υπολογίσει και να βάλει τη σωστή δυαδική τιμή. Στη γλώσσα μηχανής, οι εντολές διακλάδωσης ακολουθούν το I-format, και η διεύθυνση προορισμού προκύπτει ως εξής:
όπου 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).
Στον MIPS, η συνθήκη διακλάδωσης μπορεί να έχει περιορισμένες μόνο μορφές, γιά λόγους ταχύτητας. Οι μόνες συνθήκες διακλαδώσεων που υπάρχουν αφορούν συγκρίσεις ενός καταχωρητή με το μηδέν (δεν θα ασχοληθούμε με αυτές στο "δικό μας" υποσύνολο του MIPS), και συγκρίσεις δύο καταχωρητών μόνο γιά ισότητα ή ανισότητα και όχι γιά άλλων μορφών σχέσεις (μικρότερος, μεγαλύτερος, κλπ). Οι εντολές αυτές είναι:
Οι υπόλοιπες μορφές συγκρίσεων, που δεν γίνονται μέσα στις εντολές διακλάδωσης, υλοποιούνται με ειδικές, ξεχωριστές, αριθμητικές εντολές σύγκρισης. Πρόκειται γιά εντολές ανάλογες προς την πρόσθεση ή την αφαίρεση, μόνο που το αποτέλεσμά τους είναι τύπου Boolean αντί τύπου ακέραιος. Τέτοια αποτελέσματα τύπου Boolean έχουν δύο μόνο δυνατές τιμές: 0 γιά ψευδές, και 1 γιά αληθές. Τα αποτελέσματα αυτά γράφονται στους γνωστούς μας, κανονικούς (32μπιτους) καταχωρητές, σαν οι ακέραιοι 0 ή 1, δηλαδή στο LS bit του καταχωρητή, με όλα τα υπόλοιπα bits του καταχωρητή μηδενικά. Οι εντολές σύγκρισης που εμείς θα έχουμε στο δικό μας υποσύνολο του MIPS είναι οι παρακάτω δύο (αυτές κάνουν σύγκριση προσημασμένων - ο πραγματικός MIPS έχει κι άλλες, που κάνουν σύγκριση μη προσημασμένων, αλλά εμείς δεν θα ασχοληθούμε με εκείνες):
Εκτός από τις εντολές διακλάδωσης υπό συνθήκη, το υποσύνολο εντολών του MIPS που χρησιμοποιούμε στο μάθημα περιλαμβάνει και τις παρακάτω άλλες εντολές μεταφοράς ελέγχου:
Γιά το switch statement, όπως περιγράφεται στη σελίδα 150 του βιβλίου, η βασική ιδέα είναι η εξής: ο κώδικας της κάθε περίπτωσης (case) γράφεται σε κάποια περιοχή μνήμης, και ο compiler θυμάται σε ποιά διεύθυνση αρχίζει αυτός ο κώδικας, γιά την καθεμία περίπτωση. Στη συνέχεια, ο compiler κατασκευάζει έναν πίνακα (array), τον "jump table", ο οποίος περιέχει σε κάθε θέση του αυτές τις διευθύνσεις όπου αρχίζει ο κώδικας της κάθε περίπτωσης, με τη σειρά, γιά όλες τις (αριθμητικές) τιμές της κάθε περίπτωσης. Όταν είναι να εκτελεστεί το switch statement, παίρνουμε την τιμή της μεταβλητής του switch (αυτήν της οποίας την κάθε περίπτωση τιμών εξετάζουμε), και χρησιμοποιούμε αυτή την τιμή σαν index στον jump table, γιά να επιλέξουμε ένα από τα περιεχόμενα του jump table --αυτό που αντιστοιχεί στην περίπτωση της τωρινής τιμής της μεταβλητής του switch. Το στοιχείο του πίνακα που διαλέξαμε είναι η διεύθυνση του κώδικα που πρέπει να εκτελεστεί γιά την περίπτωση της μεταβλητής που τώρα μας ήλθε. Αυτό ακριβώς το στοιχείο του jump table το φέρνουμε σε έναν καταχωρητή $r, και στη συνέχεια εκτελούμε την εντολή jr $r, η οποία κάνει ώστε η επόμενη εντολή που θα εκτελεστεί να είναι εκεί που δείχνει ο $r, δηλαδή εκεί που μας είπε ο jump table να πάμε γιά την περίπτωση της τιμής που τώρα είχε η μεταβλητή.
Είπαμε ότι, γιά λόγους ταχύτητας, οι μόνες συνθήκες διακλάδωσης του MIPS που αφορούν δύο αυθαίρετους αριθμούς (όχι έναν αριθμό και το μηδέν) είναι συγκρίσεις ισότητας/ανισότητας και όχι συγκρίσεις μεγαλύτερος/μικρότερος. Ομως, επίσης, οι εντολές αυτές (beq, bne) υπάρχουν μόνο στη μορφή που δέχεται δύο καταχωρητές σαν τελεστέους, και δεν μπορούν να συγκρίνουν καταχωρητή με σταθερή ποσότητα (immediate). Ο λόγος δεν μπορεί να έχει να κάνει με ταχύτητα, αφού η σύγκριση ισότητας/ανισότητας καταχωρητή-σταθεράς είναι τουλάχιστο το ίδιο γρήγορη με την αντίστοιχη σύγκριση δύο καταχωρητών. Γιατί λοιπόν πιστεύετε ότι δεν υπάρχουν τέτοιες εντολές "beqi" και "bnei" στον MIPS; Δώστε την απάντησή σας γραπτά και εξηγήστε.
Έστω ότι η μεταβλητή i βρίσκεται στον καταχωρητή $12, η μεταβλητή j στον καταχωρητή $13, και ότι CONST σημαίνει μια αυθαίρετη προσημασμένη σταθερή ποσότητα μέχρι και 16 bits. Συνθέστε τις παρακάτω περιπτώσεις κώδικα χρησιμοποιώντας αποκλειστικά και μόνο εντολές μεταξύ των:
Στην παράγραφο 2.7 του βιβλίου, σελ. 147, υπάρχει ένας βρόχος μεταφρασμένος σε Assembly. Θεωρήστε την εξής μικρή παραλλαγή του βρόχου αυτού που ψάχνει σε έναν πίνακα (ακεραίων) table[] μέχρι να βρεί μία επιθυμητή τιμή value (που ξέρουμε ότι υπάρχει στον πίνακα):
Ας υποθέσουμε ότι η μεταβλητή i βρίσκεται στον καταχωρητή $s3, η τιμή value, βρίσκεται στον καταχωρητή $s5, και ότι ο καταχωρητής $s6 περιέχει τη διεύθυνση του στοιχείου table[0], δηλαδή τη διεύθυνση βάσης του πίνακα. Τότε, ο βρόχος αυτός, όπως υπάρχει στο βιβλίο, είναι ως εξής, όπου η εντολή sll είναι η "shift left logical", δηλαδή αριστερή ολίσθηση, εδώ κατά 2 θέσεις (bits), δηλαδή πολλαπλασιασμός επί 4:
add $s3, $0, $0 # i=0;
Loop: sll $t1, $s3, 2 # t1 = 4 * i
add $t1, $t1, $s6 # t1 = διεύθυνση του table[i]
lw $t0, 0($t1) # t0 = table[i]
beq $t0, $s5, Exit # if table[i] == value goto Exit
addi $s3, $s3, 1 # i = i+1
j Loop # επανάληψη: goto Loop
Exit: .... # υπόλοιπο πρόγραμμα
Παρατηρήστε τώρα ότι σε κάθε ανακύκλωση αυτού του βρόχου
εκτελούνται τόσο μια διακλάδωση υπό συνθήκη (branch),
όσο και ένα άλμα χωρίς συνθήκη (jump).
Όμως, μόνον οι εξαιρετικά απλοϊκοί μεταφραστές
θα έφτιαχναν τέτοιο κώδικα
--οι συνηθισμένοι μεταφραστές παράγουν κώδικα
που τρέχει πιο γρήγορα στη συνηθισμένη περίπτωση.
Η συνηθισμένη περίπτωση είναι ο βρόχος να επαναλαμβάνεται
αρκετές φορές πριν βγούμε από αυτόν
--γύρω στις 10 φορές κατά μέσον όρο, λένε οι στατιστικές.
Ξαναγράψτε το βρόχο σε Assembly, ούτως ώστε μόνο ένα branch ή jump να εκτελείται σε κάθε ανακύκλωση. Κατά την είσοδο ή την έξοδο από το βρόχο επιτρέπεται να εκτελούνται δύο εντολές μεταφοράς ελέγχου --αυτό που μας ενδιαφέρει είναι να γλυτώνουμε τη μια από αυτές κατά τις υπόλοιπες επαναλήψεις του βρόχου, που αποτελούν και την πλειοψηφία των φορών που αυτός εκτελείται. Έστω ότι ο βρόχος εκτελείται 10 φορές. Πόσες εντολές συνολικά εκτελούνταν με τον παλαιό κώδικα, και πόσες συνολικά με τον νέο;
Τρόπος Παράδοσης:
Παραδώστε μαζί την προηγούμενη άσκηση 4 και αυτήν εδώ τη σειρά 5,
on-line, σε μορφή PDF (μόνον)
(μπορεί να είναι κείμενο μηχανογραφημένο ή/και "σκαναρισμένο" χειρόγραφο,
αλλά μόνον σε μορφή PDF).
Παραδώστε μέσω turnin ex045@hy225 [directoryName]
ένα αρχείο ονόματι ex045.pdf
που θα περιέχει τις απαντήσεις σας σε όλες τις ασκήσεις, 4 και 5.