Performance and Accuracy Analysis of Programs Using Approximation Technique

Approximate programming is becoming more important due to its potential for improving performance and consequently, energy efficiency by trading off programs' accuracy but not correctness. Writing multithreaded programs is becoming more challenging due to the occurrence of concurrency bugs as well as the demand for performance and energy efficiency. Existing techniques try to trade system efficiency for correctness by debugging and preventing concurrency bugs, but still programmers are struggling. We investigate the potential for deviating from the conventional wisdom of writing concurrency bug free, parallel programs. It explores the benefit of accepting buggy but approximately correct parallel programs by leveraging the inherent tolerance of emerging parallel applications to inaccuracy in computations. Under algorithmic noise tolerance, a new class of concurrency bugs, Accuracy Bugs, degrade the accuracy of computation (often at acceptable levels) rather than causing catastrophic termination. Based on the findings of multithreaded programs' accuracy analysis, we explore the potential for approximating locks. We start out with the observation that many applications can tolerate occasional skipping of computations done inside a critical section protected by a lock. This means that for certain critical sections, when the enclosed computation is occasionally skipped, the application suffers from quality degradation in the final outcome but it never crashes/deadlocks. To exploit this opportunity, we propose Approximate Lock (ALock). The thread executing ALock checks if a certain condition (e.g., high contention, long waiting time) is met and if so, the thread returns without acquiring the lock. However, to apply various approximation techniques, a programmer has to manually identify approximable code sections of a program. Such an approach is error prone and cannot scale well beyond small applications. Therefore, we contribute with a tool, called Approximeter, to automatically identify and quantify code sections where approximation can be used and to what extent. The tool works by first identifying potential approximable functions and then, injecting errors at appropriate locations. The tool runs Monte Carlo experiments to quantify statistical relation between injected error and corresponding output accuracy. The tool also provides a rough estimate of potential performance gain from approximating a certain function. Finally, it ranks the approximable functions based on their error tolerance and performance gain. A programmer can use such a rank as a guideline to apply any approximation technique. For our accuracy bugs' investigation and performance analysis using approximate locks, we provide some results to show programs' significant characteristics of inaccuracy tolerance. We demonstrate how embracing accuracy bugs affects the application output quality and performance and analyze the impact on execution semantics. We also show the effects of approximate locks by modifying some selected critical sections using ALock so that those sections are skipped when ALock returns without acquiring the lock. Finally, we provide analysis to show how effective Approximeter is in finding approximable functions. Our experiments with two well known approximation techniques show that Approximeter is fairly accurate in predicting accuracy and performance improvement.