BARRIER & APPLICATION BROKEN BARRIERS
BROADCASTED
•
• •
•
•
BARRIER
Sometimes when we use parallelized algorithm, we need to stop at some checkpoints.
Next iteration relies on previous iteration.
Need to wait for all the threads to complete their job. Barrier is a solution
All the threads have to arrive at barrier before any of them moves on.
First Iteration
BARRIER
Second Iteration
BARRIER
THREAD I
THREAD J
THREAD K
• •
• • • •
•
typedef struct barrier_t {
pthread_mutex_t mtx; pthread_cond_t cv; unsigned n_threads; unsigned count;
} barrier_t;
BARRIER
• •
• •
•
•
BARRIER
A NON-REUSABLE SOLUTION
Use ‘count’ to keep track of #(threads arrived) If ‘count’ reaches #total threads
Good to go.
Tell all the threads waiting. Else
Wait until the condition is satisfied.
BARRIER REUSABLE BARRIER
reuse
BARRIER
BARRIER
THREAD I
THREAD J
THREAD K
BARRIER REUSABLE BARRIER
What is the problem for reusable barrier
You have to reset the barrier when all the threads are leaving.
Count variable has to be reset.
If your wait condition relies on `count’
What happens to other threads when count variable is reset by one thread? Race Condition?
•
•
•
•
•
POISSON SOLVER
err3
Y X3
err2 err1
x x
X1
X2
x2 = g(x1, err1)
2 = g(x1,err1) 3 = g(x2,err2) xj = g(xi,erri)
When err < epsilon the solution is good enough!e!!rr3 Y epsilon x2 = g(x1,err1) x3 = g(x2,err2) xj = g(xi,erri) POISSON SOLVER Take x3 as solution X3 X2 X1 POISSON SOLVER If your x is a vector (a,b,c,d) You want to parallelize your solver err1 err2 Err err3 err4 A2 B2 C2 D2 A1 B1 X1 C1 D1 update POISSON SERIAL VERSION MAIN SERIAL_POISSON POISSON_SETUP SOLVE_POISSON WRITE_FILE POISSON_DESTROY poisson_test.c POISSON MAIN serial_poisson() 1. SET UP PARAMETERS AND FUNCTIONS 2. RUN POISSON SOLVER MAIN() parallel_poisson() 1. SET UP PARAMETERS AND FUNCTIONS 2. SET UP THE NUMBER OF THREADS 3. RUN POISSON SOLVER POISSON SOLVER SOLVE_POISSON_HELPER 1. Calculate error 1. Write temp result to file SERIAL_POISSON SOLVE_POISSON Write to file Do until error < epsilon Image Matrix POISSON HOW TO PARALLELIZE IT SOLVER Image Matrix solve_poisson_helper(...,startX, startY, width, height) POISSON HOW TO PARALLELIZE IT SOLVER I SOLVER II SOLVERIII startY height SUB MATRIX width startX POISSON HOW TO PARALLELIZE IT Image Matrix ERR1 ERR2 ERR3 ERR4 ERR5 ERR6 ERR7 ERR8 ERR9 Total Error 1. Share between threads! (HINT!HINT!) 2. When can threads move on to next iteration? height SUB MATRIX width startX startY • • Can each solver thread move on to next iteration right after calculating errors? Can each solver thread move on to next iteration right after they update the image matrix? Do these problems happen many times? Think of following questions • • POISSON WHY DO WE NEED BARRIER