Параллельные вычисления

1.

Параллельные вычисления
Учебный год – 2020/21, осенний семестр
Группы P42142
Лекция 2
Преподаватели:
Балáкшин Павел Валерьевич
([email protected]),
Мишенёв Алексей
([email protected])

2.

Типовой сценарий работы
программиста
1.
2.
3.
4.
5.
6.
7.
Write a single threaded program.
Stop.
Try automatic paralleling.
Stop.
Try parallel libraries and data structures.
Stop.
Profile the application, estimate the maximum achievable
paralleling effect.
8. Stop.
9. Parallelize bottlenecks and frequently called functions.
Цель параллельного программирования – избежать
параллельного программирования!
2

3.

Parallel programming terminology
• Process – процесс: наиболее тяжеловесный механизм;
сложные или медленные механизмы синхронизации общих
переменных; процессы имеют независимые адресные
пространства. Могут иметь несколько потоков выполнения.
• Thread – поток = нить = тред: имеют общее разделяемое
между ними адресное пространство и развитые механизмы
синхронизации доступа к общим переменным. Используются
механизмы синхронизации данных.
• Fiber – волокно = легковесный поток: минимальные
накладные расходы; отсутствие истинного физического
распараллеливания; нужны для удобства программирования.
Все волокна в отличее от потоков исполняются на одном и
том же ядре.
3

4.

Жизненые цикл потока
4

5.

Parallel programming terminology (2)
Источник
Thread-safe
Reentrant / reentrable
Qt
Внутри функции обращение ко
всем общим переменным
осуществляется строго последовательно, а не параллельно
(Thread safe является reentrant,
но не наоборот)
При вызове функции
одновременно несколькими
потоками гарантируется
правильная работа, только
если потоки не используют
общие данные
Linux
Функция показывает
правильные результаты, даже
если вызвана несколькими
тредами одновременно
Функция показывает
правильные результаты,
даже если повторно вызвана
изнутри себя
POSIX
?
Функция показывает
правильные результаты,
даже если вызвана
несколькими
тредами одновременно 5

6.

Not thread-safe, not reentrant
6

7.

Thread-safe, not reentrant
7

8.

Not thread-safe, reentrant
8

9.

Thread-safe, reentrant
9

10.

Hardware parallelism types
According to S. Akhter “Multi-Core Programming”
10

11.

Hyperthreading
According to S. Akhter “Multi-Core Programming”
11

12.

Multithreading on single-processor
systems vs. multiprocessor systems
• On a single-processor (single-core) system you can use thread
priorities to arrange their access to the processor (on a multiprocessor system you cannot do it).
• On a single-processor system you need to pack structures more
tightly to optimize the memory cache, and on a multi-core system
you need to cut them by the size of the cache string to prevent
False Sharing.
12

13.

Parallel programming problems
Measuring parallel efficiency.
Instability of floating point calculation results.
Race conditions.
Mutual interlocks.
The ABA problem.
Inversion of priorities.
Load Balancing (LJF).
Scalability.
False sharing (+ hardware optimization).
13

14.

Problems measuring parallel
speedup
Reasons:
1. Background load
presence.
2. Random nature
of the algorithm.
According to materials of Prof. A.V. Boukhanovsky
14

15.

Measurement of parallel program
execution time
Universal tools:
• Unix utility time (measures the total execution of a program
without possibility of any detail).
• C-function clock (does not take into account idle time).
• C-function ctime (not reenterable, see not cross-platform
alternative to ctime_r).
• C-function gettimeofday, clock_gettime.
Specialized tools:
• Library function omp_get_wtime (maybe the function
omp_get_wtick will need to be used).
15

16.

Measurement of parallel program
execution time (2)
Solutions:
• Use thread-safe reentrant functions (for example rand_r instead
of rand).
• Measure the time several times and then:
1) take minimum sampling/measurement OR
2) calculate the confidence interval.
16

17.

Subunit and super linear speedups
Possible reasons:
1. Overhead costs (i.e. 1000 division
instructions).
2. Caching effects.
3. Paralleling algorithm error.
According to materials of Prof. A.V. Boukhanovsky
17

18.

Changing the results of floating
point calculations
1 thread:
8 threads:
Diff:
s = 14.357357
s = 14.393189
0.25%
18