★
This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
# K3.2 Parallelization Overheads

Parallelization of a program always introduces some extra work in addition to the work done by the sequential version of the program.
The main sources of parallelization overhead are data communication (between processes) and synchronization (of processes and threads).
Other sources are additional operations that are introduced at the algorithmic level (for example in global reduction operations) or at a lower software level (for example by address calculations).


## Learning Outcomes

* Comprehend that **Data communication** is necessary for programs that are parallelized for distributed memory computers (if data communication is not necessary the program is called trivially or embarrassingly parallel).
* Comprehend that **Synchronization** plays an important role with shared memory parallelization.
* Comprehend that there are also other sources of parallel inefficiency like:
    * Parts of a program that were not parallelized and still run serially.
    * Unbalanced loads.
* Comprehend that there are two hardware effects that can reduce the efficiency of the execution of shared-memory parallel programs:
    * **NUMA** can lead to noticeable performance degradation if data locality is bad (i.e. if too much data that a thread need is not in its NUMA domain).
    * **False sharing** occurs if threads process data that is in the same data cache line, which can lead to serial execution or even take longer than explicitly serial execution of the affected piece of code.
* Comprehend the overheads caused by redundant computations
* Comprehend the problems of execution speed noise (OS jitter, cache contention, thermal throttling, etc.), and typical trade-offs (e.g. reducing the synchronization overhead by increasing the communication overhead)
Links

Submit a proposal for an examination question