Content deleted Content added
Line 38:
The algorithm works as follows. Observe that hypercubes of dimension <math>d</math> can be split into two hypercubes of dimension <math>d - 1</math>. Refer to the sub cube containing nodes with a leading 0 as the 0-sub cube and the sub cube consisting of nodes with a leading 1 as 1-sub cube. Once both sub cubes have calculated the prefix sum, the sum over all elements in the 0-sub cube has to be added to the every element in the 1-sub cube, since every processing element in the 0-sub cube has a lower rank than the processing elements in the 1-sub cube. The pseudo code stores the prefix sum in variable <math>x</math> and the sum over all nodes in a sub cube in variable <math>\sigma</math>.
This makes it possible for all vertex in 1-sub cube to receive the sum over the 0-sub cube in every step.
This results in a factor of <math>\log p</math> for <math>T_\text{start}</math> and a factor of <math>n\log p</math> for <math>T_\text{byte}</math>: <math>T(n,p) = (T_\text{start} + nT_\text{byte})\log p</math>.
| |||