skill-tree:k:3:2:b
Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| skill-tree:k:3:2:b [2020/07/19 19:38] – lucy | skill-tree:k:3:2:b [2025/04/16 18:30] (current) – external edit 127.0.0.1 | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | # K3.2-B Parallelization Overheads | + | # K3.2 Parallelization Overheads |
| - | # Background | + | |
| Parallelization of a program always introduces some extra work in addition to the work done by the sequential version of the program. | 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). | 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). | 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). | ||
| - | # Aim | ||
| - | * To provide knowledge about overheads for communication and synchronization that are introduced by parallelization. | ||
| - | * To provide knowledge about other sources of parallel inefficiency: | ||
| - | # Outcomes | + | ## Learning |
| - | * 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 **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 there are also other sources of parallel inefficiency like: | + | * 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. | * Parts of a program that were not parallelized and still run serially. | ||
| * Unbalanced loads. | * 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). | * **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. | * **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) | ||
| - | # Subskills | ||
skill-tree/k/3/2/b.1595180309.txt.gz · Last modified: 2020/07/19 19:38 by lucy