Ευφυή ενσωματωμένα συστήματα

Abstract

In recent years, due to the increased demand for computing power, combined with the requirement for portability, a large increase in the application field of embedded systems is observed. An Embedded System (ES) may be defined as a special purpose system with limited physical size, which performs a specific and predetermined task. Indeed, depending on the time constraints of the application, ES can be divided into two broad categories: those where real-time applications must be handled strictly (hard real time embedded) and those where time restrictions do not matter that much (soft real time embedded). In order to carry out the desired task, an ES is usually equipped with a microcontroller or even a microprocessor and has the lowest possible power requirements and relatively low cost. Therefore, instead of selecting a general purpose system, the usage of a system that can perform only a particular task but is small in size, has low power consumption, increased time requirements and low cost is preferred for specific applications. With the growing use of ES, there is a shift in applications from the field of pure software running on general purpose hardware to the field of specialized hardware/software coexistence (dedicated hardware). This shift has been significantly influenced by the progress in programmable hardware and more specifically of FPGA (Field Programmable Gate Arrays), which are hardware units that can be hardware programmed in order to execute a specific task. Thus, the programming goes to a new level, where the programmer is no longer required to write source code that will run on a specific processor but the code describes the hardware itself. The description is made with special Hardware Description Languages (HDL), typical HDL are Yerilog and YHDL. The main purpose of this thesis is the implementation in hardware (FPGA) of appropriate algorithms that add “intelligence'’ to an ES, through the recognition of sentences that belong in a context free grammar (CFG) and through the evaluation of the corresponding attributes for sentences belonging to an attribute grammar (AG). A grammar is defined as a system of production rules that produce strings. The grammar categories, as defined by Chomsky, vary but in the specific thesis only CFG and an extension of them, AG, will be used. For the syntactic recognition of a sentence, suitable algorithms are used to determine whether or not a sentence belongs to a given grammar. These binary algorithms, which only respond with a yes or a no for each sentence, are called recognizers. In the case that during the recognition, a parse tree is also constructed for the given sentence, the algorithm is called parser. Furthermore, a platform for the automatic production of intelligent ES is proposed. Rather than describing the ES in classical Yerilog or YHDL, it is described at a higher level using the symbolism of attribute grammars. The implementation of attribute grammars is based on the parallel implementation of Earley’s algorithm and is an extension of the latter, allowing its implementation with smaller space and time requirements. Moreover, it has been properly extended in order to be capable to also handle attribute grammars and evaluate the corresponding attributes, defining the semantics of the grammar. To evaluate these attributes, a unit to perform the necessary actions is essential. During this work, different architectures for the syntactic analysis and the attribute evaluation have been used. More specifically, to evaluate the attributes depending on the requirements in computing power and size, the following has been chosen; the usage of a microcontroller, an external general purpose microprocessor, an internal general purpose microprocessor and finally the usage of special purpose processor specially designed for the needs of each application.

