ΗΥ-225: Οργάνωση Υπολογιστών Άνοιξη 2018

Τμ. Επ. Υπολογιστών © Πανεπιστήμιο Κρήτης

Σειρά Ασκήσεων 10:
Επίδοση Επεξεργαστών, CPI

κάντε τις έως Δευτέρα 23 Απριλίου 2018 (βδ. 10.1) (από βδ. 9.1)

[Up - Table of Contents]

[printer version - PDF]

Βιβλίο: Διαβάστε την §1.4, σελίδες 61-74.

Άσκηση 10.1:   Επίδοση Επεξεργαστών

Η επίδοση (performance) ενός υπολογιστή, κατά την εκτέλεση δοθέντος προγράμματος, είναι αντίστροφα ανάλογη προς τον χρόνο εκτέλεσης αυτού του προγράμματος σε αυτόν τον υπολογιστή. Η επίδοση ενός υπολογιστή, γενικά και αόριστα, ανεξαρτήτως εκτελουμένου προγράμματος, δεν μπορεί να οριστεί επακριβώς και επιστημονικά, μπορεί δε να ποικίλλει ευρέως ανάλογα με τα χαρακτηριστικά των διαφόρων προγραμμάτων.

Εάν ο υπολογιστής A εκτελεί ένα δοθέν πρόγραμμα σε χρόνο tA, ο δε υπολογιστής B το εκτελεί σε χρόνο tB, όπου tB > tA και (tB / tA) = 1.xy, τότε λέμε ότι "ο υπολογιστής A είναι ταχύτερος του B κατά xy % γιά το δοθέν πρόγραμμα". Παραδείγματος χάριν, αν tA = 4s και tB = 5s, τότε (tB/tA) = 1.25, και ο A είναι ταχύτερος του Β κατά 25 % γιά το δοθέν πρόγραμμα. Ο χρόνος t_exec εκτέλεσης ενός προγράμματος σ' έναν υπολογιστή μπορεί συχνά να εκφραστεί σαν:

t_exec = N_instructions * CPI_average * T_clock

όπου N_instructions είναι το πλήθος (ο αριθμός) των εντολών που ο υπολογιστής εκτελεί προκειμένου να ολοκληρωθεί η εκτέλεση του δοθέντος προγράμματος, CPI_average είναι το μέσο πλήθος (μέσος αριθμός) των κύκλων ρολογιού που απαιτούνται γιά την εκτέλεση μιάς εντολής (Cycles Per Instruction --CPI), και T_clock είναι ο χρόνος που διαρκεί ένας κύκλος ρολογιού, δηλαδή η περίοδος του ρολογιού, δηλαδή το αντίστροφο της συχνότητας ρολογιού.

Ερώτηση: Θεωρήστε έναν υπολογιστή A (τύπου RISC), που γιά να τελειώσει ένα δοθέν πρόγραμμα πρέπει να εκτελέσει 2,500,000 εντολές, με μέσο CPI = 3.2 κύκλους ρολογιού ανά εντολή, και με ρολόϊ 1.25 GHz. Ενας άλλος υπολογιστής B (τύπου CISC --complex instruction set computer) έχει πιό "πλούσιο" ρεπερτόριο εντολών, κι έτσι του αρκεί να εκτελέσει μόνο 1,800,000 εντολές γιά να τελειώσει το ίδιο πρόγραμμα. Ομως, λόγω της αυξημένης πολυπλοκότητάς του, έχει μέσο CPI = 4.0 κύκλους ρολογιού ανά εντολή, και ρολόϊ 1.0 GHz. Πόσους κύκλους ρολογιού και πόσα δευτερόλεπτα χρειάζεται ο κάθε υπολογιστής γιά να εκτελέσει το δοθέν πρόγραμμα; Ποιός από τους δύο υπολογιστές είναι ταχύτερος από τον άλλον γιά το δοθέν πρόγραμμα, και πόσο ταχύτερος;

Άσκηση 10.2:   Μέσο CPI του Επεξεργαστή πολλαπλών κύκλων ανά εντολή

Ας πούμε ότι κάποιος υπολογιστής έχει δύο ειδών εντολές: (i) εντολές τύπου Α, που καθεμιά τους χρειάζεται CPI_A κύκλους ρολογιού γιά να εκτελεστεί, και (ii) εντολές τύπου B, που καθεμιά τους χρειάζεται CPI_Β κύκλους ρολογιού γιά να εκτελεστεί. Το πρόγραμμά μας, γιά να ολοκληρωθεί η εκτέλεσή του, χρειάζεται να εκτελεστούν: N_A το πλήθος εντολές τύπου A, και N_B το πλήθος εντολές τύπου B (Προφανώς, γιά ολόκληρο το πρόγραμμα: N_instructions = N_A + N_B). Τότε, ο συνολικός χρόνος εκτέλεσης του προγράμματος θα είναι:

