National and Kapodistrian University of Athens
A Framework for Parallel Programming of Graph Applications Using Optimistic Concurrency Control
Abstract
dc:descriptionΣτην παρούσα διπλωματική εργασία παρουσιάζουμε ένα framework που επιτρέπει στους χρήστες να αναπτύσσουν παράλληλα προγράμματα σε γράφους, υλοποιώντας διαδικασίες ως κλάσεις στην Java. Υποστηρίζονται γράφοι κάθε τύπου ενώ παρέχεται εύκολη πρόσβαση σε αυτούς μέσω ενός API που υλοποιήθηκε με χρήση του Redis [1]. Κάθε διαδικασία μπορεί να δημιουργήσει δευτερεύουσες διαδικασίες αφού ολοκληρωθεί και να επιστρέψει ένα αποτέλεσμα. Ταυτόχρονα, ο χρήστης μπορεί να ορίσει πώς μπορεί να συνδυαστεί αυτό το αποτέλεσμα με τις εξόδους των δευτερευουσών διαδικασιών για να παραχθεί η τελική έξοδος. Το framework χρησιμοποιεί αισιόδοξο έλεγχο ταυτοχρονισμού [2], ώστε να διασφαλίσει ότι δεν παραβιάζεται η ακεραιότητα των δεδομένων, γεγονός που αποκρύπτεται από το API πρόσβασης στους γράφους. Ένας διακομιστής, που καλείται manager server, χρησιμοποιείται για να εκτελεστούν οι διαδικασίες παράλληλα, αναθέτοντας την εκτέλεση τους σε άλλους διακομιστές, που ονομάζονται node servers. Ο manager server μπορεί να δεχτεί αιτήματα για εγγραφή ή διαγραφή ενός node server κατά τη διάρκεια της εκτέλεσης. Όλοι οι διακομιστές αναπτύχθηκαν σε Java 11 ως ανεξάρτητες εφαρμογές Spring Boot [3] και χτίστηκαν χρησιμοποιώντας Docker [4]. Ενδεχόμενες εξωτερικές εφαρμογές μπορούν να υποβάλουν αιτήματα στον manager server για την εκτέλεση διαδικασιών ή να αιτηθούν την δημιουργία διαδικασιών σε όλους τους κόμβους πολλαπλών γράφων. Κάθε node server αναλαμβάνει την εκτέλεση εργασιών και την παραγωγή της τελικής εξόδου των διεργασιών χρησιμοποιώντας πολλαπλά νήματα. Οι node servers εκτελούν τις διεργασίες ως ανεξάρτητες συναλλαγές και εφαρμόζουν τις αλλαγές μόνο αν εξασφαλιστεί ότι δεν υπάρχουν συγκρούσεις μεταξύ συναλλαγών. Σε αντίθετη περίπτωση η εκάστοτε συναλλαγή ματαιώνεται και η διεργασία εκτελείται ξανά. Τέλος, παρουσιάζουμε παραδείγματα χρήσης του framework και αξιολογούμε την απόδοσή του μέσα από ένα σύνολο πειραμάτων. Συμπεραίνουμε ότι το framework παρέχει σημαντικές βελτιώσεις στην απόδοση ακόμα και όταν οι συγκρούσεις είναι συχνές. Καθώς προσθέτουμε node servers, παρατηρούμε ότι ο έλεγχος για συγκρούσεις καθώς και οι εφαρμογή των αλλαγών αποτελούν το μεγαλύτερο μέρος του συνολικού χρόνου εκτέλεσης καθώς εκτελούνται από έναν node server την φορά.
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Τοράκης Μανούσος
- Torakis Manousos
Subjects
dc:subject × 2Rights
- Language dc:language
- Ελληνικά, English, Greek
Identifiers
dc:identifier.*- Identifier
- uoadl:2974075