aproposorg / approx

A library of approximate arithmetic units in Chisel.
MIT License
1 stars 1 forks source link

approx: A Library of Approximate Arithmetic Units in Chisel

Actions Status

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.


Requirements

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.


Adders

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.

Exact designs

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

Approximate designs

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.


Multipliers

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.

Exact designs

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

Approximate designs

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.

Dividers

The approx.division library currently only contains an exact, sequential radix-2 divider. We hope to extend this collection in the future.

Exact designs

Type Signed/unsigned Name Code location
Radix-2 sequential divider Unsigned Radix2SeqDivider approx.division.Radix2SeqDivider

Approximate designs

N/A


Accumulators

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.

Exact designs

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

Approximate designs

N/A