Επόμενο:Aσκήσεις Πάνω: Κεφάλαιο 10o : Αντίγραφα Εργαζομένων Πίσω: Αναφορές

ΠΡΟΓΡΑΜΜΑΤΙΣΤΙΚΕΣ ΕΡΓΑΣΙΕΣ

1. Αναζήτηση Μάζας

Στην εργασία αυτή θα γράψετε και θα εκτελέσετε ένα παράλληλο πρόγραμμα Αναζήτησης Μάζας για ένα σύστημα διαμοιραζόμενης μνήμης. Το υπόδειγμα των Αντιγράφων Εργαζομένων του παράλληλου προγραμματισμού θα είναι η βάση για το σχεδιασμό του προγράμματος. Μπορείτε επίσης να χρησιμοποιήσετε την υλοποίηση της Δεξαμενής Εργασίας που αναπτύχθηκε. Συνεπώς το βασικό θέμα είναι να αποφασίσετε τη μορφή των περιγραφών εργασιών για τη Δεξαμενή Εργασίας και να γράψετε την διαδικασία Worker σε Multi-Pascal.

Βασικά κάθε περιγραφή εργασίας θα είναι ένα μερικά ολοκληρωμένο μονοπάτι μέσα στη μάζα. Αφού ένας εργαζόμενος διαβάσει αυτό το μερικό μονοπάτι από τη Δεξαμενή Εργασίας θα επεκτείνει το μονοπάτι μέχρι το επόμενο “σημείο διακλάδωσης”, όπου πρέπει να γίνει μια επιλογή. Στην συνέχεια ο εργαζόμενος θα δημιουργήσει ένα καινούργιο μερικό μονοπάτι για κάθε επιλογή και θα τα γράψει όλα στην Δεξαμενή Εργασίας. Ένας εργαζόμενος πριν να φτάσει σε ένα σημείο διακλάδωσης μπορεί να βρεθεί σε ένα “αδιέξοδο”. Σε αυτή την περίπτωση, απλά το μερικό μονοπάτι απορρίπτεται. Επίσης, ο Εργαζόμενος μπορεί να φτάσει σε μία θέση “στόχο” στη μάζα και στην περίπτωση αυτή το τρέχον μονοπάτι γίνεται ένα μονοπάτι λύσης για τη μάζα.

Η μάζα έχει ένα σημείο “αφετηρίας” και ένα σημείο “στόχο”. Το σημείο αφετηρίας τοποθετείται στην Δεξαμενή Εργασίας ως το πρώτο μερικά ολοκληρωμένο μονοπάτι. Καθώς το πρόγραμμα των Αντιγράφων Εργαζομένων προχωράει δημιουργούνται νέα μονοπάτια, από την επέκταση των παλιών. Καθώς δημιουργούνται νέα μονοπάτια κάποια από αυτά θα απορριφθούν και κάποια άλλα θα επεκταθούν. Τελικά, ένα μονοπάτι θα βρει το στόχο. Η είσοδος του προγράμματός σας θα πρέπει να είναι μια περιγραφή της μάζας και η έξοδος πρέπει να είναι ένα μονοπάτι από το σημείο αφετηρίας προς το στόχο.

Μια επιπλέον βελτίωση του αλγορίθμου αναζήτησης για μεγαλύτερη απόδοση είναι να τοποθετούν οι εργαζόμενοι ένα ειδικό “σημάδι” στα σημεία διακλάδωσης της μάζας καθώς τα προσπερνούν. Με τον τρόπο αυτό θα αποφευχθεί η εξερεύνηση του ίδιου σημείου διακλάδωσης από άλλα μονοπάτια αργότερα. Έτσι θα μειωθεί στο ήμισυ η προσπάθεια και επίσης θα αποφευχθεί η δημιουργία κυκλικών μονοπατιών που δεν τελειώνουν.

Η μάζα μπορεί να αναπαρασταθεί με ένα μη-προσανατολισμένο γράφημα. Κάθε διάδρομος της μάζας αντιστοιχεί σε μια ακμή του γραφήματος και κάθε σημείο διακλάδωσης σε έναν κόμβο. Το πρόγραμμά σας πρέπει να αρχίζει διαβάζοντας μια δομή δεδομένων που περιγράφει τη δομή του γραφήματος, συμπεριλαμβανόμενου και του καθορισμού του κόμβου αφετηρίας και του κόμβου στόχου. Για να ελέγξετε το πρόγραμμά σας χρησιμοποιήστε μικρή μάζα. Όμως, για να διατηρήσουμε πολλούς επεξεργαστές απασχολημένους και για να επιτευχθεί καλή επιτάχυνση χρειάζεται μια πολύ μεγάλη μάζα με πολλά εναλλακτικά μονοπάτια.

