Optimization of program execution using computational significance

Abstract

To this day, advancements in terms of performance and power efficiency for computing systems are primarily the result of transistor shrinking, frequency scaling, and parallelism exploitation. However, according to the 2013 report of the International Technology Roadmap for Semiconductors, this trend is predicted to come to a halt beyond 2020. Past practices are bound to hit the so-called power-wall of CMOS technology. Power consumption is a limiting factor and a key concern for the future of computing systems.Heterogeneous architectures are a step towards realizing power-, performance-, and energy- efficient computing platforms. The advantage of using different compute units in the same system is that each one may be very efficient for specific computation patterns. A modern example is General Purpose programming on Graphics Processing Units (GPGPU), which exploits GPUs to perform embarrassingly parallel computations efficiently. Exotic heterogeneous architectures involve the use of approximate hardware, such as Google's Tensor Processing Units. Approximate hardware enables developers to increase the performance and energy efficiency of their applications by relaxing their expectations on the accuracy of the results.Heterogeneity is not applicable to just hardware. It is inherently present at the level of software as well. After all, not all parts or execution phases of a program affect the quality of its output equally. In this Thesis we explore ways to optimize applications based on this aspect of software heterogeneity, through the algorithmic property of significance. The significance of computations is a metric that qualitatively defines the impact of the computations to the application's output quality. We introduce methodologies and frameworks which aim to identify and exploit opportunities to aggressively optimize the execution of the least significant parts of a program. These parts are costly to execute but do not heavily impact the output quality of the application.We show that it is possible to optimize applications through the principles of significance-aware approximate computing. In addition to approximate computing, we explore a more aggressive approach, significance-aware fault tolerant computing realized through the use of unreliable hardware. Our motivation is the observation that hardware designers sacrifice performance, energy, and power efficiency to maintain the illusion of hardware reliability. Consequently, it is possible to relax the reliability constraints of hardware to reduce the associated costs. Unfortunately, unreliable hardware may adversely affect the execution of applications. To this end, beyond approximate computing, we introduce a collection of frameworks, and methodologies which make it possible for a developer to execute parts of her application on extremely efficient, albeit unreliable hardware. First, we introduce the basic framework for significance aware computing. It consists of a versatile programming model and accompanying runtime-systems. It allows developers to exploit the algorithmic property of significance and gracefully trade-off output accuracy with optimized code execution. Developers may characterize the different parts of their code with respect to their significance, in other words their impact to the final application output. Following the significance characterization of the code, developers opt for either approximating the least significant parts of their code, or executing them using hardware configured at potentially unreliable operating points. During execution time, the respective runtime system orchestrates the execution of different parts of the application. Application developers provide hints to the runtime systems in order to guide the accuracy/optimization trade-off through the use of a single knob, the so called "ratio". Ratio serves as a single knob to enforce a minimum quality in the performance / quality / energy optimization space. Smaller ratios give the runtimes more opportunities for optimization, however at a potential quality penalty. For applications implemented using the fault tolerant flavor of the programming model, developers may implement result checking functions and instruct the runtime system to execute them at appropriate times. In the case of the approximate computing programming model, application developers may supply an alternative, approximate implementation of tasks. Beyond discussing the basic framework for significance-aware approximate and fault-tolerant computing we also provide methodologies to automate the process of porting applications to these two computing paradigms. Firstly, we introduce a hybrid, mathematically rigorous, profile-driven methodology which combines automatic algorithmic differentiation and interval analysis to compute the impact of selected parts of a program to its output quality. Beyond significance characterization, the same methodology may be used to provide hints to a developer to design light-weight approximate implementations of tasks.Secondly, we propose an analytical model to predict the energy consumption of an application under different input sizes and execution configurations, in terms of number of cores used, processor frequency, and the mix of accurately and approximately executed tasks. The model is used during execution-time by the runtime system to pick the best configuration for a user-specified energy budget. Even though we discuss the model in the context of approximate computing, the same methodology with minimal modifications can be used in the context of fault-tolerant computing. Finally, we present a methodology for automatic error detection in the output of tasks, based on Artificial Neural Networks (ANNs). We show that ANNs can be quite effective for error detection purposes, offering a good trade-off between accuracy and execution overhead. At the same time, they can be generated in a highly automated manner, with limited developer effort.

