Performance Tip: Data Dependency & Out-of-Order execution

[DarthMoul]

Πριν μιλήσουμε για το θέμα του τίτλου θα πρέπει να πούμε κάποια πράγματα για την λειτουργία του πυρήνα της CPU μας. Όλοι οι επεξεργαστές της τελευταίας δεκαετίας έχουν το χαρακτηριστικό να μην εκτελούν τις εντολές με την σειρά που τις ανακτούν από την μνήμη. Αυτό που κάνουν είναι να τις ανακτούν καθ'ομάδες μέσα σε μια buffer και να τις αναδιατάσουν (reorder) με τέτοιον τρόπο ώστε να παράγουν το ίδιο αποτέλεσμα μεν, αλλά σε μικρότερο χρόνο. Η διαδικασία αυτή ονομάζεται Out-of-Order Execution εν συντομία μια και η πλήρης ονομασία του είναι Non-Sequential Dynamic Execution Scheduling. Αν υποθέσουμε ότι έχουμε τις παρακάτω γραμμές κώδικα:
a=b/c;
d=d+2;
e=e+3;

Οι προσθέσεις θα διαρκέσουν έναν κύκλο μηχανής ενώ η διαίρεση 2 ή περισσότερους ανάλογα με τον επεξεργαστή. H CPU φέρνοντας τις μικροεντολές και των τριών πράξεων μέσα στην instruction reordering buffer, θα δρομολογήσει την εκτέλεση των παραπάνω γραμμών έτσι ώστε οι προσθέσεις να εκτελεστούν εν παραλλήλω με την διαίρεση και θα συγχρονίσει την επιστροφή και των τριών αποτελεσμάτων. Αυτό μπορεί να το κάνει γιατί οι επεξεργαστές εδώ και πολλά χρόνια είναι superscalar δηλαδή έχουν περισσότερες από μία μονάδες εκτέλεσης. Έτσι λοιπόν η FPU θα αναλάβει την διαίρεση σε δύο κύκλους ενώ η ALU τις προσθέσεις σε έναν κύκλο την κάθε μία με αποτέλεσμα η συνολική επεξεργασία να διαρκέσει μόνο 2 κύκλους μηχανής αντί για 4. Όλη αυτή η διαδικασία είναι αόρατη στον προγραμματιστή και δεν έχουμε καμμία δυνατότητα επέμβασης. Έχουμε όμως δυνατότητα να την διευκολύνουμε, γράφοντας τον κώδικα μας κατάλληλα για την αξιοποιήσει.

[DarthMoul]

Το Out-of-Order Execution Unit καταλαμβάνει πολύ μεγάλο μέρος του πυρήνα και είναι μία διαδικασία δύσκολη γιατί πρέπει να διασφαλιστεί η ορθότητα του παραγώμενου αποτελέσματος μετά την αναδιάταξη. Επίσης είναι και μια διαδικασία χρονοβόρα η οποία στηρίζεται πάνω στην υπόθεση ότι το κόστος της αναδιάταξης θα είναι μικρότερο από το κέρδος που θα έχουμε στον χρόνο εκτέλεσης των εντολών. Εάν τελικά η αναδιάταξη δεν είναι δυνατή, τότε θα υποστούμε μόνο το κόστος, χωρίς να απολαύσουμε κανένα ώφελος.

