Μεθοδολογία Παραμετροποίησης Εφαρμογών Βασισμένων Σε Ταυτόχρονες Δομές Δεδομένων Για Ενσωματωμένα Συστήματα

Abstract

Μεγάλος αριθμός από αρχιτεκτονικές σύγχρονων ενσωματωμένων συστημάτων περιλαμβάνει πολλαπλούς πυρήνες. Στις συγκεκριμένες αρχιτεκτονικές εκτελούνται συχνά εφαρμογές που βασίζονται σε ταυτόχρονες δομές δεδομένων, όπως βάσεις δεδομένων, αλγόριθμοι work-stealing κ.α.. Η επιλογή κατάλληλης δομής δεδομένων είναι ένα πολύπλοκο πρόβλημα που αφενός η λύση του από τον προγραμματιστή είναι χρονοβόρα και αφετέρου επιλογή μη κατάλληλης υλοποίησης μπορεί να έχει αρνητική επίπτωση σε διάφορους σχεδιαστικούς περιορισμούς, όπως η απόδοση και η κατανάλωση ενέργειας. Για την αντιμετώπιση αυτού του προβλήματος, στην διατριβή παρουσιάζεται μία συστηματική μεθοδολογία για την επιλογή κατάλληλων ταυτόχρονων δομών δεδομένων στις εφαρμογές που εκτελούνται σε ενσωματωμένα συστήματα, συμβάλλοντας έτσι στη βελτιστοποίηση των εφαρμογών τις χρησιμοποιούν. Η μεθοδολογία είναι ημιαυτόματη και βασίζεται στην εξερεύνηση του χώρου λύσεων των ταυτόχρονων δομών δεδομένων. Υποστηρίζεται από μία ροή εργαλείων που αυτοματοποιεί πολλά βήματα της μεθοδολογίας και παρέχει δυνατότητες για αποτελεσματική εξερεύνηση και επεκτασιμότητα. Δίνει τη δυνατότητα στους προγραμματιστές να αξιολογήσουν με συστηματικό και αποτελεσματικό τρόπο υλοποιήσεις από τον χώρο λύσεων των ταυτόχρονων δομών δεδομένων και να επιλέξουν αυτήν που παρέχει τα καλύτερα αποτελέσματα σύμφωνα με τους σχεδιαστικούς περιορισμούς. Η μεθοδολογία εφαρμόστηκε σε μια σειρά από benchmarks υλοποιημένα σε δύο ενσωματωμένα συστήματα με διαφορετικές αρχιτεκτονικές. Τα αποτελέσματα έδειξαν ότι με κατάλληλη επιλογή υλοποίησης ταυτόχρονων δομών δεδομένων επιτυγχάνονται σε πολλές περιπτώσεις ανταλλάγματα ανάμεσα σε μετρικές όπως η απόδοση, η κατανάλωση ενέργειας του συστήματος και το fairness της δομής.Στα πλαίσια της διατριβής αναλύεται ο σχεδιασμός ταυτόχρονων δομών δεδομένων βασισμένων στο μοντέλο clients-server, το οποίο είναι μία παραλλαγή του μοντέλου Remote-core-locking που έχει προταθεί στον χώρο των HPC, προσαρμοσμένο στα χαρακτηριστικά των ενσωματωμένων συστημάτων. Μελετώνται τα χαρακτηριστικά των ενσωματωμένων συστημάτων και των δομών δεδομένων για τα οποία το συγκεκριμένο μοντέλο είναι κατάλληλο. Επίσης, παρουσιάζονται αποτελέσματα της σύγκρισης ταυτόχρονων δομών δεδομένων σχεδιασμένων με τυπικό τρόπο και σχεδιασμένων με το μοντέλο clients-server. Τα αποτελέσματα δείχνουν ότι ταυτόχρονες δομές δεδομένων βασισμένες στο μοντέλο client-server θα πρέπει να αξιολογούνται, σε συστήματα που παρέχουν αποτελεσματική επικοινωνία μεταξύ των πυρήνων και σε δομές που παρέχουν μειωμένο παραλληλισμό (π.χ. ουρές, στοίβες). Τέλος, δείχνεται ότι η μέθοδος ταξινόμησης του χώρου σχεδιασμού και η εξερεύνησή του ώστε να εντοπιστούν ανταλλάγματα, μπορεί να εφαρμοστεί σε διάφορους χώρους. Στη διατριβή μελετάται η εφαρμογή της μεθόδου στον χώρο επεξεργασίας ροών δεδομένων σε ενσωματωμένα συστήματα. Παρουσιάζεται ο χώρος σχεδιασμού βασισμένος σε δέντρα αποφάσεων και εντοπίζονται οι παράμετροι της υλοποίησης που επηρεάζουν έναν αριθμό από μετρικές (απόδοση, απαιτούμενο μέγεθος μνήμης, κατανάλωση ενέργειας, κ.α.). Έτσι, επιλέγοντας διαφορετικές υλοποιήσεις, επιτυγχάνονται ανταλλάγματα μεταξύ των μετρικών.