Parallel, Dist, wbe centric computing midterm terms

Race condition

When the outcome of a program is determined by the uncontrollable timing of two events. For example, two threads trying to increment the same counter. Both read 0, both add 1, both write 1 back. The expected output is 2 but the final result is 1.

Critical section

A specific section of code that must not be executed by more than one thread at a time to prevent race conditions.

Critical Section syntax

#pragma omp critical <name>

Deadlock

A state where a set of processes are blocked becasuse each process is holding a resource and witing for another resource held be another process in the set. Nobody can more forward.

Process Synchronization

Coordination of the execution between multiple processes to ensure they dont interfere with each other.

Semaphore

A signaling mechanism used to control accesss to a common resource

Barrier

All threads must reach a certain point before continuation

Thread safety

A property of a piece of code or data structure that guarantees it will function correctly, meaning no data corruption or race conditions, when accessed by multiple threads simultaneously.

Amdahls law

Speedup(S) = 1 / (1-p) + p/s where p is the proportion of the program that can be made parallel and s is the speedup of that part.

Efficiency

Speedup/ # of processors

Speedup

The ratio of the time taken to solve a problem on a single processor to the time taken on n processors. T1/Tn

Static scheduling

Loop iterations divided into fixed-size chunks assigned to threads at the very beginning

Dynamic scheduling

Iterations are broken into chunks and assigned to threads on-demand during runtime. When a thread is finished with a chunk it asks for the next available chunk.

Guided scheduling

Designed to reduce the overhead of dynamic scheduling. Starts wiht large chunks to reduce overhead then progressively decreases the chunk size as it reaches the end of the loop.

Situations for each scheduling type.

Fixed is best when work per iteration is equal. Dynamic is best when work per iteration is unpredictable. Dynamic is best when work is unbalances but you want less overhead.

Mutex

Mutex’s are critical sections for pthreads, you lock and unlock a mutex with the critical section falling within

#pragma omp critical vs #pragma omp atomic

atomic is used for single operations li ++ or — while critical can be used for more complex sections