Go backward to Global Communication Go up to Top Go forward to Unstructured/Dynamic Communication

Global Communication

1. Distribute communication/computation

   S_i = X_i+S_i-1

   Concurrency only for multiple summations!
2. Uncover concurrency: divide&conquer

   sumi=02n-1Xi=sumi=02n-1-1Xi+sumi=2n-12n-1Xi

   Concurrency within one summation!

   divide&conquer:
     if base_case then
       solve_problem
     else 
       partition problem into L and R
       solve subproblem L with d&c
       solve subproblem R with d&c
       combine solutions of L and R
   

(See Foster, Figures 2.7 and 2.8)