Σχεδιασμός και Υλοποίηση του Μοντέλου LINDA σε Μηχανές Κατανεμημένης Μνήμης

 
This item is provided by the institution :
University of Crete
Repository :
E-Locus Institutional Repository
see the original item page
in the repository's web site and access all digital files if the item*
share




1993 (EN)
Design and implementation of the Linda model on distributed memory machines
Σχεδιασμός και Υλοποίηση του Μοντέλου LINDA σε Μηχανές Κατανεμημένης Μνήμης

Καβακλής, Ιωάννης (EL)
Kavaklis, John (EN)

Σ. Ορφανουδάκης

Ένας από τους πονοκέφαλους στον κόσμο τον παράλληλων συστημάτων είναι ο προγραμματισμός τους. Αντίθετα με το σειριακό μοντέλο προγραμματισμού, όπου ακολουθίες εντολών μας οδηγούν στο τελικό αποτέλεσμα, στον παράλληλο προγραμματισμό, πολλές διεργασίες αλληλεπιδρούν παράλληλα στα δεδομένα. Ακόμα κι αν υποθέσουμε ότι λύνουμε με επιτυχία το πρόβλημα της εύρεσης του κατάλληλου παράλληλου αλγόριθμου για κάθε πρόβλημα, υπάρχει το πρόβλημα της απόδοσής του στη γλώσσα και το μοντέλο που υποστηρίζει η κάθε μηχανή. Ο προγραμματιστής καλείται να μάθει το προγραμματιστικό περιβάλλον που υποστηρίζει η μηχανή, να λύσει το πρόβλημα της ανάθεσης και της δημιουργίας των διεργασιών στους επεξεργαστές, να καταφέρει να συγχρονίσει τις διάφορες διεργασίες ώστε να λάβει χώρα η ανταλλαγή πληροφορίας και τέλος να βρει πού πρέπει να απευθυνθεί η κάθε διεργασία για να βρει αυτήν την πληροφορία. Επιπλέον σε όλα αυτά πρέπει να επισημάνουμε και το θέμα του portability του προγράμματος, μια και διαφορετικές αρχιτεκτονικές έχουν συνήθως και διαφορετικά πρωτόγονα υπολογιστικά και επικοινωνιακά χαρακτηριστικά (primitives). Το πρόβλημα που έχει αντιμετωπιστεί μέχρι σήμερα με σχετική επιτυχία είναι το portability, με τη δημιουργία βιβλιοθηκών που τις υποστηρίζουν πολλές αρχιτεκτονικές και κρύβουν το στρώμα των calls που υποστηρίζει η κάθε μια. Ένα σύστημα που προσπαθεί, και σε μεγάλο βαθμό πετυχαίνει, να αντιμετωπίσει συνολικά το πρόβλημα είναι το μοντέλο προγραμματισμού Linda. Το Linda επιτυγχάνει να αποδεσμεύσει τον προγραμματιστή από το πρόβλημα των χωρικών (πού βρίσκεται το δεδομένο, διεργασία) και χρονικών (πότε πρέπει να γίνει η επικοινωνία και ο συγχρονισμός) αλληλεξαρτήσεων του προγράμματος, ενώ ταυτόχρονα διατίθεται απαράλλαχτο σε πολλές αρχιτεκτονικές. Το Linda προσφέροντας ένα ασυνήθιστο μοντέλο κοινής μνήμης καταφέρνει να είναι ένα από τα καλύτερα μοντέλα δημιουργίας και συγχρονισμού παράλληλων διεργασιών. Όλα αυτά βέβαια δεν γίνονται χωρίς κόστος. Το Linda δεν προσπαθεί να πείσει ότι θα παράγει ένα πρόγραμμα πιο γρήγορο από αυτό που θα έκανε ένας έμπειρος προγραμματιστής χρησιμοποιώντας απευθείας τα calls της μηχανής. Εγγυάται όμως ότι ο χρόνος υλοποίησης θα είναι ελάχιστος, η απόδοση πολύ καλή, ενώ ταυτόχρονα το απαιτούμενο υπόβαθρο γνώσεων παράλληλου προγραμματισμού πολύ μικρό. Το POSYBL είναι μια προσπάθεια υλοποίησης του μοντέλου Linda σε δίκτυο από σταθμούς εργασίας Unix. Εμείς, συνεχίζοντας αυτήν την προσπάθεια αποφασίσαμε να το βελτιώσουμε, πρώτα με τη δημιουργία πρωτόκολλων τοπικής (interprocess) και ενδοδικτυακής (internetwork) επικοινωνίας μεταξύ διεργασιών, και στη συνέχεια βελτιώνοντας τους αλγορίθμους αποθήκευσης, ανεύρεσης και κατανομής των δεδομένων. Το αποτέλεσμα αυτής της προσπάθειας λέγεται NPOSYBL. Χρησιμοποιώντας την πείρα και τα μαθήματα που κερδίσαμε σε αυτήν τη διαδικασία, προχωρήσαμε στη δημιουργία του ΙΣΤΟΣ, μιας υλοποίησης Linda σε παράλληλη αρχιτεκτονική, καθώς και τον προσομοιωτή του σε Sun Workstations. Το ΙΣΤΟΣ ξεφεύγει από το στάδιο της πειραματικής υλοποίησης και παρέχει ένα αξιόπιστο περιβάλλον παράλληλου προγραμματισμού που μπορεί να χρησιμοποιηθεί για ερευνητικούς και εκπαιδευτικούς σκοπούς. (EL)
Linda is an easy-to-use language for parallel programming; it is not based on shared variables or message passing, but it uses a novel communication mechanism called the tuple space. It supports (but does not enforce) a programming methodology based on distributed data structures and replicated workers. The goal of this methodology is to release the programmer from thinking in terms of parallel computations and simultaneous events, hence making parallel programming conceptually similar to sequential programming. POSYBL is a Linda implementation for Unix networks. We decided to extend this work by optimizing the various components of POSYBL. The first step was to improve the network communication between the various processes that take part in the POSYBL program. Network communication is expensive, and the available protocols that the UNIX operating system offers are not suitable for asynchronous reliable message passing between network nodes. We developed our own protocol which is a subset of the VMTP protocol used in the V distributed kernel. The second step was to design and implement an efficient protocol for asynchronous message passing between processes on the same node. For this reason we implemented a protocol that uses shared memory to transfer data between processes, and message queues for the synchronization of the shared memory accesses. The final step was the optimization of the search, distribution and storage of tuples in the tuple space. Regarding storage, a hashing algorithm that uses hashing at two levels was developed. The first level is used to segment the tuple space in orthogonal segments based on the tuple fields. The second level is used for the indexing of tuples in each segment. For the distribution of tuples, statistical information is used to discover the communication pattern of the POSYBL program. This information can be used to avoid unnecessary network traffic. This is achieved by sending the tuples directly to the node that is most likely to search for them. Using the experience of this design, we developed ISTOS Linda. ISTOS Linda is a Linda implementation on a distributed memory parallel machine based on the transputer architecture and the PARIX operating system. Furthermore, a simulator of ISTOS was developed for Sun Workstations using the Sun LWP package. ISTOS uses distributed hashing to distribute the tuples between the nodes of the parallel machine. We have also developed a precompiler that translates the Linda calls to run time library calls. ISTOS is a full implementation of the Linda model. It is a useful and reliable programming tool that can be used for educational and research purposes. (EN)

text
Τύπος Εργασίας--Μεταπτυχιακές εργασίες ειδίκευσης

Παράλληλα και Κατανεμημένα Συστήματα

Πανεπιστήμιο Κρήτης (EL)
University of Crete (EN)

1993-12-01
1997-06-2


Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Επιστήμης Υπολογιστών--Μεταπτυχιακές εργασίες ειδίκευσης



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)