HY555 - Παράλληλα Συστήματα και GRIDs

Φθινόπωρο 2007

Ασκηση 1: Sudoku puzzle solution

Σκοπος της ασκησης αυτης ειναι η υλοποιηση ενος παραλληλου προγραμματος

για τη λυση ενος Sudoku puzzle.

Θεωρια

Το Sudoku είναι ένα παζλ που βασίζεται στη λογική. Στόχος είναι να συμπληρωθούν όλα τα κουτάκια στον πίνακα (συνηθως 9x9), ώστε κάθε στήλη, κάθε σειρά και κάθε κουτάκι 3x3 να περιέχουν όλα τα ψηφία από το 1 μέχρι το 9. Μερικά κουτάκια είναι ήδη συμπληρωμένα, ώστε να υπάρχει μόνο μία δυνατή λύση.

Ενα τυπικο Sudoku παζλ μπορειτε να δειτε στον παρακατω συνδεσμο:

http://el.wikipedia.org/wiki/Sudoku

Ο τροπος λυσης, οπως επισης και η λυση, των Sudoku δεν ειναι παντα μονοσημαντος.

Μια τυπικη διαδικασια λυσης αρχιζει ως εξης:

Αρχικα εξεταζουμε τη δυνατοτητα να βαλουμε οσα περισσοτερες φορες μπορουμε εναν

δοθεν αριθμο απο το 1-9, συνεχιζουμε με τον επομενο, κοκ (το λεγομενο cross-hatching).

Εαν σε καποιο σημειο εχουμε την ευκαιρια να συμπληρωσουμε επιπλεον τετραγωνακια στο παζλ, το κανουμε.

Τελικα, εξεταζοντας ποιοι αριθμοι λειπουν απο μια γραμμη/στηλη/εννιαδα, τους συμπληρωνουμε για να τελειοποιησουμε τη λυση.

Απο αυτο το σημειο και μετα, εαν δεν μπορουμε να ανακαλυψουμε περαιτερω ψηφια, ειναι αναγκαιο να καταφυγουμε στη λογικη. Μια μεθοδος ειναι να καθοδηγησουμε το παζλ συμπληρωνοντας

υποψηφια ψηφια σε καποιο(-α) κουτι(-α) και να διαπιστωσουμε εαν οδηγουμαστε σε λυση ή οχι (what-if method).

Υλοποίηση

Ο αλγοριθμος που σας ζητουμε να υλοποιησετε, για διευκολυνση σας, μπορει να κανει χρηση

λογικων αλγοριθμων για την επιλυση του sudoku. Δηλαδη, μπορειτε να χρησιμοποιησετε backtracking

τεχνικες, ειτε human-style λυσεις ("μνημη ψηφιων" και "what-if" μεθοδους), ή απλα brute-forcing.

Γραψτε κωδικα ο οποιος λυνει ενα sudoku παζλ με τη μεθοδο της επιλογης σας. Αρχικα,

θα πρεπει να διαβαζετε το παζλ απο ενα αρχειο σαν ενα συνολο απο αδεια κουτια

καθως και δοθεντα ψηφια. Επειτα θα πρεπει να ακολουθησετε την προαναφερθεισα

διαδικασια για να λυσετε το παζλ. Εδω εχετε αρκετες εναλλακτικες ως προς τη διαδικασια

που θα ακολουθηθει μετα (ή ενδεχομενως και πριν) το cross-hatching:

            * να ξεκινησετε με μια τυχαια μαντεψια της λυσης και να την βελτιωνετε

            οσο δεν αποτελει λυση, μεχρι να λυθει το παζλ. Εδω θα σας βοηθησει να

            βρειτε μια ποσοτητα που θα αποτελει το μετρο το οποιο προσπαθειτε να

            ελαχιστοποιησετε προκειμενου να βρεθει μια λυση.

            * να ξεκινησετε απο το μηδεν και επαναληπτικα να δοκιμασετε ολες τις

            πιθανες περιπτωσεις.

            * κ.ο.κ.

Χρησιμοποιηστε την τεχνικη PCAM προκειμενου να αναλυσετε και να χωρισετε το

προβλημα στις συνιστωσες που θα επιλεξετε, κατοπιν σχεδιαστε και υλοποιηστε την παραλληλη

λυση με χρηση της βιβλιοθηκης MPI. Θα σας ζητηθει να περιγραψετε σε λεπτομερεια:

            - Τις δομες επικοινωνιας που ορισατε ή/και χρησιμοποιησατε

            - Τον τροπο διαμοιρασμου της εργασιας μεταξυ διεργασιων

            - Τον τροπο διαμοιρασμου των δεδομενων

Μετρηστε τους χρονους εκτελεσης της σειριακης καθως και της παραλληλης εκδοσης

της λυσης σας για διαφορους αριθμους επεξεργαστων (2 ... 16) και υπολογιστε το

speedup που επιτυγχανετε σε καθε περιπτωση (χρησιμοποιηστε NχN puzzles, with N being a large enough number).

Σχολιαστε τα αποτελεσματα, και ιδιως το scalability της προσεγγισης σας.

Ημερομηνία παράδοσης: 29/10

Σημ. Θα σας γινει φροντιστηριο πανω στη βασικη χρηση της βιβλιοθηκης MPI στις 12/10.