DarthMoul
26-07-2004, 09:06
Πριν μιλήσουμε για το θέμα του τίτλου, θα πρέπει να πούμε μερικά χρήσιμα πράγματα για το cache.
Όταν ο memory controller συναντάει ένα cache miss στο L1 cache, ξεκινάει αναζήτηση στο L2, το L3 και τελικά στην μνήμη μέχρι να βρει τα δεδομένα που ζητήσαμε, να τα μεταφέρει στους registers για επεξεργασία, και φυσικά να τα αποθηκεύσει στο cache για χρήση στο άμεσο μέλλον αν χρειαστεί. Ενδεικτικά το κόστος αυτής της διαδικασίας είναι όπως παρακάτω:
Pentium 4 3.2 EE
L1 latency = 2 cycles
L2 latency = 19 cycles
L3 latency = 43 cycles
RAM latency = 206 cycles
Athlon 64 3400+
L1 latency = 3 cycles
L2 latency = 13 cycles
RAM latency = 101 cycles
Το L1 cache είναι πάντα χωρισμένο σε 2 ίσα μέρη. Το Dcache (Data cache) στο οποίο αποθηκεύονται οι τελευταίες μεταβλητές που προσπελάσαμε, και το Icache (Instruction cache) στο οποίο αποθηκεύονται οι τελευταίες εντολές που εκτελέσαμε. Η μεταφορά δεδομένων από την μνήμη στο Dcache δεν γίνεται μεμονωμένα για τις μεταβλητές που ζητάμε, αλλά σε ομάδες από συνεχόμενα bytes που ονομάζονται cache lines. Τι μέγεθος έχουν τα cache lines; Για τους P3 είναι 32 bytes και για όλους τους AMD επεξεργαστές καθώς και για τους P4 είναι 64 bytes.
Αυτό σημαίνει ότι αν θέλουμε να δουλέψουμε με έναν πίνακα ακεραίων, για να κάνουμε το preload, αρκεί να «αγγίξουμε», ένα στοιχείο του ανά 16, και ολόκληρος ο πίνακας θα βρεθεί μέσα στο cache. Αν είχαμε να δουλέψουμε με πίνακα χαρακτήρων, θα αρκούσε να «αγγίξουμε» ένα Byte ανά 64.
Παράλληλα όμως υπάρχει και ένας περιορισμός. Σε κάθε δεδομένη στιγμή, έχουμε πρόσβαση στα δεδομένα ενός μόνο cache line. Αν τα δεδομένα που χρειαζόμαστε είναι μοιρασμένα σε περισσότερα από ένα cache lines, τότε λέμε ότι έχουμε την περίπτωση του cache line split. Αυτό σημαίνει ότι για την χρήση κάθε επιπλέον cache line καλούμαστε να πληρώσουμε το κόστος προσπέλασης του L1 cache που όπως βλέπουμε πιο πάνω είναι 2 κύκλοι για τους P4EE και 3 κύκλοι για τους A64. Αυτός ο περιορισμός, μπορεί εν μέρει και υπό συνθήκες να παρακαμφθεί αλλά θα το συζητήσουμε κάποια άλλη στιγμή.
Για προσπέλαση δεδομένων που έχουν μέγεθος μικρότερο από αυτό του cache line, καλό θα ήταν να προτιμούμε μεγέθη που είναι ακέραια υποπολλαπλάσια του cache line size. Για παράδειγμα, αν πρέπει να επεξεργαστούμε έναν πίνακα από strings των 10 bytes, από πλευράς ταχύτητας μας συμφέρει να δουλέψουμε με strings των 16 bytes γιατί έτσι θα αποφύγουμε το κόστος του cache line split. Αυτό βέβαια εις βάρος της μνήμης μας, αφού τα 6 τελευταία bytes κάθε string θα μείνουν άχρηστα. Για δεδομένα με μέγεθος μεγαλύτερο του cache line, μας συμφέρει το ακέραιο πολλαπλάσιο του cache line size. Έτσι θα μειώσουμε το κόστος του cache line split έως και 50%. Αν πχ πρέπει να δουλέψουμε με έναν πίνακα από records που έχουν μέγεθος 97 bytes το καθένα, το καλύτερο που έχουμε να κάνουμε είναι να προσθέσουμε στο τέλος κάθε record όσα bytes χρειάζεται για να φτάσουμε τα 128 bytes.
Όταν ο memory controller συναντάει ένα cache miss στο L1 cache, ξεκινάει αναζήτηση στο L2, το L3 και τελικά στην μνήμη μέχρι να βρει τα δεδομένα που ζητήσαμε, να τα μεταφέρει στους registers για επεξεργασία, και φυσικά να τα αποθηκεύσει στο cache για χρήση στο άμεσο μέλλον αν χρειαστεί. Ενδεικτικά το κόστος αυτής της διαδικασίας είναι όπως παρακάτω:
Pentium 4 3.2 EE
L1 latency = 2 cycles
L2 latency = 19 cycles
L3 latency = 43 cycles
RAM latency = 206 cycles
Athlon 64 3400+
L1 latency = 3 cycles
L2 latency = 13 cycles
RAM latency = 101 cycles
Το L1 cache είναι πάντα χωρισμένο σε 2 ίσα μέρη. Το Dcache (Data cache) στο οποίο αποθηκεύονται οι τελευταίες μεταβλητές που προσπελάσαμε, και το Icache (Instruction cache) στο οποίο αποθηκεύονται οι τελευταίες εντολές που εκτελέσαμε. Η μεταφορά δεδομένων από την μνήμη στο Dcache δεν γίνεται μεμονωμένα για τις μεταβλητές που ζητάμε, αλλά σε ομάδες από συνεχόμενα bytes που ονομάζονται cache lines. Τι μέγεθος έχουν τα cache lines; Για τους P3 είναι 32 bytes και για όλους τους AMD επεξεργαστές καθώς και για τους P4 είναι 64 bytes.
Αυτό σημαίνει ότι αν θέλουμε να δουλέψουμε με έναν πίνακα ακεραίων, για να κάνουμε το preload, αρκεί να «αγγίξουμε», ένα στοιχείο του ανά 16, και ολόκληρος ο πίνακας θα βρεθεί μέσα στο cache. Αν είχαμε να δουλέψουμε με πίνακα χαρακτήρων, θα αρκούσε να «αγγίξουμε» ένα Byte ανά 64.
Παράλληλα όμως υπάρχει και ένας περιορισμός. Σε κάθε δεδομένη στιγμή, έχουμε πρόσβαση στα δεδομένα ενός μόνο cache line. Αν τα δεδομένα που χρειαζόμαστε είναι μοιρασμένα σε περισσότερα από ένα cache lines, τότε λέμε ότι έχουμε την περίπτωση του cache line split. Αυτό σημαίνει ότι για την χρήση κάθε επιπλέον cache line καλούμαστε να πληρώσουμε το κόστος προσπέλασης του L1 cache που όπως βλέπουμε πιο πάνω είναι 2 κύκλοι για τους P4EE και 3 κύκλοι για τους A64. Αυτός ο περιορισμός, μπορεί εν μέρει και υπό συνθήκες να παρακαμφθεί αλλά θα το συζητήσουμε κάποια άλλη στιγμή.
Για προσπέλαση δεδομένων που έχουν μέγεθος μικρότερο από αυτό του cache line, καλό θα ήταν να προτιμούμε μεγέθη που είναι ακέραια υποπολλαπλάσια του cache line size. Για παράδειγμα, αν πρέπει να επεξεργαστούμε έναν πίνακα από strings των 10 bytes, από πλευράς ταχύτητας μας συμφέρει να δουλέψουμε με strings των 16 bytes γιατί έτσι θα αποφύγουμε το κόστος του cache line split. Αυτό βέβαια εις βάρος της μνήμης μας, αφού τα 6 τελευταία bytes κάθε string θα μείνουν άχρηστα. Για δεδομένα με μέγεθος μεγαλύτερο του cache line, μας συμφέρει το ακέραιο πολλαπλάσιο του cache line size. Έτσι θα μειώσουμε το κόστος του cache line split έως και 50%. Αν πχ πρέπει να δουλέψουμε με έναν πίνακα από records που έχουν μέγεθος 97 bytes το καθένα, το καλύτερο που έχουμε να κάνουμε είναι να προσθέσουμε στο τέλος κάθε record όσα bytes χρειάζεται για να φτάσουμε τα 128 bytes.