Παράλληλοι Αλγόριθμοι
Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής, Πανεπιστήμιο Πατρών
Αρχική › Γενικές Πληροφορίες

Γενικές πληροφορίες

 

Προγραμματισμένη ώρα και αίθουσα διαλέξεων: δείτε ωρολόγιο πρόγραμμα

Ακαδημαϊκό ημερολόγιο 2020-2021

Ο παράλληλος υπολογισμός προϋποθέτει την ύπαρξη πολλών επεξεργαστών (ή υπολογιστών) που δουλεύουν μαζί για ένα κοινό πρόβλημα. Κάθε επεξεργαστής δουλεύει για μέρος του προβλήματος που του έχει ανατεθεί. Οι επεξεργαστές μπορούν να ανταλλάσσουν πληροφορία. Στον ακολουθιακό υπολογισμό (όταν δηλ., υπάρχει ένας επεξεργαστής), το λογισμικό και το υλικό στο οποίο εκτελείται ακολουθεί το μοντέλο RAM που βασίζεται στο μοντέλο αποθηκευμένου προγράμματος (stored program model) του Von Neumann.

Πολλές διεργασίες στη φύση και την καθημερινότητα ενέχουν παραλληλισμό, π.χ., καιρικά φαινόμενα, κίνηση τεκτονικών πλακών, σχηματισμός γαλαξιών, οδική κυκλοφορία, συναρμολόγηση αυτοκινήτων, κατασκευή αεροσκαφών, κτλ. Παράλληλος υπολογισμός χρησιμοποιείται σε πολλές περιοχές έρευνας και ανάπτυξης (όπως Επιστήμη των Υπολογιστών, Μαθηματικά, Ηλεκτρολογία, Μηχανολογία, Φυσική, Βιοεπιστήμες, Βιοτεχνολογία, Γενετική, Χημεία, Γεωλογία, Σεισμολογία, κτλ).
Ειδικά, στην Επιστήμη των Υπολογιστών, παράλληλος υπολογισμός χρησιμοποιείται για εργασίες όπως εξόρυξη πληροφορίας, αναζήτηση στον Παγκόσμιο Ιστό, επεξεργασία εικόνας, εικονική πραγματικότητα, χρηματική και οικονομική μοντελοποίηση, διαχείριση οργανισμών, δικτυακές τεχνολογίες video και πολυμέσων, συνεργατικά περιβάλλοντα εργασίας.

Ο παράλληλος υπολογισμός χρησιμοποιείται προκειμένου να ξεπερατούν οι περιορισμοί που επιβάλλονται από τον ακολουθιακό υπολογισμό και ειδικότερα για για εξοικονόμηση χρόνου και χρηματικών δαπανών, για επίλυση μεγάλων προβλημάτων, για εξασφάλιση ταυτόχρονης πρόσβασης σε πληροφορίες/υπηρεσίες καθώς και για χρήση μη τοπικών πληροφοριών (π.χ., SETI@home).

Στο πλαίσιο του μαθήματος εξετάζεται η έννοια, η εφαρμογή και η αποδοτικότητα του παραλληλισμού στο σχεδιασμό και την εκτέλεση υπολογιστικών εργασιών (αλγορίθμων)

Τα προβλήματα και οι αντίστοιχοι αλγόριθμοι που μελετώνται περιλαμβάνουν υπολογιστικές εργασίες που γίνονται μέσα σε ένα ολοκληρωμένο κύκλωμα (chip) ή σε ένα μικροεπεξεργαστή, όπως π.χ., ταξινόμηση, μέτρηση, πρόσθεση, πολλαπλασιασμός, υπολογισμός προθεμάτων, συνέλιξη, κτλ, υπολογιστικές εργασίες που γίνονται σε ένα υπολογιστικό σύστημα, όπως π.χ., ταξινόμηση, δρομολόγηση, κτλ και άλλες υπολογιστικές εργασίες σχετικές με επικοινωνία σε δίκτυα δεδομένων, κατανομή πόρων, κτλ.

Εξετάζονται διάφορες μορφές δικτύων σταθερών συνδέσεων όπως γραμμές, πλέγματα, δέντρα, υπερκύβους, πεταλούδες.

Οι προτεινόμενοι παράλληλοι αλγόριθμοι αναλύονται ως προς την επιτάχυνση που επιτυγχάνουν σε σύγκριση με τους αντίστοιχους ακολουθιακούς, την αποδοτικότητα και το έργο τους, δηλ., το πόσο ομοιόμορφα χρησιμοποιούνται οι διαθέσιμοι πόροι. Χρησιμοποιείται ασυμπτωτική ανάλυση για την εκτίμηση της απόδοσης μέσω υπολογισμό άνω και κάτω φραγμάτων. Η ανάλυση είναι κυρίως θεωρητική αλλά μπορεί να στηριχθεί και σε πειραματισμό

.