t_exec = ( N_A * CPI_A + N_B * CPI_B ) * T_clock = N_instructions * CPI_average * T_clock

Το αριστερό μέρος της εξίσωσης αυτής προέρχεται από το πόσο χρόνο χρειάζονται γιά να εκτελεστούν όλες οι εντολές --και οι τύπου Α και οι τύπου Β. Το δεξιό μέρος της εξίσωσης είναι η "απλοποιητική" σχέση της παραπάνω §10.1, η οποία χρησιμεύει και σαν ορισμός του μέσου CPI. Από τη δεξιά ισότητα, λοιπόν, απλοποιώντας το T_clock και διαιρώντας διά N_instructions προκύπτει ότι το μέσο CPI είναι ο σταθμισμένος μέσος όρος των κύκλων ρολογιού ανά εντολή, όπου οι συντελεστές στάθμισης είναι τα ποσοστά (συχνότητα) εκτέλεσης του κάθε τύπου εντολών:

CPI_average = ( N_A / N_instructions ) * CPI_A + ( N_B / N_instructions ) * CPI_B

Ας εξετάσουμε λοιπόν μια συγκεκριμένη περίπτωση: Στα προγράμματα ακεραίων (όχι κινητής υποδιαστολής) μεταξύ των SPEC benchmarks, όταν αυτά εκτελούνται στον MIPS, η συχνότητα εκτέλεσης των διαφόρων εντολών είναι περίπου η εξής:

• 26 % load (lw, κλπ),
• 11 % store (sw, κλπ),
• 40 % ALU (add, addi, sub, and, or, slt, slti, κλπ),
•   3 % load upper immediate (lui),
• 16 % conditional branches (beq, bne, κλπ),
•   4 % unconditional jumps (j, jr, jal, κλπ).

(α) Στην υλοποίηση του επεξεργαστή μας σε πολλαπλούς "σύντομους" κύκλους ρολογιού (αλλά όχι ακόμα pipelined) που είδαμε στην §8.9, έστω ότι οι κύκλοι ρολογιού που χρειάζονται γιά την εκτέλεση του κάθε τύπου εντολής είναι: πέντε (5) κύκλοι γιά κάθε εντολή load· τέσσερεις (4) κύκλοι γιά κάθε εντολή store ή ALU· και τρείς (3) κύκλοι γιά κάθε εντολή lui, branch, ή jump.

Βασει της διάρκειας αυτής εκτέλεσης του κάθε τύπου εντολής, και βάσει των παραπάνω ποσοστών εκτέλεσης των διαφόρων τύπων εντολών, πόσο θα είναι το μέσο CPI αυτού του επεξεργαστή γιά αυτά τα προγράμματα;

(β) Έστω τώρα ότι κάνουμε βελτιστοποιήσεις: έστω ότι κάνουμε όλες τις εντολές άλματος (j, jr, jal, κλπ) καθώς και την εντολή load upper immediate (lui) να εκτελούνται σε δύο (2) αντί τριών κύκλων ρολογιού καθεμία. Πόσο θα είναι τότε το νέο μέσο CPI του επεξεργαστή γιά αυτά τα προγράμματα;

(γ) Αν η βελτιστοποίηση (β) έχει σαν αρνητική παρενέργεια να αυξήσει τον κύκλο ρολογιού από 0.80 ns σε 0.85 ns, ποιός από τους δύο επεξεργαστές (α) και (β) θα είναι ταχύτερος, και κατά πόσο; (Υπόδειξη: προφανώς, το πλήθος των εκτελούμενων εντολών N_instructions δεν αλλάζει από τον (α) στον (β)).

Άσκηση 10.3:   Μέσο CPI Επεξεργαστή με Ομοχειρία (Pipelining)

Στο κεφάλαιο (άσκηση) 9 περί ομοχειρίας (pipelining), είδαμε ότι, όσο ο επεξεργαστής βρίσκει ανεξάρτητες μεταξύ τους εντολές, τις εκτελεί με ρυθμό μία εντολή ανά κύκλο ρολογιού. Έτσι, παρά ο γεγονός ότι η εκτέλεση της κάθε εντολής διαρκεί περισσότερους του ενός κύκλους ρολογιού, το συνολικό πλήθος κύκλων ρολογιού γιά την εκτέλεση ενός ολόκληρου προγράμματος --που είναι και αυτό που μας ενδιαφέρει-- είναι περίπου τόσο όσες και οι εκτελούμενες εντολές (υπό τις παραπάνω προϋποθέσεις ανεξαρτησίας). Αρα, το μέσο CPI υπό τις συνθήκες αυτές θα είναι 1, δηλαδή η κάθε εντολή μας "κοστίζει" 1 κύκλο ρολογιού, όσο δηλαδή μας "καθυστερεί" μέχρι να ξεκινήσουμε και την επόμενή της.

