ΗΥ-225: Οργάνωση Υπολογιστών
Άνοιξη 2012
Τμ. Επ. Υπολογιστών
© Πανεπιστήμιο Κρήτης

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

Παράδοση: Παρασκευή 18 Μαΐου 2012 (βδ.12), σε χαρτί, στο μάθημα
[Up - Table of Contents] [printer version - PDF]

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

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

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

texec = Ninstructions * CPIaverage * Tclock

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

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

Άσκηση 11.2:   Μέσο CPI του Επεξεργαστή του Μαθήματος

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

texec = ( NA * CPIA + NB * CPIB ) * Tclock = Ninstructions * CPIaverage * Tclock

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

CPIaverage = ( NA / Ninstructions ) * CPIA + ( NB / Ninstructions ) * CPIB

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

(α) Στην υλοποίησή σας της άσκησης 9 (Verilog - τμήμα ελέγχου), πόσους κύκλους ρολογιού παίρνει η εκτέλεση μιάς εντολής του κάθε τύπου; (εάν δεν υλοποιήσατε την load-upper-immediate, θεωρήστε ότι αυτή διαρκεί όσο και η jump). Βασει της διάρκειας αυτής εκτέλεσης του κάθε τύπου εντολής, και βάσει των παραπάνω ποσοστών εκτέλεσης των διαφόρων τύπων εντολών, πόσο θα είναι το μέσο CPI αυτού του επεξεργαστή γιά αυτά τα προγράμματα;
(β) Έστω τώρα ότι κάνουμε βελτιστοποιήσεις: έστω ότι κάνουμε όλες τις εντολές άλματος (j, jr, jal, κλπ) καθώς και την εντολή load upper immediate (lui) να εκτελούνται σε δύο αντί τριών ή περισσοτέρων κύκλων ρολογιού καθεμία. Πόσο θα είναι τότε το νέο μέσο CPI του επεξεργαστή γιά αυτά τα προγράμματα;
(γ) Αν η βελτιστοποίηση (β) έχει σαν αρνητική παρενέργεια να αυξήσει τον κύκλο ρολογιού από 2.4 ns σε 2.6 ns, ποιός από τους δύο επεξεργαστές (α) και (β) θα είναι ταχύτερος, και κατά πόσο; (Υπόδειξη: προφανώς, το πλήθος των εκτελούμενων εντολών Ninstructions δεν αλλάζει από τον (α) στον (β)).

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

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

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

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

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

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

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


© copyright University of Crete, Greece. Last updated: 8 May 2012 (16 May add'l explanations in ex.11.2) by M. Katevenis.