| Abstract |
We are at the threshold of an explosion in new data, produced not only by large, powerful scientific and commercial computers, but also by the billions of low-power devices, from notebooks and mobile interface devices to cell phones and sensors of various kinds. The traditional techniques of processing such information by first storing them in databases and then manipulating and serving them through large computers are becoming too expensive. These complex large systems have a high acquisition cost, but, in addition, suffer also from high running costs, especially in power consumption. Both these costs can be contained by recognizing that there is a precision implied by traditional computing that is not needed in the processing of most new types of data. The relaxation of precision, such as the strict guarantees of memory coherence and consistency, can help in the wider exploitation of known energy-efficient modes of computing like throughput computing. More important, the relaxation of requirement of deterministic execution provides us an opportunity to deploy in the processing of this vast new data the same low-power, low-cost technology that was used to generate the data in the first place. Such energy-efficient circuits suffer from greater unreliability and variability in performance when used in the high-throughput mode, but these problems can be addressed by changing the way we design such systems, changing the nature of the algorithms for such systems, and by modifying the expectation of the quality of results produced by such systems. We have called this the approximate computing paradigm [1]. Solutions that provide non-exact results have long been used in computing. The precision of numbers represented in computers is limited and hence values of quantities represented in a computer are only an approximation of their actual values. Heuristic algorithms produce solutions to hard problems in much shorter time compared to optimal algorithms in exchange for results that may only approach in quality those produced by optimal algorithms. The difference is that these approaches, while approximate, produce the same results each time they are used on a piece of data, whereas in approximate computing we do not expect to produce the same results each time the algorithm is exercised on the same data. There are two sources of imperfection in approximate computing. The first arises from imperfect execution of an algorithm. This can be due to problems with the design of the algorithm or of the hardware, due to faults that occur after deployment of the hardware, due to the variability of operation of circuits when pushed to their design limits, or due to malicious attacks on systems. The second arises from imperfection in the data stream itself because of missing data or modified data, produced intentionally, as through data compression, or unintentionally, as through faulty communication channels. All these imperfections could potentially be rectified through the use of expensive techniques such as redundancy, conservative design, or conservative device operating range. The goal of approximate computing, however, is to combat these sources of imperfection inexpensively and in an energy-efficient manner while producing results that may be different, yet acceptable. Computing models that achieve this goal have to address both the detection and the correction of such imperfections. The detection of such imperfections can be done either by the user observing and reacting to a wrong result as in media applications, by the algorithm expecting a range of correct results as in the estimation technique of [2], or by the run-time monitoring of the execution of the system as in [3]. The correction of system behavior can be done either by attempting a different algorithm as in [2], by patching the code as in [3], or by repeating the execution. We will argue in this talk that future systems will need to combine all these techniques and integrate new ones into a single dynamically optimized system that employs feedback from the user to guide the high-level choice of energy-efficient algorithms, and that employs prediction based on past experience to guide the low-level energy-efficient execution of the system. This has a tantalizing similarity to some models of functioning of a remarkably efficient approximate computing appliance we all know — the human brain. [1] R. Nair and D. A. Prener, “Computing, Approximately,” Wild and Crazy Ideas VI, ASPLOS-XIII, Seattle, WA, March 2008. [2] S. P. Narayanan et al, “Computation as estimation: Estimation-theoretic IC design improves robustness and reduces power,” Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing, March 30-April 4, 2008. [3] J. H. Perkins et al, “Automatically Patching Errors in Deployed Software,” 22nd ACM Symposium on Operating Systems Principles, Big Sky, Montana, October 2009. |
