Παρακαλώ χρησιμοποιήστε αυτό το αναγνωριστικό για να παραπέμψετε ή να δημιουργήσετε σύνδεσμο προς αυτό το τεκμήριο: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/15377
Τίτλος: Αλγόριθμοι Διάσχισης Γράφων Σε Σύγχρονες Πολυπύρηνες Αρχιτεκτονικές
Συγγραφείς: Σταύρος Βώλος
Κοζύρης Νεκτάριος
Λέξεις κλειδιά: αλγόριθμος breadth first search
transactional memory
logtm
tcc
gems
simics
Ημερομηνία έκδοσης: 10-Ιου-2009
Περίληψη: Οι σύγχρονες αρχιτεκτονικές έχουν πλέον ξεφύγει από την χρήση ενός πυρήνα λόγω των τεχνολογικών ορίων που υπάρχουν. Στηρίζονται πλέον στην χρήση πολλαπλών πυρήνων με σκοπό την παράλληλη εκτέλεση νημάτων (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
URI: http://artemis-new.cslab.ece.ntua.gr:8080/jspui/handle/123456789/15377
Εμφανίζεται στις συλλογές:Διπλωματικές Εργασίες - Theses

Αρχεία σε αυτό το τεκμήριο:
Αρχείο ΜέγεθοςΜορφότυπος 
DT2009-0114.pdf865.97 kBAdobe PDFΕμφάνιση/Άνοιγμα


Όλα τα τεκμήρια του δικτυακού τόπου προστατεύονται από πνευματικά δικαιώματα.