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).

• 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.
• the overheads caused by redundant computations
• 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)