Approximate Synthesis: State-of-the-art and Future Directions
TimeMonday, December 6th1:30pm - 5:00pm PST
DescriptionApproximate computing is an emerging paradigm that enables reduced design area and power consumption by relaxing the requirement for full accuracy. This paradigm is particularly attractive in applications where the underlying computation has inherent resilience to small errors, which include, among many others, machine learning, computer vision and signal processing. In circuit design, a major challenge is the capability to synthesize approximate circuits automatically, without manually relying on the expertise of designers. In this tutorial, we will (1) overview error metrics and error estimation methods, (2) overview all major methods devised to synthesize approximate circuits given their exact functionality, (3) provide video tutorials for available open-source approximate synthesis tools, and (4) discuss future prospects of approximate logic synthesis.
We will outline the importance of a preliminary error-modeling phase aimed at guiding Approximate Logic Synthesis (ALS) algorithms towards efficient solutions. We will discuss the state of the art approaches for error-modeling, along with their strengths and weaknesses. Available design and benchmark circuits will be overviewed together with their associated quality metrics.
For Approximate Logic Synthesis, we will provide a categorization of existing techniques illustrating the differences between netlist transformation, where a netlist is manipulated by modifying its structure, and Boolean rewriting, whereby the logic of the circuit is first captured in a formal Boolean representation that is modified to yield an approximate Boolean representation; this is, in turn, synthesized to a gate-based netlist. For the first category, we review four different techniques: (i) greedy heuristics for netlist pruning (ii) greedy heuristics for netlist manipulation (iii) stochastic netlist transformation; and (iv) exhaustive exploration for netlist pruning. For Boolean rewriting instead, we review the following techniques: (i) logic rewriting by Boolean optimization; (ii) logic rewriting by Boolean matrix factorization; (iii) logic rewriting by binary decision diagrams; and (iv) logic rewriting by and-inverter graphs. We will provide a quantitative comparison of the performance of some of existing ALS techniques.
Approximate High-Level Logic Synthesis (AHLS) focuses on the highest level of abstraction for ALS, where the function is described at behavioural level, such as in RTL Verilog or C language. We overview AHLS techniques that (i) identify acceptable reductions to numerical precisions, (ii) simplify arithmetic expressions, (ii) deploy approximate arithmetic instead of exact arithmetic units, and (iii) utilize mixed-precision loop control and loop perforation. We will show how machine learning methods based on genetic programming can be used to approximate gate- and RT-level circuits. As many candidate approximate circuits are automatically generated by these methods, it is essential to quickly evaluate these circuits in terms of approximation error and electrical parameters. State of the art methods effectively combining search algorithms and error evaluation will be discussed.
We will also provide an overview and video demos of existing open-source tools for approximate synthesis. In particular, we will overview (i) the BACS benchmark set, (ii) ABACUS, which is a tool for AHLS, (iii) BLASYS, which is a tool for ALS; (iv) Partition and Propagate, which is a tool for error estimation;