LSV Final: Approximate Logic Synthesis

Approximate Logic Synthesis performs logic simplification and generate a functionally approximate version of the circuit that satisfies the pre-defined error bounds, such that the area is minimized.

Error rate handling methods

• ODCs [1]:
  • Construct a QoR (Quality of Result) circuit with \(f\) and \(\hat{f}\) as input, outputs 1 if the error distance between them is small enough.
  • Find the ODC of the POs of \(\hat{f}\) as the XDC to minimize \(\hat{f}\)
• Error rate estimation [2]:
  • Simplifying a node \(n\) in the Boolean network
    • Apparent Error PI Pattern causes error to occur at the output of node \(n\)
    • Real Error PI Pattern causes error to occur at the PO (intersects the fanout of \(n\))
    • The apparent error rate is an over-estimate of real error rate
  • From local to glbal
    • Compute the Local Error Input Pattern of node \(n\). Ignore the pattern if its a SDC or ODC of node \(n\)
    • Calculate the sum of probability for these remaining patterns (random simulation / or use knowledge compilation?)
    • Getting all SDCs and ODCs could be computationally expensive, could derive some only (yet the error rate is an over-estimate)
  • Algorithm
    • Single selection: Iteratively picks one most effective node \(n\) to simplify until the error rate exceeds the given threshold, but time-consuming
    • Multi-selection: Change multiple nodes at once, then the real error rate can be bounded by sum of all apparent error rate
    • Use the knapsack formulation to minimize area at most while satisfying the error-rate constraint for multi-selection
• Simulation-free error rate estimation [3]
  • Problems of approximating global error rate from local error rate, since error propagation of different nodes \(n_1, n_2\) may be dependent
    • fanout-reconvergence
    • Error masking (PI patterns that causes \(n_1\) errornous may also cause \(n_2\) to be errornous)
  • Proposed a simulation-free error rate estimation when there are no fanout-reconvergence ???

Local Change Methods

References

1. SALSA: Systematic Logic Synthesis of Approximate Circuit
2. An Efficient Method for Multi-level Approximate Logic Synthesis under Error Rate Constraint
3. Probabilistic Error Propagation through Approximated Boolean Networks