page_title: Prefix sum
section_title: Large Message Sizes: Pipelined Binary Tree
hierarchical_section_title: Prefix sum / Parallel algorithms / Concrete implementations of prefix sum algorithms / Large Message Sizes: Pipelined Binary Tree
caption_attribution_description: English: The graph represents the subtree local prefix sums of the left and right subtree of a processing element (PE) which are passed to higher level PEs during the upward phase and the partial prefix sums which are passed down during the downward phase.
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 Pipelined Binary Tree Algorithm is another algorithm for distributed memory platforms which is specifically well suited for large message sizes.
  Like the hypercube algorithm, it assumes a special communication structure. The processing elements (PEs) are hypothetically arranged in a binary tree (e.g. a Fibonacci Tree) with infix numeration according to their index within the PEs. Communication on such a tree always occurs between parent and child nodes.
  The infix numeration ensures that for any given PEⱼ, the indices of all nodes reachable by its left subtree  are less than  and the indices  of all nodes in the right subtree are greater than . The parent's index is greater than any of the indices in PEⱼ's subtree if PEⱼ is a left child and smaller if PEⱼ is a right child. 
  This allows for the following reasoning:
  The local prefix sum  of the left subtree has to be aggregated to calculate PEⱼ's local prefix sum .
  The local prefix sum  of the right subtree has to be aggregated to calculate the local prefix sum of higher level PEₕ which are reached on a path containing a left children connection (which means ).
  The total prefix sum  of PEⱼ is necessary to calculate the total prefix sums in the right subtree (e.g.  for the highest index node in the subtree).
  PEⱼ needs to include the total prefix sum  of the first higher order node which is reached via an upward path including a right children connection to calculate its total prefix sum.
  Note the distinction between subtree-local and total prefix sums. The points two, three and four can lead to believe they would form a circular dependency, but this is not the case. Lower level PEs might require the total prefix sum of higher level PEs to calculate their total prefix sum, but higher level PEs only require subtree local prefix sums to calculate their total prefix sum. The root node as highest level node only requires the local prefix sum of its left subtree to calculate its own prefix sum. Each PE on the path from PE₀ to the root PE only requires the local prefix sum of its left subtree to calculate its own prefix sum, whereas every node on the path from PEₚ₋₁ (last PE) to the PEᵣₒₒₜ requires the total prefix sum of its parent to calculate its own total prefix sum.
  This leads to a two-phase algorithm:
  Upward Phase
  Propagate the subtree local prefix sum  to its parent for each PEⱼ.
  Downward phase
  Propagate the exclusive (exclusive PEⱼ as well as the PEs in its left subtree) total prefix sum  of all lower index PEs which are not included in the addressed subtree of PEⱼ to lower level PEs in the left child subtree of PEⱼ. Propagate the inclusive prefix sum  to the right child subtree of PEⱼ.
  Note that the algorithm is run in parallel at each PE and the PEs will block upon receive until their children/parents provide them with packets.
  k := number of packets in a message m of a PEm @ {left, right, parent, this} := // Messages at the different PEsx = m @ this// Upward phase - Calculate subtree local prefix sumsfor j=0 to k-1: // Pipelining: For each packet of a message
      if hasLeftChild:
          blocking receive m[j] @ left // This replaces the local m[j] with the received m[j]
          // Aggregate inclusive local prefix sum from lower index PEs
          x[j] = m[j] ⨁ x[j]
  
      if hasRightChild:
          blocking receive m[j] @ right
          // We do not aggregate m[j] into the local prefix sum, since the right children are higher index PEs
          send x[j] ⨁ m[j] to parent
      else:
          send x[j] to parent// Downward phasefor j=0 to k-1:
      m[j] @ this = 0
  
      if hasParent:
          blocking receive m[j] @ parent
          // For a left child m[j] is the parents exclusive prefix sum, for a right child the inclusive prefix sum
          x[j] = m[j] ⨁ x[j] 
      
      send m[j] to left  // The total prefix sum of all PE's smaller than this or any PE in the left subtree
      send x[j] to right // The total prefix sum of all PE's smaller or equal than this PE
caption: Information exchange between processing elements during upward (blue) and downward (red) phase in the Pipelined Binary Tree Prefix Sum algorithm.
exif: {}