Πάμε τώρα να δούμε τις διαφορές μεταξύ Pentium και Athlon. Ο φίλος μας ο sakattack έκανε τον κόπο να μας δώσει πολύ ενδιαφέροντα links για την ιστορία των Pentium. Η πιο σημαντική παράγραφος κατά την γνώμη μου είναι αυτή που γράφει ότι όσο μικραίνει το μέγεθος των ημιαγωγών, οι επιλογές του σχεδιαστή είναι δύο. Η μία να αυξήσει την συχνότητα και η άλλη να αυξήσει την λειτουργικότητα. Εδώ βρίσκεται και το μυστικό του Athlon που ανταγωνίζεται ευθέως τον Pentium σε επιδόσεις με πολύ μικρότερες συχνότητες. Το instruction reordering buffer του Athlon έχει μέγεθος για 40 μικροεντολές ενώ του Pentium μόνο 12 (και στους ΕΕ 20 αν δεν κάνω λάθος). Το instruction reordering δεν είναι τίποτα παραπάνω από micro-optimization που κάνει η ίδια η CPU μέσα στον πυρήνα. Όσο μεγαλύτερο το υποσύνολο των εντολών που βελτιστοποιείς σε σχέση με τον συνολικό αριθμό των εντολών, τόσο μεγαλύτερες και οι βελτιώσεις που πετυχαίνεις. Ενδεχόμενη αύξηση του υποσυνόλου που βελτιστοποιείς προκαλεί εκθετική βελτίωση των επιδόσεων.

Όσοι ασχολούνται με software συστηματικά το γνωρίζουν αυτό πολύ καλά. Οι πιο εξελιγμένοι compilers σου επιτρέπουν να δημιουργείς profiling statistics για την εκτέλεση του συνόλου του project ακόμα και αν αυτό αποτελείται από πολλά εκτελέσιμα προγράμματα. Αυτά τα στατιστικά καταγράφονται σε ένα feedback αρχείο το οποίο χρησιμοποιεί ο optimizer του compiler στο επόμενο compilation που θα κάνεις. Έτσι μπορεί να πετύχει εκπληκτική αύξηση των επιδόσεων της εφαρμογής που με το πρώτο compilation θα ήταν αδύνατο, αφού η βελτιστοποίηση λάμβανε χώρα σε κάθε module ξεχωριστά και όχι στο σύνολο του project. Άρα όσο πιο μεγάλο κομμάτι του κώδικα σου βελτιστοποιείς σε κάθε πέρασμα, τόσο καλύτερες επιδόσεις πετυχαίνεις. Αυτό ακριβώς επιδιώκει και ο Athlon σε αντίθεση με τον Pentium. Προτιμά να βελτιστοποιεί μεγαλύτερα κομμάτια κώδικα, εκεί που ο Pentium βελτιστοποιεί μικρότερα και ανεβάζει την συχνότητα για να καλύψει την διαφορά.

[DarthMoul]

Τα περισσότερα προγράμματα που κυκλοφορούν είναι compiled για 486, Pentium ή στην καλύτερη περίπτωση Pentium Pro. Αυτό περιλαμβάνει και τα Windows και σχεδόν όλες τις εφαρμογές που χρησιμοποιούμε, ακόμα και τα benchmarks. Αυτοί οι παλιοί επεξεργαστές όπως είχαν τελείως διαφορετικό instruction scheduling απ'ότι ένας P3 ή ένας P4 ή ένας Athlon παρόλο που το instruction set είναι πανομοιότυπο. Το γεγονός αυτό διευκολύνει τον Athlon να διατηρεί τις επιδόσεις του ή ακόμα και να ξεπερνά τον Pentium σε πολλά σημεία.

Όμως ουδέν καλόν αμιγές κακού. Όσο πιο βελτιστοποιημένο είναι ένα πρόγραμμα, καθώς και όσο πιο προσεγμένο κώδικα παράγει ο compiler και όσο πιο έξυπνη δουλειά κάνει ο optimizer ο Athlon κερδίζει λιγότερο σε σχέση με τον Pentium. Ο λόγος είναι ότι ενώ καταναλώνει χρόνο στο reordering, έχει να κερδίσει ελάχιστα από αυτό, με αποτέλεσμα η σχέση μεταξύ κόστους και κέρδους που λέγαμε παραπάνω, να ανατρέπεται υπέρ του κόστους. Ο Pentium αντίθετα που αφιερώνει λιγότερο χρόνο σε αυτήν την διαδικασία βγαίνει πολύ περισσότερο κερδισμένος σε σχέση με τον Athlon.

