Αρχιτεκτονική σχεδίαση, υλοποίηση και εφαρμογή ευφυών αλγορίθμων ελέγχου σε ψηφιακά συστήματα VLSI
Date Issued
2010
Author(s)
Advisor
Abstract
Ένα από τα πιο σοβαρά μειονεκτήματα των ευφυών αλγορίθμων ελέγχου που έχουν αναπτυχθεί σε λογισμικό, είναι κυρίως ο χρόνος εκτέλεσής τους και η αυξημένη ανάγκη υπολογιστικών πόρων. Για παράδειγμα, στην περίπτωση των γενετικών αλγορίθμων η σύγκλισή τους προς το βέλτιστο μπορεί να είναι υπερβολικά αργή για δύσκολα και περίπλοκα προβλήματα βελτιστοποίησης, με αποτέλεσμα να είναι αδύνατη η χρήση τους σε εφαρμογές πραγματικού χρόνου. Έτσι γίνεται άμεσα αντιληπτό ότι η εφαρμογή των αλγορίθμων αυτών σε ρομποτικές εφαρμογές πραγματικού χρόνου (real-time) καθιστά τις υλοποιήσεις σε λογισμικό ανεπαρκείς. Βάση του τελευταίου, τα τελευταία χρόνια λόγω της ταχείας ανάπτυξης στην τεχνολογία των ψηφιακών κυκλωμάτων, έχει αναφερθεί ένας σημαντικά μεγάλος αριθμός ερευνητικών εργασιών που ασχολούνται με υλοποιήσεις ευφυών αλγορίθμων σε υλικό. Η υλοποίηση τέτοιων αλγορίθμων σε υλικό προσφέρει σημαντική αύξηση στην ταχύτητα επεξεργασίας των δεδομένων λόγω της ενδογενούς παραλληλίας που προσφέρει η ψηφιακή σχεδίαση επιτρέποντάς τους έτσι να χρησιμοποιηθούν ικανοποιητικά σε εφαρμογές πραγματικού χρόνου και αυξημένης υπολογιστικής πολυπλοκότητας. Η δημιουργία ξεχωριστών πυρήνων (cores) διαφορετικών ευφυών αλγορίθμων επιτρέπει την εύκολη ενσωμάτωσή τους με άλλες δομικές μονάδες (π.χ., πυρήνες μικροεπεξεργαστών) για την υλοποίηση συστημάτων σε ψηφίδα (System on a Chip - SoC) που τελικά μπορούν να ολοκληρώσουν μια αυτόνομη υπολογιστική πλατφόρμα. Επιπρόσθετα, οι πυρήνες αυτοί μπορούν να χρησιμοποιηθούν σε μελλοντικές εφαρμογές αυξάνοντας έτσι τη δυνατότητα επαναχρησιμότητας της σχεδίασης (design reusability). Τέλος, η υλοποίησή τους σε ολοκληρωμένα κυκλώματα προγραμματιζόμενης λογικής (Field Programmable Gate Arrays - FPGAs) συντελεί στη σημαντική μείωση της απαιτούμενης ισχύος λειτουργίας, τη σημαντική μείωση του μεγέθους, τη δυνατότητα λειτουργίας σε δύσκολα περιβάλλοντα, τη μείωση κόστους και την εύκολη μεταφορά τους σε δομημένα ολοκληρωμένα κυκλώματα ASIC (structured Application Specific Integrated Circuits) εάν αυτό απαιτείται. Στην παρούσα εργασία παρουσιάζονται νέες αρχιτεκτονικές για τη σχεδίαση ασαφών ελεγκτών και γενετικών αλγορίθμων σε υλικό με τη χρήση γλωσσών περιγραφής υλικού (Flardware Description Languages - HDLs) και εργαλεία αυτοματοποίησης της σχεδίασης (Electronic Design Automation - EDA tools). Πιο συγκεκριμένα παρουσιάζεται η αρχιτεκτονική σχεδίαση και υλοποίηση ενός παραμετρικού πυρήνα ασαφούς ελεγκτή τύπου Takagi-Sugeno μηδενικού-βαθμού, που επεξεργάζεται μόνο τους ενεργούς κανόνες και επιτυγχάνει υψηλή συχνότητα λειτουργίας. Στη συνέχεια δίνεται μια τροποποιημένη εκδοχή του πυρήνα αυτού χρησιμοποιώντας μια μέθοδο που αυξάνει την παραλληλία της σχεδίασης και επιτυγχάνει διπλάσιο ρυθμό επεξεργασίας δεδομένων μέσω της ταυτόχρονης επεξεργασίας στην είσοδο του ελεγκτή περισσότερων από ένα ενεργών κανόνων σε κάθε κύκλο ρολογιού. Στη συνέχεια, ο πυρήνας ασαφούς ελεγκτή συνδέθηκε με έναν πυρήνα μικροεπεξεργαστή και άλλες δευτερεύουσες δομικές μονάδες για να αποτελέσουν ένα SoC που ολοκληρώνει μία ρομποτική πλατφόρμα παρακολούθησης πορείας με τη χρήση ασαφούς λογικής για αυτόνομα κινητά ρομπότ. Η συγκεκριμένη πλατφόρμα προσφέρει αυξημένη δυνατότητα επεξεργασίας και ευέλικτο υλικό για διαφορετικές διεργασίες. Επιπρόσθετα, το αναφερόμενο SoC προσαρμόστηκε πάνω σε ένα κινητό ρομπότ Pioneer P3-DX8 και στη συνέχεια εκτελέστηκαν διάφορα πειράματα σε εσωτερικό και εξωτερικό χώρο, ούτως ώστε να γίνει αποτίμηση της γενικής απόδοσης του συστήματος. Τέλος, στην παρούσα εργασία αναλύεται η αρχιτεκτονική σχεδίαση και υλοποίηση ενός πυρήνα Γενετικού Αλγορίθμου που επιτυγχάνει μεγάλη συχνότητα λειτουργίας και εκμεταλλεύεται την παραλληλία που προσφέρει η σχεδίαση σε υλικό δίνοντάς του τη δυνατότητα να χρησιμοποιηθεί σε εφαρμογές πραγματικού χρόνου. Ο πυρήνας αξιολογείται με τη χρήση συναρτήσεων σύγκρισης και με την εφαρμογή του πυρήνα στην επίλυση του προβλήματος του Πλανόδιου Πωλητή για διαφορετικό αριθμό πόλεων.