Content deleted Content added
Line 39:
Hypercubes of dimension <math>d</math> can be split into two hypercubes of dimension <math>d - 1</math>. In the following the sub cube of all vertices starting with 0 will be referred to as 0-subcube and the sub cube of all vertices starting with a 1 as 1-subcube. Once both sub cubes have calculated the prefix sum, the sum over all elements in the 0-subcube has to be added to the every element in the 1-subcube, because every processing element in the 0-subcube has a lower rank than the processing elements in 1-subcube. In the implementation each vertex not saves his prefix sum (variable <math>x</math>) and the sum over all elements in his sub cube (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>.
[[File:Hypergraph Communication Steps for Prefix Sum.png|thumb|Example for a prefix sum calculation. Upper number: number <math>m_i</math> that each processing element contributes to the prefix sum. Lower number: prefix sum (at the end of the computation).]]
| |||