Μετά την ανάπτυξη ενός προγράμματος που δουλεύει, χρησιμοποιήστε ένα συνδυασμό μαθηματικής ανάλυσης και εμπειρικών παρατηρήσεων για να καθορίσετε ποιο τμήμα της συνολικής απώλειας της επιτάχυνσης είναι αποτέλεσμα καθενός από τους παρακάτω παράγοντες: έλλειψη διαθέσιμης εργασίας, συμφόρηση και ανισορροπία φορτίου.

2. Το πρόβλημα του Περιοδεύοντος Πωλητή

Το πρόβλημα του Περιοδεύοντος Πωλητή είναι ένα κλασσικό πρόβλημα, που έχει λάβει ιδιαίτερη προσοχή στην βιβλιογραφία της επιστήμης των ηλεκτρονικών υπολογιστών. Αποτελεί ένα παράδειγμα των NP-Complete προβλημάτων, που σημαίνει ότι δεν υπάρχει κάποια γνωστή τεχνική επίλυσης που να είναι σημαντικά καλύτερη πέρα από την απλή αναζήτηση όλων των πιθανών εναλλακτικών. Σε ένα δεδομένο σύνολο πόλεων με καθορισμένη απόσταση μεταξύ κάθε ζεύγους πόλεων το πρόβλημα αφορά την εύρεση του συντομότερου ταξιδιού που επισκέπτεται κάθε πόλη ακριβώς μια φορά.

Όπως και το πρόβλημα των Ν Βασιλισσών έτσι και το πρόβλημα του Περιοδεύοντος Πωλητή μπορεί να λυθεί με μια συνδυαστική αναζήτηση όλων των πιθανών ταξιδιών. Συνεπώς, είναι κατάλληλο για την λύση των Αντιγράφων Εργαζομένων. Καθώς δημιουργούνται μερικώς ολοκληρωμένα ταξίδια κατά τη διάρκεια της αναζήτησης, μπορούν να αποθηκεύονται στην Δεξαμενή Εργασίας. Κάθε Εργαζόμενος αφαιρεί ένα μερικό ταξίδι από τη Δεξαμενή Εργασίας, υπολογίζει όλες τις πιθανές επεκτάσεις του ταξιδιού σε μια επιπλέον πόλη και στη συνέχεια γράφει όλα αυτά τα καινούργια ταξίδια στην Δεξαμενή Εργασίας.

Οι πόλεις αριθμούνται από το 1 ως το n και οι αποστάσεις δίνονται σε έναν δι-διάστατο πίνακα distance, για παράδειγμα η distance[i,j] δίνει την απόσταση από την πόλη i στην πόλη j. Για λόγους απλότητας υποθέστε ότι όλα τα ταξίδια ξεκινούν από την πόλη 1, επισκέπτονται όλες τις άλλες πόλεις ακριβώς μια φορά και στο τέλος επιστρέφουν στην πόλη 1. Το πρόβλημα του Περιοδεύοντος Πωλητή αφορά την εύρεση εκείνου του ταξιδιού που έχει την μικρότερη συνολική απόσταση.

Ένα μερικό ταξίδι είναι απλά μια ακολουθία αριθμών πόλεων αρχίζοντας από την πόλη 1. Η απόσταση ενός δεδομένου ταξιδιού έχει άμεση σχέση με τα αντίστοιχα μερικά ταξίδια που περιλαμβάνει. Για να επεκτείνουμε ένα μερικό ταξίδι πρέπει να λάβουμε υπόψη όλες τις πόλεις που έχουν απομείνει και δεν έχουν πάρει ακόμα μέρος στο ταξίδι: κάθε μια από αυτές είναι μια πιθανή υποψήφια ως επόμενη πόλη στο ταξίδι. Κάθε εργαζόμενος διαβάζει ένα μερικό ταξίδι από τη Δεξαμενή Εργασίας, υπολογίζει όλες τις πιθανές επεκτάσεις του ταξιδιού μέσω αυτής της πόλης και στη συνέχεια θα τις γράψει όλες στην Δεξαμενή Εργασίας.

Για το συντομότερο πλήρες ταξίδι που έχει βρεθεί μέχρι στιγμής διατηρείται ένα καθολικό ελάχιστο. Όποτε κάθε εργαζόμενος βρίσκει ένα πλήρες ταξίδι συγκρίνει την απόστασή του με το καθολικό ελάχιστο του πλήρους ταξιδιού και αντικαθιστά αν είναι αναγκαίο το καθολικό ελάχιστο. Μετά το τέλος του προγράμματος των Αντιγράφων Εργαζομένων αυτό το καθολικό ελάχιστο είναι και η τελική λύση.

