stapl::skeletons::spans::binomial_tree< OnSpan, Phase > Struct Template Reference

A span for binomial trees which is used in algorithms such as binomial tree scan. More...

Detailed Description

template<typename OnSpan, typename Phase>
struct stapl::skeletons::spans::binomial_tree< OnSpan, Phase >

A span for binomial trees which is used in algorithms such as binomial tree scan.

A binomial tree based algorithm consists of two phases: an up-phase and a down-phase. The up-phase looks similar to a right_aligned tree if the input size is power-of-two. In the case of arbitrary size inputs the right_aligned tree is extended with partial right_trees in order to make the up-phase. Both phases for an input of size 10 can be depicted as:

O O O O O O
|\| |\| |\|
| O_| O | O
| | |\| | |
| | | O | |
| | | | | |
| | | O | |
| | | |\|_|
| O | O | O
| |\| |\| |
O O O O O O

Template Parameters

OnSpan	the span on which this tree is defined
Phase	phase of the binomial tree (up_phase or down_phase)

See also

inclusive_scan(op,tags::binomial_tree)

---

The documentation for this struct was generated from the following file:

• binomial_tree.hpp