Σύγχρονα Θέματα Αρχιτεκτονικής Υπολογιστών — Φεβρουάριος 2016¶
Μεταγραφή από το PDF 2016-2.pdf (θέματα εξέτασης 9ης Φεβρουαρίου 2016, με τις απαντήσεις όπως δίνονται στο αρχείο).
2016-2.pdf¶
Ονοματεπώνυμο:
Έτος:
ΑΜ:
ΑΡΧΙΤΕΚΤΟΝΙΚΗ ΥΠΟΛΟΓΙΣΤΩΝ IΙ¶
9-2-2016¶
ΘΕΜΑ 1. Θεωρήστε επεξεργαστή μερικώς επικαλυπτόμενων λειτουργιών (pipeline) με πέντε βαθμίδες. (2 μον.) α. Ποια είναι η μέγιστη τιμή της επιτάχυνσης του ρυθμού ολοκλήρωσης εντολών σε σχέση με αντίστοιχο επεξεργαστή που δεν υλοποιεί την τεχνική των μερικώς επικαλυπτόμενων λειτουργιών;
β. Να αναφέρετε τους λόγους για τους οποίους δεν μπορούμε να πετύχουμε αυτή την τιμή.
γ. Ποιος είναι ο χρόνος εκτέλεσης μίας εντολής;
Απάντηση
α. Η μέγιστη τιμή της επιτάχυνσης του ρυθμού ολοκλήρωσης εντολών ισούται με το πλήθος των βαθμίδων, δηλαδή 5.
β.
-
Η χρησιμοποίηση των καταχωρητών μεταξύ των βαθμίδων.
-
Δεν μπορούμε να διαμερίσουμε την εντολή σε 5 βήματα με τέτοιο τρόπο ώστε κάθε βήμα για την εκτέλεσή του να απαιτεί τον ίδιο χρόνο, επομένως δεν έχουν όλες οι βαθμίδες την ίδια καθυστέρηση.
-
Όλες οι εντολές δεν χρησιμοποιούν και τις 5 βαθμίδες.
-
Δομικές εξαρτήσεις
-
Εξαρτήσεις δεδομένων.
-
Διαδικασιακές εξαρτήσεις.
-
γ. O χρόνος εκτέλεσης μίας εντολής ισούται με το γινόμενο της περιόδου του σήματος χρονισμού και του πλήθους των βαθμίδων του μηχανισμού.
ΘΕΜΑ 2. Θεωρήστε υπολογιστή με κύρια μνήμη χωρητικότητας 4 Gψηφιολέξεις (1 ψηφιολέξη = 1 byte) και οργάνωση μιας ψηφιολέξης ανά θέση μνήμης, ιδεατή μνήμη που χρησιμοποιεί διευθύνσεις των 54 δυαδικών ψηφίων και μέγεθος σελίδας 8 Κψηφιολέξεις. (2,5 μον.)
α. Εάν η ιδεατή μνήμη υλοποιείται με πίνακα σελίδων ενός επιπέδου να υπολογίσετε το μέγεθος της κύριας μνήμης που απαιτείται για την αποθήκευση του πίνακα σελίδων.
β. Εάν η ιδεατή μνήμη υλοποιείται με την τεχνική του αντιστραμμένου πίνακα σελίδων (inverted page table) με 5 αντιστοιχίσεις ανά θέση του πίνακα να υπολογίσετε το μέγεθος της κύριας μνήμης που καταλαμβάνει ο αντιστραμμένος πίνακας σελίδων.
Θεωρήστε ότι τα πεδία ελέγχου καταλαμβάνουν 7 δυαδικά ψηφία. Απάντηση
Η κύρια μνήμη έχει χωρητικότητα 4 Gψηφιολέξεις = 22 ×230 ψηφιολέξεις = 232 ψηφιολέξεις, άρα η φυσική διεύθυνση είναι των 32 δυαδικών ψηφίων. Η ιδεατή μνήμη χρησιμοποιεί διευθύνσεις των 54 δυαδικών ψηφίων άρα η λογική διεύθυνση είναι των 54 δυαδικών ψηφίων. Αφού το μέγεθος σελίδας 8 Κψηφιολέξεις = 23 ×210 ψηφιολέξεις =213 ψηφιολέξεις, δμΣ: 13 δυαδικά ψηφία, φδΣ: 32-13=19 δυαδικά ψηφία και ΑΛΣ: 54-13=41 δυαδικά ψηφία.
α. Χωρητικότητα πίνακα σελίδων = (δυαδικά ψηφία ελέγχου + φδΣ)×(πλήθος λογικών σελίδων) =
(7 δυαδικά ψηφία + 19 δυαδικά ψηφία) ×241 = 26×241 δυαδικά ψηφία = 13×2×4×239 δυαδικά ψηφία =13×239 ψηφιολέξεις = 13×29 Gψηφιολέξεις.
β. Χωρητικότητα πίνακα σελίδων = (πλήθος αντιστοιχίσεων ανά θέση του πίνακα) ×
(δυαδικά ψηφία ελέγχου + ΑΛΣ + φδΣ) × (πλήθος φυσικών σελίδων) =
=5×(7 δυαδικά ψηφία +41 δυαδικά ψηφία +19 δυαδικά ψηφία)×219 = 5×67×219 δυαδικά ψηφία = 335×219 δυαδικά ψηφία = 335×216 ψηφιολέξεις =335×26 ×Κψηφιολέξεις.
| ΘΕΜΑ 3. Δίνεται επεξεργαστής μερικώς επικαλυπτόμενων λειτουργιών με πέντε βαθμίδες (ΠΕ : Προσκόμιση εντολής, ΑΕ : Αποκωδικοποίηση |
πρόγ | ραμμα |
|---|---|---|
| εντολών και ανάγνωση καταχωρητών, ΕΠ : Εκτέλεση πράξης, ΠΜ: Προσπέλαση μνήμης, ΑΑ: Αποθήκευση αποτελεσμάτων) και κοινή κρυφή μνήμη εντολών και δεδομένων. |
LOAD r1, (r2) ADD r3, r4, r5 |
// r1M(r2) // r3+r4r5 |
| Θεωρήστε ότι ο μηχανισμός δεν υλοποιεί την τεχνική παροχέτευσης. (2,5 μον.) |
SUB r1, r3, r6 ADD r8, r6, r9 |
// r1-r3r6 // r8+r6r9 |
| AND r3, r4, r10 | // r3∧r4r10 |
α.1. Συμπληρώστε τον επόμενο πίνακα και αναγνωρίστε τις εξαρτήσεις που υπάρχουν (που εμφανίζονται και τι είδους είναι) για το πρόγραμμα που δίνεται στον διπλανό πίνακα.
| π | ερίοδος | σήματος χρον | ισμού | ||||||
|---|---|---|---|---|---|---|---|---|---|
| εντολή | |||||||||
| λ λ+1 |
λ+2 | λ+3 | λ+4 | λ+5 λ+6 |
λ+7 | λ+8 | λ+9 λ+10 |
λ+11 λ+12 |
α.2. Να αναφέρετε τις τεχνικές που θα χρησιμοποιήσετε για να επιλύσετε το πρόβλημα των εξαρτήσεων και να τις εφαρμόσετε συμπληρώνοντας τον επόμενο πίνακα.
| εντολή | π | ερίοδος | σήματος χρον | ισμού | |||||
|---|---|---|---|---|---|---|---|---|---|
| λ λ+1 |
λ+2 | λ+3 | λ+4 | λ+5 λ+6 |
λ+7 | λ+8 | λ+9 λ+10 |
λ+11 λ+12 |
Απάντηση¶
α.
| εντολή | περ | ίοδος σ | ήματος χ | ρονισμ | ού | ||||
|---|---|---|---|---|---|---|---|---|---|
| λ | λ+1 | λ+2 | λ+3 | λ+4 | λ+5 | λ+6 | λ+7 | λ+8 | |
| LOAD r1, (r2) | ΠΕ | ΑΕ | ΕΠ | ΠΜ | ΑΑ | ||||
| ADD r3, r4, r5 | ΠΕ | ΑΕ | ΕΠ | ΠΜ | ΑΑ | ||||
| SUB r1, r3, r6 | ΠΕ | ΑΕ | ΕΠ | ΠΜ | ΑΑ | ||||
| ADD r8, r6, r9 | ΠΕ | ΑΕ | ΕΠ | ΠΜ | ΑΑ | ||||
| AND r3, r4, r10 | ΠΕ | ΑΕ | ΕΠ | ΠΜ | ΑΑ |
Η υπ’ αριθμόν 1 εξάρτηση είναι δομική. Η υπ’ αριθμόν 2 εξάρτηση είναι ΑΜΕ. Η υπ’ αριθμόν 3 εξάρτηση είναι ΑΜΕ.
α.2. Το πρόβλημα της δομικής εξάρτησης μπορεί να λυθεί μόνο με την τεχνική του κλειδώματος βαθμίδων. Οι εξαρτήσεις τύπου ΑΜΕ μπορούν να επιλυθούν είτε με την τεχνική κλειδώματος είτε με τη χρησιμοποίηση εντολών NOP. Στη συνέχεια θα δώσουμε και τις δύο λύσεις. Ως απάντηση στην εξέταση η μία εκ των δύο ήταν αρκετή.
- Λύση με κλείδωμα για την επίλυση του προβλήματος της δομικής εξάρτησης και χρήση εντολών NOP για τις εξαρτήσεις τύπου ΑΜΕ.
| εντολή | λ | λ+1 | λ+2 | π λ+3 |
ερίοδος λ+4 |
σήματ λ+5 |
ος χρον λ+6 |
ισμού λ+7 |
λ+8 | λ+9 | λ+10 | λ+11 | λ+12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| LOAD r1, (r2) | ΠΕ | ΑΕ | ΕΠ | ΠΜ | ΑΑ | ||||||||
| ADD r3, r4, r5 | ΠΕ | ΑΕ | ΕΠ | ΠΜ | ΑΑ | ||||||||
| NOP | ΠΕ | ΑΕ | ΕΠ | ΠΜ | ΑΑ | ||||||||
| SUB r1, r3, r6 | X | ΠΕ | ΑΕ | ΕΠ | ΠΜ | ΑΑ | |||||||
| NOP | ΠΕ | ΑΕ | ΕΠ | ΠΜ | ΑΑ | ||||||||
| NOP | ΠΕ | ΑΕ | ΕΠ | ΠΜ | ΑΑ | ||||||||
| ADD r8, r6, r9 | ΠΕ | ΑΕ | ΕΠ | ΠΜ | ΑΑ | ||||||||
| AND r3, r4, r10 | ΠΕ | ΑΕ | ΕΠ | ΠΜ | ΑΑ |
- Λύση με κλείδωμα τόσο για την επίλυση του προβλήματος της δομικής εξάρτησης όσο και των εξαρτήσεων τύπου ΑΜΕ.
| εντολή | λ | λ+1 | λ+2 | π λ+3 |
ερίοδος λ+4 |
σήματ λ+5 |
ος χρονι λ+6 |
σμού λ+7 |
λ+8 | λ+9 | λ+10 | λ+11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| LOAD r1, (r2) | ΠΕ | ΑΕ | ΕΠ | ΠΜ | ΑΑ | |||||||
| ADD r3, r4, r5 | ΠΕ | ΑΕ | ΕΠ | ΠΜ | ΑΑ | |||||||
| SUB r1, r3, r6 | ΠΕ | ΑΕ’ | ΑΕ | ΕΠ | ΠΜ | ΑΑ | ||||||
| ADD r8, r6, r9 | X | ΠΕ | ΑΕ’ | X | ΑΕ | ΕΠ | ΠΜ | ΑΑ | ||||
| AND r3, r4, r10 | ΠΕ | ΑΕ | ΕΠ | ΠΜ | ΑΑ |
ΘΕΜΑ 4. Θεωρήστε κρυφή μνήμη των 512 πλαισίων με 32 λέξεις ανά πλαίσιο και οργάνωση: (3 μον.) α. Μονοσήμαντης απεικόνισης
β. 2-τρόπων συνόλου συσχέτισης
Θεωρήστε ότι το εύρος της θέσης μνήμης είναι ίσο με το εύρος της λέξης και ο επεξεργαστής παράγει διευθύνσεις των 24 δυαδικών ψηφίων.
-
Για κάθε μία από τις περιπτώσεις α, και β να δώσετε πως χρησιμοποιείται η διεύθυνση που παράγει ο επεξεργαστής για την προσπέλαση της κρυφής μνήμης (δηλαδή τα πεδία της διεύθυνσης, το εύρος κάθε πεδίου και τι δηλώνει κάθε πεδίο).
-
Να δώσετε τις διευθύνσεις των πλαισίων της κρυφής μνήμης στα οποία μπορούν να αποθηκευτούν τα περιεχόμενα των θέσεων της κύριας μνήμης με διευθύνσεις στο δεκαεξαδικό F80CD3, F83CD8, F84CC5και F80CC0 σε κάθε μία από τις περιπτώσεις α, και β.
-
Ποια από τα περιεχόμενα των ανωτέρω θέσεων της κύριας μνήμης δεν είναι δυνατόν να βρίσκονται ταυτόχρονα στην κρυφή μνήμη σε κάθε μία από τις περιπτώσεις α, και β και γιατί; Απάντηση
α. Οργάνωση μονοσήμαντης απεικόνισης¶
- Αφού έχουμε 512 πλαίσια η διεύθυνση πλαισίου θα είναι των 9 δυαδικών ψηφίων και αφού έχουμε 32 λέξεις ανά πλαίσιο όπου σε κάθε λέξη αντιστοιχεί μια διεύθυνση, η διεύθυνση της λέξης μέσα στο πλαίσιο θα είναι των 5 δυαδικών ψηφίων. Επομένως η διεύθυνση που παράγεται από τον επεξεργαστή χρησιμοποιείται για την προσπέλαση της κρυφής μνήμης ως εξής:
| 10 δυαδικά ψηφία | 9 δυαδικά ψηφία | 5 δυαδικά ψηφία |
|---|---|---|
| ετικέτα | Διεύθυνση πλαισίου | Διεύθυνση της λέξης μέσα |
| στο πλαίσιο |
2.¶
| 10 δυαδικά ψηφία | 9 δυαδικά ψηφία | 5 δυαδικά ψηφία | |
|---|---|---|---|
| διευθύνσεις | ετικέτα | Διεύθυνση πλαισίου | Διεύθυνση της λέξης μέσα στο πλαίσιο |
| F80CD3 | 1111100000 | 001100110 | 10011 |
| F83CD8 | 1111100000 | 111100110 | 11000 |
| F84CC5 | 1111100001 | 001100110 | 00101 |
| F80CC0 | 1111100000 | 001100110 | 00000 |
- Δεν μπορούν να βρίσκονται ταυτόχρονα τα περιεχόμενα της διεύθυνσης F84CC5 με τα περιεχόμενα των διευθύνσεων F80CC0 και F80CD3 (οι δύο τελευταίες διευθύνσεις ανήκουν στο ίδιο μπλοκ) διότι έχουν την ίδια διεύθυνση πλαισίου και διαφορετική ετικέτα, δηλαδή ανήκουν σε διαφορετικά μπλοκ που αντιστοιχούν στο ίδιο πλαίσιο.
β. Οργάνωση 2-τρόπων συνόλου συσχέτισης¶
Αφού έχουμε κρυφή μνήμη 2-τρόπων συνόλου συσχέτισης με 512 πλαίσια συνεπάγεται ότι η κρυφή μνήμη θα έχει 512/2=256 σύνολα, άρα η διεύθυνση συνόλου θα είναι των 8 δυαδικών ψηφίων. Αφού έχουμε 32 λέξεις ανά πλαίσιο όπου σε κάθε λέξη αντιστοιχεί μια διεύθυνση, η διεύθυνση της λέξης μέσα στο πλαίσιο θα είναι των 5 δυαδικών ψηφίων. Επομένως η διεύθυνση που παράγεται από τον επεξεργαστή χρησιμοποιείται για την προσπέλαση της κρυφής μνήμης ως εξής:
2.¶
| 11 δυαδικάψηφία | 8 δυαδικάψηφία | 5 δυαδικάψηφία |
|---|---|---|
| ετικέτα | Διεύθυνση συνόλου | Διεύθυνση της λέξης μέσα στο πλαίσιο |
| 11δυαδικά ψηφία | 8 δυαδικά ψηφία 5 δυαδικά ψηφία |
|
| διευθύνσεις | ετικέτα | Διεύθυνση συνόλου Διεύθυνση της λέξης μέσα στο πλαίσιο |
| F80CD3 | 11111000000 | 01100110 10011 |
| F83CD8 | 11111000001 | 11100110 11000 |
| F84CC5 | 11111000010 | 01100110 00101 |
| F80CC0 | 11111000000 | 01100110 00000 |
Δεν μπορούμε να απαντήσουμε σε ποιο πλαίσιο της κρυφής μνήμης θα αποθηκευτεί ένα μπλοκ, αλλά σε ποιο σύνολο (σε ένα από τα δύο πλαίσια του συνόλου).
- Δεν υπάρχουν διευθύνσεις των οποίων τα περιεχόμενα δε μπορούν να βρίσκονται ταυτόχρονα στην κρυφή μνήμη. Τα περιεχόμενα της διεύθυνσης F84CC5 με τα περιεχόμενα των διευθύνσεων F80CC0 και F80CD3 (οι δύο τελευταίες διευθύνσεις ανήκουν στο ίδιο μπλοκ) ανήκουν σε δύο διαφορετικά μπλοκ που αντιστοιχούν στο ίδιο σύνολο. Ωστόσο το σύνολο έχει δύο πλαίσια οπότε και τα δύο μπλοκ μπορούν να βρίσκονται ταυτόχρονα στην κρυφή μνήμη. Η διεύθυνση F83CD8 ανήκει σε μπλοκ που αντιστοιχεί σε άλλο σύνολο, οπότε μπορούν τα περιεχόμενά της να βρίσκονται ταυτόχρονα στην κρυφή μνήμη με αυτά των προηγούμενων.