Synchronous Iteration Synchronous Parallelism Barriers Counter Barrier Implementation Tree Barrier Implementation Butterfly Connection Pattern Message Passing Barrier Synchronous Iteration Program Example Iterative Solution of Linear Equations Dynamic Load Balancing Centralized Dynamic Load Balancing Decentralized Dynamic Load Balancing Distributed Work Pool Using Divide And Conquer Distributed Work Pool With Local Queues In Slaves Termination Detection for Decentralized Dynamic Load Balancing Program Example Shortest Path Problem EECC756 Shaaban 1 lec 9 Spring2002 4 18 2002 Synchronous Iteration Iteration based computation is a powerful method for solving numerical and some non numerical problems For numerical problems a calculation is repeated and each time a result is obtained which is used on the next execution The process is repeated until the desired results are obtained Though iterative methods are is sequential in nature parallel implementation can be successfully employed when there are multiple independent instances of the iteration In some cases this is part of the problem specification and sometimes one must rearrange the problem to obtain multiple independent instances The term synchronous iteration is used to describe solving a problem by iteration where different tasks may be performing separate iterations but the iterations must be synchronized using point to point synchronization barriers or other synchronization mechanisms EECC756 Shaaban 2 lec 9 Spring2002 4 18 2002 Synchronous Iteration Synchronous Parallelism Each iteration composed of several processes that start together at beginning of iteration Next iteration cannot begin until all processes have finished previous iteration Using forall for j 0 j n j for each synch iteration forall i 0 i N i N processes each using body i specific value of i or for j 0 j n j for each synchr iteration i myrank find value of i to be used body i barrier mygroup EECC756 Shaaban 3 lec 9 Spring2002 4 18 2002 A synchronization mechanism applicable to shared memory as well as message passing pvm barrier MPI barrier where each process must wait until all members of a specific process group reach a specific reference point in their computation Barriers Possible Implementations Using a counter linear barrier Using individual point to point synchronization forming A tree Butterfly connection pattern EECC756 Shaaban 4 lec 9 Spring2002 4 18 2002 Processes Reaching A Barrier At Different Times EECC756 Shaaban 5 lec 9 Spring2002 4 18 2002 Centralized Counter Barrier Implementation Called linear barrier since access to centralized counter is serialized thus O n time complexity EECC756 Shaaban 6 lec 9 Spring2002 4 18 2002 Message Passing Counter Implementation of Barriers If the master process maintains the barrier counter It counts the messages received from slave processes as they reach their barrier during arrival phase Release slaves processes during departure phase after all the processes have arrived for i 0 i n i count slaves as they reach their barrier recv Pany O n Time Complexity for i 0 i n i release slaves send Pi EECC756 Shaaban 7 lec 9 Spring2002 4 18 2002 Tree Barrier Implementation 2 log n steps time complexity O log n EECC756 Shaaban 8 lec 9 Spring2002 4 18 2002 Tree Barrier Implementation Suppose 8 processes P0 P1 P2 P3 P4 P5 P6 P7 Arrival phase log8 3 stages First stage P1 sends message to P0 when P1 reaches its barrier P3 sends message to P2 when P3 reaches its barrier P5 sends message to P4 when P5 reaches its barrier P7 sends message to P6 when P7 reaches its barrier Second stage P2 sends message to P0 P2 P3 reached their barrier P6 sends message to P4 P6 P7 reached their barrier Third stage P4 sends message to P0 P4 P5 P6 P7 reached barrier P0 terminates arrival phase when P0 reaches barrier received message from P4 Release phase also 3 stages with a reverse tree construction Total number of steps 2 log n 2 log 8 6 EECC756 Shaaban 9 lec 9 Spring2002 4 18 2002 Butterfly Connection Pattern Message Passing Barrier Butterfly pattern tree construction Log n stages thus O log n time complexity Pairs of processes synchronize at each stage two pairs of send receive For 8 processes First stage P0 P1 P2 P3 P4 P5 P6 P7 Second stage P0 P2 P1 P3 P4 P6 P5 P7 Third stage P0 P4 P1 P5 P2 P6 P3 P7 EECC756 Shaaban 10 lec 9 Spring2002 4 18 2002 Message Passing Local Synchronization Process Pi 1 Process Pi recv Pi send Pi send Pi 1 send Pi 1 recv Pi 1 recv pi 1 Process Pi 1 recv Pi send Pi EECC756 Shaaban 11 lec 9 Spring2002 4 18 2002 Synchronous Iteration Program Example Iterative Solution of Linear Equations Given a system of n linear equations with n unknowns an 1 0 x0 an 1 1x1 a n 1 2 x2 an 1 n 1xn 1 a1 0 x0 a1 1 x1 a1 2x2 a1 n 1x n 1 a0 0 x0 a0 1x1 a0 2 x2 a0 n 1 xn 1 By rearranging the ith equation ai 0 x0 ai 1x1 ai 2 x2 ai n 1 xn 1 bn 1 b1 b0 bi to xi 1 a i i bi ai 0 x0 ai 1x1 ai 2 x2 ai i 1 xi 1 ai i 1 xi 1 ai n 1 xn 1 or This equation can be used as an iteration formula for each of the unknowns to obtain a better approximation Jacobi Iteration All the values of x are updated at once EECC756 Shaaban 12 lec 9 Spring2002 4 18 2002 Iterative Solution of Linear Equations Jacobi Iteration Sequential Code Given the arrays a and b holding the constants in the equations x provided to hold the unknowns and a fixed number of iterations the code might look like for i 0 i n i x i b i initialize unknowns for iteration 0 iteration limit iteration for i 0 i n i sum 0 for j 0 j n j compute summation of a x if i j sum sum a i j x j new x i b i sum a i i Update unknown for i 0 i n i update values x i new x i EECC756 Shaaban 13 lec 9 Spring2002 4 18 2002 Iterative Solution of Linear Equations Jacobi Iteration Parallel Code In the sequential code the for loop is a natural barrier between iterations In parallel code we have to insert a specific barrier Also all the newly computed values of the unknowns need to be broadcast to all the other processes Process Pi could be of the form x i b i initialize values for iteration 0 iteration limit iteration sum a i i x i for j 1 j n j compute summation of a x sum sum a i j x j new x i b i sum a i i compute unknown broadcast receive new x i broadcast values global barrier wait for all processes The broadcast routine broadcast receive sends the newly computed value of x i from process i to other processes and collects data broadcast from other processes EECC756 Shaaban 14 lec 9 Spring2002 4 18 2002