53
3.5 Παραλληλοποίηση
Για την παράλληλη εκτέλεση του αλγορίθμου χρησιμοποιείται το MPI [28]. To MPI
κάνει χρήση διεργασιών που επικοινωνούν μεταξύ τους με στόχο την επιτάχυνση της
εκτέλεσης του κώδικα. Οι διεργασίες εκτελούν τον ίδιο κώδικα με τη σειριακή εκτέλεση και
βασίζονται στον προγραμματιστή να ορίσει διαφορετική είσοδο για την κάθε διεργασία, ώστε
να παράγει διαφορετικά αποτελέσματα. Οι επιμέρους είσοδοι για κάθε διεργασία καθορίζονται
με την επικοινωνία μεταξύ των διεργασιών λαμβάνοντας υπόψη των αριθμό των διεργασιών
που χρησιμοποιεί ο κάθε χρήστης. Σημαντικό είναι η επικοινωνία μεταξύ των διεργασιών να
αποφεύγεται, αν δεν είναι απαραίτητη, καθώς επιβραδύνει την εκτέλεση του κώδικα. Στον
παρόντα αλγόριθμο απαιτείται η χρήση τουλάχιστον δυο διεργασιών. Η πρώτη διεργασία
χρησιμοποιείται για να συγκεντρώνει τους υπολογισμούς των άλλων διεργασιών, ενώ οι
υπόλοιπες διεργασίες αναλαμβάνουν τους υπολογισμούς της ορατότητας. Αρχικά, για την
είσοδο των διεργασιών χωρίζεται το DEM σε κομμάτια με ίσο εμβαδό, τα οποία μοιράζονται
σε όλες τις διεργασίες, εκτός από την πρώτη. Κάθε διεργασία εκτελεί τον αλγόριθμο για το
κομμάτι που έχει αναλάβει και υπολογίζει την ορατότητα του.
Σχήμα 36 Παράδειγμα διαχωρισμού του DEM για την παράλληλη εκτέλεση του σε αλγορίθμου σε τομείς A, B,
C, D, E με βάση τον παρατηρητή στο σημείο Ο.
Ο διαχωρισμός των κομματιών για κάθε διεργασία γίνεται με βάση τη θέση του παρατηρητή,
καθώς ο υπολογισμός εξαρτάται, τόσο στην απόσταση από τον παρατηρητή, όσο και στην
γωνία περιστροφής της ημιευθείας που συμβαίνουν τα γεγονότα. Ο διαχωρισμός απεικονίζεται
στο παραπάνω σχήμα (
) για τα κομμάτια A, B, C, D, E. Κάθε διεργασία αναλαμβάνει
ένα από τα παραπάνω κομμάτια και υπολογίζει η ορατότητα όλων των κελιών που
περιλαμβάνει. Έπειτα, κάθε διεργασία επιστρέφει τις τιμές που υπολόγισε, για το κομμάτι που
έχει αναλάβει, στην πρώτη διεργασία. Τέλος, η πρώτη διεργασία συγκεντρώνει τα
αποτελέσματα και έχει ως έξοδο τα κελιά που είναι ορατά στον παρατηρητή για το σύνολο του
DEM.