CarrySaveAdder

chisel3.util.CarrySaveAdder

Carry-save adder circuit generation functions. Constructs a tree to reduce an arbitrary number of input terms to two terms.

Example resulting circuit topology if applied to 8 4-bit-wide terms, a...h:

Rank 1: create groups of 3 terms, reducing each group to 2 terms; i,j,k,l,g,h
     GROUP0    GROUP1   GROUP2
       aaaa      dddd     gggg
       bbbb      eeee     hhhh
       cccc      ffff
      _____+    _____+   _____+
       iiii      kkkk     gggg
      jjjj.     llll.     hhhh
Rank 2: create groups of 3 terms, reducing each group to 2 terms: m,n,o,p
     GROUP0    GROUP1
       iiii    llll.
      jjjj.     gggg
       kkkk     hhhh
     ______+  ______+
      mmmmm    ooooo
      nnnn.    pppp.
Rank 3: create groups of 3 terms, reducing each group to 2 terms: q,r,p
     GROUP0   GROUP1
      mmmmm    pppp.
      nnnn.
      ooooo
     ______+  ______+
      qqqqq    pppp.
     rrrrr.
Rank 4: reduce last group of 3 terms to 2 terms: s,t
      qqqqq
     rrrrr.
      pppp.
     ______+
     ssssss
     tttt..

Every . is an empty spot introduced by the topology, constant zero in the carry LSB. If the input has single-bit terms, insert those there. In the example tree above, there are six spots where we can insert a single-bit term: j,l,n,p,r,t

Future improvement suggestion (not implemented yet):

  • Add support for negative weights at arbitrary bit positions; required to support subtraction.
  • The circuitry then returns two UInt hardware terms; final addition includes a signed constant offset.

Attributes

Source
CircuitMath.scala
Graph
Supertypes
class Object
trait Matchable
class Any
Self type

Members list

Value members

Concrete methods

def apply(terms: Seq[UInt], bits: Seq[Bool])(implicit sourceInfo: SourceInfo): UInt

Adds an arbitrary-length sequence of UInts in an area- and timing-efficient way, by using a Carry-Save Adder tree. The elements from the bits parameter are inserted in the holes at the LSB positions in the tree, without adding logic depth. If more bits are offered than holes are available, elaboration fails.

Adds an arbitrary-length sequence of UInts in an area- and timing-efficient way, by using a Carry-Save Adder tree. The elements from the bits parameter are inserted in the holes at the LSB positions in the tree, without adding logic depth. If more bits are offered than holes are available, elaboration fails.

Attributes

Source
CircuitMath.scala
def apply(terms: Seq[UInt])(implicit sourceInfo: SourceInfo): UInt

Adds the arbitrary-length sequence of UInts in an area- and timing-efficient way, by using a Carry-Save Adder tree.

Adds the arbitrary-length sequence of UInts in an area- and timing-efficient way, by using a Carry-Save Adder tree.

Attributes

Source
CircuitMath.scala
def apply(firstTerm: UInt, moreTerms: UInt*)(implicit sourceInfo: SourceInfo): UInt

Adds an arbitrary number of UInts in an area- and timing-efficient way, by using a Carry-Save Adder tree.

Adds an arbitrary number of UInts in an area- and timing-efficient way, by using a Carry-Save Adder tree.

Attributes

Source
CircuitMath.scala
def apply(terms: Seq[UInt], bit: Bool)(implicit sourceInfo: SourceInfo): UInt

Adds the arbitrary-length sequence of UInts in an area- and timing-efficient way, by using a Carry-Save Adder tree. Inserts an additional bit in the LSB bit position, without adding logic depth. If less than three terms are provided, there is no hole for the addtional bit, and elaboration fails.

Adds the arbitrary-length sequence of UInts in an area- and timing-efficient way, by using a Carry-Save Adder tree. Inserts an additional bit in the LSB bit position, without adding logic depth. If less than three terms are provided, there is no hole for the addtional bit, and elaboration fails.

Attributes

Source
CircuitMath.scala
def apply(terms: Seq[UInt], bit: Bool, moreBits: Bool*)(implicit sourceInfo: SourceInfo): UInt

