Please use this identifier to cite or link to this item: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/8553
Title: Μη-γραμμικοί Μετασχηματισμοί Αποθήκευσης Και Τεχνικές Πρώιμης Ανάκλησης Δεδομένων Για Την Αξιοποίηση Της Τοπικότητας Αναφοράς Σε Σύγχρονες Αρχιτεκτονικές Μικροεπεξεργαστών Με Πολυεπίπεδες Ιεραρχίες Μνημών
Authors: Ευαγγελία Αθανασάκη
Τσανάκας Παναγιώτης
Keywords: ιεραρχία μνήμης
μετασχηματισμός υπερκόμβων (tiling)
μη-γραμμικοί μετασχηματισμοί δεδομένων
δυαδικές μάσκες
πρώιμη ανάκληση δεδομένων
ξεδίπλωμα βρόχων
επιλογή μεγέθους tile
ταυτόχρονη πολυνημάτωση
φορτίο μίας μόνο εφαρμογής
απελευθέρωση πόρων συστήματος από τα άεργα νήματα.
Issue Date: 28-Jul-2006
Abstract: Ένα από τα βασικότερα ζητήματα που έχουν να αντιμετωπίσουν οι αρχιτέκτονες υπολογιστών και οι συγγραφείς μεταγλωττιστών είναι η συνεχώς αυξανόμενη διαφορά επίδοσης μεταξύ του επεξεργαστή και της κύριας μνήμης. Προκειμένου να ξεπεραστεί το πρόβλημα αυτό χρησιμοποιούνται διάφοροι μετασχηματισμοί κώδικα, με στόχο τη μείωση του αριθμού των αστοχιών μνήμης και επομένως τη μείωση του μέσου χρόνου που καθυστερούν οι εφαρμογές περιμένοντας τα δεδομένανα φτάσουν από την κύρια μνήμη. Ο μετασχηματισμός υπερκόμβων χρησιμοποιείται ευρέως στους κώδικες φωλιασμένων βρόχων, αναδιατάσσοντας τη σειρά εκτέλεσης των επαναλήψεων, για τη βελτίωση της τοπικότητας των αναφορών σε δεδομένα μνήμης.Η διατριβή αυτή συμβάλλει στην περαιτέρω αξιοποίηση τηςτοπικότητας αναφοράς για ιεραρχίες μνημών, βελτιστοποιώντας τον τρόπο αναφοράς επαναληπτικών κωδίκων στη μνήμη. Επιχειρεί να ελαχιστοποιήσει τον αριθμό των αστοχιών μνήμης, αναδιατάσσοντας τη σειρά αποθήκευσης των δεδομένων των πολυδιάστατων πινάκων στη μνήμη, ώστε να ακολουθεί τη σειρά προσπέλασής τους από τον κώδικαφωλιασμένων βρόχων, αφότου έχει εφαρμοστεί σε αυτόνμετασχηματισμός υπερκόμβων. Στη μέθοδο μη-γραμμικής αποθήκευσης που αναπτύσσεται, τα δεδομένα των πινάκων χωρίζονται σε ομάδες (blocks) οι οποίες ταυτίζονται με τα tiles του μετασχηματισμού υπερκόμβων, και αποθηκεύονται σε διαδοχικές θέσεις μνήμης. Με τον τρόπο αυτό, η ακολουθία των προσπελάσεων δεδομένων από τον κώδικα βρόχων ευθυγραμμίζεται με τη σειρά αποθήκευσής τους στη μνήμη. Ημετατροπή της πολυδιάστατης δεικτοδότησης των πινάκων στηδεικτοδότηση των μη-γραμμικών διατάξεων δεδομένων που προκύπτουν, γίνεται ταχύτατα με απλές δυαδικές πράξεις πάνω σε "αραιωμένους" ακεραίους. Τα πειραματικά αποτελέσματα και οι προσομοιώσεις αποδεικνύουν ότι η συνολική επίδοση βελτιώνεται σημαντικά, χάρη στη μείωση των αστοχιών μνήμης, όταν συνδυάζεται ο μετασχηματισμόςυπερκόμβων με τις μη-γραμμικές διατάξεις δεδομένων σε ομάδες και την δυαδική δεικτοδότηση των δεδομένων.Η συνέπεια της προτεινόμενης μεθόδου σε ότι αφορά τη συνολική επιτάχυνση του χρόνου εκτέλεσης εξαρτάται σε μεγάλο βαθμό από την επιλογή του κατάλληλου μεγέθους tile. Στην παρούσα διατριβή αναλύεται η διαδικασία παραγωγής των αστοχιών κρυφής μνήμης και TLB στις μη-γραμμικές διατάξεις δεδομένων σε ομάδες. Σύμφωνα με τα αποτελέσματα της ανάλυσης αυτής, επιλέγεται το βέλτιστο μέγεθος tile, με στόχο τη μέγιστη αξιοποίηση του μεγέθους της L1 κρυφήςμνήμης και ταυτόχρονα την αποτροπή των αστοχιών λόγω συγκρούσεων στην κρυφή μνήμη. Αποδεικνύεται ότι σε βελτιστοποιημένους κώδικες, που έχει εφαρμοστεί πρώιμη ανάκληση δεδομένων, ξεδίπλωμα βρόχων, ανάθεση μεταβλητών σε προσωρινούς καταχωρητές και ευθυγράμμιση των διαφορετικών πινάκων, τα tiles, με μέγεθος ίσο με την χωρητικότητα της L1 κρυφής μνήμης, αξιοποιούν την L1 κρυφή μνήμη κατά βέλτιστο τρόπο, ακόμα και στις περιπτώσεις που προσπελαύνονται περισσότεροι από ένας πίνακες δεδομένων. Το προτεινόμενο μέγεθος tile είναι συγκριτικά με άλλες μεθόδους μεγαλύτερο, δίνοντας επιπλέον το πλεονέκτημα του μειωμένου αριθμού αστοχιών λόγω των λανθασμένων προβλέψεων διακλάδωσης των φωλιασμένων βρόχων.Τέλος, ένα άλλο θέμα που δεν είχε μέχρι στιγμής εξεταστεί στην έως τώρα βιβλιογραφία είναι η επίδοση μίας εφαρμογής, όταν αυτή εκτελείται μόνη της σε μηχανήματα που είναι εξοπλισμένα με την τεχνική της Ταυτόχρονης Πολυνημάτωσης. Η τεχνική αυτή είχε προταθεί για τη βελτίωση του ρυθμού εκτέλεσης εντολών μέσω της ταυτόχρονης εκτέλεσης εντολών από διαφορετικά νήματα (τα οποία προέρχονται είτε από διαφορετικές εφαρμογές ή από παραλληλοποιημένες εφαρμογές). Οι πρόσφατες μελέτες έχουν δείξει ότι η ανομοιογένεια των ταυτόχρονα εκτελούμενων νημάτων είναι απότους παράγοντες που επηρεάζουν θετικά την επίδοση των εφαρμογών. Ωστόσο, η επιτάχυνση των παράλληλων εφαρμογών εξαρτάται σε μεγάλο βαθμό από τους μηχανισμούς συγχρονισμού και επικονωνίας μεταξύ των διαφορετικών, αλλά πιθανότατα εξαρτώμενων μεταξύ τους, νημάτων. Επιπλέον, καθώς τα διαφορετικά νήματα των παράλληλων εφαρμογών έχουν στις περισσοτέρες περιπτώσεις όμοιου τύπου εντολές (π.χ.πράξεις κινητής υποδιαστολής, ακέραιες πράξεις, άλματα, κλπ), κατά την εκτέλεσή τους στους κοινούς πορους του συστήματος συνωστίζονται και σειριοποιούνται κατά τη διέλευσή τους μέσα από συγκεκριμένες λειτουργικές μονάδες, με αποτέλεσμα να μην μπορεί να επιτευχθεί σημαντική επιτάχυνση των εφαρμογών. Στη διατριβή αυτή αποτιμώνται και συγκρίνονται η πρώιμη ανάκληση δεδομένων και οπαραλληλισμός επιπέδου νήματος (thread-level parallelism - TLP). Τέλος εξετάζεται η επίδραση των μηχανισμών συγχρονισμού στις πολυνηματικές παράλληλες εφαρμογές που εκτελούνται από επεξεργαστές που διαθέτουν ταυτόχρονη πολυνημάτωση.
URI: http://artemis-new.cslab.ece.ntua.gr:8080/jspui/handle/123456789/8553
Appears in Collections:Διδακτορικές Διατριβές - Ph.D. Theses

Files in This Item:
File SizeFormat 
PD2006-0025.pdf3.24 MBAdobe PDFView/Open


Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.