Ο καλύτερος C compiler για x86 είναι αυτός της Intel. H AMD τον χρησιμοποιεί ακόμα και στα spec submissions. Παρ'όλα αυτά ο κώδικας που παράγει μπορεί να δώσει ώθηση εώς και 70% σε έναν Pentium ενώ στον Athlon το κέρδος κυμαίνεται από 5% εώς 10% σε σχέση με τον compiler της microsoft. Ο λόγος είναι αυτός που περιγράψαμε παραπάνω.

Όπως είχαμε πει και παλιότερα, όσο πιο καλογραμμένα είναι τα προγράμματα μας και όσο πιο καλός είναι ο κωδικας που παράγει ο compiler, τόσο καλύτερο είναι το frequency scaling. Ενας από τους λόγους είναι ότι η CPU θα αφιερώσει λιγότερο χρόνο στο instruction reordering. Κατά συνέπεια όσο πιο μεγάλες συχνότητες έχεις και όσο λιγότερο reordering κάνεις, όπως ο Pentium, τόσο το καλύτερο. Δυστυχώς όμως για τον Pentium, η πραγματικότητα όσον αφορά το software που κυκλοφορεί είναι πολύ διαφορετική. Οι software developers δεν αποκλείουν κανέναν από την πελατεία τους. Ακόμα και αυτόν που για κάποιο λόγο ξέμεινε με Pentium Pro. Άρα ο κώδικας που θα πουλήσουν στην αγορά θα είναι για Pentium Pro και όχι για P4EE. Τα δε shareware/freeware που είναι δωρεάν, δεν έχουν καν την υποχρέωση να διασφαλίσουν την ποιότητα του κώδικα τους σε σχέση με τις επιδόσεις. Ευτυχώς υπάρχει το opensource που ο κώδικας του είναι ορατός σε όλους. Όσο ποιό πολλά μάτια βλέπουν τον κώδικα, τόσο το καλύτερο και από πλευράς bugs και ασφάλειας αλλά και από πλευράς επιδόσεων. Αν αναρωτηθήκατε ποτέ για ποιόν λόγο ένα δωρεάν Linux αξιοποιεί την CPU σας 10% ή 20% καλύτερα από τα Windows ή ακόμα και το MAC OS X, νομίζω πως τώρα ξέρετε και τον λόγο.

[DarthMoul]

Data dependency είναι η εξάρτηση της εκτέλεσης μια γραμμής κώδικα, από το αποτέλεσμα της εκτέλεσης της προηγούμενης γραμμής. Κοιτάξτε τον παρακάτω κώδικα:

a[i]=a[i]+a[i+1]; (1 cycle)
b=a[i] + 100; (1 cycle)
c=k/n; (2 cycles)

Εδώ το out-of-order execution είναι αδύνατον. Η γραμμή b=a[i] + 100; θα πρέπει να περιμένει την εκτέλεση της a[i]=a[i]+a[i+1]; για να δουλέψει. Συνεπώς τον παραλληλισμό τον ξεχνάμε. Οι παραπάνω γραμμές θα κοστίσουν 4 κύκλους. Πάμε να δούμε πως πρέπει να είναι γραμμένος ο κώδικας μας για να πετύχουμε παραλληλισμό:

b=a[i]+a[i+1]+100; (2 cycles)
a[i]=a[i]+a[i+1];(1 cycle)
c=k/n;(2 cycles)

Εδώ καμμία γραμμή δεν εξαρτάται από το αποτέλεσμα της προηγούμενης. Η cpu θα δρομολογήσει την παράλληλη εκτέλεση όλων των γραμμών. Συνολικό κόστος 2 κύκλοι παρόλο που κάναμε μία πρόσθεση παραπάνω, δηλαδή βελτίωση 50% σε σχέση με πριν!!!

Προσοχή στο data dependency: Είναι silent performance killer