Μελέτη Και Αξιολόγηση Του Tsx Στους Haswell Επεξεργαστές Της Intel: Παραλληλοποίηση Red Black Tree

Abstract

Έχουμε πλέον φτάσει στην εποχή που όλοι οι επεξεργαστές στηρίζονται σε πολυπύρηνες αρχιτεκτονικές για να μπορέσουν να αυξήσουν την απόδοσή τους και να παρακάμψουν τους τεχνολογικούς περιορισμούς που συναντούσαν τα μονοπύρηνα συστήματα. Ωστόσο η ταυτόχρονη αξιοποίηση πολλαπλών πυρήνων από μια εφαρμογή δεν είναι εύκολη διαδικασία.Στην προσπάθεια να υλοποιήσουμε παράλληλα προγράμματα που θα χρησιμοποιούν πολλαπλά νήματα (threads), ώστε να εκμεταλλεύονται όλους τους πυρήνες του επεξεργαστή ήρθαμε μπροστά στην πρόκληση του συγχρονισμού τους στις προσβάσεις σε κοινή μνήμη. Ο συγχρονισμός αυτός αποδείχτηκε μια περίπλοκη και δύσκολη διαδικασία. Οι συμβατικοί τρόποι συγχρονισμού περιόρισαν την απόδοση των παράλληλων προγραμμάτων και οδήγησαν στην αναζήτηση νέων καλύτερων μεθόδων που θα προσφέρουν μεγαλύτερη κλιμακωσιμότητα.Την λύση στο πρόβλημα αυτό φαίνεται να δίνει το Transactional Memory. Πιο συγκεκριμένα το Hardware Transactional Memory υπόσχεται να δώσει ένα εύρωστο, απλό και κλιμακώσιμο τρόπο για συγχρονισμό παράλληλων νημάτων σε κοινή μνήμη. Μέσα από τους Haswell επεξεργαστές της Intel που προσφέρουν για πρώτη φορά σε εμπορική μορφή μια υλοποίηση Hardware Transactional Memory, θέλουμε να εξετάσουμε τις δυνατότητές του, να δούμε τα πλεονεκτήματά του, αλλά και τους περιορισμούς που εισάγει η χρήση του.Ο πειραματισμός και η αξιολόγηση του Hardware Transactional Memory των Haswell επεξεργαστών γίνεται μέσα από την παραλληλοποίηση δομών Red Black Tree. Τα Red Black Trees είναι γνωστά για την περίπλοκη δομή τους και την δυσκολία παραλληλοποίησής τους, με τις μέχρι σήμερα συμβατικές μεθόδους συγχρονισμού.