Μεθοδολογία παραμετροποίησης εφαρμογών βασισμένων σε ταυτόχρονες δομές δεδομένων για ενσωματωμένα συστήματα

Customization methodology of applications based on concurrent data structures in embedded systems

Μεθοδολογία παραμετροποίησης εφαρμογών βασισμένων σε ταυτόχρονες δομές δεδομένων για ενσωματωμένα συστήματα

Papadopoulos, Lazaros

Παπαδόπουλος, Λάζαρος

PhD Thesis

2016

Modern embedded system architectures integrate multiple cores and they often execute applications that rely on concurrent data structures. The selection of an efficient concurrent data structure implementation is a difficult and time consuming task. Selecting a non-efficient implementation usually has negative impact on various embedded system metrics such as the performance and the energy consumption. In the present thesis, we propose a systematic methodology for the selection of effective concurrent data structures in modern embedded system applications. The methodology is semi-automatic and it is based on the exploration of the design space of concurrent data structures. It is supported by a tool flow which automates a number of steps of the methodology. The methodology allows the exploration of a number of concurrent data structures implementations by developers and the selection of the most efficient one in each context. It is applied in a number of benchmarks implemented in two modern embedded devices with different architectural specifications. The results show that by changing concurrent data structure implementations, trade-offs can be identified in many cases between metrics such as performance, energy consumption and fairness of the data structure. A similar customization methodology is proposed for the implementation of the streaming aggregation operator in embedded devices. Trade-offs between throughput, latency, required memory size and energy consumption can be identified, by selecting different customized implementations.

Στις σύγχρονες πολυπύρηνες αρχιτεκτονικές ενσωματωμένων συστημάτων, εκτελούνται συχνά εφαρμογές που βασίζονται σε ταυτόχρονες δομές δεδομένων, όπως βάσεις δεδομένων, αλγόριθμοι work-stealing κ.α.. Η επιλογή κατάλληλης δομής δεδομένων είναι ένα πολύπλοκο πρόβλημα, που αφενός η εύρεση λύσης από τον προγραμματιστή είναι χρονοβόρα διαδικασία και αφετέρου η επιλογή μη κατάλληλης υλοποίησης μπορεί να έχει αρνητική επίπτωση σε διάφορους σχεδιαστικούς περιορισμούς, όπως στην απόδοση και στην κατανάλωση ενέργειας. Για την αντιμετώπιση αυτού του προβλήματος, στην παρούσα διατριβή παρουσιάζουμε μία συστηματική μεθοδολογία για την επιλογή κατάλληλων ταυτόχρονων δομών δεδομένων στις εφαρμογές που εκτελούνται σε ενσωματωμένα συστήματα, συμβάλλοντας έτσι στη βελτιστοποίηση των εφαρμογών που τις χρησιμοποιούν. Η μεθοδολογία είναι ημιαυτόματη και βασίζεται στην εξερεύνηση του χώρου λύσεων των ταυτόχρονων δομών δεδομένων. Υποστηρίζεται από μία ροή εργαλείων που αυτοματοποιεί πολλά βήματα της μεθοδολογίας και παρέχει δυνατότητες για αποτελεσματική εξερεύνηση και επεκτασιμότητα. Δίνει την δυνατότητα στους προγραμματιστές να αξιολογήσουν με συστηματικό και αποτελεσματικό τρόπο υλοποιήσεις από τον χώρο λύσεων των ταυτόχρονων δομών δεδομένων και να επιλέξουν αυτήν που παρέχει τα καλύτερα αποτελέσματα σύμφωνα με τους σχεδιαστικούς περιορισμούς. Η μεθοδολογία εφαρμόστηκε σε μια σειρά από benchmarks υλοποιημένα σε δύο ενσωματωμένα συστήματα με διαφορετικές αρχιτεκτονικές. Τα αποτελέσματα έδειξαν ότι με κατάλληλη επιλογή υλοποίησης ταυτόχρονων δομών δεδομένων επιτυγχάνονται σε πολλές περιπτώσεις ανταλλάγματα ανάμεσα σε μετρικές όπως στην απόδοση, στην κατανάλωση ενέργειας του συστήματος και στο fairness της ταυτόχρονης δομής. Επιπλέον, αντίστοιχη μεθοδολογία παραμετροποίησης εφαρμόστηκε σε υλοποιήσεις operators επεξεργασίας ροών δεδομένων εκτελεσμένες σε ενσωματωμένες αρχιτεκτονικές. Μέσω των υλοποιήσεων που προέκυψαν, μπορούν να επιτευχθούν ανταλλάγματα μεταξύ των throughput, latency, μεγέθους απαιτούμενης μνήμης και κατανάλωσης ενέργειας.

Επιστήμες Μηχανικού και Τεχνολογία ➨ Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ

Επιστήμες Μηχανικού και Τεχνολογία

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

Embedded systems

Engineering and Technology

Ταυτόχρονες Δομές Δεδομένων

Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ

Electrical Engineering, Electronic Engineering, Information Engineering

Concurrent Data Structures

Ελληνική γλώσσα

Εθνικό Μετσόβιο Πολυτεχνείο (ΕΜΠ)

National Technical University of Athens (NTUA)

Εθνικό Μετσόβιο Πολυτεχνείο (ΕΜΠ). Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών. Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών. Εργαστήριο Μικροϋπολογιστών και Ψηφιακών Συστημάτων VLSI

National Documentation Centre (EKT)

National Archive of PhD Theses

Συλλογή ΕΑΔΔ