ΗΥ-225: Οργάνωση Υπολογιστών
Άνοιξη 2021 |
Τμ. Επ. Υπολογιστών © Πανεπιστήμιο Κρήτης |
[Up - Table of Contents] [Prev - 6. Procedure Call] |
[printer version - PDF] [8. Single-Cycle Processor - Next] |
Γράψτε και τρέξτε στον RARS, σε Assembly του RISC-V, ένα πρόγραμμα που πρώτα θα κατασκευάζει και θα γεμίζει με θετικούς ακέραιους αριθμούς μία συνδεδεμένη λίστα (linked list), και στη συνέχεια θα την σαρώνει επαναληπτικά, τυπώνοντας κάθε φορά ένα διαφορετικό υποσύνολο των στοιχείων της –συγκεκριμένα: όσα στοιχεία της είναι μεγαλύτερα από δοθείσα τιμή. Το πρόγραμμά σας θα κρατάει στον καταχωρητή s0 (x8) τον pointer στην αρχή (στον πρώτο κόμβο) της λίστας, και θα αποτελείται από δύο κομμάτια, 7.4 και 7.5 –βλ. αμέσως παρακάτω. Στη συνέχεια, βασικά κομμάτια του προγράμματός σας θα τα κάνετε διαδικασίες (procedures), όπως περιγράφει η §7.6. Μερικές από τις διαδικασίες θα είναι υπερβολικά μικρές, αλλά αυτό γίνεται γιά λόγους εξάσκησης, ούτως ώστε το βάθος καλεσμάτων να φτάνει 2 επίπεδα κάτω από την main. (Σημείωση γιά την επιστροφή από διαδικασία: την ψευδοεντολή jr, που γιά επιστροφή από διαδικασία κανονικά είναι "jr ra", ο RARS δεν την δέχεται έτσι, αλλά απαιτεί να εμφανίζεται και το Immediate Offset, οπότε πρέπει να την δίνετε ως: "jr ra, 0").
Χρησιμοποιήστε τον καταχωρητή s1 (x9) σαν pointer στην ουρά (στον τελευταίο κόμβο) της λίστας. Γιά διευκόλυνση του βρόχου κατασκευής της λίστας (επειδή η εισαγωγή σε κενή λίστα διαφέρει από την εισαγωγή σε μη κενή λίστα), αρχικοποιήστε τη λίστα να περιέχει ένα αδιάφορο ("dummy") κόμβο: ένα κόμβο με data=0. Η αρχικοποίηση γίνεται ζητώντας και παίρνοντας ένα κόμβο από το περιβάλλον (λειτουργικό σύστημα), γράφοντας data=0 και nxtPtr=0 (τελευταίος κόμβος) σε αυτόν, και κάνοντας τους s0 και s1 να δείχνουν σε αυτόν τον κόμβο (να περιέχουν τη διεύθυνσή του). Μετά, μπείτε στο βρόχο ανάγνωσης στοιχείων και κατασκευής της λίστας. Σε κάθε ανακύκλωση αυτού του βρόχου:
Το δεύτερο μέρος του προγράμματος θα διαβάζει έναν μη αρνητικό αριθμό, και θα τυπώνει, με τη σειρά από την αρχή μέχρι το τέλος, όσα στοιχεία της λίστας είναι μεγαλύτερα από αυτόν τον αριθμό. (Αφού ο αριθμός είναι ≥0, και τυπώνουμε τα στοιχεία που είναι μεγαλύτερα από αυτόν, προκύπτει ότι ο κόμβος "dummy", που έχει data=0, δεν θα τυπώνεται ποτέ· παρατηρήστε ότι όταν δίδεται το 0 ως αριθμός σύγκρισης, θα τυπώνονται όλα τα στοιχεία της λίστας (που είναι πάντα όλα θετικά), εκτός του "dummy"). Μην χρησιμοποιήστε τον pointer στον τελευταίο κόμβο της λίστας (από την παλαιά τιμή του καταχωρητή s1 (x9)) γιά να βρίσκετε πού τελειώνει η λίστα –χρησιμοποιήστε τον nxtPtr κάθε κόμβου γιά να ξέρετε αν υπάρχει ή όχι επόμενος κόμβος στη λίστα. Το μέρος αυτό του προγράμματος κάνει τα εξής:
Τρόπος Παράδοσης:
Παραδώστε ηλεκτρονικά τον κώδικά σας, "ex07.asm",
κι ένα στιγμιότυπο της εκτέλεσής του στον RARS,
"ex07.jpg".
Παραδώστε τα αυτά μέσω:
turnin ex07@hy225 [directoryName]
Θα εξεταστείτε και προφορικά για την Άσκηση 7,
με διαδικασία γιά την οποία θα ενημερωθείτε
μέσω ηλτά (email) στη λίστα του μαθήματος.
Έστω ο προσημασμένος ακέραιος As,k με k bits, τον οποίο θέλουμε να μετατρέψουμε στον ίδιο αριθμό As,n με n bits: As,n = As,k όπου n>k. Εάν τα bits του As,k τα ερμηνεύσουμε σαν μη προσημασμένο (unsigned) ακέραιο, τότε θα μοιάζουν με (θα δηλώνουν) έναν αριθμό που ας το ονομάσουμε Au,k και ομοίως εάν τα bits του As,n τα ερμηνεύσουμε σαν unsigned τότε θα μοιάζουν με τον Au,n . Εάν ο As,k = As,n είναι μη αρνητικός (δηλ. θετικός ή μηδέν), τότε, κατά τον ορισμό της κωδικοποίησης συμπληρώματος ως-προς-2, (α) το αριστερό bit τους θα είναι μηδέν, και (β) οι απρόσημες ερμηνίες τους θα είναι: Au,k = As,k και Au,n = As,n , και αφού As,n = As,k τότε θα είναι και: Au,n = Au,k. Αυτοί οι δύο τελευταίοι, αφού είνα unsigned ακέραιοι, με n και k bits αντίστοιχα, και είναι ίσοι μεταξύ τους, προκύπτει ότι ο Au,n που έχει περισσότερα bits θα είναι ίδιος με τον Au,k αλλά με n-k μηδενικά προστεθημένα αριστερά από τον Au,k .
Αλλιώς, εάν οι As,n = As,k είναι αρνητικοί, τότε, κατά τον ορισμό μας, (α) το αριστερό bit τους θα είναι ένα, και (β) οι απρόσημες ερμηνίες τους θα είναι: Au,k = As,k + 2k και Au,n = As,n + 2n . Δεδομένου ότι: As,n = As,k προκύπτει ότι θα είναι και: Au,n - 2n = Au,k - 2k . Επομένως, η αναπαράσταση που ψάχνουμε είναι η: Au,n = Au,k - 2k + 2n = Au,k + (2n - 2k) = (2n-k - 1) · 2k + Au,k . Σε αυτήν την τελευταία έκφραση, ο μεν αριστερός προσθετέος, (2n-k - 1) · 2k, αποτελείται από (n-k) το πλήθος άσσους (που είναι ο αριθμός 2n-k - 1) ολισθημένους αριστερά κατά k θέσεις bits (που είναι ο πολλαπλασιασμός επί 2k), ο δε δεξιός προσθετέος, Au,k , είναι τα αρχικά k bits του αρχικού αριθμού που μας δόθηκε. Δεδομένου ότι ο πρώτος προσθετέος έχει όλο μηδενικά στις k δεξιές θέσεις, ο δε δεύτερος προσθετέος έχει όλο μηδενικά στις (n-k) αριστερές θέσεις, το άθροισμά τους θα είναι προφανώς απλώς η "συγκόλληση" (concatenation) των δύο αυτών ποσοτήτων. Επομένως, η αναπαράσταση με n bits του αρχικού αριθμού που μας δόθηκε θα αποτελείται από τα αρχικά k bits, δεξιά, μαζί με (n-k) άσσους κολλημένους ακριβώς αριστερά τους.
Συνολικά λοιπόν, γιά να μετατρέψουμε ένα προσημασμένο (signed) ακέραιο από k (λιγότερα) bits σε n (περισσότερα) bits, δεν έχουμε παρά να κάνουμε το εξής: Τοποθετούμε αριστερά από τα bits που μας δόθηκαν (n-k) επιπλέον bits τα οποία είναι όλα τους αντίγραφα του αριστερού (most significant) bit του αριθμού που μας δόθηκε, δηλαδή αντίγραφα του bit που υποδεικνύει το πρόσημο του δοθέντος αριθμού (0 γιά θετικούς ή το μηδεν, 1 γιά αρνητικούς). Η πράξη αυτή ονομάζεται επομένως, προφανώς, επέκταση προσήμου (sign extension).
Στη συνήθη χρήση της ακολουθείται από μιάν εντολή addi (add immediate), η οποία προσθέτει στον ίδιο καταχωρητή το 12-μπιτο Immediate της. Δεδομένου ότι η lui έβαλε 12 μηδενικά δεξιά στον καταχωρητή, η πρόσθεση καταλήγει στο να αφήσει στα 12 δεξιά bits τη σταθερή ποσότητα από την εντολή addi. Στον 32-μπιτο RISC-V, στα 20 αριστερά bits του καταχωρητή, η μεν εντολή lui έβαλε την 20-μπιτη σταθερά της, η δε εντολή addi προσθέτει σε αυτήν είτε (α) 20 μηδενικά εάν η (12-μπιτη) σταθερά της έχει 0 στο αριστερό bit της, είτε (β) 20 άσους εάν η (12-μπιτη) σταθερά της έχει 1 στο αριστερό bit της. Στη μεν περίπτωση (α) τα 20 μηδενικά αφήνουν αναλοίωτα τα 20 αριστερά bits, στη δε περίπτωση (β) η πρόσθεση 20 άσων ισοδυναμεί με την πρόσθεση του αριθμού -1 (μείον 1) σε αυτά τα 20 bits. Έτσι τελικά μπορούμε να συνθέσουμε την οιαδήποτε αυθαίρετη 32-μπιτη σταθερά, βάζοντας τα μεν 12 δεξιά bits της στο Immediate της addi, τα δε 20 αριστερά bits της, είτε αυτούσια είτε αυξημένα κατά +1, στο Immediate της lui – όπου η επιλογή "αυτούσια" ή "αυξημένα κατά +1" γίνεται όταν τα 12ο από δεξιά bit είναι 0 ή 1, αντίστοιχα. Στο βιβλίο η εντολή αυτή, καθώς και η τυπική χρήση της, περιγράφονται στην αρχή της §2.10.
Επίσης ο RISC-V προσφέρει υποστήριξη γιά Relocatable Code, δηλαδή κώδικα Assermbly/Object τον οποίο μπορεί εύκολα ο Linker να αλλάξει (ή ακόμα και να μην χρειάζεται καμία αλλαγή) προκειμένου να τον συνενώνει (link) με άλλον κώδικα, τοποθετώντας (φορτώνοντάς) τον σε αυθαίρετη θέση στη μνήμη (δηλαδή να τον κάνει rellocate), όπως π.χ. χρειάζεται γιά τη δυναμική συνένωση διαδικασιών βιβλιοθήκης (dynamically linked libraries - §2.12, pp. 130-132 Αγγλικού βιβλίου). Το βασικό addressing mode (τρόπος δημιουργίας διευθύνσεων μνήμης) γιά σκοπούς εύκολου relocation είναι το PC-relative: όταν μιά διεύθυνση μνήμης εκφράζεται σαν σχετική απόσταση από την τιμή του PC της εντολής που την γεννά, τότε αυτή η απόσταση δεν αλλάζει κατά το relocation. Γιά τις διακλαδώσεις υπό συνθήκη, η διεύθυνση προορισμού δίδεται πάντα σαν PC-relative όπως έχουμε δεί, με βεληνεκές ±4 KBytes. Το ίδιο ισχύει και γιά το κάλεσμα διαδικασίας (jal), καθώς και γιά το απλό άλμα (jump) του συντίθεται ως ψευδοεντολή μέσω αυτού, με βεληνεκές ±1 MByte. Ο RISC-V προσφέρει μία ακόμα εντολή, την auipc (add upper immediate to PC), προκειμένου (α) να επεκτείνει το κάλεσμα/άλμα σε οιαδήποτε αυθαίρετη 32-μπιτη απόσταση, και (β) να προσφέρει επίσης PC-relative addressing, και μάλιστα με αυθαίρετη 32-μπιτη απόσταση, γιά εντολές load και store δεδομένων, ως εξής.
Η εντολή auipc rd, Imm20 (add upper immediate to PC), με format επίσης "U" όπως και η lui, πρώτα κατασκευάζει την ίδια σταθερή ποσότητα όπως και η lui, και στη συνέχεια προσθέτει αυτή τη σταθερή ποσότητα στην τιμή του PC της και γράφει το αποτέλεσμα της πρόσθεσης στον καταχωρητή rd· με άλλα λόγια, είναι σαν να κάνει: lui rd, Imm20 και αμέσως μετά να κάνει: rd ← PC+rd. Ή αλλιώς μπορούμε να πούμε ότι η auipc rd, Imm20 κάνει: rd ← PC + (sign-extended)Imm20×212. Όπως και η lui, η auipc μπορεί να χρησιμοποιηθεί σαν η πρώτη εντολή σε ένα ζευγάρι εντολών με δεύτερη εντολή είτε ένα κάλεσμα/άλμα είτε μία load/store, γιά να προκαλέσει κάλεσμα/άλμα ή προσπέλαση δεδομένων PC-relative στη διεύθυνση PC+Const32, όπου Const32 είναι μιά αυθαίρετη 32-μπιτη σταθερά αποτελούμενη από δύο κομάτια, HI τα 20 αριστερά bits, και LO τα 12 δεξιά bits, ως εξής. Η πρώτη εντολή του ζεύγους κατασκευάζει την τιμή PC+ΗΙ×212 και την τοποθετεί σ' έναν προσωρινό καταχωρητή, π.χ. τον t0: auipc t0, HI (ή auipc t0, HI+1 εάν το κομάτι LO αρχίζει με 1, όπως σχολιάζαμε παραπάνω και γιά την lui). Η δεύτερη εντολή του ζεύγους είναι είτε jalr γιά κάλεσμα/άλμα είτε load/store, όπου και στις δύο περιπτώσεις χρησιμοποιείται σαν pointer ο προηγούμενος καταχωρητής t0, και σαν Offset τα δεξιά 12 bits της Const32, το LO, άρα τελικά η διεύθυνση είναι η PC+ΗΙ×212+LO = PC+Const32: