At the beginning of a [[Prefix_sum|prefix sum]] operation, each processing unitelement <math>i</math> owns a message <math>m_i</math>. AtThe thegoal endis each processing unit <math>i</math> shouldto recievecalculate <math>\bigoplus_{0 \le j \le i} m_j</math>, where <math>\oplus</math> is an associative operation. The following pseudo code describes the algorithm.
'''Input''': message <math>m_i</math> of processor <math>i</math>.
Line 37:
'''endfor'''
HypercubesThe algorithm works as follows. Observe that hypercubes of dimension <math>d</math> can be split into two hypercubes of dimension <math>d - 1</math>. InRefer the followingto the sub cube ofcontaining allnodes verticeswith startinga withleading 0 willas be referred to asthe 0-subcubesub cube and the sub cube consisting of all vertices startingnodes with a leading 1 as 1-subcubesub cube. Once both sub cubes have calculated the prefix sum, the sum over all elements in the 0-subcubesub cube has to be added to the every element in the 1-subcubesub cube, becausesince every processing element in the 0-subcubesub cube has a lower rank than the processing elements in the 1-subcubesub cube. InThe thepseudo implementationcode eachstores vertex not saves histhe prefix sum (in variable <math>x</math>) and the sum over all elementsnodes in hisa sub cube (in variable <math>\sigma</math>).
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>.
