Low-discrepancy Deterministic Bit-stream Processing

Applications

• Stochastic computing
• Digital chips operating in domains such as image and signal processing and machine learning applications.
• Approximate computing applications and applications that tolerate some degree of uncertainty (such as video processing, image processing, neural networks)

Deterministic computation based-on low-discrepancy sequences

While deterministic approaches of stochastic computing using unary and pseudo-random bit-streams (such as linear feedback shift registers) to produce completely accurate results, they suffer from major drawbacks such as high processing time and energy consumption compared to conventional binary radix-based designs. With unary stream-based deterministic methods, the output converges to the expected correct value slowly - poor progressive precision. This slow convergence makes the deterministic approaches inefficient for applications that can tolerate some inaccuracy (e.g., image processing and neural network applications). In addition, deterministic methods developed so far have limited scalability.

Researchers at the University of Minnesota have developed two novel methods for fast-converging, scalable deterministic computation based-on low-discrepancy sequences. Of these, one method provides the best accuracy for a fixed processing time while the other method has the lowest area × delay product. Both methods produce completely accurate results if running the operation for a specific number of cycles. The bit-streams can quickly and monotonically converge to the target value, producing acceptable results in a much shorter time compared to state-of-the-art methods. These methods significantly reduce the processing time and the energy consumption when a slight inaccuracy is acceptable.

Key Benefits & Differentiators

• Significantly lower processing time and area-delay product compared to state-of-the-art methods
• Lower error rate compared to conventional methods for the same processing time; Mean absolute error of 10^-3 while processing 2^15 bit streams
• No random fluctuations
• Scales well with increasing number of inputs

Phase of Development

Theoretical foundation developed; validated with simulation and design verification tools (SPICE)