Design methodologies for resource management of many-core embedded systems

Abstract

The current status of embedded systems contains a variety of complex computing devices featuring high-end, architecturally rich processors, heterogeneous devices and many-core systems. Furthermore, new computing architectures have been proposed at the system level, extending the concept of Internet of Things (IoT) to a multi-layer distributed infrastructure, known as Edge (or Fog) computing. This infrastructure stems from the intention to mitigate a number of inefficiencies of the original Cloud-centric deployment of IoT systems, suffering from dependency on Cloud resources, connectivity issues and unacceptably high bandwidth requirements. In such deployments, the numerous, involved computing nodes must cooperate in order to execute the variety of input tasks resulting from the highly dynamic setup of the system, which includes mobile users and unpredictable application execution requests. The developed IoT applications, must also be designed under the consideration of the updated distributed architecture to be able to fully take advantage of it.The course of this dissertation, begins by focusing on the requirements and design of embedded applications, operating on systems of multiple nodes. The target applications belong to the medical domain and thus their design requirements include but are not limited to performance, since dependability and accuracy of operations are critical in this field. The design of the IoT-oriented applications is also performed in a modular, pipelined manner in order to provide different runtime configuration knobs, for the effective operation of the device in a Gateway based offloading environment. Automated HW/SW co-design approaches using High Level Synthesis are employed in order to provide a version of the developed applications that is capable of using HW accelerators on combined CPU-FPGA Systems-on-Chip, that are able to significantly decrease the execution latency of the computationally intensive parts of the application. With respect to the design choice of the IoT Gateway, a many-core embedded system with Network-on-Chip topology is considered as a promising design alternative to meet the computational and communicational requirements, resulting from the interaction of the Gateway with numerous IoT nodes. An efficient run-time decision making mechanism is necessary for the manycore system to yield high performance operation. Due to the complexity of dynamically mapping many applications on a many-core system, a Distributed Run-Time Resource Management (DRTRM) framework is designed, implemented and evaluated on top of Intel SCC, an actual many-core NoC based computing platform.Motivated by the highly dynamic IoT environment, an additional analysis is performed to investigate the correlation of the arrival rate of incoming application requests and the effectiveness of DRTRM on allocating the available system resources. The analysis shows, that a fast and resource hungry scenario of incoming applications can be the breaking point for the effectiveness of DRTRM. Moreover, the enforcement of a relevant run-time mitigation scheme is complicated due to the distributed decision making, which requires the consensus of many agents, thus adding up to the required decision-making latency. This issue is mitigated by use of a Voltage and Frequency Scaling regulation policy, which indirectly slows down application admission, while requiring the cooperation of only a small subset of the agents of the system. The policy is implemented and evaluated on top of DRTRM, showing that it can relieve the congestion of applications under stressful conditions.The deep scaling of modern many-core systems, combined with the long operation cycles increase the probability of errors in their processing elements. Taking this into account, due to the importance of DRTRM for the operationof multiple IoT nodes and applications, SoftRM is introduced, a DRTRM augmented with fault tolerant features. The design of SoftRM relies on dynamic, workload-aware error mitigation and refrains from the provisioning of spare cores, via the self-organization of healthy agents in order to replace the failed ones. In addition, an error detection mechanism is implemented, which takes advantage of the communication patterns of DRTRM in order to reduce the overhead of error detection on the operation of healthy agents.Last, the concepts of distributed management utilized in DRTRM are extended to aid the negotiation of resources at Edge computing systems with multiple intermediate IoT Gateways. These distributed nodes, make use of trade-based mechanisms, in order to dynamically optimize the offered Service Quality to their subscribed IoT devices, while meeting their run-time constraints. These mechanisms allow to dynamically achieve more efficient binding of IoT devices to Gateways and thus fully exploit the resources of the latter in order to aid the operation of the first.

