Available Diploma Thesis
— Ανάπτυξη ευρετικού αλγορίθμου για την βελτίωση των επιδόσεων ψηφιακών σχεδιασμών με τη τεχνική του προσεγγιστικού υπολογισμού
— Ανάπτυξη αλγορίθμου διερεύνησης εναλλακτικών αρχιτεκτονικών επιλογών με τη βοήθεια γενετικών αλγορίθμων
— Σχεδίαση και υλοποίηση ενός Virtual FPGA
— Ανάπτυξη αλγορίθμου για την δυναμική τμηματοποίηση και ανάθεση ψηφιακών σχεδιασμών σε 2Δ και 3Δ αρχιτεκτονικές
— Ανάπτυξη αλγορίθμου τοποθέτησης ψηφιακών κυκλωμάτων σε επαναδιαμορφούμενες αρχιτεκτονικές με τη χρήση γενετικού αλγορίθμου
— Ανάπτυξη αλγορίθμου διασύνδεσης για 2Δ και 3Δ ψηφιακά συστήματα με τη βοήθεια της βελτιστοποίησης με αποικίες μυρμηγκιών
— Υλοποίηση αλγορίθμου διαχείρισης πόρων σε πολυπύρηνες αρχιτεκτονικές με τη βοήθεια θεωρίας αγορών
Ανάπτυξη ευρετικού αλγορίθμου για την βελτίωση των επιδόσεων ψηφιακών σχεδιασμών με τη τεχνική του προσεγγιστικού υπολογισμού
Οι τεχνολογίες πληροφορικής βρίσκονται πλέον σε μια εποχή που για να διατηρηθεί αλλά και να βελτιωθεί η απόδοση και αποτελεσματικότητα των υπολογιστικών συστημάτων είναι αναγκαίες ριζικές αλλαγές συγκριτικά με τις παραδοσιακές τεχνικές. Ο προσεγγιστικός υπολογισμός αποτελεί ένα χαρακτηριστικό πρότυπο ριζικής μεταβολής που έχει εισέλθει στο σχεδιασμό και τη λειτουργία των σύγχρονων συστημάτων. Βασίζεται στην ιδέα ότι περιορίζουμε την απόδοση των υπολογιστικών συστημάτων εξαναγκάζοντας τα να επιτελούν υπολογισμούς μεγαλύτερης ακρίβειας απ’ όσο πραγματικά χρειάζεται. Είναι γεγονός ότι ακριβείς απαντήσεις δεν είναι εφικτές/απαραίτητες σε πληθώρα εφαρμογών όπως για παράδειγμα στους τομείς βαθιάς μάθησης, όρασης υπολογιστών, προβολή βίντεο, κτλ. Όμως, ο προσεγγιστικός υπολογισμός πρέπει να εφαρμόζεται μέσω μιας αυστηρής και τυπικής μεθοδολογίας. Για το λόγο αυτό είναι αναγκαία υπολογιστικά επίπεδα αφαίρεσης που να επιτρέπουν την μεθοδική μείωση της υπολογιστικής ακρίβειας κερδίζοντας σε άλλες μετρικές όπως επίδοση και ενέργεια. Λόγω του ότι πολλές φορές το είδος του προσεγγιστικού υπολογισμού εξαρτάται από τα δεδομένα εισόδου, θα διερευνηθεί επίσης η δυνατότητα χρήσης ενός νευρωνικού δικτύου στην είσοδο της μεθοδολογίας/εργαλείου προκειμένου να καθορίζει το επίπεδο στο οποίο θα πρέπει να εφαρμοστεί ο προσεγγιστικός υπολογισμός.
Στόχος της διπλωματικής εργασίας είναι η ανάπτυξη ενός ευρετικού (heuristic) αλγορίθμου για τη βελτίωση των επιδόσεων ψηφιακών σχεδιασμών με τη χρήση τεχνικών προσεγγιστικού υπολογισμού.
Ανάπτυξη αλγορίθμου διερεύνησης εναλλακτικών αρχιτεκτονικών επιλογών με τη βοήθεια γενετικών αλγορίθμων
Η αύξηση των διαθέσιμων επιλογών που παρατηρείται στην υλοποίηση ψηφιακών κυκλωμάτων (π.χ. αύξηση αριθμού υπολογιστικών πυρήνων, πυρήνες με διαφορετικά χαρακτηριστικά από πλευράς επιδόσεων, κατανάλωσης και επιφάνειας πυριτίου, κτλ.) οδηγεί σε αντίστοιχη αύξηση της πολυπλοκότητας του σχεδιασμού αυτών. Αυτό συμβαίνει κυρίως διότι ο μηχανικός που αναλαμβάνει τη σχεδίαση πρέπει να διερευνήσει την αποτελεσματικότητα ενός μεγάλου αριθμού συνδυασμών από αρχιτεκτονικές επιλογές για καθένα από τα βασικά δομικά μπλοκ του συστήματος, καθώς επίσης και συνδυασμούς αυτών. Επιπλέον παράμετρο στη συγκεκριμένη διερεύνηση αποτελούν οι απαιτήσεις που έχει η προς υλοποίηση εφαρμογή, η οποίες καθορίζουν και τις προδιαγραφές του τελικού συστήματος. Οι υπάρχουσες προσεγγίσεις που επιχειρούν να διερευνήσουν το χώρο λύσεων (design space exploration) παρουσιάζουν υψηλή υπολογιστική πολυπλοκότητα, η οποία καθιστά απαγορευτική την αποτελεσματική διερεύνηση όλων των λύσεων (συνήθως διερευνούν ένα υποσύνολο αυτών), καθώς ο σχεδιαστικός χώρος δεν μπορεί να καλυφθεί επαρκώς σε εύλογο χρονικό διάστημα. Για το σκοπό αυτό, στα πλαίσια της εργασίας θα αναπτυχθεί ένας ευρετικός αλγόριθμος, ο οποίος θα αντιμετοπίζει την αυξημένη υπολογιστική πολυπλοκότητα (π.χ. χρόνο επίλυσης του προβλήματος) που εμφανίζουν οι τυπικοί μέθοδοι μαθηματικής βελτιστοποίησης. Η πλειοψηφία αυτών των υπολογιστικών προβλημάτων ανήκουν στην κλάση NP-hard, και δεν είναι δυνατή η εύρεση λύσης σε πολυωνυμικό χρόνο (εκτός αν P = NP). Για την αποδοτική επίλυση τέτοιων προβλημάτων, έχουν μελετηθεί και διαφορετικές ευρετικές μέθοδοι στη συμβιβαστική προσπάθεια αναζήτησης μιας υπό-βέλτιστης λύσης σε σύντομο χρόνο υπολογισμού. Οι ευρετικές μέθοδοι αναζήτησης συνήθως παράγονται με βάση απλής διαισθητικής και δημιουργικής σκέψης του ανθρώπου, και είναι συχνά χρήσιμες στην τοπική αναζήτηση για την γρήγορη εύρεση καλών λύσεων σε μια περιορισμένη περιοχή. Οι μεθευρετικές μέθοδοι είναι μέθοδοι υψηλότερου επιπέδου, οι οποίες με συστηματικό τρόπο καθοδηγούν όλη την διαδικασία της αναζήτησης με χρήση ευρετικών μεθόδων. Οι μεθευρετικοί αλγόριθμοι αν και δεν αποτελούν εγγύηση για την εύρεση μιας ολικά βέλτιστης λύσεως, συχνά προσφέρουν πολύ καλά αποτελέσματα σε πολλά πρακτικά προβλήματα.
Στόχος της διπλωματικής εργασίας είναι η ανάπτυξη ενός γενετικού αλγορίθμου για την αποτελεσματική διερεύνηση εναλλακτικών αρχιτεκτονικών επιλογών.
Σχεδίαση και υλοποίηση ενός Virtual FPGA
Οι επαναδιαρθρώσιμες αρχιτεκτονικές, γνωστές και με τον όρο FPGAs (Field-Programmable Gate Arrays), αποτελούν μια σημαντική τεχνολογία που επιτρέπει στους σχεδιαστές την αποδοτική υλοποίηση ψηφιακών συστημάτων λαμβάνοντας υπόψιν τις απαιτήσεις για υψηλότερες επιδώσεις και χαμηλότερη κατανάλωση ισχύος (Performance/Watt) συγκρινόμενες με τις αντίστοιχες υλοποιήσεις σε CPU/GPU. Βασική διαφοροποίηση μιας υλοποίησης σε αρχιτεκτονική FPGA, ως προς τις αντίστοιχες προσεγγίσεις ειδικού σκοπού (ASIC), είναι η δυνατότητα τροποποίησης του ψηφιακού σχεδιασμού (αξιοποιώντας τεχνικές μερικού επαναπρογραμματισμού του συστήματος). Αν και πολλά υποσχόμενη, η συγκεκριμένη ιδιότητα δεν εφαρμόζεται σ’ όλες τις αρχιτεκτονικές FPGA κυρίως λόγω του αυξημένου σχεδιαστικού κόστους που επιφέρει. Στα πλαίσια της διπλωματικής εργασίας θα αναπτυχθεί σε γλώσσα περιγραφής υλικού (π.χ. VHDL ή Verilog) ένα «εικονικό» (virtual) FPGA τύπου νησίδας (island-style), παρόμοιο με αυτό που χρησιμοποιείται στην πλειονότητα των εμπορικά διαθέσιμων FPGA. Για τα πλαίσια του σχεδιασμού θα μπορούσε επίσης να χρησιμοποιηθούν τεχνικές σύνθεσης από υψηλότερο επίπεδο (High-Level Synthesis). Για τον προγραμματισμό της εικονικής αρχιτεκτονικής (virtual FPGA) θα χρησιμοποιηθεί το ακαδημαϊκό περιβάλλον MEANDER.
Στόχος της διπλωματικής εργασίας είναι η σχεδίαση ενός ψηφιακού συστήματος, το οποίο θα υλοποιεί τη λειτουργία μιας επαναδιαμορφούμενης αρχιτεκτονικής (FPGA), τα χαρακτηριστικά της οποίας θα μπορούν να μεταβάλλονται κατά το χρόνο σχεδίασης.
Ανάπτυξη αλγορίθμου για την δυναμική τμηματοποίηση και ανάθεση ψηφιακών σχεδιασμών σε 2Δ και 3Δ αρχιτεκτονικές
Το διαρκώς αυξανόμενο μέγεθος των ψηφιακών σχεδιασμών που συνθέτουν ένα ψηφιακό σύστημα συχνά οδηγεί στο πρόβλημα της τμηματοποίησης και ανάθεσης μέρος του σχεδιασμού σε πολλαπλούς επεξεργαστικούς πόρους. Αν και το πρόβλημα της τμηματοποίησης έχει μελετηθεί εκτενώς στο παρελθόν, στα πλαίσια της Διπλωματικής θα υλοποιηθεί ένας αλγόριθμος που θα επιτρέπει την ταυτόχρονη επίλυση αυτού με το πρόβλημα της ανάθεσης (partition assignment) στους διαφορετικούς πόρους της αρχιτεκτονικής. Για την επίλυση του συγκεκριμένου προβλήματος θα αναπτυχθεί ένας ευρετικός αλγόριθμος. Πιο συγκεκριμένα, στην επίλυση προβλημάτων βελτιστοποίησης εφαρμόζονται κυρίως διάφοροι ακριβείς αλγόριθμοι μαθηματικού προγραμματισμού. Ωστόσο, σε προβλήματα συνδυαστικής ή ολικής βελτιστοποίησης οι συμβατικές μέθοδοι δεν είναι συνήθως αρκετά αποτελεσματικές, ειδικά, όταν ο χώρος αναζήτησης του προβλήματος είναι μεγάλος και πολύπλοκος. Η πλειοψηφία αυτών των υπολογιστικών προβλημάτων ανήκουν στην κλάση NP-hard, και δεν είναι δυνατή η εύρεση λύσης σε πολυωνυμικό χρόνο (εκτός αν P = NP). Για την αποδοτική επίλυση τέτοιων προβλημάτων, έχουν μελετηθεί και διαφορετικές ευρετικές μέθοδοι στη συμβιβαστική προσπάθεια αναζήτησης μιας υπό-βέλτιστης λύσης σε σύντομο χρόνο υπολογισμού. Οι ευρετικές μέθοδοι αναζήτησης συνήθως παράγονται με βάση απλής διαισθητικής και δημιουργικής σκέψης του ανθρώπου, και είναι συχνά χρήσιμες στην τοπική αναζήτηση για την γρήγορη εύρεση καλών λύσεων σε μια περιορισμένη περιοχή. Οι μεθευρετικές μέθοδοι είναι μέθοδοι υψηλότερου επιπέδου, οι οποίες με συστηματικό τρόπο καθοδηγούν όλη την διαδικασία της αναζήτησης με χρήση ευρετικών μεθόδων. Οι μεθευρετικοί αλγόριθμοι αν και δεν αποτελούν εγγύηση για την εύρεση μιας ολικά βέλτιστης λύσεως, συχνά προσφέρουν πολύ καλά αποτελέσματα σε πολλά πρακτικά προβλήματα.
Στόχος της διπλωματικής εργασίας είναι η ανάπτυξη ενός αλγορίθμου τμηματοποίησης και ανάθεσης πόρων σε 2Δ και 3Δ υπολογιστικές αρχιτεκτονικές.
Ανάπτυξη αλγορίθμου τοποθέτησης ψηφιακών κυκλωμάτων σε επαναδιαμορφούμενες αρχιτεκτονικές με τη χρήση γενετικού αλγορίθμου
Οι επαναδιαρθρώσιμες αρχιτεκτονικές FPGA (Field-Programmable Gate Array) αποτελούν μια σημαντική τεχνολογία, η οποία επιτρέπει αποδοτική υλοποίηση ψηφιακών σχεδιασμών σε υλικό προκειμένου να εμφανίζουν σημαντικά κέρδη από πλευράς συχνότητας λειτουργίας και κατανάλωσης ισχύος, ως προς τις αντίστοιχες υλοποιήσεις σε επίπεδο λογισμικού (CPU/GPU). Η τοποθέτηση (placement) των ψηφιακών σχεδιασμών στο FPGA αποτελεί ένα από τα σημαντικότερα βήματα της σχεδιαστικής διαδικασίας μιας και καθορίζει τις επιδώσεις του τελικού συστήματος (π.χ. συχνότητα λειτουργίας, κατανάλωση, απαιτήσεις πόρων υλικού, κτλ). Οι υπάρχουσες προσεγγίσεις στο συγκεκριμένο πρόβλημα εμφανίζουν υψηλή υπολογιστική πολυπλοκότητα, κάτι που εμμέσως περιορίζει τις επιδώσεις τους στην εύρεση βέλτιστης λύσης. Στα πλαίσια της συγκεκριμένης εργασίας θα αναπτυχθεί ένας αλγόριθμος βελτιστοποίησης πολυ-παραγοντικών προβλημάτων με τη βοήθεια Γεννετικών Αλγορίθμων, ο τρόπος λειτουργίας των οποίων είναι εμπνευσμένος από τη βιολογία. Χρησιμοποιεί την ιδέα της εξέλιξης μέσω γενετικής μετάλλαξης, φυσικής επιλογής και διασταύρωσης. Οι Γενετικοί Αλγόριθμοι διατηρούν έναν πληθυσμό πιθανών λύσεων, του προβλήματος που μας ενδιαφέρει, πάνω στον οποίο δουλεύουν, σε αντίθεση με άλλες μεθόδους αναζήτησης που επεξεργάζονται ένα μόνο σημείο του διαστήματος αναζήτησης. Έτσι ένας Γενετικός Αλγόριθμος πραγματοποιεί αναζήτηση σε πολλές κατευθύνσεις και υποστηρίζει καταγραφή και ανταλλαγή πληροφοριών μεταξύ αυτών των κατευθύνσεων. Ο πληθυσμός υφίσταται μια προσομοιωμένη γενετική εξέλιξη χρησιμοποιώντας διάφορους γενετικούς τελεστές όπως η επιλογή, η διασταύρωση και η μετάλλαξη. Στην πράξη ο αλγόριθμος ξεκινά μ’ ένα σύνολο λύσεων – ονομάζονται γονιδιώματα, δανειζόμενες το όνομά τους από τη βιολογία- οι οποίες συνιστούν τον “πληθυσμό”. Κατόπιν ζητείται από τον υπολογιστή να δημιουργήσει μια σειρά τυχαίων ανασυνδυασμών και μεταλλάξεων των “γονιδιωμάτων”. Οι πιο ικανές λύσεις για ένα συγκεκριμένο πρόβλημα συνεχίζουν να εξελίσσονται και ανασυνδυάζονται τυχαία, μέχρις ότου “επιβιώσουν” οι καλύτερες. Συνήθως, όσο περισσότερες γενιές περνούν τόσο καλύτερες λύσεις βρίσκονται, μπορεί όμως ο αλγόριθμος να βρεθεί σε σημείο του πεδίου των λύσεων από όπου και δεν μπορεί να προχωρήσει λόγο του ότι βρίσκεται σε τοπικό μέγιστο. Για το λόγο αυτό έχουν υπάρχουν διαφορετικές εκδοχές του αλγόριθμου ανάλογα με τη μορφή του προβλήματος.
Στόχος της διπλωματικής εργασίας είναι η ανάπτυξη ενός αλγορίθμου τοποθέτησης (placement) για επαναδιαρθρώσιμες αρχιτεκτονικές FPGA με τη βοήθεια γενετικού αλγορίθμου.
Ανάπτυξη αλγορίθμου διασύνδεσης για 2Δ και 3Δ ψηφιακά συστήματα με τη βοήθεια της βελτιστοποίησης με αποικίες μυρμηγκιών
Η ραγδαία τεχνολογική εξέλιξη στον τομέα των ηλεκτρονικών έχει κάνει δυνατή την κατασκευή πολύπλοκων ηλεκτρονικών κυκλωμάτων σε μικρή επιφάνεια πυριτίου. Η προαναφερθείσα τάση σμίκρυνσης της τεχνολογίας σχεδιασμού, σε συνδυασμό με την ολοένα αυξανόμενη απαίτηση για υψηλότερες αποδώσεις καθιστούν επιτακτική τη χρήση νέων τεχνολογιών για τη κατασκευή των chip. Η τρισδιάστατη ολοκλήρωση, ή αλλιώς 3-D integration (3D), αποτελεί μια καινοτόμα προσέγγιση για την διασύνδεση ενός μεγάλου αριθμού τρανζίστορ, πετυχαίνοντας μεταξύ άλλων χαμηλή καθυστέρηση (υψηλή συχνότητα λειτουργίας), μειωμένη κατανάλωση ισχύος και σημαντική σμίκρυνση στην επιφάνεια πυριτίου. Στα πλαίσια της διπλωματικής εργασίας θα αναπτυχθεί ένας αλγόριθμος διασύνδεσης για τους πυρήνες που συνθέτουν 2Δ και 3Δ ψηφιακά συστήματα. Για την εύρεση αυτών των μονοπατιών θα υλοποιηθεί σε κώδικα μια προσέγγιση που θα στηρίζεται στη βελτιστοποίηση με αποικίες μυρμηγκιών (Ant Colony Optimization – ACO). Η θεωρία της βελτιστοποίησης μέσω της εφαρμογής της μελέτης της συμπεριφοράς της κοινωνίας των μυρμηγκιών εισήχθη στις αρχές της δεκαετίας του 1990 σαν μια ευρετική προσπάθεια επίλυσης δύσκολων συνδυαστικών προβλημάτων. Η έμπνευση αυτής της θεωρίας προέρχεται από τον τρόπο εύρεσης τροφής των μυρμηγκιών καθώς και την επικοινωνία μεταξύ τους για την διάδοση της πληροφορίας αυτής μέσω της εναπόθεσης φερομονών. Η αυτο-οργάνωση οδηγεί τις αποικίες να κινούνται ξεκινώντας από μια τυχαία κατάσταση σε μια πιο πολύπλοκη χωρίς την επιβολή ελέγχου αλλά με αυθόρμητο τρόπο. Ένα μοντέλο συμπεριφοράς στο οποίο ακολουθούνται συγκεκριμένοι κανόνες που καθορίζουν τη συμπεριφορά των πρακτόρων του ανάλογα με τις εξελίξεις στο περιβάλλον παρουσιάζει μεγάλη προσαρμοστικότητα και ευελιξία. Παράλληλα, επειδή στην πραγματικότητα το αποτέλεσμα λόγω της κατανεμημένης εργασίας αλλά και του συνήθους μεγάλου αριθμού πρακτόρων εμφανίζει μεγάλη ανοχή στην αποτυχία μεμονωμένων ατόμων του πληθυσμού χωρίς αυτό να επηρεάζει τη συνολική απόδοση. Στόχος της προτεινόμενης λύσης πέρα από την μεγιστοποίηση των σχεδιαστικών κερδών (π.χ. μικρότερα μήκη καλωδίου, αύξηση ταχύτητας, περιορισμός κατανάλωσης ενέργειας, κτλ) αποτελεί και η μείωση του χρόνου υπολογισμού των λύσεων (π.χ. αξιοποιώντας τεχνικές παράλληλου προγραμματισμού).
Στόχος της διπλωματικής εργασίας είναι η ανάπτυξη ενός αλγορίθμου που στηρίζεται στο Ant Theory για τον υπολογισμό της διασύνδεσης πόρων υλικού ενός 2Δ/3Δ ψηφιακού συστήματος.
Υλοποίηση αλγορίθμου διαχείρισης πόρων σε πολυπύρηνες αρχιτεκτονικές με τη βοήθεια θεωρίας αγορών
Τα συστήματα πολλαπλών πυρήνων (multi-core και many-core) καθίστανται μονόδρομος για την επίτευξη υψηλών επιδόσεων. Οι αυστηροί περιορισμοί των συγκεκριμένων συστημάτων στην κατανάλωση ενέργειας, το κόστος και την απόδοση τους μπορούν να διασφαλιστούν μόνο με τη χρήση μεθοδολογιών διαχείρισης πόρων που παρακολουθούν τις απαιτήσεις των υπο-εκτέλεση εφαρμογών σε συνδυασμό με την κατάσταση της πλατφόρμας (ύπαρξη διαθέσιμων πόρων υλικού). Για το σκοπό αυτό, τα τελευταία χρόνια δίνεται ιδιαίτερη έμφαση στην ανάπτυξη μηχανισμών που διαχειρίζονται τους πόρους υλικού (resource management). Στα πλαίσια της διπλωματικής εργασίας, θα αναπτυχθεί ένας αλγόριθμος διαχείρισης πόρων υλικού για τέτοιες αρχιτεκτονικές, ο οποίος θα βασίζεται σε αρχές της θεωρίας αγορών (Market Theory). Ο συγκεκριμένος αλγόριθμος θα καθορίζει τους πόρους υλικού στους οποίους θα ανατεθεί η εκτέλεση τμημάτων της εφαρμογής λαμβάνοντας υπόψιν παραμέτρους που σχετίζονται τόσο με την ίδια την αρχιτεκτονική (π.χ. μείωση κατανάλωσης, περιορισμός γήρανσης υλικού, κτλ), όσο και της εφαρμογής που εκτελείται (π.χ. ικανοποίηση χρονικών περιορισμών). Για την επίλυση του συγκεκριμένου προβλήματος, οι προαναφερθέντες παράμετροι θεωρούνται τιμές σε μια διαδικασία διαπραγμάτευσης που λαμβάνει χώρα σε μια αγορά. Κάθε φορά που η τιμή που προσφέρει μια εργασία ικανοποιεί έναν συγκεκριμένο πόρο υλικού (του συστήματος πολλαπλών πυρήνων), η εργασία ανατίθεται για εκτέλεση στον δεδομένο πόρο. Ο επιλεγμένος τρόπος επίλυσης του συγκεκριμένου προβλήματος επιτρέπει επίσης την παραλληλοποίηση του αξιοποιώντας τεχνικές παράλληλου προγραμματισμού.
Στόχος της διπλωματικής εργασίας είναι η υλοποίηση ενός αλγορίθμου διαχείρισης πόρων σε συστήματα πολλαπλών πυρήνων με τη βοήθεια της θεωρίας αγορών.