Optimal SAT-based Minimum Adder Synthesis of Linear Transformations
| Autor: | Shenghou Ma, Paul Ampadu |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Combinational logic
Very-large-scale integration Adder business.industry Computer science 02 engineering and technology Matrix multiplication 020202 computer hardware & architecture Application-specific integrated circuit 0202 electrical engineering electronic engineering information engineering Discrete cosine transform 020201 artificial intelligence & image processing Multiplier (economics) Arithmetic business Field-programmable gate array Boolean satisfiability problem Infinite impulse response Digital signal processing |
| Zdroj: | MWSCAS |
| DOI: | 10.1109/mwscas.2019.8885033 |
| Popis: | Linear transformation with known fixed coefficients in commonly used in VLSI circuits, e.g., discrete cosine transformation (DCT) used in image/video compression, FIR/IIR filters used in DSP, and generic matrix multiplication (GEMM) used in artificial neural networks. In all these applications, because one of the multiplicands is constant, it is possible to apply optimizations that exploit the relationships between coefficients to reduce the hardware complexity. Additionally, in hardware implementations, the coefficients are usually carefully chosen to remove the need for a generic multiplier, and instead, multiplications are implemented using only adders and shifters. Unfortunately, finding the optimal minimum adder implementations for those is NP-hard, even in the simplest GF(2) case. In this paper, we extends an existing boolean satisfiability (SAT) based formalization of this problem from GF(2) to generic case, and proposes a successive approximate framework to make the formulation feasible with current SAT solvers. This approach could not only find optimal solutions but could also formally prove the optimality of the result. When applying this to synthesis of lightweight linear transformations (e.g., approximate DCT), it could find optimal multi-layer implementations that save up to 3.4% area and 3% power comparing to state-of-the-art ASIC synthesizers and up to 22% area saving and 6% delay improvements compared to FPGA synthesizers. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|