Μελέτη Και Αξιολόγηση Του Hardware Transactional Memory Για Παραλληλοποίηση Skip Lists

Abstract

Τα τελευταία χρόνια η ανάγκη για εργαλεία που διευκολύνουν τον παράλληλο προγραμματισμό έχει φέρει το Transactional Memory (TM) στο προσκήνιο. Το ΤΜ απλοποιεί την παραλληλοποίηση πολύπλοκων δομών δεδομένων, όπως Skip Lists, δέντρα, πίνακες κατακερματισμού, κλπ. Στη παρούσα διπλωματική υλοποιούμε παράλληλες δομές δεδομένων Skip List χρησιμοποιώντας Hardware Transactional Memory (ΗΤΜ). Τις μελετάμε πειραματικά και τις συγκρίνουμε με υλοποιήσεις που βασίζονται σε Lock-Based και Lock-Free τεχνικές. Από τη μελέτη αυτή βγάζουμε συμπεράσματα τόσο σε σχέση με την εφαρμογή διαφόρων τεχνικών HTM σε δομές δεδομένων και ουρές προτεραιότητας Skip List, όσο και για την επίδραση που έχουν ορισμένες παράμετροι όπως το Hyper-Threading ή ένα σύστημα NUMA στην λειτουργία HTM υλοποιήσεων. Τέλος, τα αποτελέσματα αναδεικνύουν πλεονεκτήματα και μειονεκτήματα της HTM εκδοχής σε σχέση με τις άλλες τεχνικές καθώς και περιοχές εφαρμογής όπου η HTM υλοποίηση υπερέχει έως και 250% σε απόδοση συγκριτικά με τις υπόλοιπες.