University of Thessaly (UTH)
Optimization of program execution using computational significance
Abstract
dc:descriptionTo 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.
Degree
thesis:*- Grantor dc:publisher
- University of Thessaly (UTH)
- Year dc:date
- 2017
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Vassiliadis, Vassils
- Βασιλειάδης, Βασίλειος
Subjects
dc:subject × 11- Εκτέλεση εφαρμογών με χρήση της ιδιότητας της σημαντικότητας
- Προσσεγιστικός υπολογισμός
- Ανοχή σε Σφάλματα
- Approximate computing
- Significance computing
- Unreliable computing
- Fault tolerance
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Engineering and Technology
- Electrical Engineering, Electronic Engineering, Information Engineering
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/42225