Ανάπτυξη μεθοδολογίας για την βελτιστοποίηση τύπων δεδομένων δυναμικών εφαρμογών σε ενσωματωμένα συστήματα

Abstract

The next generation of embedded computing systems will be dominated by mobile, smart devices capable of delivering a wide range of communication and multimedia services anywhere. This set of devices includes PDAs, smartphones and video consoles. On the other hand, as technology progresses, users demand more and more complex and dynamic applications. Cases like voice transmission VoIP, high definition video rendering, internet browsing and 3D applications share as common characteristic the increased need in data storage and access. In order to provide a flowing performance in this wide range of applications, the optimization of the embedded systems is necessary in both the hardware and the software level. In dynamic applications, data is stored in entities called data structures, dynamic data types or simply containers, like arrays, lists or trees, which can adapt dynamically to its needs. These containers are realized at the software architecture level and are responsible for keeping and organizing the data in the memory and also servicing the application’s requests at run-time. The latter include abstract data type operators for storing, retrieving or altering any data value, which is not tied to a specific container implementation and shares a common interface. The implementation of these operators depends on the chosen container and each one of them can favour specific data access and storage patterns. Moreover, modern applications behave differently based on the various inputs that stimulate them. This leads to the execution of different paths in the source code, which in turn translates to a dynamic and most importantly unpredictable use of data. Since data are stored on data structures, the implementation of these structures should be customized to the particular data usage pattern. Therefore, it is necessary to carefully design the data structures inside a modern application. Unfortunately, in today’s development cycles for embedded systems, often there is not time for such an optimization. Developers tend to target the fast completion and debugging of the source code in order to quickly enter the market. As a result, they use existing solutions either in the form of template libraries or own implementations developed for other applications. These solutions are not customized for the particular application, which can lead to suboptimal performance. This thesis addresses the optimization of dynamic data structures in dynamic applications, focusing on the customization of these structures to meet the exact needs of the application. The proposed approach is automatic and tested in a variety of application domains.

Η επόμενη γενιά των ενσωματωμένων συστημάτων θα κυριαρχείται από κινητές, έξυπνες συσκευές, οι οποίες θα είναι ικανές να προσφέρουν ένα μεγάλος εύρος υπηρεσιών επικοινωνίας και πολυμέσων σε οποιοδήποτε σημείο βρίσκονται. Το σύνολο αυτών των συσκευών περιλαμβάνει συσκευές όπως, PDA, έξυπνα τηλέφωνα και κονσόλες βιντεοπαιχνιδιών. Από την άλλη μεριά, οι εφαρμογές που καλούνται τα εκτελέσουν τα ενσωματωμένα συστήματα γίνονται ολοένα πιο πολύπλοκες και δυναμικές. Εφαρμογές όπως η μετάδοση φωνής μέσω διαδικτύου (VoIP), η αναπαραγωγή βίντεο, η πρόσβαση στο διαδίκτυο, και η αναπαραγωγή τρισδιάστατων εφαρμογών, έχουν ως κοινό χαρακτηριστικό τις αυξημένες ανάγκες σε αποθήκευση και πρόσβαση δεδομένων. Για την αποδοτική εκτέλεση αυτών των εφαρμογών απαιτείται η βελτιστοποίηση των ενσωματωμένων συστημάτων, τόσο σε επίπεδο υλικού, όσο και σε επίπεδο πηγαίου κώδικα. Στις δυναμικές εφαρμογές τα δεδομένα αποθηκεύονται σε συγκεκριμένες δομές που ονομάζονται δομές δεδομένων, δυναμικοί τύποι δεδομένων ή περιέχοντες τύποι, όπως πίνακες, λίστες, δέντρα και οι οποίες μπορούν να προσαρμόζονται στις ανάγκες των εφαρμογών. Οι δομές αυτές είναι υπεύθυνες για την οργάνωση των δεδομένων στη μνήμη αλλά και την εξυπηρέτηση των αναγκών των εφαρμογών κατά την ώρα εκτέλεσής τους. Τέτοιες ανάγκες αποτελούν οι λειτουργίες για την αποθήκευση, ανάγνωση ή μεταβολή των δεδομένων μιας δομής. Η υλοποίηση αυτών των λειτουργιών εξαρτάται από την εκάστοτε δομή και μπορεί να ευνοήσει συγκεκριμένες ακολουθίες πρόσβασης και αποθήκευσης δεδομένων. Κάθε δυναμικός τύπος δεδομένων σε μια εφαρμογή μπορεί να υλοποιηθεί ως πίνακας, ως λίστα ή ως δέντρο. Το γεγονός αυτό διευρύνει τις πιθανές επιλογές του σχεδιαστή, που πρέπει να εξεταστούν για να βρεθεί η βέλτιστη υλοποίηση, σύμφωνα με τις ανάγκες του. Επιπλέον, η συμπεριφορά των μοντέρνων δυναμικών εφαρμογών εξαρτάται από τα δεδομένα εισόδου. Αυτό συχνά σημαίνει ότι ακολουθούνται πολλαπλά και διαφορετικά μονοπάτια εκτέλεσης της εφαρμογής, πράγμα που οδηγεί σε πολύπλοκη, δυναμική χρήση των δεδομένων, σύμφωνα με τη συμπεριφορά του χρήστη. Η υλοποίηση των δομών δεδομένων μιας εφαρμογής πρέπει να προσαρμόζεται στις εκάστοτε συνθήκες χρήσης των δυναμικών δεδομένων. Επομένως, απαιτείται προσεκτικός σχεδιασμός πριν την τελική επιλογή της υλοποίησης των δυναμικών δομών σε μια εφαρμογή, κάτι το οποίο δεν αποτελεί κανόνα στο σημερινό τρόπο ανάπτυξης εφαρμογών στα ενσωματωμένα συστήματα. Συνήθως, οι σχεδιαστές λογισμικού έχουν ως στόχο την ολοκλήρωση του κώδικα σε μικρό χρονικό διάστημα, με αποτέλεσμα να βασίζονται σε έτοιμες λύσεις για την υλοποίηση των δομών δεδομένων, είτε με τη μορφή καθιερωμένων βιβλιοθηκών, είτε με τη μορφή δικών τους υλοποιήσεων που ανέπτυξαν για άλλες εφαρμογές. Οι λύσεις αυτές δεν είναι προσαρμοσμένες στην εκάστοτε εφαρμογή, γεγονός που μπορεί να οδηγήσει σε μη βέλτιστες επιδόσεις. Η συγκεκριμένη διατριβή αντιμετωπίζει το πρόβλημα της βελτιστοποίησης δυναμικών δομών δεδομένων σε εφαρμογές ενσωματωμένων συστημάτων. Στόχος είναι η προσαρμογή της υλοποίησης των δομών στις εκάστοτε ανάγκες της εφαρμογής, καθώς και η αυτοματοποίηση της όλης διαδικασίας.