Parallel prefix or 'scan' trees are useful for efficient implementation of computations which involve associative operators. They are used in computations like encoding, or-reduction, and addition. By leveraging advanced programming idioms, like functors, allowing for passing of function that generates prefix trees into an scan-based generator for that computation, we can have a wide variety of that computation supported by our component library. For example, we have tree patterns defined by ripple, Sklanksy, Kogge-Stone, and Brent-Kung which gives us those four varieties of prefix reduction trees we can use across addition, or-reduction, and priority encoding.
ROHD HCL implements a set of parallel prefix compute operations using different parallel prefix computation trees based on the 'ParallelPrefix' node class.
For example, we have unary operations like a word-level 'or'
ParallelPrefixOrScan
class, and a priority encoder
ParallelPrefixPriorityEncoder
class which computes the position of the first bit set to '1'. We have
simple unary arithmetic operations like an increment
ParallelPrefixIncr
class, and a decrement
ParallelPrefixDecr
class. Finally, we have a binary adder
ParallelPrefixAdder
class. For background on basic parallel prefix adder structures, see
https://en.wikipedia.org/wiki/Kogge%E2%80%93Stone_adder. In this
case, the prefix trees are carrying two-bit words at each node.
Each of these operations can be implemented with different 'ParallelPrefix' types:
Here is an example adder schematic: ParallelPrefixAdder Schematic