Ο αλγόριθμος που περιγράφτηκε παραπάνω είναι κατάλληλος για ένα πρόγραμμα Αντιγράφων Εργαζομένων για το πρόβλημα του Περιοδεύοντος Πωλητή. Όμως, η απόδοση μπορεί να βελτιωθεί με μια μικρή τροποποίηση. Στον παραπάνω αλγόριθμο κάθε ταξίδι επεκτείνεται κατά μια πόλη και στην συνέχεια γράφεται στη Δεξαμενή Εργασίας. Έτσι, όλα τα μερικά ταξίδια αναπτύσσονται σταδιακά κατά μία πόλη κάθε φορά. Καθώς ο αλγόριθμος προχωρεί, ο αριθμός αυτών των μερικών ταξιδιών θα αυξηθεί πολύ, απαιτώντας πολλούς υπολογισμούς και μπορεί ακόμα και να κατακλύσει το σύστημα αποθήκευσης.

Αυτή η συνδυαστική “έκρηξη” μπορεί να μειωθεί χρησιμοποιώντας μια ευρετική τεχνική αναζήτησης, η οποία επιχειρεί να βρει πρώτα “καλά” ταξίδια και στη συνέχεια τα χρησιμοποιεί για να περιορίσει τα “κακά” ταξίδια στα πρώτα στάδια της δημιουργίας τους. Όταν ένας εργαζόμενος διαβάζει ένα μερικό ταξίδι από την Δεξαμενή Εργασίας η επόμενη πόλη που επιλέγει για αυτό το ταξίδι είναι η πιο κοντινή από τις πόλεις που έχουν απομείνει. Υπολογίζονται επίσης και ταξίδια για άλλες πόλεις αλλά αυτά γράφονται κατευθείαν στην Δεξαμενή Εργασίας. Στην συνέχεια ο εργαζόμενος θα επεκτείνει το μερικό του ταξίδι κατά μια μόνο πόλη, βρίσκοντας εκείνη που είναι πιο κοντά από αυτές που δεν έχει επισκεφτεί ακόμα. Ο εργαζόμενος θα συνεχίσει με αυτόν τον τρόπο το μερικό ταξίδι του μέχρι να επισκεφτεί όλες τις πόλεις και να δημιουργηθεί ένα πλήρες ταξίδι.

Ο αλγόριθμος αυτός είναι σχεδόν ο ίδιος με αυτόν που περιγράψαμε προηγουμένως. Ο εργαζόμενος υπολογίζει όλες τις πιθανές επεκτάσεις μιας-πόλης για κάθε μερικό ταξίδι. Όμως, αντί να τις γράφει όλες κατευθείαν στη Δεξαμενή Εργασίας, διατηρεί το συντομότερο από τα ταξίδια που προκύπτουν, το επεκτείνει, ενώ τα άλλα γράφονται στην Δεξαμενή Εργασίας. Με αυτόν τον τρόπο κάθε εργαζόμενος προσπαθεί να βρει γρήγορα κάποια λογικά καλά ταξίδια, τα οποία αποθηκεύονται στον καθολικό ελάχιστο.

Στη συνέχεια το καθολικό ελάχιστο μπορεί να χρησιμοποιηθεί για να περιορίσει πολλά ταξίδια πριν να ολοκληρωθούν. Καθώς κάθε καινούργιο μερικό ταξίδι δημιουργείται η απόστασή του συγκρίνεται με το καθολικό ελάχιστο. Με αυτόν τον τρόπο πολλά “κακά” ταξίδια που ακολουθούν μεγάλες αποστάσεις μεταξύ των πόλεων περιορίζονται στα αρχικά τους στάδια. Αυτή η απλή ευρετική λύση μειώνει κατά πολύ τον αριθμό των μερικών ταξιδιών που δημιουργούνται. Επίσης, μειώνονται οι απαιτήσεις αποθήκευσης για τη Δεξαμενή Εργασίας, γιατί οι εργαζόμενοι εξακολουθούν να προσπαθούν να επεκτείνουν τα μερικά ταξίδια προς ολοκληρωμένα και συνεπώς να τα βγάλουν από τη Δεξαμενή Εργασίας.

Αφού αναπτύξετε ένα πρόγραμμα που δουλεύει χρησιμοποιήστε ένα συνδυασμό μαθηματικής ανάλυσης και εμπειρικών παρατηρήσεων για να καθορίσετε ποιο τμήμα της συνολικής απώλειας της επιτάχυνσης είναι αποτέλεσμα καθενός από τους παρακάτω παράγοντες: έλλειψη διαθέσιμης εργασίας, συμφόρηση και ανισορροπία φορτίου.

Επόμενο:Aσκήσεις Πάνω: Κεφάλαιο 10o : Αντίγραφα Εργαζομένων Πίσω: Αναφορές