Your browser does not support JavaScript!

Αρχική    Συλλογές    Τύπος Εργασίας    Μεταπτυχιακές εργασίες ειδίκευσης  

Μεταπτυχιακές εργασίες ειδίκευσης

Εντολή Αναζήτησης : Συγγραφέας="Στεφανίδης"  Και Συγγραφέας="Κωνσταντίνος"

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

Πίσω στα Αποτελέσματα Προηγούμενη σελίδα
Επόμενη σελίδα
Προσθήκη στο καλάθι
[Προσθήκη στο καλάθι]
Κωδικός Πόρου 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
Συλλογή   Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Επιστήμης Υπολογιστών--Μεταπτυχιακές εργασίες ειδίκευσης
  Τύπος Εργασίας--Μεταπτυχιακές εργασίες ειδίκευσης
Μόνιμη Σύνδεση https://elocus.lib.uoc.gr//dlib/4/0/f/metadata-dlib-1586248430-183641-3758.tkl Bookmark and Share
Εμφανίσεις 320

Ψηφιακά τεκμήρια
No preview available

Δεν έχετε δικαιώματα για να δείτε το έγγραφο.
Δεν θα είναι διαθέσιμο έως: 2021-03-27