page_title: Hypercube (communication pattern)
section_title: Prefix sum
hierarchical_section_title: Hypercube (communication pattern) / Communication primitives / Prefix sum
caption_attribution_description: English: Example on how to calculate a prefix sum on parallel computers using a Hypercube network topology. Each node represents a processor with its own message (upper number). After the last step, the lower numbers are the prefix sum.
context_page_description: -dimensional hypercube is a network topology for parallel computers with processing elements. The topology allows for an efficient implementation of some basic communication primitives such as Broadcast, All-Reduce, and Prefix sum. The processing elements are numbered through. Each processing element is adjacent to processing elements whose numbers differ in one and only one bit. The algorithms described in this page utilize this structure efficiently.
context_section_description: In the beginning of a prefix sum operation, each processing element  owns a message . The goal is to compute , where  is an associative operation. The following pseudo code describes the algorithm.
  Input: message  of processor .
  Output: prefix sum  of processor .
   
  for  do
      
      Send  to 
      Receive  from 
      
      if bit  in  is set then endfor
  The algorithm works as follows. Observe that hypercubes of dimension  can be split into two hypercubes of dimension . 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  and the sum over all nodes in a sub cube in variable .
  This makes it possible for all nodes in 1-sub cube to receive the sum over the 0-sub cube in every step.
  This results in a factor of  for  and a factor of  for : .
caption: Example for a prefix sum calculation. Upper number: tentatetive prefix sum (variable 
    
      
        
          x
        
      
      {\displaystyle x}
    
  ). Lower number: sum over all elements in the sub cube (variable 
    
      
        
          σ
        
      
      {\displaystyle \sigma }
    
  ).
exif: {}