Κ15
– Αρχιτεκτονική Υπολογιστών Ι
Τμήμα
Πληροφορικής και Τηλεπικοινωνιών
Εθνικό
και Καποδιστριακό Πανεπιστήμιο Αθηνών
Ενδεικτικά Ερωτήματα για το
Τελικό Διαγώνισμα
Ανδρέας Μόσχοβος
Υλοποίηση Επεξεργαστή Πολλαπλών Κύκλων ανα Εντολή
Θέλουμε να υλοποιήσουμε μια νέα
εντολή lwu (load word update). Η εντολή συντάσεται ως εξής:
lwu R1, Imm16(R2)
όπου R1 και R2 δύο καταχωρητές και Imm16 μια προσημασμένη σταθερά των 16 bit. Υποθέστε πως οι R1 και R2 είναι πάντα διαφορετικοί. Η lwu αντιστοιχεί στην παρακάτω
ακολουθία εντολών:
lw R1, Imm16(R2)
addi R2, R2, Imm16
α) Δείξτε τα βήματα τα
οποία πρέπει να ακολουθηθούν για την εκτέλέση της εντολής lwu. Τα βήματα π.χ. που υλοποιούν την εντολή load είναι:
1. IR = MEM[PC]; PC = PC + 4
2. A = Reg[IR[25-21]]; B= Reg[IR[20-16]]; AluOut = PC +
sign-extend (IR[15-0] << 2)
3. AluOut = A + sign-extend(IR[15-0])
4. MDR = Mem[AluOut]
5. Reg[IR[20-16]]
= MDR
BHMATA:
1.
______________________________________________________
2.
______________________________________________________
3.
______________________________________________________
4.
______________________________________________________
5.
______________________________________________________
6.
______________________________________________________
7.
______________________________________________________
β) Στο διάγραμμα που ακολουθεί σημείωστε τις απαραίτητες αλλαγές στο datapath. Εξηγήστε συνοπτικά τις αλλαγές αυτές.
1) (30 Points) Ακολουθούν προγράμματα
γλώσσας μηχανής σε διαφορετικές, υποθετικές αρχιτεκτονικές. Καθένα από τα
προγράμματα χρησιμοποιεί τις τιμές στις διευθύνσεις μνήμης A, B, C και D και υπολογίζει μια συνάρτηση που τελικά αποθηκεύεται στη διεύθυνση μνήμης
Ε. Περιγράψτε τη συνάρτηση που υπολογίζεται κάθε φορά, π.χ. Ε = (A+B) * C + D.
α) Αρχιτεκτονική μηχανισμού
σωρού:
PUSH A
PUSH B
MUL
PUSH C
PUSH D
ADD
SUB
POP E
E =
____________________________________________
β) Αρχιτεκτονική συσσωρευτή:
LOAD B
ADD A
SUB C
STORE E
E =
____________________________________________
γ) Αρχιτεκτονική καταχωρητή-μνήμης:
LOAD R1, A
SUB R1, B
ADD R1, C
STORE R1, E
ADD R1, E
STORE
E, R1
E =
____________________________________________
2)
Η παρακάτω ρουτίνα δέχεται δύο παραμέτρους, συμβολικά Α
και Β. Οι παράμετροι είναι διευθύνσεις στη μνήμη λέξεων που τερματίζονται με το
0 (όπως τα strings της γλώσσας C). Η ρουτίνα αντιγράφει τη
λέξη Α στη λέξη Β. Ως έχει ο κώδικας έχει προβλήματα.
Σημειώστε (με Χ στην στήλη «λαθος») τις γραμμές
κώδικα που παρουσίαζουν πρόβλημα και εξηγήστε συνοπτικά γιατί στο χώρο δίπλα σε κάθε γραμμή. Π.χ., «χρησιμοποιείται ο $s8 αντί
του $s2».
|
Λάθος |
Εντολή |
Γιατί |
|
|
mega: subu $sp, $sp,
3 |
|
|
|
sw $s0,
0($sp) |
|
|
|
|
|
|
|
sb $s1,
0($a1) |
|
|
|
addu $a0,
$a0, 2 |
|
|
|
bne $s0,
$0, |
|
|
|
addu $sp,
$sp, 3 |
|
|
|
jr $a3 |
|
Οργάνωση
και λειτουργία Κρυφών Μνημών:
α) Έστω μια κρυφή μνήμη
χωρητικότητας 2M λέξεων (2 x 220 bytes). Κάθε πλαίσιο
(block) αποτελείται από 128 λέξεις (bytes).
Τέλος, στον συγκεκριμένο
υπολογιστή υπάρχουν 16G (16 x
230) λέξεις (bytes) στη μνήμη.
i.
Πόσα bits απαιτούνται για τον
προσδιορισμό των διευθύνσεων μνήμης; ______
ii.
Πόσα πλαίσια υπάρχουν στην κρυφή μνήμη;
____________________________
iii.
Πόσα δυαδικά ψηφία (bits) χρησιμοποιούνται αντίστοιχα για τα πεδία ΕΤΙΚΕΤΤΑ (TAG), ΔΙΕΥΘΥΝΣΗ ΤΟΥ ΠΛΑΙΣΙΟΥ ΣΤΗΝ ΚΡΥΦΗ ΜΝΗΜΗ (SET) και ΔΙΕΥΘΥΝΣΗ ΜΕΣΑ ΣΤΟ ΠΛΑΙΣΙΟ (OFFSET) όταν η κρυφή μνήμη είναι άμεσης οργάνωσης (direct mapped);
TAG
________ SET
________ OFFSET _________
iv.
Πόσα δυαδικά ψηφία (bits) χρησιμοποιούνται αντίστοιχα για τα πεδία ΕΤΙΚΕΤΤΑ (TAG), ΣΥΝΟΛΟ (SET) και και ΔΙΕΥΘΥΝΣΗ ΜΕΣΑ
ΣΤΟ ΠΛΑΙΣΙΟ (OFFSET) όταν η οργάνωση της κρυφής
μνήμης 16-τρόπων συνόλου συσχέτισης (8-way set associative);
TAG ________ SET ________ OFFSET
_________
Χρόνος
εκτέλεσης:
Έστω
δύο υλοποιήσεις τις αρχιτεκτονικής MIPS. Στην υλοποίηση Α όλες οι
εντολές εκτελούνται σε έναν (αργό) κύκλο. Στην υλοποίηση Β οι εντολές load εκτελούνται
σε 5 κύκλους, οι εντολές branch σε 3, και οι υπόλοιπες εντολές σε 4. Υποθέστε πως όλες οι ψευτοεντολές αντιστοιχούν
σε δύο εντολες MIPS.
Υπολογίστε πόσοι κύκλοι θα χρειαστούν για την εκτέλεση της παρακάτω
ακολουθίας εντολών Υποθέστε πως η
διεύθυνση PINA είναι
διαιρέσιμες με το 32Κ (32768). Εκφράστε
τον αριθμό κύκλων ως συνάρτηση της σταθεράς N
(πρώτη εντολή).
α)
li $t0, N
la $a0, PINA
li
$t2, 0
brox:
lw
$t3, 0($a0)
addu
$t2, $t2, $t3
subu
$t0, $t0, 4
addu
$a0, $a0, 4
bgt
$t0, $0, brox
Υλοποίηση Α =
_____________________________________________
Υλοποίηση Β = _____________________________________________
Εξηγήστε συνοπτικά τις απαντήσεις σας.
β) Έστω κρυφή μνήμη άμεσης
οργάνωσης (direct mapped) χωρητικότητας 16Κ bytes με blocks των 32 bytes. Οι εντολές load εκτελούνται σε 5 ή 200 κύκλους ανάλογα με το
αν βρίσκουν αυτό που θέλουν στη κρυφή μνήμη ή όχι αντίστοιχα. Πόσοι κύκλοι θα
χρειαστούν για την εκτέλεση του κώδικα τους ερωτήματος Α.
Υλοποίηση Β =
_______________________________________________
Εξηγήστε συνοπτικά την απάντηση σας.
Υλοποιήστε την παρακάτω ρουτίνα C σε γλώσσα μηχανής MIPS.
int
koko (int
a, int b)
{
int i;
for (i
= 0; i < 16; i++)
{
if ( b & (1 << (16 – i))) a |= (i << 1);
}
}
Σημειώνεται πως (a
& b) ειναι το λογικό και (AND), (α | β) το λογικό ή (OR) και
το (α << β) είναι ολίσθηση του α προς τα αριστερά κατά β bits.
7) ΚΩΔΙΚΟΠΟΙΗΣΗ ΕΝΤΟΛΩΝ
‘Εστω αρχιτεκτονική με 16 καταχωρητές
γενικού σκοπού των 16 bit ο καθένας. Έστω πως το εύρος των διευθύνσεων είναι
65536 bytes. Έστω
πως υπάρχουν τουλάχιστον 13 εντολές. Οι εντολές είναι παρόμοιες με αυτές του MIPS. Οι εντολές που κάνουν πράξεις μεταξύ καταχωρητών
έχουν τη μορφή «εντολή R1, R2» όπου το R1 και R2 είναι καταχωρητές.
Οι εντολές αυτές υπολογίζουν το R1 = R1 χ R2 όπου
χ μια πράξη. Η προσπέλαση μνήμης γίνεται μέσω των
εντολών load και
store που
είναι ανάλογες αυτών του MIPS. Π.χ.
η load έχει
τη μορφή «load
R1, σταθερά(R2)». Αντίστοιχα υπάρχουν
εντολές ελέγχου ροής της μορφής «εντολή R1, σταθερά» οι οποίες συγκρίνουν
τα περιεχόμενα του R1 με το μηδέν και ανάλογα αλλάζουν τη ροή του
προγράμματος (PC
= PC + (σταθερα
<< 1)).
Αν όλες
οι εντολές πρέπει να κωδικοποιηθούν σε 16 bit προτείνεται μια πιθανή
κωδικοποίηση τους. Δείξτε τα σχετικά πεδία και εξηγήστε πως χρησιμοποιούνται
για την περιγραφή των τριών κατηγοριών εντολών: πράξεις, προσπέλαση μνήμης και
έλεγχος ροής. Για τα πεδία σταθερών χρησιμοποιήστε το μέγιστο αριθμό bit.
8) Έστω κρυφή μνήμη άμεσης οργάνωσης συνολικής χωρητικότητας 16Κ λέξεων (bytes), με πλαίσια των 8 λέξεων και που χρησιμοποιεί τις τακτικές «τελικής ενημέρωσης» (write-back) και «προσκόμισης κατά την εγγραφή» (write-allocate). Έστω ότι απαιτείται 1 κύκλος για την προσπέλαση της κρυφής μνήμης. Αν τα δεδομένα δε βρεθούν στην κρυφή μνήμη απαιτούνται επιπλέον 16 κύκλοι για την προσπέλαση της κύριας μνήμης και την ανάκτηση ολόκληρου του μπλοκ μνήμης στο οποίο ανήκει η ζητούμενη διεύθυνση. Οπότε μια προσπέλαση που δε βρίσκει τα δεδομένα που ζητά στην κρυφή μνήμη χρειάζεται τουλάχιστον (16 + 1) κύκλους για να ολοκληρωθεί είτε πρόκειται για ανάγνωση είτε για εγγραφή. Στην περίπτωση αποβολής (αντικατάστασης) ενός μπλοκ από τη κρυφή μνήμη και εφόσον χρειάζεται απαιτούνται επιπλέον 16 κύκλοι για την ενημέρωση της κύριας μνήμης. Υπολογίστε τον συνολικό αριθμό κύκλων που απαιτούνται για την ολοκλήρωση των παρακάτω ακολουθιών προσπέλασης διευθύνσεων λέξεων μνήμης. Υποθέστε πως οι προσπελάσεις εξυπηρετούνται από το σύστημα μνήμης ξεχωριστά η μία μετά την άλλη. Σε καθένα από τα υποερωτήματα θεωρήστε πως αρχικά η κρυφή μνήμη είναι άδεια. Εξηγείστε αναλυτικά τους υπολογισμούς σας.
α) Ακολουθία διευθύνσεων και τύπου προσπέλασης:
Ανάγνωση: 0,1,2,3…,16382,16383. Σημείωση: 16383 = 16K - 1
β) Η ακολουθία του υποερωτήματος (α) επαναλαμβανόμενη 10 φορές, δηλαδή:
0,1,2,...,16383,0,1,2,...,16383,...,0,1,2...,16383.
γ) Ανάγνωση 0,1,2,...,65535.
δ) Εγγραφή 0,1,2,...,32767,
Ανάγνωση 32768,32769,...,65535.