E-Locus - Ιδρυματικό Καταθετήριο Πανεπιστημίου Κρήτης

Αρχική Αναζήτηση

Αποτελέσματα - Λεπτομέρειες

Εντολή Αναζήτησης : Συγγραφέας="Κιοστεράκης" Και Συγγραφέας="Χαρίδημος" Και Συγγραφέας="Μ."

Τρέχουσα Εγγραφή: 1 από 1

[Προσθήκη στο καλάθι]

Κωδικός Πόρου

000429246

Τίτλος

Efficient implementations of concurrent snapshot objects

Άλλος τίτλος

Αποδοτικές υλοποιήσεις ατομικών στιγμιοτύπων κοινόχρηστης μνήμης

Συγγραφέας

Κιοστεράκης, Χαρίδημος Μ.

Σύμβουλος διατριβής

Κατεβαίνης, Μανώλης
Καλλιμάνης, Νικόλαος

Μέλος κριτικής επιτροπής

Μαρκάτος, Ευάγγελος
Μαγκούτης, Κωνσταντίνος

Περίληψη

Την τελευταία δεκαετία έχει αυξηθεί αισθητά η χρήση των πολυπύρηνων συστημάτων, οι εφαρμογές των οποίων καλύπτουν ένα ευρύ φάσμα, όπως έξυπνα τηλέφωνα και υπολογιστές έως διακομιστές σε σύγχρονα πληροφοριακά κέντρα. Τα πολυπύρηνα συστήματα παρέχουν καλύτερες επιδόσεις μόνο υπό την προϋπόθεση ότι οι εφαρμογές τους μπορούν να χρησιμοποιήσουν τις δυνατότητες πολλαπλών υπολογιστικών πυρήνων. Ωστόσο αυτό δεν είναι τετριμμένο, μιας που ο παράλληλος προγραμματισμός είναι αρκετά δυσκολότερος από τον σειριακό. Η χρήση αποδοτικών κοινόχρηστων δομών δεδομένων ωστόσο, δίνει τη δυνατότητα πλήρους αξιοποίησης των πόρων ενός πολυπύρηνου συστήματος. Μια διαδεδομένη κοινόχρηστη δομή δεδομένων είναι τα ατομικά στιγμιότυπα τα οποία και έχουν πληθώρα εφαρμογών στην επιστήμη των υπολογιστών. Τα ατομικά στιγμιότυπα μπορούν να χρησιμοποιηθούν για την επίλυση προβλημάτων, όπου συγκεκριμένες ενέργειες πρέπει να γίνουν όταν η κατάσταση του συστήματος ικανοποιεί κάποιες συνθήκες. Επιπρόσθετα, η χρήση ατομικών στιγμιοτύπων είναι ιδιαίτερα διαδεδομένη για την σχεδίαση αλλά και τον έλεγχο ορθότητας κοινόχρηστων δομών δεδομένων, όπως στην κατασκευή concurrent timestamps ή randomized consensus. Ένα ατομικό στιγμιότυπο αποτελείται από 𝑚 συνιστώσες, οι οποίες αποθηκεύουν μια τιμή από ένα προκαθορισμένο σύνολο τιμών. Οι διεργασίες μπορούν να τροποποιούν ή/και να διαβάζουν τα αποθηκευμένα δεδομένα του αντικειμένου μέσα από την κλήση των διαδικασιών 𝑈𝑃𝐷𝐴𝑇𝐸 και 𝑆𝐶𝐴𝑁. Η 𝑈𝑃𝐷𝐴𝑇𝐸 δίνει τη δυνατότητα στις διεργασίες να τροποποιήσουν την τιμή μιας συνιστώσας θέτοντας σε αυτή μια τιμή από το προκαθορισμένο σύνολο τιμών. Από την άλλη, η 𝑆𝐶𝐴𝑁 επιστρέφει ένα συνεπές αντίγραφο των τιμών όλων των συνιστωσών του στιγμιότυπου. Στην παρούσα εργασία μελετάμε διάφορες κατηγορίες ατομικών στιγμιότυπων. Πρώτα μελετάμε τα singlescanner στιγμιότυπα, σε αυτές τις υλοποιήσεις μόνο μια ενεργή 𝑆𝐶𝐴𝑁 επιτρέπεται να υπάρχει στο σύστημα οποιαδήποτε χρονική στιγμή, ταυτόχρονα το σύστημα όμως υποστηρίζει την συνύπαρξη πολλών 𝑈𝑃𝐷𝐴𝑇𝐸. Μια δεύτερη κατηγορία είναι τα multiscanner στιγμιότυπα, όπου αυτά υποστηρίζουν ανά πάσα χρονική στιγμή την ύπαρξη στο σύστημα πολλών 𝑈𝑃𝐷𝐴𝑇𝐸 αλλά και 𝑆𝐶𝐴𝑁. Μια ιδιαίτερη περίπτωση, των multi-scanner είναι τα λ-scanner στιγμιότυπα, όπου αυτά υποστηρίζουν 𝜆 ενεργές 𝑆𝐶𝐴𝑁 ανά πάσα χρονική στιγμή και οσοδήποτε πολλές 𝑈𝑃𝐷𝐴𝑇𝐸. Όταν το 𝜆 είναι ίσο με το συνολικό πλήθος διεργασιών σε ένα σύστημα τότε ένα 𝜆 − 𝑠𝑐𝑎𝑛𝑛𝑒𝑟 ατομικό στιγμιότυπο είναι ταυτόσημο με ένα multi-scanner. Στην παρούσα εργασία, παρουσιάζονται δύο wait-free υλοποιήσεις ατομικών στιγμιότυπων. Η πρώτη αποτελεί υλοποίηση ενός single-scanner στιγμιότυπου ενώ η δεύτερη είναι υλοποίηση ενός λ-scanner στιγμιότυπου. Τόσο η χρονική τους πολυπλοκότητα όσο και η χωρική τους πολυπλοκότητα είναι γραμμική συνάρτηση του 𝜆. Επιπρόσθετα, οι υλοποιήσεις μας έχουν σχετικά χαμηλή χωρική πολυπλοκότητα θυσιάζοντας μέρος της χρονικής πολυπλοκότητας. Η χαμηλή χωρική πολυπλοκότητα που παρέχουν οι υλοποιήσεις μας τις καθιστούν ελκυστικές σε εφαρμογές πραγματικών συστημάτων. Αρχικά παρουσιάζεται μια απλή υλοποίηση ενός single-scanner στιγμιότυπου, την οποία ονομάζουμε 1 − 𝑂𝑃𝑇. Αυτή η υλοποίηση χρησιμοποιεί 𝑂(𝑚) 𝐶𝐴𝑆 καταχωρητές. Η 𝑈𝑃𝐷𝐴𝑇𝐸 έχει χρονική πολυπλοκότητα 𝛰(1), ενώ η 𝑆𝐶𝐴𝑁 𝑂(𝑚). Τέλος παρουσιάζεται μια υλοποίηση ενός λ-scanner στιγμιότυπου, την οποία ονομάζουμε 𝜆 − 𝑂𝑃𝑇. Αυτή η υλοποίηση χρησιμοποιεί 𝛰(𝜆𝑚) καταχωρητές μη πεπερασμένου μεγέθους. Η χρονική πολυπλοκότητα της 𝑈𝑃𝐷𝐴𝑇𝐸 είναι 𝛰(𝜆) ενώ εκείνη της 𝑆𝐶𝐴𝑁 είναι μόλις 𝛰(𝜆𝑚).

Φυσική περιγραφή

xvi, 48 σ. : σχεδ., πιν., εικ ; 30 εκ.

Γλώσσα

Αγγλικά

Θέμα

Concurrent algorithms

Concurrent data structures

Κατανεμημένες δομές δεδομένων

Κατανεμημένος αλγόριθμος

Στιγμιότυπα

Ημερομηνία έκδοσης

2020-03-27