Τα σύγχρονα ενσωματωμένα συστήματα, περιέχουν πληθώρα σύνθετων υπολογιστικών συσκευών συμπεριλαμβάνοντας αρχιτεκτονικά πλούσιους επεξεργαστές υψηλού κόστους, ετερογενείς συσκευές καθώς και πολυπύρηνους επεξεργαστές. Συνάμα, στο επίπεδο του συστήματος, έχουν προταθεί νέες αρχιτεκτονικές που επεκτείνουν την ιδέα του Διαδικτύου των Πραγμάτων (ΙοΤ), κάνοντας χρήση μιας πολύ-επίπεδης κατανεμημένης υποδομής, γνωστή ως υπολογισμός στα άκρα του δικτύου (Edge computing). Η σύλληψη αυτής της υποδομής πηγάζει από την ανάγκη να αντιμετωπιστούν μια σειρά από ανεπάρκειες της αρχικής υποδομής του ΙοΤ, που ήταν βασισμένη στο Νέφος (Cloud) και ήταν ως εκ τούτου εξαρτημένη από αυτό, έπασχε από προβλήματα συνδεσιμότητας και οδηγούσε σε μη αποδεκτά μεγάλες ανάγκες για επικοινωνία από τις ΙοΤ συσκευές προς το Νέφος. Στις προτεινόμενες υπολογιστικές υποδομές, προκύπτει η ανάγκη συνεργασίας των υπολογιστικών κόμβων με σκοπό να εκτελεστεί η ποικιλία των εργασιών που προέρχονται από τα εξαιρετικά δυναμικά χαρακτηριστικά του συστήματος, το οποίο περιλαμβάνει κινούμενους χρήστες και αδυναμία πρόβλεψης των αιτημάτων εκτέλεσης εφαρμογών. Επιπρόσθετα, οι νέες υπό ανάπτυξη εφαρμογές, πρέπει να έχουν σχεδιαστεί έχοντας υπόψιν την κατανομή των συσκευών, ώστε να είναι σε θέση να επωφεληθούν πλήρως από την ανανεωμένη υποδομή.Η τρέχουσα διατριβή ξεκινά εστιάζοντας στις απαιτήσεις και τον σχεδιασμό εφαρμογών που απευθύνονται σε ενσωματωμένα συστήματα πολλαπλών κόμβων. Οι υπό σχεδίαση εφαρμογές προέρχονται από τον ιατρικό κλάδο και ως εκ τούτου οι σχεδιαστικές απαιτήσεις τους δεν περιορίζονται στην υψηλή απόδοση, καθώς η ορθή και ακριβής λειτουργία των συσκευών είναι κρίσιμη για τον εν λόγω τομέα. Οι υπό ανάπτυξη εφαρμογές που στοχεύουν στην ΙοΤ αρχιτεκτονική, σχεδιάζονται ώστε να περιλαμβάνουν διακριτά, διαδοχικά στάδια εκτέλεσης που αποτελούν διαφορετικές δυναμικές διαμορφώσεις της συσκευής ώστε να μπορεί μια εφαρμογή να εκτελεστεί αποτελεσματικά σε ένα περιβάλλον που κομμάτια της ανατίθενται να εκτελεστούν σε άλλες συσκευές πύλες (Gateways). Κεφάλαια της διατριβής αφορούν επίσης τον αυτοματοποιημένο συ-σχεδιασμό υλικού και λογισμικού με χρήση σύνθεσης υψηλού επιπέδου (High Level Synthesis), ώστε να χτιστούν επιταχυμένες εκδόσεις υπολογιστικών πυρήνων για συστήματα που συνδυάζουν κεντρικές μονάδες επεξεργασίας (CPU) καθώς και επαναδιαμορφούμενο υλικό (FPGA). Οι μεθοδολογίες αυτές καταφέρουν αξιοσημείωτη μείωση στον χρόνο εκτέλεσης των υπολογιστικά απαιτητικών τμημάτων των ΙοΤ εφαρμογών.Αναφορικά με τον σχεδιασμό μιας ΙοΤ πύλης (Gateway), η χρήση ενός πολυπύρηνου συστήματος με διασύνδεση Δικτύου-σε-Ψηφίδα (Network-on-Chip) θεωρείται ως μια υποσχόμενη σχεδιαστική επιλογή ικανή να πληροί τις υπολογιστικές και επικοινωνιακές ανάγκες που προκύπτουν από την συνεργασία την πύλης με πληθώρα ΙοΤ συσκευών. Ωστόσο, το πολυπύρηνο σύστημα χρειάζεται έναν αποδοτικό μηχανισμό δυναμικής διαχείρισης των πόρων του, ώστε να αποδώσει τις αναμενόμενες επιδόσεις. Δεδομένης της πολυπλοκότητας της δυναμικής χαρτογράφησης (mapping) πολλών εφαρμογών σε ένα πολυπύρηνο σύστημα, σχεδιάστηκε και αναπτύχθηκε ένας Κατανεμημένος Δυναμικός Διαχειριστής Πόρων. Οι επιδόσεις του εν λόγω διαχειριστή αξιολογήθηκαν σε ένα πραγματικό πολυπύρηνο σύστημα, με διασύνδεση Δικτύου-σε-Ψηφίδα εν ονόματι Intel SCC. Η δυναμική φύση του περιβάλλοντος ΙοΤ, οδήγησε στην ανάλυση του συσχετισμού του ρυθμού άφιξης νέων εφαρμογών στο σύστημα, σε σχέση με την αποτελεσματικότητα του Κατανεμημένου Διαχειριστή Πόρων. Η ανάλυση αυτή έδειξε, ότι ένα γρήγορο και πολύ απαιτητικό σενάριο έλευσης εφαρμογών μπορεί να αποτελέσει το σημείο καμπής για την ποιότητα της διαχείρισης των πόρων. Επιπρόσθετα, η εφαρμογή μια κατάλληλης δυναμικής πολιτικής για την αποφυγή αυτού του προβλήματος, δυσχεραίνεται αισθητά από την κατανεμημένη φύση του διαχειριστή που απαιτεί την ομοφωνία πολλών επί μέρους δραστών (agents), ώστε να παρθεί μια τελική απόφαση, οδηγώντας αναπόφευκτα στην επιβράδυνση της λήψης της. Με σκοπό να ξεπεραστεί αυτή η αδυναμία, έγινε χρήση τεχνικών δυναμικής μεταβολής της τάσης και συχνότητας λειτουργίας του συστήματος, οι οποίες επιτρέπουν την έμμεση επιβράδυνση του ρυθμού εισαγωγής νέων εφαρμογών στο σύστημα, απαιτώντας παράλληλα την συνεννόηση μόνο ενός μικρού υποσυνόλου των δραστών που είναι ενεργοί. Η πολιτική αυτή υλοποιήθηκε ως επέκταση του κατανεμημένου διαχειριστή πόρων και απεδείχθη ότι είναι σε θέση να ανακουφίσει αποτελεσματικά το σύστημα όταν βρίσκεται σε επιβαρυμένη κατάσταση.Η υψηλή κλιμάκωση των ψηφιακών κυκλωμάτων των σύγχρονων πολυπύρηνων συστημάτων, καθώς και η διαρκής και παρατεταμένη λειτουργία τους αυξάνει την πιθανότητα παρουσίασης σφαλμάτων στα επεξεργαστικά τους στοιχεία. Αυτό, σε συνδυασμό με την εξάρτηση των ΙοΤ συσκευών από την ορθή λειτουργίας της συσκευής πύλης, οδήγησε στην επέκταση του κατανεμημένου διαχειριστή πόρων ώστε να χαρακτηρίζεται από ανοχή στα προαναφερθέντα σφάλματα. Η επέκταση αυτή βασίζεται στην δυναμική αντιμετώπιση των σφαλμάτων, λαμβάνοντας επίσης υπόψιν τον φόρτο εργασίας του κάθε πυρήνα κατά την διάρκεια της ανάνηψης από το σφάλμα. Ακόμα, ο σχεδιασμός απέχει από την χρήση εφεδρικών (spare) πυρήνων, αλλά βασίζεται στην αυτό-οργάνωση των υγιών δραστών του συστήματος ώστε να αντικατασταθούν οι εσφαλμένοι. Πέρα από την ανάνηψη, αναπτύχθηκε και ένας μηχανισμός αναγνώρισης των σφαλμάτων, ο οποίος λαμβάνει υπόψιν του τα επικοινωνιακά μοτίβα του διαχειριστή πόρων, ώστε να μειώσει την επιβάρυνση της αναγνώρισης σφαλμάτων στην δραστηριότητα των υγιών δραστών του συστήματος.Τέλος, οι βασικές ιδέες της κατανεμημένης διαχείρισης πόρων επεκτάθηκαν ώστε να υποστηρίξουν την δυναμική διαπραγμάτευση πόρων σε συστήματα υπολογισμού στην άκρη του δικτύου (Edge computing) με πολλούς ενδιάμεσους κόμβους πύλες. Αυτοί οι κατανεμημένοι κόμβοι, κάνουν χρήση μηχανισμών βασισμένων στις ιδέες του εμπορίου ώστε να βελτιστοποιήσουν την παρεχόμενη ποιότητα υπηρεσίας στους αντίστοιχους ΙοΤ κόμβους συνδρομητές στις υπηρεσίες της πύλης, τηρώντας ταυτόχρονα τους λειτουργικούς περιορισμούς αυτών των ΙοΤ συσκευών. Οι μηχανισμοί αυτοί οδηγούν στην πιο αποτελεσματική σύνδεση των ΙοΤ συσκευών στις πύλες, επιτρέποντας έτσι την πλήρη χρήση των πόρων των δεύτερων για την εξυπηρέτηση της λειτουργίας των πρώτων.