Η κατανάλωση ενέργειας αποτελεί έναν περιοριστικό παράγοντα και βασικό μέλημα για το μέλλον των υπολογιστικών συστημάτων. Οι ετερογενείς αρχιτεκτονικές αποτελούν ένα βήμα προς την υλοποίηση πλατφορμών υπολογιστών με μεγάλη απόδοση στους τομείς της ισχύος, επίδοσης, και κατανάλωσης ενέργειας. Φυσικά, η ετερογένεια δεν ισχύει μόνο για το υλικό. Είναι εγγενώς παρούσα και στο επίπεδο του λογισμικού. Όλα τα τμήματα ή οι φάσεις εκτέλεσης ενός προγράμματος δεν επηρεάζουν την ποιότητα των παραγόμενων αποτελεσμάτων στον ίδιο βαθμό. Στην παρούσα διδακτορική διατριβή διερευνώνται τρόποι βελτιστοποίησης των εφαρμογών με βάση αυτή την πτυχή της ετερογένειας του λογισμικού, μέσω της αλγοριθμικής ιδιότητας της σημαντικότητας (significance). Η σημαντικότητα των υπολογισμών είναι μια μετρική που καθορίζει ποιοτικά τον αντίκτυπο συγκεκριμένων υπολογισμών στην ποιότητα εξόδου της εφαρμογής. Εισάγουμε μεθοδολογίες και υλοποιούμε εργαλεία λογισμικού που στοχεύουν στον εντοπισμό και την αξιοποίηση των ευκαιριών για φιλόδοξη βελτιστοποίηση της εκτέλεσης των λιγότερο σημαντικών τμημάτων ενός προγράμματος. Αυτά τα τμήματα μπορεί να έχουν αντίστοιχο κόστος εκτέλεσης με σημαντικότερα τμήματα αλλά δεν επηρεάζουν εξίσου έντονα την ποιότητα εξόδου της εφαρμογής.Δείχνουμε ότι είναι δυνατή η βελτιστοποίηση των εφαρμογών μέσω των αρχών της προσεγγιστικής υπολογιστικής, που κάνει χρήση της αλγοριθμικής ιδιότητας της σημαντικότητας. Εκτός από την προσεγγιστική υπολογιστική, διερευνάμε και μια πιο φιλόδοξη προσέγγιση η οποία βασίζεται στη χρήση αναξιόπιστου υλικού και τις αρχές της ανοχής εφαρμογών σε σφάλματα. Το κίνητρό μας είναι η παρατήρηση ότι οι σχεδιαστές υλικού θυσιάζουν τις επιδόσεις, την ενέργεια και την αποδοτικότητα ισχύος για να διατηρήσουν την ψευδαίσθηση της αξιοπιστίας του υλικού. Κατά συνέπεια, μπορεί κανείς να χαλαρώσει τους περιορισμούς αξιοπιστίας του υλικού για να μειώσει τα σχετικά κόστη του σε ισχύ, απόδοση, καθώς και ενέργεια. Δυστυχώς, το μη αξιόπιστο υλικό μπορεί να επηρεάσει δυσμενώς την ορθότητα της εκτέλεσης των εφαρμογών. Για το σκοπό αυτό, σχεδιάζουμε μεθοδολογίες και υλοποιούμε υποστήριξη λογισμικού που δίνουν την επιλογή σε έναν χρήστη να εκτελέσει τμήματα της εφαρμογής του σε ενεργειακά αποδοτικό, αν και αναξιόπιστο υλικό.Αρχικά, εισάγουμε το βασικό πλαίσιο για τον υπολογισμό της σημαντικότητας. Αυτό συμπεριλαμβάνει ένα ευέλικτο μοντέλο προγραμματισμού και συνοδευτικά συστήματα χρόνου εκτέλεσης. Επιτρέπει στους προγραμματιστές να εκμεταλλευτούν την αλγοριθμική ιδιότητα της σημαντικότητας και την ακρίβεια της απόδοσης εξόδου με βελτιστοποιημένη εκτέλεση κώδικα. Οι προγραμματιστές μπορούν να χαρακτηρίζουν τα διάφορα μέρη του κώδικά τους σε σχέση με τον αντίκτυπό τους στην τελική έξοδο της εφαρμογής. Μετά τον χαρακτηρισμό του κώδικα ως προς τη σημαντικότητα του, οι προγραμματιστές επιλέγουν είτε να εκτελέσουν προσεγγιστικά τα λιγότερο σημαντικά τμήματα του κώδικα τους είτε να τα εκτελέσουν χρησιμοποιώντας εξοπλισμό διαμορφωμένο σε δυνητικά αναξιόπιστα σημεία λειτουργίας. Κατά τη διάρκεια του χρόνου εκτέλεσης, το αντίστοιχο σύστημα χρόνου εκτέλεσης ενορχηστρώνει την εκτέλεση διαφορετικών τμημάτων της εφαρμογής.Οι προγραμματιστές εφαρμογών παρέχουν συμβουλές στα συστήματα χρόνου εκτέλεσης για να καθοδηγήσουν την αντιστοίχιση ακρίβειας / βελτιστοποίησης μέσω της χρήσης μιας μόνο ρύθμισης, του λεγόμενου "ratio". Το ratio χρησιμεύει ως ενιαίο μοχλός για την επιβολή ελάχιστης ποιότητας στο χώρο απόδοσης / ποιότητας / ενεργειακής βελτιστοποίησης. Μικρότερες αναλογίες δίνουν στους χρόνους εκτέλεσης περισσότερες ευκαιρίες για βελτιστοποίηση, αλλά δυστυχώς και μεγαλύτερη πιθανή ποινή στην ποιότητα. Για εφαρμογές που υλοποιούνται υπό τις αρχές της ανοχής σε σφάλματα, οι προγραμματιστές μπορούν να υλοποιήσουν μεθοδολογίες για τον έλεγχο των ενδιάμεσων αποτελεσμάτων και να δώσουν εντολή στο σύστημα χρόνου εκτέλεσης να τις εκτελέσει σε κατάλληλες στιγμές. Στην περίπτωση του μοντέλου προγραμματισμού προσέγγισης, οι προγραμματιστές εφαρμογών μπορούν να παρέχουν στο σύστημα χρόνου εκτέλεσης μια εναλλακτική, κατά προσέγγιση υλοποίηση των εργασιών (approximate tasks) η οποία απαιτεί μειωμένο κόστος εκτέλεσης.Πέρα από τη συζήτηση του βασικού πλαισίου για προσεγγιστικούς υπολογισμούς αλλά και υπολογισμούς ανθεκτικούς σε σφάλματα, παρέχουμε επίσης μεθοδολογίες για την αυτοματοποίηση της διαδικασίας μεταφοράς εφαρμογών σε αυτά τα δύο υποδείγματα υπολογισμών. Βασιζόμαστε σε μια υβριδική, μαθηματικά αυστηρή μεθοδολογία η οποία όμως είναι καθοδηγούμενη από profiling εκτελέσεις και συνδυάζει την αυτόματη αλγοριθμική διαφοροποίηση (algorithmic differentiation) αλλά και την ανάλυση διαστημάτων (interval analysis) για να υπολογίσει την επίδραση επιλεγμένων τμημάτων ενός προγράμματος στην ποιότητα εξόδου του. Εισάγουμε μεθοδολογίες ώστε να εντοπίζονται σημαντικές διαφοροποιήσεις της σημαντικότητας (significance) σε μονοπάτια του κώδικα ώστε να χαρακτηρίζεται η σημαντικότητα υπολογισμών σε αδρότερο βαθμό καταμερισμού (tasks), αλλά και να παρέχεται καθοδήγηση στους προγραμματιστές για την υλοποίηση προσεγγιστικών εναλλακτικών των tasks.Στη συνέχεια, προτείνουμε ένα αναλυτικό μοντέλο για την πρόβλεψη της κατανάλωσης ενέργειας μιας εφαρμογής με διαφορετικά μεγέθη εισόδου και διαμορφώσεις εκτέλεσης. Μία τέτοια διαμόρφωση συμπεριλαμβάνει τον αριθμό των χρησιμοποιούμενων πυρήνων, την συχνότητα του επεξεργαστή καθώς και τον λόγο (ratio) των εργασιών που εκτελούνται με ακρίβεια και κατά προσέγγιση. Το μοντέλο χρησιμοποιείται κατά το χρόνο εκτέλεσης από το σύστημα χρόνου εκτέλεσης για να επιλέξει την καλύτερη διαμόρφωση για έναν προϋπολογισμό ενέργειας που καθορίζεται από τον χρήστη. Μολονότι συζητούμε το μοντέλο στο πλαίσιο της προσεγγιστικής υπολογιστικής, η ίδια μεθοδολογία με ελάχιστες τροποποιήσεις μπορεί να χρησιμοποιηθεί στο πλαίσιο των υπολογισμών ανθεκτικότητας σε σφάλματα.Τέλος, παρουσιάζουμε μια μεθοδολογία για την αυτόματη ανίχνευση σφαλμάτων στις εξόδους των εργασιών, με βάση τα Τεχνητά Νευρωνικά Δίκτυα (ΤΝΔ). Δείχνουμε ότι τα ΤΝΔ μπορεί να είναι αρκετά αποτελεσματικά για τους σκοπούς ανίχνευσης σφαλμάτων. Προσφέρουν έτσι ένα καλό αντιστάθμισμα μεταξύ ακρίβειας στην αναγνώριση σφαλμάτων και κόστους για την εκτέλεσή τους. Ταυτόχρονα, μπορούν να δημιουργηθούν με πολύ αυτοματοποιημένο τρόπο, καθώς απαιτούν περιορισμένη προσπάθεια από τη μεριά του προγραμματιστή εφαρμογών.