TL;DR
This paper introduces a novel, general design for stochastic computing circuits that can implement arbitrary arithmetic functions. Their synthesis method significantly reduces circuit area and delay compared to existing approaches, making stochastic computing more practical for complex computations.
What Problem Does This Paper Address?
As microchip technology scales down, circuits become more susceptible to errors due to process variations and voltage fluctuations. Stochastic Computing (SC) offers a promising alternative by representing numbers as streams of bits where the probability of a '1' encodes the value. This approach inherently provides high tolerance to errors and can be implemented with simpler circuits for basic operations like multiplication. However, realizing complex arithmetic functions using SC has been a challenge, with existing methods often limited to specific function types or requiring manual circuit design. This paper aims to bridge this gap by proposing a general design and a systematic synthesis method for arbitrary arithmetic functions in the stochastic domain.
Methods
The core of the paper lies in a general design for a combinational stochastic circuit. This design takes n input variables, each representing a probability between 0 and 1, and m additional inputs fixed at a probability of 1/2. The key insight is that this architecture can implement functions of a specific form: a binary combination polynomial (BCP).
The paper then details a synthesis methodology to map arbitrary arithmetic functions (specifically polynomials) to this BCP form. This involves:
- Transformation to MLP: General polynomials are first converted into multi-linear polynomials (MLPs).
- MLP to BCP: MLPs are then uniquely mapped to BCPs. The coefficients of the BCP are derived directly from the MLP's function values at specific input points.
- BCP Coefficient Normalization: Since the proposed circuit requires coefficients within a specific range, a linear transformation is applied to normalize them.
- Heuristic for Boolean Function Synthesis: A crucial step is selecting the specific combinational logic (Boolean function) that realizes the target BCP. The paper proposes a heuristic that aims to cover the required probability values using a minimal number of "cubes" (product terms), leading to smaller and faster circuits. This heuristic prioritizes covering larger probability ranges with fewer components.
Datasets
Not discussed in the paper. The paper focuses on synthesizing circuits for arbitrary functions and uses randomly generated polynomials for experimental evaluation.
Key Insights and Ideas
- Generalizable Stochastic Circuit Design: The proposed design is flexible enough to implement a wide range of arithmetic functions, moving beyond simple operations.
- Binary Combination Polynomials (BCPs) as a Unifying Form: The paper establishes BCPs as a canonical representation for functions implementable by their proposed stochastic circuit.
- Heuristic for Efficient Synthesis: The core innovation lies in the heuristic for selecting the Boolean function. By strategically covering probability ranges, it significantly reduces circuit complexity (area and delay) compared to exhaustive or simpler approaches.
- Trade-offs in Synthesis: The paper acknowledges that while their heuristic doesn't guarantee optimality, it provides a good balance between circuit performance and synthesis complexity.
Key Results
The experimental results demonstrate the effectiveness of the proposed method:
- Significant Area and Delay Reduction: Compared to a prior state-of-the-art method for synthesizing multi-linear polynomials, the proposed approach achieved much smaller circuit area and delay, with savings growing as the number of variables and precision requirements increased. Ratios of area and delay were often below 0.4.
- Improved Performance for General Polynomials: For general polynomials, an "uneven distribution" heuristic for assigning BCP coefficients (prioritizing larger probability ranges) outperformed an "even distribution" heuristic, leading to better area, delay, and literal counts. This was shown for benchmark functions like
cos(x)andx^0.45. - Practicality: The authors note that while the synthesis runtime is exponential in m (precision) and n (variables), it remains practical for typical SC applications where these parameters are usually small.
Limitations and Future Work
- Runtime Complexity: The synthesis runtime is exponential in m and n, which could be a bottleneck for very high precision or a large number of variables.
- Heuristic vs. Optimality: The proposed synthesis heuristic does not guarantee the absolute optimal circuit, though it provides good results.
- Future Work: The paper suggests exploring more advanced heuristics for Boolean function synthesis and potentially extending the design to sequential circuits for further optimization.
Summary updated