National and Kapodistrian University of Athens
Παραλληλοποίηση του Παιχνιδιού της Ζωής του Conway με την χρήση MPI και CUDA
Abstract
dc:descriptionΣτην παρούσα εργασία θα κάνουμε μελέτη κλιμάκωσης του Παιχνιδιού της Ζωής σε παράλληλα υπολογιστικά συστήματα. Το Παιχνίδι της Ζωής δημιουργήθηκε από τον Βρετανό μαθηματικό John Horton Conway το 1970. Ανήκει στην κατηγορία των παχνιδιών τύπου cellular automata[1]. Παρόλο που αποκαλείται «παιχνίδι», στην πραγματικότητα δεν απαιτεί κάποια ενέργεια από τον χρήστη. Η έκβασή του καθορίζεται αποκλειστικά από την αρχική του κατάσταση. Ο πίνακας του παιχνιδιού είναι απλώς ένα δισδιάστατο πλέγμα m ∗ n, την κάθε θέση του οποίου καταλαμβάνει ένας οργανισμός. Η κατάσταση του κάθε οργανισμού καθορίζεται μόνο από τους άμεσους 8 γείτονές του. Το Παιχνίδι της Ζωής αποτελεί ιδανικό υποψήφιο για παραλληλοποίηση, καθώς κάθε οργανισμός εξαρτάται μόνο από τους άμεσους 8 γείτονές του. Επομένως, ο υπολογισμός της επόμενης γενιάς δεν χρειάζεται να γίνει σειριακά. Στην παρούσα διπλωματική εργασία, θα επιχειρήσουμε παραλληλοποίηση με τις εξής βιβλιοθήκες: • MPI • CUDA • Υβριδικό MPI/CUDA Η μελέτη παραλληλοποίησης του Παιχνιδιού της Ζωής είναι σημαντική, επειδή, όπως θα δούμε και παρακάτω, οι μέθοδοι που θα χρησιμοποιήσουμε μπορούν να χρησιμοποιηθούν και για την παραλληλοποίηση διαφορικών εξισώσεων και γενικότερα περίπλοκων επιστημονικών προβλημάτων. Τα αποτελέσματα είναι ιδιαιτέρως ενθαρρυντικά, αφού και με τις τρεις μεθόδους επιτύχαμε σημαντική επιτάχυνση, και τα καλύτερα αποτελέσματα είχαμε με το υβριδικό μοντέλο MPI/CUDA. Ωστόσο, όπως θα δούμε και αναλυτικά παρακάτω, κάθε μέθοδος έχει τα πλεονεκτήματα και μειονεκτήματά της, οπότε η επιλογή της κατάλληλης μεθόδου πρέπει να γίνεται πάντοτε με βάση την φύση του προβλήματος που καλούμαστε να λύσουμε. Συνοπτικά, τα αποτελέσματα της κάθε υλοποίησης ήταν τα εξής: • MPI: Καλή κλιμάκωση, αλλά οι πιο αργές ταχύτητες από όλες τις υλοποιήσεις. • CUDA: Η γρηγορότερη υλοποίηση από όλες, αλλά περιορίζεται από την μνήμη που είναι διαθέσιμη στην εκάστοτε κάρτα γραφικών. Ιδανικό για μικρότερα προβλήματα. • Υβριδικό MPI/CUDA: Πολύ γρηγορότερο από το απλό MPI, πιο αργό από το απλό CUDA. Παρέχει ταυτόχρονα την δυνατότητα κλιμάκωσης που προσφέρουν οι πολλοί κόμβοι και τις γρήγορες ταχύτητες του CUDA. Ιδανικό εφόσον είναι διαθέσιμο ως επιλογή.
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Ραδιώτης Βασίλειος
- Radiotis Vasileios
Subjects
dc:subject × 2Rights
- Language dc:language
- Ελληνικά, Greek
Identifiers
dc:identifier.*- Identifier
- uoadl:3368420