Τα τελευταία χρόνια έχουν γίνει σημαντικές προσπάθειες o Πληροφορικός-Επιστήμονας των Υπολογισμών να εκθέσει με εύληπτο τρόπο τη γνώση και εμπειρία του στις κοινότητες εκείνων που θέλουν να κάνουν υπολογισμούς. Κάτι τέτοιο έχει καταστεί δυνατό με την κατασκευή σύνθετων στη δομή, αλλά εύκολων στη χρήση, εργαλείων-περιβαλλόντων υπολογισμού στα οποία κανείς μπορεί με εντελώς φυσικό τρόπο να προδιαγράψει το πρόβλημά του και -ανάλογα με την εμπειρία του- να επέμβει στη ροή επίλυσής του. Τα Περιβάλλοντα Επίλυσης Προβλημάτων (ΠΕΠ) προβάλλουν λοιπόν ως μια πολύ ελκυστική λύση για τον επιστήμονα των εφαρμογών που αναζητεί μια εύχρηστη, ισχυρή και αξιόπιστη πλατφόρμα λογισμικού για τους υπολογισμούς του.
Σε πολλές περιπτώσεις αυτοί οι υπολογισμοί είναι πολύ μεγάλης κλίμακας και απαιτούν πολυάριθμους και αποδοτικούς πόρους. Η τιθάσευσή τους σε κάποια έκταση έγινε δυνατή με τη στροφή σε παράλληλες-κατανεμημένες αρχιτεκτονικές, πρόσφατα μεγάλης κλίμακας, με έμφαση στην ευχρηστία, στην ασφάλεια πρόσβασης και στη συνεργατικότητα (Πλέγμα (Grid)). Σε άλλες περιπτώσεις οι πολυπύρηνοι επεξεργαστές που εξοπλίζουν πλέον τους τυπικούς οικιακούς υπολογιστές μας και οι προβλέψεις για αθρόα κλιμάκωση του αριθμού των προσφερόμενων πυρήνων, προτρέπουν σε επαναδιαπραγμάτευση κλασικών αλγορίθμων με στόχευση στην εξαγωγή παραλληλίας, αφού πλέον αυτή μπορεί να απεικονιστεί άμεσα στο διαθέσιμο υλικό. Επιπρόσθετα μια τέτοια στροφή ώθησε και τη διερεύνηση εναλλακτικών μοντέλων υπολογισμού: Το ασύγχρονο μοντέλο υπολογισμού προσφέροντας τη δυνατότητα για εξάλειψη των χρονοβόρων φάσεων συγχρονισμού των πολλαπλών μονάδων επεξεργασίας προβάλλει ως μια ενδιαφέρουσα επιλογή.
Συστηματοποιούμε τη μελέτη των Περιβαλλόντων Επίλυσης Προβλημάτων (ΠΕΠ) εντοπίζοντας τους άξονες που χαρακτηρίζουν αυτήν την κατηγορία συστημάτων λογισμικού και υλοποιώντας το Jylab, ένα πρωτότυπο ΠΕΠ με έμφαση στη φορητότητα, την επαναχρησιμοποίηση ελεύθερα διαθέσιμου κώδικα και τη δυνατότητα για ακολουθιακό, παράλληλο και κατανεμημένο υπολογισμό σε πολλαπλές πλατφόρμες. Ειδικότερα, το Jylab περιλαμβάνει υποστήριξη για ασύγχρονο κατανεμημένο υπολογισμό, ανάλυση ιστογραφημάτων και εκτέλεση υπολογισμών στο Πλέγμα (Grid).
Αμέσως μετά εισάγουμε το ασύγχρονο μοντέλο υπολογισμού εστιάζοντας σε καίρια ζητήματα όπως η ανάλυση της σύγκλισης, η ανίχνευση του τερματισμού και η υλοποίησή του. Προτείνουμε πιθανοτικό πλαίσιο εντοπισμού της σύγκλισης και διερευνούμε την πολυπλοκότητα του μοντέλου.
Στη συνέχεια μελετούμε αλγορίθμους διάταξης των κόμβων ενός γραφήματος, επικεντρώνοντας στον υπολογισμό του διανύσματος του PageRank το οποίο χρησιμοποιεί η Google για να διατάξει τα αποτελέσματα μιας ερώτησης που υποβάλλουμε στη μηχανή αναζήτησής της.
Αποδεικνύουμε πως και άλλες μέθοδοι διάταξης, οι οποίες εκφράζονται πρωταρχικά ως δυναμοσειρές ενός τροποποιημένου μητρώου συνδέσμων μπορούν να γραφτούν ως γινόμενα των επαναληπτικών μητρώων που χρησιμοποιούνται στον υπολογισμό του διανύσματος PageRank, αλλά με διαφορετική παράμετρο σε κάθε όρο τους (μέθοδος της πολυπαραμετρικής απόσβεσης).
Στη συνέχεια εκθέτουμε την πειραματική συμπεριφορά του ασύγχρονου μοντέλου, όπως αυτή προκύπτει από υλοποιήσεις κυρίως του αλγορίθμου του PageRank, σε διάφορες πλατφόρμες (τοπικά, στη συστάδα υπολογισμών και στο Πλέγμα (Grid)) και με μονάδες εκτέλεσης νήματα ή διεργασίες. To Jylab χρησιμοποιήθηκε εντατικά σε αυτές τις διερευνήσεις και αποδείχτηκε πως όλοι οι πειραματισμοί μπορούν να τεθούν κάτω από ενιαίο πλαίσιο λογισμικού.
Επίσης εισάγουμε μια κλάση αλγορίθμων κατανεμημένου υπολογισμού στατιστικών μεγεθών, τους gossip αλγορίθμους, σε κάθε στοιχειώδες βήμα των οποίων μόνο δύο οντότητες επικοινωνούν και υπολογίζουν. Επεκτείνουμε αυτούς τους αλγορίθμους επιτρέποντας σε k > 2 οντότητες να αλληλεπιδρούν ανά βήμα, προσομοιώνουμε τη συμπεριφορά τους και προτείνουμε πρωτόκολλα υλοποίησής τους. / In recent years computational scientists strive to expose their knowledge and experience to the communities of people interested in performing computations. This endeavor focuses on the construction of complex in structure, however simple in use, toolchains and environments in which a researcher can specify his or her problem and - depending on his experience - change its exact solution flow.
In many cases these computations necessitate large-scale and performant resources. Harnessing them, to some extent, became possible by turning to parallel-distributed architectures, recently of large scale, emphasizing usability, security in accessing them and collaboration perspectives (Grid). In other cases, the multicore processors, nowadays powering even typical personal computers, coupled with predictions for dramatic increase in the number of available cores in the near future, suggest a reconsideration of classic algorithms aiming at extracting parallelism, since this can be directly mapped to underlying hardware. Additionally, such a move, also fuels the investigation of alternative computation models: The asynchronous computation model, offering the flexibility for the complete removal of time-consuming synchronization phases, is a very interesting option.
We study Problem Solving Environments (PSEs) in a systematic manner, specifying the axes characterizing this category of systems of software also implementing Jylab, a prototype PSE emphasizing portability and the reuse of freely available code and enabling sequential, parallel and distributed computing over multiple platforms. More specifically, Jylab includes support for asynchronous distributed computations, Web graph analysis and Grid computing.
Then we introduce the asynchronous computation model, focusing in three core subjects, namely its convergence analysis, the termination detection problem and its implementation. We propose a probabilistic framework for convergence detection and explore the complexity of the model.
Afterwards, we survey algorithms for ranking the nodes of a graph, focusing on computing the PageRank vector, which is used by Google for ranking the results of a query submitted to its search engine.
We prove that a whole class of ranking methods, primarily expressed as a power series of a modified link matrix can be written as products of iterative matrices similar to those used in computing the PageRank vector, albeit with a different damping parameter for each of its terms (multidamping).
Next, we present the experimental behavior of the asynchronous model, mainly as applied in computing the PageRank vector, over different platforms (locally, in a computer cluster and over the Grid) using either threads or processes as its units of execution. Jylab was intensively used in these investigations and it was proved that all experimentations can be cast under a unifying software framework.
We also introduce a class of algorithms for the distributed computation of statistical quantities, namely gossip algorithms, for which only two entities communicate and compute at each elementary step. We extend these algorithms be permitting k > 2 entities to interact on a per elementary step basis, simulate their behavior and propose protocols for implementing them.
| Identifer | oai:union.ndltd.org:upatras.gr/oai:nemertes:10889/2525 |
| Date | 11 January 2010 |
| Creators | Κόλλιας, Γεώργιος |
| Contributors | Γαλλόπουλος, Ευστράτιος, Kollias, Georgios, Γαλλόπουλος, Ευστράτιος, Χούστης, Ηλίας, Τριανταφύλλου, Παναγιώτης, Παπαθεοδώρου, Θεόδωρος, Βαρβαρίγος, Εμμανουήλ, Ζαρολιάγκης, Χρήστος, Κακλαμάνης, Χρήστος |
| Source Sets | University of Patras |
| Language | gr |
| Detected Language | Greek |
| Type | Thesis |
| Rights | 0 |
| Relation | Η ΒΥΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. |
Page generated in 0.0032 seconds