Ομως, όπως είπαμε, δυστυχώς, υπάρχουν και αλληλεξαρτήσεις εντολών, οι οποίες προκαλούν απώλεια κύκλου ή κύκλων ρολογιού επιπλέον του παραπάνω ενός "βασικού" κύκλου ανά εντολή. Ας θεωρήσουμε, σε σχέση και με τα ποσοστά εντολών που αναφέρθηκαν στην παραπάνω άσκηση 10.2, ότι:

• Το 33 % των εκτελουμένων load (άρα το 33% του 26% ίσον 8.6% του συνόλου των εκτελουμένων εντολών) ακολουθείται αμέσως από εξαρτημένη εντολή (εντολή που χρειάζεται τα loaded data στην 3η βαθμίδα της pipeline της), και άρα προκαλούν (αυτές οι 33% των load ίσον 8.6% του συνόλου των εντολών) την απώλεια ενός κύκλου ρολογιού επιπλέον του ενός βασικού.
• Το 25 % των εκτελουμένων διακλαδώσεων υπό συνθήκη (branch) (άρα το 25% του 16% ίσον 4% του συνόλου των εκτελουμένων εντολών) δεν καθίσταται εφικτό να περιέχει μία από τις πολλές βελτιστοποιήσεις που υπάρχουν, και κατά συνέπεια προκαλούν (και αυτές οι 4% του συνόλου των εντολών) την απώλεια ενός κύκλου ρολογιού επιπλέον του ενός βασικού.

Με αυτά τα δεδομένα, πόσο θα είναι το μέσο CPI (γιά τα παραπάνω προγράμματα της άσκησης 10.2) ενός επεξεργαστή MIPS που χρησιμοποιεί αυτή τη μορφή ομοχειρίας; Θεωρώντας ότι αυτός ο επεξεργαστής έχει το ίδιο ρολόϊ με εκείνον της άσκησης 10.2(α), και αφού, φυσικά, εκτελεί τις ίδιες εντολές ανά πρόγραμμα, πόσο ταχύτερος θα είναι αυτός ο επεξεργαστής από εκείνον της άσκησης 10.2(α);

Άσκηση 10.4:   Μέσο CPI Επεξεργαστή Superscalar με Ομοχειρία

Οι σημερινοί (μικρο-) επεξεργαστές του εμπορίου χρησιμοποιούν τόσο την τεχνική της ομοχειρίας (pipelining) που είδαμε παραπάνω, όσο και τεχνικές εκτέλεσης πολλαπλών εντολών ταυτόχρονα --συνήθως με τη μορφή που αποκαλείται "superscalar". Θεωρήστε ένα τέτοιον επεξεργαστή που σε κάθε κύκλο ρολογιού διαβάζει (fetch) από τη μνήμη τις τέσσερεις (4) επόμενες εντολές, και εκτελεί ταυτόχρονα (εν παραλλήλω) όσες από αυτές είναι ανεξάρτητες μεταξύ τους. Το μέσο CPI ενός τέτοιου επεξεργαστή είναι όσο θα ήταν με χρήση ομοχειρίας μόνο (χωρίς superscalarity), διηρημένο διά το μέσο πλήθος ταυτόχρονα εκτελούμενων εντολών, δεδομένου ότι τώρα ο κάθε κύκλος ρολογιού που περνάει "χρεώνεται" σε όλες τις ταυτόχρονα εκτελούμενες εντολές, άρα στην κάθε εντολή χρεώνονται αντίστοιχα λιγότεροι κύκλοι ρολογιού (λιγοστεύουν οι cycles per instruction --CPI).

Θεωρήστε ότι κάνουμε τον επεξεργαστή της άσκησης 10.3 superscalar, και ας πούμε γιά απλότητα ότι αυτό γίνεται χωρίς να αλλάξουμε την δομή της pipeline του και χωρίς να αλλάξει το ρολόϊ (στην πράξη δεν είναι έτσι). Εάν το μέσο πλήθος ταυτόχρονα εκτελούμενων ανεξάρτητων εντολών είναι 1.6 εντολές, τότε ποιό θα είναι το μέσο CPI του νέου επεξεργαστή; Πόσο γρηγορότερος θα είναι αυτός από εκείνον της άσκησης 10.2(α), και πόσο από εκείνον της άσκησης 10.3;

Τρόπος Παράδοσης:
Κάντε την απλή αυτή άσκηση από τώρα, γιά να την έχετε έτοιμη, παρ' ότι θα την παραδώσετε λίγο αργότερα, μαζί με επόμενη σειρά ασκήσεων. Ο τρόπος παράδοσης θα είναι on-line, σε μορφή PDF (μόνον) (μπορεί να είναι κείμενο μηχανογραφημένο ή/και "σκαναρισμένο" χειρόγραφο, αλλά μόνον σε μορφή PDF).

---

© copyright University of Crete, Greece. Last updated: 15 Apr. 2018 by M. Katevenis.