ΣΧΕΔΙΑΣΗ ΚΑΙ ΑΝΑΛΥΣΗ ΑΛΓΟΡΙΘΜΩΝ
Χαράλαμπος Κωνσταντόπουλος
Περιγραφή
Το αντικείμενο του μαθήματος είναι ο Παράλληλος Υπολογισμός. Ο Παράλληλος Υπολογισμός αποτελεί πλέον κεντρικό ζήτημα στην ανάπτυξη εφαρμογών οι οποίες εκμεταλλεύονται πλήρως το υλικό των πολυπύρηνων μικροεπεξεργαστών ή των σύγχρονων καρτών γραφικών. Σε μεγαλύτερη κλίμακα, ο παράλληλος υπολογισμός είναι σημαντικός για τον σχεδιασμό εφαρμογών σε Grid ή Cloud Αρχιτεκτονικές καθώς και σε υπολογιστικές εγκαταστάσεις που διαθέτουν πολλές ανεξάρτητες μονάδες υπολογιστών (αρχιτεκτονικές cluster). Στο μάθημα αυτό, θα μελετηθούν τα κυριότερα μοντέλα παράλληλου υπολογισμού που έχουν προταθεί στη βιβλιογραφία, θα παρουσιαστούν οι βασικές τεχνικές ανάπτυξης παράλληλων αλγορίθμων σε αυτά τα μοντέλα ενώ στη συνέχεια θα παρουσιασθούν συγκεκριμένες λύσεις για διάφορα υπολογιστικά προβλήματα. Θα γίνει επίσης επισκόπηση και των πιο σημαντικών βιβλιοθηκών ανάπτυξης λογισμικού για παράλληλο υπολογισμό.
Αναλυτικά, θα μελετηθούν τα ακόλουθα:
• Βασικές αλγοριθμικές τεχνικές για συστήματα κοινής και κατανεμημένης μνήμης:
– Pointer jumping
- Διαίρει και βασίλευε
- Pipelining
- Load Balancing
• Παράλληλοι αλγόριθμοι για
–Bασικά προβλήματα: αναζήτηση, ταξινόμηση κτλ.
–Προβλήματα γραφημάτων: ελάχιστες διαδρομές, συνεκτικές συνιστώσες, ελάχιστο γεννητικό δέντρο
–Αριθμητικοί υπολογισμοί: πολλαπλασιασμός πινάκων, επίλυση γραμμικών εξισώσεων, επίλυση διαφορικών εξισώσεων
–Επεξεργασία εικόνας: αλγόριθμοι τμηματοποίησης (segmentation)
–Υπολογιστική γεωμετρία: convex hull, προβλήματα ορατότητας
– προβλήματα μηχανικής: n-body simulation
• Προγραμματιστικά περιβάλλοντα:
- OpenMP
- Pthreads
- Java threads
- CUDA
- OpenCL
- MPI
Το αντικείμενο του μαθήματος είναι ο Παράλληλος Υπολογισμός. Ο Παράλληλος Υπολογισμός αποτελεί πλέον κεντρικό ζήτημα στην ανάπτυξη εφαρμογών οι οποίες εκμεταλλεύονται πλήρως το υλικό των πολυπύρηνων μικροεπεξεργαστών ή των σύγχρονων καρτών γραφικών. Σε μεγαλύτερη κλίμακα, ο παράλληλος υπολογισμός είναι σημαντικός για τον σχεδιασμό εφαρμογών σε Grid ή Cloud Αρχιτεκτονικές καθώς και σε υπολογιστικές εγκαταστάσεις που διαθέτουν πολλές ανεξάρτητες μονάδες υπολογιστών (αρχιτεκτονικές cluster). Στο μάθημα αυτό, θα μελετηθούν τα κυριότερα μοντέλα παράλληλου υπολογισμού που έχουν προταθεί στη βιβλιογραφία, θα παρουσιαστούν οι βασικές τεχνικές ανάπτυξης παράλληλων αλγορίθμων σε αυτά τα μοντέλα ενώ στη συνέχεια θα παρουσιασθούν συγκεκριμένες λύσεις για διάφορα υπολογιστικά προβλήματα. Θα γίνει επίσης επισκόπηση και των πιο σημαντικών βιβλιοθηκών ανάπτυξης λογισμικού για παράλληλο υπολογισμό.
Αναλυτικά, θα μελετηθούν τα ακόλουθα:
• Βασικές αλγοριθμικές τεχνικές για συστήματα κοινής και κατανεμη
Το αντικείμενο του μαθήματος είναι ο Παράλληλος Υπολογισμός. Ο Παράλληλος Υπολογισμός αποτελεί πλέον κεντρικό ζήτημα στην ανάπτυξη εφαρμογών οι οποίες εκμεταλλεύονται πλήρως το υλικό των πολυπύρηνων μικροεπεξεργαστών ή των σύγχρονων καρτών γραφικών. Σε μεγαλύτερη κλίμακα, ο παράλληλος υπολογισμός είναι σημαντικός για τον σχεδιασμό εφαρμογών σε Grid ή Cloud Αρχιτεκτονικές καθώς και σε υπολογιστικές εγκαταστάσεις που διαθέτουν πολλές ανεξάρτητες μονάδες υπολογιστών (αρχιτεκτονικές cluster). Στο μάθημα αυτό, θα μελετηθούν τα κυριότερα μοντέλα παράλληλου υπολογισμού που έχουν προταθεί στη βιβλιογραφία, θα παρουσιαστούν οι βασικές τεχνικές ανάπτυξης παράλληλων αλγορίθμων σε αυτά τα μοντέλα ενώ στη συνέχεια θα παρουσιασθούν συγκεκριμένες λύσεις για διάφορα υπολογιστικά προβλήματα. Θα γίνει επίσης επισκόπηση και των πιο σημαντικών βιβλιοθηκών ανάπτυξης λογισμικού για παράλληλο υπολογισμό.
Αναλυτικά, θα μελετηθούν τα ακόλουθα:
• Βασικές αλγοριθμικές τεχνικές για συστήματα κοινής και κατανεμη
