Μελέτη Και Αξιολόγηση Transactional Memory Σε Αλγορίθμους Άμορφου Παραλληλισμού

Abstract

Οι πολυπύρηνες αρχιτεκτονικές είναι ο κυρίαρχος τρόπος σχεδιασμού επεξεργαστών σήμερα. Οι νέοι επεξεργαστές κατασκευάζονται με όλο και αυξανόμενο αριθμό πυρήνων καθιστώντας τα υπολογιστικά συστήματα ικανά για επεξεργασία δεκάδων νημάτων. Ο προγραμματισμός ενός πολυπύρηνου συστήματος δεν είναι ίδιος σε σχέση με έναν μονοπύρηνο. Για να είναι δυνατή η πλήρης αξιοποίηση του διαθέσιμου υλικού, ο αλγόριθμος πρέπει να κάνει σαφείς διακρίσεις σε ανεξάρτητες εργασίες προς εκτέλεση. Διαφορετικοί αλγόριθμοι έχουν και διαφορετική παράλληλη συμπεριφορά, με ένα κύριο χαρακτηριστικό να είναι πόσο ευκολά υλοποιείται ο συγχρονισμός στο εκτελούμενο πρόγραμμα.Στην εργασία αυτή θα μελετηθούν αλγόριθμοι γράφων που παρουσιάζουν άμορφη πρόσβαση στα κοινά δεδομένα, υλοποιούμενοι σε worklist λογική για την αξιοποίηση του παραλληλισμού τους. Ο συγχρονισμός θα υλοποιηθεί μέσω Transactional Memory, και θα συγκριθεί με μια software lock-free τεχνική που υλοποιείται στο σύστημα Galois, πάνω στο οποίο θα γίνει και η εκτέλεση τους. Τέλος, θα αναλυθεί και θα σχολιαστεί η απόδοση τους σε πολυπύρηνα συστήματα, σε σχέση με την τεχνική του Galois.