Skip to content

Algorithm X

  • asynchronous algorithm for solving DO-ALL
  • can be used with failure model of detectable restarts
  • uses progress tree of size \(2n - 1\)
  • Total shared memory used is \(O(N + P)\)
  • consists of a single initialization and of parallel loop → will continue to loop until done

Pseudocode

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
forall processors PID=0..p - 1 parbegin
    Perform initial processor assignment to the leaves of 
    the progress tree 

    while there is still work left in the tree do
        if subtree rooted at current node u is done then
            move one level up

        else if u is a leaf then
            perform the work at the leaf

        elseif u is an interior tree node then
           Let ul and ur be the left and right children of u respectively 

            if the subtrees rooted at ul and ur are done then 
                update u 
            else if only one is done then 
                go to the one that is not done 
            else 
                move to ul or ur according to PID bit values
    fifi od
parend.

Complexity

Analysis
Termination after \(O(P \cdot N)\)
Work, \(P \geq N\) \(S = O(P \cdot N^{\log_2{\frac{3}{2}}})\)
Work, \(P \leq N\) \(S = O(N \cdot P^{\log_2{\frac{3}{2}}})\)
  • work complexity is the same for both: asynchronous systems and synchronous system with crashes and detectable restarts.
  • this is asynchronous → will not analyze time
  • \(\log_2{\frac{3}{2}} \approx 0.59\)