Βελτιστοποίηση Και Παραλληλοποίηση Κώδικα Για Αλγορίθμους Γράφων

Abstract

Σκοπός της εργασίας αυτής είναι η βέλτιστη δυνατή υλοποίηση καιπαραλληλοποίηση αλγορίθμων γράφων. Οι γραφοθεωρητικοί αλγόριθμοιβρίσκουν ολοένα περισσότερες εφαρμογές, ενώ με την πρόοδο τηςτεχνολογίας η ανάγκη για παράλληλους αλγορίθμους γίνεται επιτακτική.Για τον σκοπό αυτό εξετάζουμε την έννοια της βελτιστοποίησης,κυρίως από την σκοπιά της διαχείρισης της μνήμης καθώς και μερικέςβασικές έννοιες παράλληλων συστημάτων. Επικεντρώνουμε την προσοχήμας στον αλγόριθμο των Floyd - Warshall που επιλύει το πρόβλημα All PairShortest Path. Το πρόβλημα αυτό είναι ιδιαίτερα σημαντικό στηνβιβλιογραφία με ποικίλες εφαρμογές.Μελετούμε τις ιδιαιτερότητες του αλγορίθμου ώστε να σχεδιάσουμεπαραλλαγές του που να εκμεταλλεύονται καλύτερα την διαθέσιμη μνήμηώστε να εκτελούνται πιο γρήγορα. Στην συνέχεια εφαρμόζουμε τις ίδιεςιδέες για σχεδιασμό αντίστοιχων παράλληλων αλγορίθμων.Τα πειραματικά αποτελέσματα είναι ιδιαίτερα ενθαρρυντικά και γιαπεραιτέρω έρευνα