EECC756 - ShaabanEECC756 - Shaaban#1 lec # 8 Spring2000 4-6-2000Synchronous IterationSynchronous Iteration• Iteration-based computation is a powerful method for solvingnumerical (and some non-numerical) problems.• For numerical problems, a calculation is repeated and each time, aresult is obtained which is used on the next execution. The process isrepeated until the desired results are obtained.• Though iterative methods are is sequential in nature, parallelimplementation can be successfully employed when there are multipleindependent instances of the iteration. In some cases this is part of theproblem specification and sometimes one must rearrange the problemto obtain multiple independent instances.• The term "synchronous iteration" is used to describe solving a problemby iteration where different tasks may be performing separateiterations but the iterations must be synchronized using point-to-pointsynchronization, barriers, or other synchronization mechanisms.EECC756 - ShaabanEECC756 - Shaaban#2 lec # 8 Spring2000 4-6-2000BarriersBarriersA synchronization mechanismapplicable to shared-memoryas well as message-passing,where each process must waituntil all members of a specificprocess group reach a specificreference point in theircomputation• Possible Implementations:– A library call possibly implemented using a counter– Using individual point-to-point synchronization forming:• A tree• Butterfly connection pattern.EECC756 - ShaabanEECC756 - Shaaban#3 lec # 8 Spring2000 4-6-2000Processes Reaching A BarrierProcesses Reaching A BarrierAt Different TimesAt Different TimesEECC756 - ShaabanEECC756 - Shaaban#4 lec # 8 Spring2000 4-6-2000Message-Passing CounterMessage-Passing CounterImplementation of BarriersImplementation of BarriersIf 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);for (i = 0; i <n; i++) /* release slaves */ send(Pi);EECC756 - ShaabanEECC756 - Shaaban#5 lec # 8 Spring2000 4-6-2000Tree Barrier ImplementationTree Barrier ImplementationEECC756 - ShaabanEECC756 - Shaaban#6 lec # 8 Spring2000 4-6-2000Butterfly Connection PatternButterfly Connection PatternMessage-Passing BarrierMessage-Passing BarrierEECC756 - ShaabanEECC756 - Shaaban#7 lec # 8 Spring2000 4-6-2000Message-Passing LocalMessage-Passing LocalSynchronizationSynchronizationProcess Pi-1Process PiProcess Pi+1recv(Pi); send(Pi-1); recv(Pi);send(Pi); send(Pi+1); send(Pi);recv(Pi-1);recv(pi+1);EECC756 - ShaabanEECC756 - Shaaban#8 lec # 8 Spring2000 4-6-2000Synchronous Iteration Program Example:Synchronous Iteration Program Example:Iterative Solution of Linear EquationsIterative Solution of Linear Equations• Given n linear equations with n unknowns: an-1,0 x0 + an-1,1x1 + a n-1,2 x2 . . .+ an-1,n-1xn-1 = bn-1 . . a1,0 x0 + a1,1 x1 + a1,2x2 . . . + a1,n-1x n-1 = b1 a0,0 x0 + a0,1x1 + a0,2 x2 . . . + a0,n-1 xn-1 = b0By rearranging the ith equation: ai,0 x0 + ai,1x1 + ai,2 x2 . . . + ai,n-1 xn-1 = bito: 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 theunknowns to obtain a better approximation.• Jacobi Iteration: All the values of x are updated at once.EECC756 - ShaabanEECC756 - Shaaban#9 lec # 8 Spring2000 4-6-2000Iterative Solution of Linear EquationsIterative Solution of Linear EquationsJacobi Iteration Sequential Code:• Given the arrays a[][] and b[] holding the constants in theequations, x[] provided to hold the unknowns, and a fixednumber 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 - ShaabanEECC756 - Shaaban#10 lec # 8 Spring2000 4-6-2000Iterative Solution of Linear EquationsIterative Solution of Linear EquationsJacobi 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 newlycomputed values of the unknowns need to be broadcast to all the otherprocesses.• 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 computedvalue of x[i] from process i to other processes and collects databroadcast from other processes.EECC756 - ShaabanEECC756 - Shaaban#11 lec # 8 Spring2000 4-6-2000Jacobi Iteration: AnalysisJacobi Iteration: Analysis• Sequential Time equals iteration time * number of iterations. O(n2) foreach iteration.• Parallel execution time is the time of one processor each operating overn/p unknowns.• Computation for τ iterations:– Inner loop with n iterations, outer loop with n/p iterations– Inner loop: a multiplication and an addition.– Outer loop: a multiplication and a subtraction before inner loop anda subtraction and division after inner loop. tcomp = n/p(2n + 4) τ Time complexity O(n2/p)• Communication:– Occurs at the end of each iteration, multiple broadcasts.– p broadcasts each of size n/p require tdata to send each item tcomm= p(tstartup + (n/p)tdata) = (ptstartup + ntdata) τ• Overall Time: tp = (n/p(2n + 4) τ + ptstartup +