ΠΑΝΕΠΙΣΤΗΜΙΟ ΚΥΠΡΟΥ Τμήμα Πληροφορικής

 

ΕΠΛ 431: Σύνθεση Παράλληλων Αλγορίθμων

 

Περιεχόμενο Μαθήματος

   

 

Ενότητα

Θέματα

1

Ασυμπτωτική ανάλυση, Μαθηματική επαγωγή, Ιδιότητες λογαρίθμων

2

Παράλληλος υπολογισμός/υπολογιστής, Σημαντικότητα παράλληλου υπολογισμού, Παράλληλος αλγόριθμος (ΠΑ), Πολυπλοκότητα ΠΑ, Μέτρα επίδοσης ΠΑ, Βέλτιστος ΠΑ

3

Μοντέλα παράλληλου υπολογισμού (MISD, SIMD, MIMD), Τύποι  PRAM  (EREW, CREW, CRCW),  Παράλληλη άθροιση

4

Δίκτυα Αλληλοσύνδεσης (γραμμικό πλέγμα, δακτύλιος, δυαδικό δένδρο, αστερίας, ορθογώνιο πλέγμα, υπερκύβος), Παράμετροι ΔΑ  (διάμετρος, βαθμός, αριθμός συνδέσμων), Επεκτασιμότητα

5

PRAM vs μοντέλα ΔΑ, Αλγόριθμος μετάδοσης σε EREW PRAM, Παράλληλος πολλαπλασιασμός πινάκων σε CREW, CRCW & EREW PRAM

6

Παράλληλος προθεματικός υπολογισμός, Αλγόριθμος για EREW PRAM, Αλγόριθμος για CREW PRAM,  βέλτιστος αλγόριθμος για EREW PRAM

7

Γρήγορος παράλληλος υπολογισμός μεγίστου σε CRCW PRAM, Μέθοδος της επιταχυνόμενης πτώσης

8

Παράλληλη αναζήτηση σε μη-ταξινομημένες και ταξινομημένες λίστες, Κάτω φράγμα παράλληλης αναζήτησης

9

Παράλληλη συγχώνευση ταξινομημένων λιστών σε CREW PRAM, Κάτω φράγμα παράλληλης συγχώνευσης

10

Παράλληλη ταξινόμηση σε PRAM & γραμμικό πλέγμα, Κάτω φράγμα παράλληλης ταξινόμησης

11

Κατάταξη συνδεδεμένης λίστας, 2-χρωματισμός, ανεξάρτητα σύνολα, αφαίρεση και επαναφορά στοιχείων λίστας

12

Περιήγηση του Euler, Παράλληλη κατασκευή περιήγησης του Euler, Αλγόριθμος μετατροπής δένδρου σε ριζωμένο δένδρο, Γρήγορος παράλληλος υπολογισμός συναρτήσεων δένδρων

13

Συστολή δένδρων, Πράξη συρρίκνωσης, Γρήγορη αποτίμηση αριθμητικών εκφράσεων

14

Συνεκτικές συνιστώσες γράφων, Ψευδοδάσος και οι ιδιότητες του, Θεώρημα ομαδοποίησης βρόγχων, Γενικός παράλληλος αλγόριθμος εύρεσης συνεκτικών συνιστωσών, Παράλληλος αλγόριθμος για αραιούς γράφους 

15

Μοντέλα χρονισμού, Μειονεκτήματα και αναγκαιότητα μοντέλου PRAM, Μοντέλο XMT, Πιο ρεαλιστικά μοντέλα παράλληλου υπολογισμού, Μοντέλο φραγμένου χρονισμού BSP, Αλγόριθμοι αθροίσματος και μετάδοσης στο μοντέλο BSP

16

Μοντέλο F-PRAM, Σφάλματα κατάρρευσης, Εύρωστοι παράλληλοι αλγόριθμοι, Πολυπλοκότητα αλγορίθμων στο F-PRAM,  Πρόβλημα Write-All, Εύρωστος αλγόριθμος W

17

Μοντέλο Α-PRAM, Έννοια της ατομικότητας, Πολυπλοκότητα αλγορίθμων στο A-PRAM, Αλγόριθμος για το Write-All με 2 επεξεργαστές, Αλγόριθμος X

 

Αρχική