Foundations and Trends® in Electronic Design Automation > Vol 5 > Issue 3

Stochastic Computing

By John Sartori, University of Illinois at Urbana-Champaign, USA, sartori2@illinois.edu | Rakesh Kumar, University of Illinois at Urbana-Champaign, USA, rakeshk@illinois.edu

 
Suggested Citation
John Sartori and Rakesh Kumar (2011), "Stochastic Computing", Foundations and TrendsĀ® in Electronic Design Automation: Vol. 5: No. 3, pp 153-210. http://dx.doi.org/10.1561/1000000021

Publication Date: 21 Dec 2011
© 2011 J. Sartori and R. Kumar
 
Subjects
Physical Design
 

Free Preview:

Download extract

Share

Download article
In this article:
1 Introduction 
2 Design-Level Techniques for Stochastic Computing 
3 Architecture Frameworks for Stochastic Computing 
4 Compiler Optimizations for Stochastic Computing 
5 Scheduling and Mapping for Stochastic Processors 
6 Application and Programming Language Support for Stochastic Processors 
7 Testing Techniques 
8 Other Work 
9 Summary and Future Work 
References 

Abstract

As device sizes shrink, manufacturing challenges at the device level are resulting in increased variability in physical circuit characteristics. Exponentially increasing circuit density has not only brought about concerns in the reliable manufacturing of circuits but also has exaggerated variations in dynamic circuit behavior. The resulting uncertainty in performance, power, and reliability imposed by compounding static and dynamic nondeterminism threatens the continuation of Moore's law, which has been arguably the primary driving force behind technology and innovation for decades. This situation is exacerbated by emerging computing applications, which exert considerable power and performance pressure on processors. Paradoxically, the problem is not nondeterminism, per se, but rather the approaches that designers have used to deal with it. The traditional response to variability has been to enforce determinism on an increasingly nondeterministic substrate through guardbands. As variability in circuit behavior increases, achieving deterministic behavior becomes increasingly expensive, as performance and energy penalties must be paid to ensure that all devices work correctly under all possible conditions. As such, the benefits of technology scaling are vanishing, due to the overheads of dealing with hardware variations through traditional means. Clearly, status quo cannot continue.

Despite the above trends, the contract between hardware and software has, for the most part, remained unchanged. Software expects flawless results from hardware under all possible operating conditions. This rigid contract leaves potential performance gains and energy savings on the table, sacrificing efficiency in the common case in exchange for guaranteed correctness in all cases. However, as the marginal benefits of technology scaling continue to languish, a new vision for computing has begun to emerge. Rather than hiding variations under expensive guardbands, designers have begun to relax traditional correctness constraints and deliberately expose hardware variability to higher levels of the compute stack, thus tapping into potentially significant performance and energy benefits and also opening the potential for errors. Rather than paying the increasing price of hiding the true, stochastic nature of hardware, emerging stochastic computing techniques account for the inevitable variability and exploit it to increase efficiency. Stochastic computing techniques have been proposed at nearly all levels of the computing stack, including stochastic design optimizations, architecture frameworks, compiler optimizations, application transformations, programming language support, and testing techniques. In this monograph, we review work in the area of stochastic computing and discuss the promise and challenges of the field.

DOI:10.1561/1000000021
ISBN: 978-1-60198-508-8
64 pp. $55.00
Buy book (pb)
 
ISBN: 978-1-60198-509-5
64 pp. $100.00
Buy E-book (.pdf)
Table of contents:
1: Introduction
2. Design-Level Techniques for Stochastic Computing
3. Architecture Frameworks for Stochastic Computing
4. Compiler Optimizations for Stochastic Computing
5. Scheduling and Mapping for Stochastic Processors
6. Application and Programming Language Support for Stochastic Processors
7. Testing Techniques
8. Other Work
9. Summary and Future Work
References

Stochastic Computing

The continuing ability of manufacturers to produce smaller devices with each technology generation has enabled the exponentially increasing circuit density and capability that has driven technological innovation for decades. However, compounding static and dynamic non-determinism resulting from the manufacturing challenges that accompany technology scaling has resulted in uncertainty in performance, power, and reliability that threaten the continuation of Moore's law. This situation is exacerbated by emerging computing applications, which exert considerable power and performance pressure on processors. Paradoxically, the problem is not non-determinism, per se, but rather the approaches that designers have used to deal with it. As variability in circuit behavior increases, traditional approaches that aim to enforce deterministic behavior on a non-deterministic substrate become increasingly costly. Clearly, status quo cannot continue. In response to these challenges, stochastic computing techniques that exploit error resilience and enable energy-reliability tradeoffs have been proposed at nearly all levels of the computing stack, including stochastic design optimizations, architecture frameworks, compiler optimizations, application transformations, programming language support, and testing techniques. Though researchers have made inroads in these areas, the landscape is still ripe for exploration. This book reviews work in the area of stochastic computing and discuss the promise and challenges of the field.

 
EDA-021