Αλγόριθμοι Διάσχισης Γράφων Σε Σύγχρονες Πολυπύρηνες Αρχιτεκτονικές

Abstract

Οι σύγχρονες αρχιτεκτονικές έχουν πλέον ξεφύγει από την χρήση ενός πυρήνα λόγω των τεχνολογικών ορίων που υπάρχουν. Στηρίζονται πλέον στην χρήση πολλαπλών πυρήνων με σκοπό την παράλληλη εκτέλεση νημάτων (threads), ώστε να αυξηθεί η απόδοση του συστήματος (ένα νήμα σε κάθε πυρήνα). Περισσότερα του ενός νήματος, μπορούν να εκτελεστούν ταυτόχρονα σε κάποιο πυρήνα του επεξεργαστή, αν αυτός υποστηρίζει SMT (simultaneous multi-threading) αρχιτεκτονική. Η κοινή μνήμη, που υπάρχει στους πολυπύρηνους επεξεργαστές, εισάγει περιορισμούς στην παράλληλη εκτέλεση μιας πολυνηματικής εφαρμογής. Η ύπαρξη πολλαπλών νημάτων, τα οποία ζητούν αρκετές φορές πρόσβαση στις ίδιες διευθύνσεις μνήμης, απαιτεί κάποιο είδος συγχρονισμού των νημάτων, έτσι ώστε να διατηρηθεί η συνέπεια της εφαρμογής και τα αποτελέσματα της να είναι τα ίδια με την σειριακή εκτέλεση της. Ενώ το fine-grain locking δίνει καλή επίδοση, αλλά είναι επιρρεπής σε λάθη π.χ deadlocks, ενώ το coarse-grain locking είναι εύκολο, αλλά δίνει χαμηλή επίδοση.Ένα νέο προγραμματιστικό μοντέλο, το οποίο έχει κάνει την εμφάνιση του τα τελευταία χρόνια, είναι η Transactional Memory και έχει σκοπό την επίλυση των προβλημάτων, που εισάγει ο πολυνηματικός προγραμματισμός. Σκοπός της διπλωματικής εργασίας είναι η μελέτη των σύγχρονων αρχιτεκτονικών, που εισάγουν την Transactional Memory και επίσης την αξιολόγηση εκτέλεσης αλγορίθμων διάσχισης γράφων σε σύστημα που υποστηρίζει Hardware Transactional Memory. Η σειριακή φύση των αλγορίθμων διάσχισης γράφων περιορίζει την βελτίωση της παράλληλης υλοποίησης με την χρήση mutex-locking, ενώ αρκετές φορές η υλοποίηση αυτή είναι χειρότερη από την σειριακή. Συγκεκριμένα μελετάται η δυνατότητα βελτίωσης, που δίνει ο πολυνηματικός προγραμματισμός, χρησιμοποιώντας Transactional Memory στον αλγόριθμο διάσχισης γράφου κατά πλάτος (Breadth First Search).Εξετάζουμε την συμπεριφορά διαφορετικών υλοποιήσεων του αλγορίθμου BFS χρησιμοποιώντας τον εξομοιωτή GEMS v.2.1 (General Execution-Driven Multiprocessor Simulator) του Πανεπιστημίου του Wisconsin σε συνδυασμό με τον εξομοιωτή Simics v.3.0.31. O εξομοιωτής Simics παρέχει την εξομοίωση πολυπύρηνου επεξεργαστή αρχιτεκτονικής SPARC, ο οποίος τρέχει το λειτουργικό σύστημα Solaris. H μονάδα Ruby του GEMS παρέχει λεπτομερής εξομοίωση της ιεραρχίας μνήμης του συστήματος και φορτώνεται στον Simics. Hardware Transactional Memory υποστηρίζεται από τον GEMS μέσω του συστήματος LogTM