Τα τελευταία χρόνια, λόγω της αυξημένης ζήτησης σε υπολογιστική ισχύ σε συνδυασμό με την απαίτηση για μεταφερσιμότητα (portability) παρατηρείται μια μεγάλη αύξηση του πεδίου που βρίσκουν εφαρμογή τα Ενσωματωμένα Συστήματα. Ως Ενσωματωμένο Σύστημα (ΕΣ) μπορεί να οριστεί ένα σύστημα - περιορισμένου φυσικού μεγέθους - ειδικού σκοπού το οποίο επιτελεί μία συγκεκριμένη και προκαθορισμένη εργασία. Μάλιστα, αναλόγως με τους χρονικούς περιορισμούς της εφαρμογής χωρίζονται σε δύο μεγάλες κατηγορίες, σε αυτά που πρέπει να αντεπεξέλθουν αυστηρά σε εφαρμογές πραγματικού χρόνου (hard real time embedded) και σε εκείνα τα οποία είναι πιο χαλαρά σε σχέση με τους χρονικούς περιορισμούς (soft real time embedded). Για να εκτελέσει την εργασία του, το ΕΣ είναι συνήθως εφοδιασμένο με έναν μικροελεγκτή ή ακόμη και μικροεπεξεργαστή και έχει όσο το δυνατόν μικρότερες απαιτήσεις ενέργειας και σχετικά χαμηλό κόστος. Συνεπώς, αντί για την επιλογή ενός γενικής χρήσης συστήματος, προτιμάται για συγκεκριμένες εφαρμογές, η χρήση ενός συστήματος που μπορεί να εκτελέσει αποκλειστικά και μόνο μια συγκεκριμένη εργασία αλλά είναι μικρό σε μέγεθος, έχει χαμηλή κατανάλωση ισχύος, αυξημένες χρονικές απαιτήσεις και το κόστος του είναι χαμηλό. Με την ολοένα αυξανόμενη χρήση των ΕΣ, υπάρχει μια μετατόπιση των εφαρμογών από το πεδίο του καθαρού λογισμικού που εκτελείται σε υλικό γενικής χρήσης (pure software on general purpose hardware) σε αυτό της συνύπαρξης εξειδικευμένου υλικού/λογισμικού (dedicated hardware). Στη μετατόπιση αυτή έχει βοηθήσει σημαντικά και η εξέλιξη του προγραμματιζομένου υλικού και πιο συγκεκριμένα των FPGA (Field Programmable Gate Arrays), που αποτελούν μονάδες υλικού που επιτρέπουν τον εσωτερικό προγραμματισμό του υλικού τους, ώστε να επιτελείται μια συγκεκριμένη εργασία. Έτσι, ο προγραμματισμός περνάει σε ένα νέο επίπεδο, στο οποίο ο προγραμματιστής πια δεν καλείται να γράψει κώδικα που θα εκτελεστεί σε ένα συγκεκριμένο επεξεργαστή αλλά ο κώδικας περιγράφει το ίδιο το εξειδικευμένο υλικό. Η περιγραφή αυτή γίνεται με ειδικές γλώσσες περιγραφής υλικού (Hardware Description Languages - HDL), με κυριότερες τις Verilog και VHDL. Η συγκεκριμένη διατριβή έχει ως αντικείμενο την υλοποίηση σε υλικό (FPGA) κατάλληλων αλγορίθμων που προσθέτουν "ευφυΐα" σε ένα ΕΣ, μέσω της αναγνώρισης προτάσεων που ανήκουν σε γραμματικές χωρίς συμφραζόμενα καθώς και την αναγνώριση και υπολογισμό των αντίστοιχων κατηγορημάτων για προτάσεις που ανήκουν σε κατηγορικές γραμματικές. Ως γραμματική ορίζεται ένα σύστημα από κανόνες παραγωγής συμβολοσειρών. Οι κατηγορίες των γραμματικών, όπως έχουν οριστεί από τον Chomsky, ποικίλλουν αλλά στη συγκεκριμένη εργασία θα χρησιμοποιηθούν οι γραμματικές χωρίς συμφραζόμενα και μια επέκταση αυτών, οι κατηγορικές γραμματικές. Για τη συντακτική αναγνώριση μιας πρότασης, υπάρχουν κατάλληλοι αλγόριθμοι που ελέγχουν εάν η πρόταση ανήκει σε μια δοσμένη γραμματική ή όχι. Οι αλγόριθμοι αυτοί, που απλώς απαντούν δυαδικά με ένα ναι ή ένα όχι για κάθε πρόταση, ονομάζονται αναγνωριστές (recognizer). Στην περίπτωση που κατά τη διάρκεια της αναγνώρισης, παράγεται και το συντακτικό δέντρο αναγνώρισης (parse tree) για τη συγκεκριμένη πρόταση, τότε ο αλγόριθμος ονομάζεται συντακτικός αναλυτής (parser). Επιπλέον, προτείνεται ένα σύστημα για την αυτόματη παραγωγή ευφυών ΕΣ. Αντί να περιγράφεται το ΕΣ με τις κλασικές γλώσσες Verilog και VHDL περιγράφεται σε υψηλότερο δηλωτικό επίπεδο με τη χρήση του συμβολισμού των κατηγορικών γραμματικών. Η υλοποίηση των κατηγορικών γραμματικών βασίζεται στην παράλληλη υλοποίηση του αλγορίθμου του Earley και αποτελεί επέκταση του τελευταίου, επιτρέποντας την υλοποίησή του με μικρότερες απαιτήσεις χώρου αλλά και χρονικές απαιτήσεις. Επιπλέον, έχει επεκταθεί κατάλληλα ο αλγόριθμος προκειμένου να μπορεί να χειρισθεί και κατηγορικές γραμματικές και να υπολογίζει τα αντίστοιχα κατηγορήματα, που καθορίζουν τη σημασιολογία της γραμματικής. Για τον υπολογισμό των κατηγορημάτων, είναι απαραίτητη η ύπαρξη κάποιας μονάδας που να εκτελεί τις αναγκαίες πράξεις. Κατά τη διάρκεια της συγκεκριμένης εργασίας, έγινε χρήση διαφορετικών αρχιτεκτονικών για τη συντακτική ανάλυση και τον υπολογισμό των κατηγορημάτων. Συγκεκριμένα, για τον υπολογισμό των κατηγορημάτων - και ανάλογα με τις απαιτήσεις σε υπολογιστική ισχύ και μέγεθος - επιλέγεται ενίοτε η χρήση μικροελεγκτή, η χρήση εξωτερικού μικροεπεξεργαστή γενικής χρήσης, η χρήση εσωτερικού μικροεπεξεργαστή γενικής χρήσης και τελικά η χρήση επεξεργαστή εξειδικευμένης χρήσης ειδικά σχεδιασμένου για τις ανάγκες κάθε εφαρμογής.