This repository contains a collection of approximate arithmetic units for use in various digital designs. The units are written in Chisel with tests written for the exact units using ChiselTest. Currently only a selection of adders and multipliers and a simple sequential division unit are included - more designs to come!
When you use this library in a research project, please cite it as:
@misc{damsgaard2022approx,
title={{approx: A Library of Approximate Arithmetic Units in Chisel}},
author={Damsgaard, Hans Jakob},
year={2022},
howpublished={\url{https://github.com/aproposorg/approx}}}
This README only contains a brief overview of the library's current contents. All units are commented to be reasonably understandable for people with prior knowledge of Chisel and Scala. Refer to the Digital Design with Chisel book for more details on these topics.
Utilizing Chisel and ChiselTest, approx requires a suitable installation of Scala. For this purpose, we use the Scala Build Tool (sbt) for which we provide a suitable build script.
Moreover, some tests run too slow in ChiselTest's built-in Treadle simulator, so we have instead decided to run them using Verilator (see e.g., Radix2MultiplierSpec here). Thus, to run all provided tests, one must have a suitable installation of Verilator available. Note that only specific versions of Verilator are officially supported.
This library is tested in Ubuntu 20.04 with Verilator 4.028.
The approx.addition library contains a vast number of approximate and exact adder designs that are parameterized to be reasonably flexible. The lists below specify which designs are included currently. We gladly accept requests for other designs as issues in this repository.
All exact designs are based on descriptions in Ercegovac and Lang's book on digital arithmetic.
| Type | Name | Code location |
|---|---|---|
| Half adder | HalfAdder |
approx.addition.HalfAdder |
| Full adder | FullAdder |
approx.addition.FullAdder |
| Ripple-carry adder | RCA |
approx.addition.RCA |
| Adaptive optimized lower-part constant-OR adder | AdaptiveOFLOCA |
approx.addition.AdaptiveOFLOCA |
| Carry-lookahead adder | CLA |
approx.addition.CLA |
| Two-layer carry-lookahead adder | CLA2 |
approx.addition.CLA2 |
| Carry-select adder | CSA |
approx.addition.CSA |
| Parallel prefix adder | PPA |
approx.addition.PPA |
| Self-timed adder | STA |
approx.addition.STA |
| Parallel carry-completion sensing adder | CCA |
approx.addition.CCA |
| Type | Name(s) | Code location | Reference |
|---|---|---|---|
| Full adder | AXA1, AXA2, AXA3 |
approx.addition.AXA | Yang et al. |
| Full adder | AFA |
approx.addition.AFA | Dutt et al. |
| Full adder | InXA1, InXA2, InXA3 |
approx.addition.InXA | Almurib et al. |
| Full adder | SESA1, SESA2, SESA3 |
approx.addition.SESA | Jha et al. |
| Full adder | TCAA |
approx.addition.TCAA | Yang and Thapliyal |
| Full adder | TSAA |
approx.addition.TSAA | Yang and Thapliyal |
| Accuracy-configurable adder | ACA |
approx.addition.ACA | Kahng and Kang |
| Approximate parallel prefix adder | AxPPA |
approx.addition.AxPPA | da Rosa et al. |
| Carry cut-back adder | CCBA |
approx.addition.CCBA | Camus et al. |
| Carry estimating simultaneous adder | CESA_PERL |
approx.addition.CESA_PERL | Bhattacharjya et al. |
| Dual-mode ripple-carry adder | DualModeRCA |
approx.addition.DualModeRCA | Raha et al. |
| Dual-mode carry-lookahead adder | DualModeCLA |
approx.addition.DualModeCLA | Raha et al. |
| Error-resilient adder w/o correction | ErrorResilient |
approx.addition.ErrorResilient | Dutt et al. |
| Error-resilient adder w/ correction | ErrorResilientCorrect |
approx.addition.ErrorResilientCorrect | Dutt et al. |
| Error-tolerant adder I | ETAI |
approx.addition.ETAI | Zhu et al. |
| Error-tolerant adder II | ETAII |
approx.addition.ETAII | Zhu et al. |
| Modified error-tolerant adder II | ETAIIM |
approx.addition.ETAIIM | Zhu et al. |
| FAU LUT-based adder | FAU |
approx.addition.FAU | Echavarria et al. |
| Generic accuracy-configurable adder | GeAr |
approx.addition.GeAr | Shafique et al. |
| Hybrid error reduction lower-part OR adder | HERLOA |
approx.addition.HERLOA | Seo et al. |
| Hardware-optimized adder with normal error distribution | HOAANED |
approx.addition.HOAANED | Balasubramian et al. |
| Lower-part OR adder | LOA |
approx.addition.LOA | |
| Lower-part constant-OR adder | LOCA |
approx.addition.LOCA | Dalloo |
| Lu's adder | LUA |
approx.addition.LUA | Lu |
| LUT-based adder | LutBased |
approx.addition.LUTBased | Becher et al. |
| Optimized lower-part constant-OR adder | OFLOCA |
approx.addition.OFLOCA | Dalloo |
| Reconfigurable carry-lookahead adder | RAP_CLA |
approx.addition.RAP_CLA | Akbari et al. |
| Speculative carry-skip adder | SCSkip |
approx.addition.SCSkip | Kim et al. |
| Self-adaptive adder | SelfAdaptive |
approx.addition.SelfAdaptive | Liu et al. |
| Static segment adder | SSA |
approx.addition.SSA | Jothin and Vasanthanayaki |
Beware that some approximate adders (e.g., DualModeRCA, GeAr) do not extend the abstract Adder base class as their IOs do not match those of the basic adder. Almost all designs are purely combinational; only GeAr has an option for adding a register to support flagging errors.
Like above, the approx.multiplication library contains several approximate and exact multiplier designs that are also parameterized. The list below specifies which designs are included currently. In addition to these, the tool also includes a generic compressor tree generator for ASIC, Xilinx 7-Series/UltraScale or Versal FPGA (supported by the primitives in approx.util.Xilinx), and Intel FPGA flows. The generator supports fully exact compression as well as approximation by column or row truncation, OR-based column compression, and miscounting (i.e., inexact compression). Multiple of these approximations can also be applied concurrently.
All exact designs are based on descriptions in Ercegovac and Lang's book on digital arithmetic. Note that some exact multiplier implementations, specifically Radix2Multiplier, Radix4Multiplier, RecursiveMultiplier, and AdaptiveRadix2Multiplier, permit approximation through their arguments.
| Type | Signed/unsigned | Name | Code location |
|---|---|---|---|
| Compressor 2:2 | Compressor2to2 |
approx.multiplication.Compressor3to2 | |
| Compressor 3:2 | Compressor3to2 |
approx.multiplication.Compressor3to2 | |
| Compressor 4:2 | Compressor4to2, Compressor4to2Opt |
approx.multiplication.Compressor4to2 | |
| Compressor 5:3 | Compressor5to3 |
approx.multiplication.Compressor5to3 | |
| Compressor 7:3 | Compressor7to3 |
approx.multiplication.Compressor7to3 | |
| 2x2-bit multiplier | TwoxTwo |
approx.multiplication.TwoxTwo | |
| Radix-2 array multiplier | Both | Radix2Multiplier |
approx.multiplication.Radix2Multiplier |
| Adaptive radix-2 array multiplier | Both | AdaptiveRadix2Multiplier |
approx.multiplication.AdaptiveRadix2Multiplier |
| Radix-4 array multiplier | Both | Radix4Multiplier |
approx.multiplication.Radix4Multiplier |
| Recursive multiplier | Both | RecursiveMultiplier |
approx.multiplication.RecursiveMultiplier |
| Alphabet-set multiplier | Both | AlphabetSetMultiplier |
approx.multiplication.AlphabetSetMultiplier |
| Radix-2 sequential multiplier | Unsigned | Radix2SeqMultiplier |
approx.multiplication.Radix2SeqMultiplier |
| Type | Signed/unsigned | Name | Code location | Reference |
|---|---|---|---|---|
| Reduced compressor 4:2 | Compressor4to2D1, Compressor4to2D2 |
approx.multiplication.Compressor4to2D1 | Momeni et al. | |
| Modified compressor 4:2 | Compressor4to2CV1, Compressor4to2CV2 |
approx.multiplication.Compressor4to2CV1 | Zanandrea and Meinhardt | |
| Majority-based compressor 4:2 | Compressor4to2Maj |
approx.multiplication.Compressor4to2Maj | Moaiyeri et al. | |
| Compressor 8:3 | Compressor8to3, Compressor8to3SevenSeries, Compressor8to3Versal |
approx.multiplication.Compressor8to3 | Moaiyeri et al. | |
| Kulkarni-style 2x2-bit multiplier | Kulkarni |
approx.multiplication.Kulkarni | Kulkarni et al. | |
| Rehman-style 2x2-bit multiplier | ApproxMul2, ApproxMul3, ApproxMul4, ApproxMul5 |
approx.multiplication.Rehman | Rehman et al. | |
| Configurable partial error recovery multiplier | Unsigned | CPER |
approx.multiplication.CPER | Liu et al. |
| Dynamic range unbiased multiplier | Both | DRUM |
approx.multiplication.DRUM | Hashemi et al. |
| Error-tolerant multiplier | Both | ETM |
approx.multiplication.ETM | Kyaw et al. |
| Low-power small-area multiplier | Unsigned | LPSA |
approx.multiplication.LPSA | Baba et al. |
| Minimally-biased multiplier | Unsigned | MBM |
approx.multiplication.MBM | Saadat et al. |
| Approximate radix-2 sequential multiplier | Unsigned | ApproxRadix2SeqMultiplier |
approx.multiplication.ApproxRadix2SeqMultiplier | Mannepalli et al. |
The approx.division library currently only contains an exact, sequential radix-2 divider. We hope to extend this collection in the future.
| Type | Signed/unsigned | Name | Code location |
|---|---|---|---|
| Radix-2 sequential divider | Unsigned | Radix2SeqDivider |
approx.division.Radix2SeqDivider |
N/A
The approx.accumulation library currently only contains a number of exact, non-pipelined single-lane and parallel accumulators with options for the parallel designs to be approximated with the custom compressor trees from approx.multiplication.comptree. We also hope to extend this collection in the future.
| Type | Signed/unsigned | Name | Code location |
|---|---|---|---|
| Simple accumulator | Both | SimpleAccumulator |
approx.accumulation.SimpleAccumulator |
| Multiply accumulator | Both | MultiplyAccumulator |
approx.accumulation.MultiplyAccumulator |
| Bit matrix accumulator | BitMatrixAccumulator |
approx.accumulation.BitMatrixAccumulator | |
| Parallel simple accumulator | Both | ParallelSimpleAccumulator |
approx.accumulation.ParallelSimpleAccumulator |
| Parallel multiply accumulator | Both | ParallelMultiplyAccumulator |
approx.accumulation.ParallelMultiplyAccumulator |
N/A