Στο κεφάλαιο αυτό περιγράφεται η διαδικασία μελέτης της απόδοσης ενός παράλληλου αλγόριθμου λείανσης με φίλτρο μέσης τιμής, που χρησιμοποιείται ευρέως σε θέματα επεξεργασίας εικόνας. Η εφαρμογή εκτελέστηκε σε ένα παράλληλο σύστημα 5 επεξεργαστών ALPHA 3000.
Με εφαρμογή αυτή ακολουθεί το μοντέλο αφέντη-σκλάβου. Η διεργασία αφέντης κατανέμει το πρόβλημα σε 4 διεργασίες σκλάβους που αναλαμβάνουν να εκτελέσουν τον αλγόριθμο λείανσης και να επιστρέψουν το αποτέλεσμα στην διεργασία αφέντης. Κατά τη μελέτη της εφαρμογής ανιχνεύθηκε πρόβλημα στην απόδοση που οφείλεται σε λανθασμένο τρόπο παραλληλισμού του σειριακού αλγορίθμου λείανσης.
Figure: Απόδοση του παράλληλου αλγόριθμου λείανσης
Από το Time Diagram, σχ. .
παρατηρούμε ότι
ο χρόνος που δαπανάται για επικοινωνία και για συγχρονισμό των
διεργασιών είναι πολύ μικρός σε σχέση με το χρόνο που δαπανάται για
υπολογισμούς. Αυτό προκύπτει από τη απεικόνιση των αντίστοιχων
ιστογραμμάτων στο Time Diagram. Επιπλέον με πρώτη ματιά
διαφαίνεται πρόβλημα στην κατανομή του προβλήματος σε επιμέρους
διεργασίες. Αυτό προκύπτει από το γεγονός ότι η διεργασία αφέντης
φαίνεται ότι δαπανά πολύ περισσότερο υπολογιστικό χρόνο σε σχέση με
τις διεργασίες σκλάβους που επιλύουν το πρόβλημα.
Από το Utilization Count Diagram, σχ. .
,
προκύπτει η παρατήρηση ότι κατά την εκτέλεση της εφαρμογής μόνο ένας
επεξεργαστής εκτελούσε χρήσιμη εργασία (κατάσταση Busy).
Το πρόβλημα που ανιχνεύθηκε οφείλεται στην ανάγνωση των δεδομένων εισόδου από τη διεργασία αφέντης. Ο χρόνος προσπέλασης στο δίσκο είναι μεγάλος σε σχέση με τον υπολογιστικό χρόνο του καθεαυτού αλγορίθμου. Επιπλέον δεν κατανέμεται σωστά.
Figure: Βελτίωση της απόδοσης του αλγόριθμου λείανσης
Εγινε προσπάθεια βελτίωσης της απόδοσης με τη μετατροπή του παραλληλοποιημένου αλγορίθμου. Ετσι η διεργασία αφέντης δημιουργεί τις διεργασίες σκλάβους και στη συνέχεια αντί να διαβάσει τα δεδομένα και να τα κατανέμει, στέλνει σε κάθε σκλάβο το όνομα του αρχείου που περιέχει τα δεδομένα που πρόκειται να επεξεργαστεί και το οποίο αρχείο βρίσκεται στον τοπικό δίσκο του κάθε επεξεργαστή. Αρα στην βελτιωμένη αυτή υλοποίηση κατανέμεται και ο χρόνος που δαπανάται για την ανάγνωση από το δίσκο.
Στο σχ. παρουσιάζονται εμφανώς βελτιωμένα
αποτελέσματα. Πιο αναλυτικά στο σχ.
.
, παρατηρούμε
πλέον μια ομοιόμορφη κατανομή του χρόνου εκτέλεσης υπολογιστικής
εργασίας στις διεργασίες σκλάβους. Επιπλέον ο χρόνος εκτέλεσης της
εφαρμογής φαίνεται να ελαττώνεται στο ένα τρίτο του αρχικού. Ακόμη στο
σχ.
.
,
παρατηρούμε ότι κατά το μεγαλύτερο τμήμα του χρόνου εκτέλεσης 4
επεξεργαστές του συστήματος ήταν ταυτόχρονα σε κατάσταση Busy,
δηλαδή εκτελούσαν χρήσιμη εργασία.
Figure: Χρόνοι εκτέλεσης της αρχικής εφαρμογής και της βελτιωμένης
Πράγματι στο σχ. βλέπουμε καθαρά ότι ο χρόνος
εκτέλεσης της εφαρμογής βελτιώθηκε. Η εφαρμογή εκτελέσθηκε σε 1, 3, 5
επεξεργαστές, δηλαδή οι 4 διεργασίες σκλάβοι μοιράσθηκαν σε 0, 2, 4
επεξεργαστές και τα αποτελέσματα έδειξαν ότι η εφαρμογή
επιταχύνεται. Στην περίπτωση των 0 επεξεργαστών ο χρόνος εκτέλεσης
είναι σχεδόν ο ίδιος με τον αρχικό, αυτό συμβαίνει προφανώς αφού οι
προσπελάσεις σε διαφορετικά αρχεία σειριοποιούνται στον τοπικό
δίσκο. Αυξάνοντας τον αριθμό των επεξεργαστών σε 2 και στη συνέχεια σε
4 η βελτίωση παρουσιάζεται μεγαλύτερη.