Κατάλογος Εκδηλώσεων

ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών

ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ

Εμμανουήλ Μυλωνάκη

με θέμα

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

Development of a CAD Tool and Hardware Design in Order to Execute Cellular Automata on a Reconfigurable Platform by non-FPGA-Conversant Users

Εξεταστική Επιτροπή
Καθηγητής Απόστολος Δόλλας (επιβλέπων)
Αναπληρωτής Καθηγητής Σωτήριος Ιωαννίδης
Καθηγητής Μιχαήλ Ζερβάκης

Περίληψη

Τα κυψελωτά αυτόματα (cellular automata - CA) είναι μία δομή των διακριτών μαθηματικών με σημαντικές υπολογιστικές ιδιότητες (Turing complete). Εφευρέθηκαν από τον John Von Neumann και τον Stanislaw Ulam. Αποτελεί ένα σημαντικό μαθηματικό εργαλείο για μοντελοποίηση πληθώρας προβλημάτων σε πολλά και διαφορετικά επιστημονικά πεδία. Η τεχνολογία αναδιατασσόμενης λογικής (Field Programmable Gate Array - FPGA) έχει χρησιμοποιηθεί επί δεκαετίες για να επιταχύνει υπολογισμούς κυψελωτών αυτομάτων. Σε προγενέστερη εργασία, ο Νικόλαος Κυπαρισσάς στην Διπλωματική του Εργασία στο Πολυτεχνείο Κρήτης δημιούργησε ένα παραμετροποιήσιμο πλαίσιο εργασίας και μία αρχιτεκτονική για επιτάχυνση υπολογισμών CA με γειτονιές έως 29 × 29. Στην εργασία αυτή η αρχικοποίηση και η παραμετροποίηση του επιταχυντή πρέπει
να οριστούν εκ νέου για κάθε διαφορετικό μοντέλο CA, και η σχεδίαση να περάσει μέσα από τα εργαλεία CAD του κατασκευαστή Xilinx για τοποθέτηση και διασύνδεση πόρων (Place and Route) της FPGA. Στην παρούσα διπλωματική εργασία επεκτείνουμε τα παραπάνω αποτελέσματα ώστε ο χρήστης να μην χρειάζεται να γράψει κώδικα ή να περάσει την σχεδίασή του μέσα από τα εργαλεία της εταιρίας Xilinx για τοποθέτηση και διασύνδεση πόρων. Αυτό επιτυγχάνεται μέσω αλλαγών στην υφιστάμενη αρχιτεκτονική που επιτρέπουν την χρήση της
για διαφορετικά μοντέλα του χρήστη, και μέσω ενός γραφικού περιβάλλοντος που αλληλεπιδρά με το υλικό (hardware) του συστήματος για να φορτώνει νέες σχεδιάσεις. Μία επί πλέον γραφική διεπαφή (Graphical User Interface - GUI) έχει δημιουργηθεί στα πλαίσια της παρούσας διπλωματικής, ώστε ο χρήστης να μην χρειάζεται να ορίζει τα έως και 841 (29 × 29) βάρη στις γειτονιές ένα-ένα, αλλά με γραφικό τρόπο και μάλιστα αυτόματο όπου υπάρχουν συμμετρίες.

Abstract

Cellular Automata (CA) are Turing-Complete, discrete, computational models, invented by John Von Neumann and Stanislaw Ulam. It is a powerful mathematical tool, finding application to numerous scientific fields. Field-
Programmable Gate Array (FPGA) Technology has been used for decades to speed up CA computations. In previous work, Nikolaos Kyparissas designed in his Technical University of Crete (TUC) M.Eng. Diploma Thesis a customizable framework and an architecture to accelerate CA computations, with neighborhoods as large as 29 × 29. In Kyparissas’ work the initialization of the machine and the customization of the framework have to be manually redefined for every different CA model, and the design placed and routed with the CAD tools of the FPGA vendor, Xilinx. In the present thesis we extend that work so that the user does not need to write code for the hardware implementation or go through the Xilinx CAD tools for placement and routing. A re-programmable structure of the framework has been introduced, while a new CAD tool, developed in the present thesis, drives the design at the software level. Finally, a Graphical User Interface (GUI) environment has also been developed to help the user define CA neighborhoods without having to enter one-by-one the as-many-as 841 (29 × 29) weights.