[Parallel Algo.] 11. Pointer Jumping(Doubling)

Parallel Algorithm

11. Pointer Jumping (Doubling)

Main idea

      每次和距離乘以二的processor的資料做運算直到遇到self-loop root為止

      Original version: 

          The computation proceeds by a recursive application of the calculation in hand to all   
          elements over a certain distance (in the data structure) from each individual element. 
          This distance doubles in successive steps. 

Example: Parallel prefix on a rooted directed tree

 

Input: P [1...n] = {2, 5, 2, 7, 5, 8, 6, 3, 1} and W[1...n] = {1, 2, 3, 1, 0, 3, 1, 2, 3}.
           (P[i] and W[i], is the parent and weight of node i, respectively.)Output: For each node i, W[i] is set equal to the sum of the weights of nodes on the path from i to the root of its tree. 

 The tree is self-loop at its root and the weight of the root is 0.

      [Pseudo code]

      for i from 1 􏰁 to 􏰁 n, parallel do S[i] = P[i]

      for k = 1 to log n do

             for i from 1 􏰁 to 􏰁 n, parallel do 
             begin
                   W[i] = W[i] + W[S[i]]
                   S[i] = S[S[i]] 
             end