Αρχιτεκτονική σχεδίαση, υλοποίηση και εφαρμογή ευφυών αλγορίθμων ελέγχου σε ψηφιακά συστήματα VLSI

Abstract

Software implementations of intelligent control algorithms suffer slow execution time and increased resources demand. Referring to Genetic Algorithms, convergence to the optimal point can prove extremely time-consuming for hard or complex optimization problems, hence not allowing their use in real-time applications. Therefore, it is obvious that applying these algorithms, implemented in software, in real-time robotic applications is practically unfeasible. Based on the last fact, and the fast growth in digital circuit technology, a large number of research work dealing with intelligent control algorithms in programmable logic chips such as Field Programmable Gate Arrays or FPGAs, have been conducted and published over the last few years. The implementation of such algorithms in hardware, offers a substantial increase of data processing speed due to the inherent parallelism of the logic resources into the FPGA that allows for considerable computational throughput, thus rendering them capable of being used in real-time and increased computational complexity applications. Various intelligent algorithm cores can be easily combined with other core modules (e.g., microprocessor core) in order to form a System on a Chip (SoC), which it can be part of an autonomous robotic platform. Moreover, these cores could be used in future applications, thus increasing design re-usability. Finally, intelligent control algorithms implementation on FPGA devices helps to secure reduced power consumption, size, and cost, operation in harsh environments, and easy transfer to structured Application Specific Integrated Circuits (ASICs) if necessary. In this work, several new architectures for the design of intelligent control algorithms are proposed, specifically fuzzy controllers and genetic algorithm cores with the use of Hardware Description Languages (HDLs) and Electronic Design Automation (EDA) tools. In particular, the architectural design and implementation of a parameterized zero-order Takagi-Sugeno Digital Fuzzy Controller (DFLC) core that processes only the active rules is presented which achieves a high clock frequency. Therein after, a modified version of the DFLC is presented using a method that increases the parallelism of the architecture and achieves twice the data processing rate of the first core, by processing more than one active rule at the input of the controller per clock cycle. The fuzzy controller core was successfully bound with a microprocessor core and other secondary modules into a SoC to be eventually integrated in a robotic platform for path tracking problems. This SoC offers increased data processing and flexible hardware for different tasks. The SoC was embodied onto a Pioneer P3-DX8 mobile robot and several experiments were performed to evaluate the system’s overall performance. Finally in this work the design, implementation and performance evaluation of a Genetic Algorithm (GA) core is being analyzed. The GA core presented here possesses a high frequency of operation and logic design parallelism, allowing it to be effectively used in real-time applications. The core was evaluated using several benchmarking functions and solving the Travelling Salesman Problem (TSP) for a different number of cities.

Ένα από τα πιο σοβαρά μειονεκτήματα των ευφυών αλγορίθμων ελέγχου που έχουν αναπτυχθεί σε λογισμικό, είναι κυρίως ο χρόνος εκτέλεσής τους και η αυξημένη ανάγκη υπολογιστικών πόρων. Για παράδειγμα, στην περίπτωση των γενετικών αλγορίθμων η σύγκλισή τους προς το βέλτιστο μπορεί να είναι υπερβολικά αργή για δύσκολα και περίπλοκα προβλήματα βελτιστοποίησης, με αποτέλεσμα να είναι αδύνατη η χρήση τους σε εφαρμογές πραγματικού χρόνου. Έτσι γίνεται άμεσα αντιληπτό ότι η εφαρμογή των αλγορίθμων αυτών σε ρομποτικές εφαρμογές πραγματικού χρόνου (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 και στη συνέχεια εκτελέστηκαν διάφορα πειράματα σε εσωτερικό και εξωτερικό χώρο, ούτως ώστε να γίνει αποτίμηση της γενικής απόδοσης του συστήματος. Τέλος, στην παρούσα εργασία αναλύεται η αρχιτεκτονική σχεδίαση και υλοποίηση ενός πυρήνα Γενετικού Αλγορίθμου που επιτυγχάνει μεγάλη συχνότητα λειτουργίας και εκμεταλλεύεται την παραλληλία που προσφέρει η σχεδίαση σε υλικό δίνοντάς του τη δυνατότητα να χρησιμοποιηθεί σε εφαρμογές πραγματικού χρόνου. Ο πυρήνας αξιολογείται με τη χρήση συναρτήσεων σύγκρισης και με την εφαρμογή του πυρήνα στην επίλυση του προβλήματος του Πλανόδιου Πωλητή για διαφορετικό αριθμό πόλεων.