page_title: Prefix sum
section_title: Distributed memory: Hypercube algorithm
hierarchical_section_title: Prefix sum / Parallel algorithms / Concrete implementations of prefix sum algorithms / Distributed memory: Hypercube algorithm
caption_attribution_description: English: Scheme of construction of hypercube up to 4D 0D is point 0D -&gt; 1D&#160;: From point to segment 1D -&gt; 2D&#160;: From segment to square 2D -&gt; 3D&#160;: From square to cube 3D -&gt; 4D&#160;: From cube to tesseract
context_page_description: In computer science, the prefix sum, cumulative sum, inclusive scan, or simply scan of a sequence of numbers x₀, x₁, x₂, ... is a second sequence of numbers y₀, y₁, y₂, ..., the sums of prefixes of the input sequence:
  y₀ = x₀
  y₁ = x₀ + x₁
  y₂ = x₀ + x₁+ x₂
  ...
  For instance, the prefix sums of the natural numbers are the triangular numbers:
  Prefix sums are trivial to compute in sequential models of computation, by using the formula yᵢ = yᵢ − 1 + xᵢ to compute each output value in sequence order. However, despite their ease of computation, prefix sums are a useful primitive in certain algorithms such as counting sort,
  and they form the basis of the scan higher-order function in functional programming languages. Prefix sums have also been much studied in parallel algorithms, both as a test problem to be solved and as a useful primitive to be used as a subroutine in other parallel algorithms.
  Abstractly, a prefix sum requires only a binary associative operator ⊕, making it useful for many applications from calculating well-separated pair decompositions of points to string processing.
context_section_description: The Hypercube Prefix Sum Algorithm is well adapted for distributed memory platforms and works with the exchange of messages between the processing elements. It assumes to have  processor elements (PEs) participating in the algorithm equal to the number of corners in a -dimensional hypercube.
  Throughout the algorithm, each PE is seen as a corner in a hypothetical hyper cube with knowledge of the total prefix sum  as well as the prefix sum  of all elements up to itself (according to the ordered indices among the PEs), both in its own hypercube.
  The algorithm starts by assuming every PE is the single corner of a zero dimensional hyper cube and therefore  and  are equal to the local prefix sum of its own elements.
  The algorithm goes on by unifying hypercubes which are adjacent along one dimension. During each unification,  is exchanged and aggregated between the two hyper cubes which keeps the invariant that all PEs at corners of this new hyper cube store the total prefix sum of this newly unified hyper cube in their variable . However, only the hyper cube containing the PEs with higher index also adds this  to their local variable , keeping the invariant that  only stores the value of the prefix sum of all elements at PEs with indices smaller or equal to their own index.
  In a -dimensional hyper cube with  PEs at the corners, the algorithm has to be repeated  times to have the zero-dimensional hyper cubes be unified into one -dimensional hyper cube.
  Assuming a duplex communication model where the  of two adjacent PEs in different hyper cubes can be exchanged in both directions in one communication step, this means  communication startups.
  i := Index of own processor element (PE)m := prefix sum of local elements of this PEd := number of dimensions of the hyper cubex = m;     // Invariant: The prefix sum up to this PE in the current sub cubeσ = m;     // Invariant: The prefix sum of all elements in the current sub cubefor (k=0; k <= d-1; k++){
      y = σ @ PE(i xor 2^k)  // Get the total prefix sum of the opposing sub cube along dimension k
      σ = σ + y              // Aggregate the prefix sum of both sub cubes
  
      if (i & 2^k){
          x = x + y  // Only aggregate the prefix sum from the other sub cube, if this PE is the higher index one.
      }}
caption: Different hypercubes for varying number of nodes
exif: {}