|
|
|
|
ΕΠΛ 431: Σύνθεση Παράλληλων Αλγορίθμων Εαρινό Εξάμηνο 2011
Σημειώσεις Διαλέξεων |
(Για την ανάγνωση των σημειώσεων χρειάζεται ο adobe acrobat reader. Μπορείτε
να το προμηθευτείτε δωρεάν εδώ)
|
Ενότητα |
Θέμα |
Σημειώσεις |
|
0 |
Εισαγωγή
- Πληροφορίες για το μάθημα |
|
|
1 |
Ασυμπτωτική
ανάλυση, Μαθηματική επαγωγή, Ιδιότητες λογαρίθμων |
[pdf] |
|
2 |
Παράλληλος υπολογισμός/υπολογιστής, Σημαντικότητα
παράλληλου υπολογισμού, Παράλληλος αλγόριθμος (ΠΑ), Πολυπλοκότητα ΠΑ, Μέτρα επίδοσης
ΠΑ, Βέλτιστος ΠΑ |
[pdf] |
|
3 |
Μοντέλα παράλληλου υπολογισμού (MISD, SIMD, MIMD), Τύποι PRAM (EREW, CREW, CRCW), Παράλληλη άθροιση |
[pdf] |
|
4 |
Δίκτυα Αλληλοσύνδεσης (γραμμικό πλέγμα, δακτύλιος,
δυαδικό δένδρο, αστερίας, ορθογώνιο πλέγμα, υπερκύβος), Παράμετροι ΔΑ
(διάμετρος, βαθμός, αριθμός συνδέσμων), Επεκτασιμότητα |
[pdf] |
|
5 |
PRAM vs μοντέλα ΔΑ, Αλγόριθμος μετάδοσης σε EREW
PRAM, Παράλληλος πολλαπλασιασμός πινάκων σε CREW, CRCW & EREW PRAM |
[pdf] |
|
6 |
Παράλληλος προθεματικός υπολογισμός, Αλγόριθμος
για EREW PRAM, Αλγόριθμος για CREW PRAM, βέλτιστος αλγόριθμος για EREW
PRAM |
[pdf] |
|
7 |
Γρήγορος παράλληλος υπολογισμός μεγίστου σε CRCW
PRAM, Μέθοδος της επιταχυνόμενης πτώσης |
[pdf] |
|
8 |
Παράλληλη αναζήτηση σε μη-ταξινομημένες και
ταξινομημένες λίστες, Κάτω φράγμα παράλληλης αναζήτησης |
[pdf] |
|
9 |
Παράλληλη συγχώνευση ταξινομημένων λιστών σε CREW PRAM, Κάτω φράγμα παράλληλης συγχώνευσης |
[pdf] |
|
10 |
Παράλληλη ταξινόμηση σε PRAM & γραμμικό πλέγμα,
Κάτω φράγμα παράλληλης ταξινόμησης |
[pdf] |
|
11 |
Κατάταξη συνδεδεμένης λίστας, 2-χρωματισμός,
ανεξάρτητα σύνολα, αφαίρεση και επαναφορά στοιχείων λίστας |
[pdf] |
|
12 |
Περιήγηση του Euler, Παράλληλη κατασκευή
περιήγησης του Euler, Αλγόριθμος μετατροπής δένδρου σε ριζωμένο
δένδρο, Γρήγορος παράλληλος υπολογισμός συναρτήσεων δένδρων |
[pdf] |
|
13 |
Συστολή
δένδρων, Πράξη συρρίκνωσης, Γρήγορη αποτίμηση αριθμητικών εκφράσεων |
[pdf] |
|
14 |
Συνεκτικές συνιστώσες γράφων, Ψευδοδάσος και οι
ιδιότητες του, Θεώρημα ομαδοποίησης βρόγχων, Γενικός παράλληλος αλγόριθμος
εύρεσης συνεκτικών συνιστωσών, Παράλληλος αλγόριθμος για αραιούς γράφους |
[pdf] |
|
15 |
Μοντέλα χρονισμού, Μειονεκτήματα και αναγκαιότητα
μοντέλου PRAM, Μοντέλο XMT, Πιο ρεαλιστικά μοντέλα
παράλληλου υπολογισμού, Μοντέλο φραγμένου χρονισμού BSP, Αλγόριθμοι αθροίσματος
και μετάδοσης στο μοντέλο BSP |
[pdf] [ΧΜΤ] |
|
16 |
Μοντέλο F-PRAM, Σφάλματα κατάρρευσης,
Εύρωστοι παράλληλοι αλγόριθμοι, Πολυπλοκότητα αλγορίθμων στο F-PRAM, Πρόβλημα Write-All, Εύρωστος αλγόριθμος W |
[pdf] |
|
17 |
Μοντέλο Α-PRAM, Έννοια της ατομικότητας,
Πολυπλοκότητα αλγορίθμων στο A-PRAM, Αλγόριθμος για το Write-All με 2
επεξεργαστές, Αλγόριθμος X |
[pdf] |
Ó Χρύσης Γεωργίου - Ιανουάριος 2012