Μελέτη Τεχνικών Βελτιστοποίησης Για Εφαρμογές Με Μη Κανονικές Προσβάσεις Στη Μνήμη

Abstract

Πολλές σύγχρονες εφαρμογές χαρακτηρίζονται ως memory-bound λόγω ακανόνιστων πρόσβασεων στη μνήμη. Ο αλγόριθμος του Dijkstra ανήκει σε αυτή την κατηγορία εφαρμογών που πάσχουν από αυτού του είδους τις προσβάσεις. Πραγματοποιήσαμε εκτεταμένο profiling στον αλγόριθμο για να ανακαλύψουμε το bottleneck του και χρησιμοποιήσαμε prefetching λογισμικού για να το αντιμετωπίσουμε. Στις περιπτώσεις ακανόνιστων προσβάσεων στη μνήμη, το prefetching λογισμικού παρέχει την δυνατότητα prefetching εκμεταλλευόμενοι τα χαρακτηριστικά του αλγορίθμου. Εν αντιθέσει, οι hardware prefetchers δεν είναι τόσο ευέλικτοι. Σε αυτή τη διατριβή, παρουσιάζουμε το σχήμα Prefetch-Process-Thread-Alternation, το οποίο βασίζεται στο πιο απλό Prefetching Helper Thread σχήμα. Το PPTA χρησιμοποιεί δύο νήματα που εναλλάσσονται μεταξύ μίας φάσης prefetch και μίας φάσης εκτέλεσης, για να αποκρύψει την καθυστέρηση απόκρισης μνήμης που προκαλείται από τα ακανόνιστα μοτίβα πρόσβασης. Αξιολογούμε και τα δύο σχήματα χρησιμοποιώντας δύο διαφορετικές πλατφόρμες, μία από τις οποίες υποστηρίζει simultaneous multithreading. Τα πειράματά μας, σε γράφους με αυξανόμενες πυκνότητες, δείχνουν ότι το PPTA επιτυγχάνει επιτάχυνση έως 1.82 για αραιούς και 1.62 για πυκνούς γράφους.