Adds the arbitrary-length sequence of UInts in an area- and timing-efficient way, by using a Carry-Save Adder tree. The elements from the bits parameter are inserted in the holes at the LSB positions in the tree, without adding logic depth. If more bits are offered than holes are available, elaboration fails.

Adds the arbitrary-length sequence of UInts in an area- and timing-efficient way, by using a Carry-Save Adder tree. The elements from the bits parameter are inserted in the holes at the LSB positions in the tree, without adding logic depth. If more bits are offered than holes are available, elaboration fails.

Attributes

Source
CircuitMath.scala
def sumCarry(terms: Seq[UInt], bits: Seq[Bool])(implicit sourceInfo: SourceInfo): (UInt, UInt)

Adds the arbitrary-length sequence of UInts in an area- and timing-efficient way, by using a Carry-Save Adder tree. The elements from the bits parameter are inserted in the holes at the LSB positions in the tree, without adding logic depth. If more bits are offered than holes are available, elaboration fails. Returns the sum in redundant format as sum/carry tuple.

Adds the arbitrary-length sequence of UInts in an area- and timing-efficient way, by using a Carry-Save Adder tree. The elements from the bits parameter are inserted in the holes at the LSB positions in the tree, without adding logic depth. If more bits are offered than holes are available, elaboration fails. Returns the sum in redundant format as sum/carry tuple.

Attributes

Source
CircuitMath.scala
def sumCarry(terms: Seq[UInt])(implicit sourceInfo: SourceInfo): (UInt, UInt)

Adds the arbitrary-length sequence of UInts in an area- and timing-efficient way, by using a Carry-Save Adder tree. Returns the sum in redundant format as sum/carry tuple.

Adds the arbitrary-length sequence of UInts in an area- and timing-efficient way, by using a Carry-Save Adder tree. Returns the sum in redundant format as sum/carry tuple.

Attributes

Source
CircuitMath.scala
def sumCarry(firstTerm: UInt, moreTerms: UInt*)(implicit sourceInfo: SourceInfo): (UInt, UInt)

Adds an arbitrary number of UInts in an area- and timing-efficient way, by using a Carry-Save Adder tree. Returns the sum in redundant format as sum/carry tuple.

Adds an arbitrary number of UInts in an area- and timing-efficient way, by using a Carry-Save Adder tree. Returns the sum in redundant format as sum/carry tuple.

Attributes

Source
CircuitMath.scala
def sumCarry(terms: Seq[UInt], bit: Bool)(implicit sourceInfo: SourceInfo): (UInt, UInt)

Adds the arbitrary-length sequence of UInts in an area- and timing-efficient way, by using a Carry-Save Adder tree. Inserts an additional bit in the LSB bit position, without adding logic depth. If less than three terms are provided, there is no hole for the addtional bit, and elaboration fails. Returns the sum in redundant format as sum/carry tuple.

Adds the arbitrary-length sequence of UInts in an area- and timing-efficient way, by using a Carry-Save Adder tree. Inserts an additional bit in the LSB bit position, without adding logic depth. If less than three terms are provided, there is no hole for the addtional bit, and elaboration fails. Returns the sum in redundant format as sum/carry tuple.

Attributes

Source
CircuitMath.scala
def sumCarry(terms: Seq[UInt], bit: Bool, moreBits: Bool*)(implicit sourceInfo: SourceInfo): (UInt, UInt)

Adds the arbitrary-length sequence of UInts in an area- and timing-efficient way, by using a Carry-Save Adder tree. The elements from the bits parameter are inserted in the holes at the LSB positions in the tree, without adding logic depth. If more bits are offered than holes are available, elaboration fails. Returns the sum in redundant format as sum/carry tuple.

Adds the arbitrary-length sequence of UInts in an area- and timing-efficient way, by using a Carry-Save Adder tree. The elements from the bits parameter are inserted in the holes at the LSB positions in the tree, without adding logic depth. If more bits are offered than holes are available, elaboration fails. Returns the sum in redundant format as sum/carry tuple.

Attributes

Source
CircuitMath.scala