параллельность + синхронизации (примеры)

[Olej]

Вопрос скорости выполнения (прироста скорости) при выполнении в несколько параллельных ветвей, или при отсутствии параллельности. При разных альтернативных способах написания одного и того же функционально кода.
(вопрос, как видно из формулировки, чисто программистский, и не программистам не актуальный )

Я давно натыкаюсь на такой вопрос ... ещё со времён издания книжки (http://www.books.ru/books/qnxunix-anato ... 04/?show=1):


Сейчас этот вопрос (отчасти и непроизвольно) выплыл в обсуждениях форума Debian: Несколько потоков в одной функции, ... но там он звучит частно и неинтересно, а вообще вопрос такой (для меня):

- насколько можно ожидать ускорение от параллельного исполнения кода?
- какие факторы на это влияют, а какие нет? (число процессоров, кэширование RAM, ...)
- как обезопасить использование потоково небезопасных (not thread-safe) функций (а таких в POSIX библиотеке C достаточно много) примитивами синхронизации?
- как способ синхронизации будет влиять на ускорение?

Но меня эти вопросы интересуют исключительно на удачных примерах кода.
Которые можно запустить и проверить...
А удачные примеры не всегда легко найти или составить.

[Olej]

- насколько можно ожидать ускорение от параллельного исполнения кода?

Здесь накопилось за долгие годы масса мнений, заблуждений, предрассудков и красивых народных легенд :

- из-за того, что начиная с середины 60-х годов, с написания Э.Дейкстрой работы "Взаимодействие последовательных процессов", с которой и началось, собственно, параллельное программирование, и до начала 2000-х - всё параллельное программирование было квази-параллельным - выполнялось на 1-м процессоре, с разделением его времени...
(реально параллельные многопроцессорные реализации существовали только как отдельные спецпроекты).

- одна из первых "легенд" - это то, что на одном процессоре распараллеливание не увеличивает скорость, а только используется для удобства ... это не соответствует действительности, но в некоторых случаях параллельные реализации могут быть даже медленнее, чем последовательная альтернатива - за счёт накладных расходов на распараллеливание.

- один из (исторически) первых способ распараллеливания - fork(); и здесь ещё одна красивая народная легенда, что реализация на fork() (параллельными процессами) намного медленнее, чем реализация через pthread_create() (параллельными потоками) ... якобы из-за частых переключений контекстов и т.д. - в этой легенде мы обязаны, скорее всего, преподавателям ВУЗов, которые сами программ не писали, но рассказывали какие-то гипотетические сказки, которые потом обрастали деталями.

- картина сильно поменялась с года ~2005 ... когда сначала широко стали распространены SMP в серверах, а потом массово - многоядерный процессоры в любом самом пионерском компьютере ... а поменялась она в сторону усложнения:
а). всё, что писалось и обсуждалось в предыдущие 40 лет, оказалось в полной мере применимо к многопроцессорам...
б). синхронизировать теперь нужно не только между параллельными ветвями кода, но и между процессорами (так появились "собственные данные процессора" в ядре Linux, афинити-маска потока и т.д.)...
в). перебрасывание выполняемой ветки между процессорами может иметь следствием частую перезагрузку кэша RAM, что увеличит время обращений к RAM в 2-4 раза, и не увеличит скорость, а уменьшит её...
в). ... и другие тонкие эффекты.

Вот на это всё хотелось бы иметь демонстрирующие примеры кода.

[Olej]

Вот на это всё хотелось бы иметь демонстрирующие примеры кода.

Хотя по многим вещам можно и в код далеко не ходить.
Вот здесь уже обсуждалось: Как правильно собирать ядро? - параллельное выполнение утилиты сборки make.

1. берём произвольны проект (не слишком маленький, чтобы сборка шла ощутимое время, но чтобы она не была и утомительной), я выбрал (но это совершенно произвольный выбор - завалялся на винчестере) проект сервера времени:

Код: Выделить всё

[olej@nvidia ntp-4.2.6p3]$ pwd
/usr/src/ntp-4.2.6p3
[olej@nvidia ntp-4.2.6p3]$ make clean > /dev/null
[olej@nvidia ntp-4.2.6p3]$ du -hs
22M     .

2. проделываю я сборку, чтобы это было показательно, на компьютере с очень быстрым SSD, но весьма медленным процессором:

Код: Выделить всё

olej@atom:/usr/src/ntp-4.2.6p3$ cat /proc/cpuinfo | grep 'model name'
model name      : Intel(R) Atom(TM) CPU  330   @ 1.60GHz
model name      : Intel(R) Atom(TM) CPU  330   @ 1.60GHz
model name      : Intel(R) Atom(TM) CPU  330   @ 1.60GHz
model name      : Intel(R) Atom(TM) CPU  330   @ 1.60GHz

3. собираем совершенно традиционно, "как всегда" - а это значит в 1 последовательный процесс:

Код: Выделить всё

olej@atom:/usr/src/ntp-4.2.6p3$ time make 2>&1 | tail -n3
make[2]: Вход в каталог `/usr/src/ntp-4.2.6p3'
make[2]: Выход из каталога `/usr/src/ntp-4.2.6p3'
make[1]: Выход из каталога `/usr/src/ntp-4.2.6p3'

real    2m1.874s
user    1m51.115s
sys     0m12.449s

4. то же, но в 2 параллельных ветви (jobs в терминологии man make):

Код: Выделить всё

olej@atom:/usr/src/ntp-4.2.6p3$ make clean > /dev/null
olej@atom:/usr/src/ntp-4.2.6p3$ time make -j2 2>&1 | tail -n3


make[2]: Вход в каталог `/usr/src/ntp-4.2.6p3'
make[2]: Выход из каталога `/usr/src/ntp-4.2.6p3'
make[1]: Выход из каталога `/usr/src/ntp-4.2.6p3'

real    1m12.252s
user    1m54.511s
sys     0m12.017s

Вдвое быстрее!

5. в 3 ветви - здесь ускорения уже почти нет:

Код: Выделить всё

olej@atom:/usr/src/ntp-4.2.6p3$ time make -j3 2>&1 | tail -n3
make[2]: Вход в каталог `/usr/src/ntp-4.2.6p3'
make[2]: Выход из каталога `/usr/src/ntp-4.2.6p3'
make[1]: Выход из каталога `/usr/src/ntp-4.2.6p3'

real    1m6.341s
user    2m19.949s
sys     0m14.485s

olej@atom:~$ top | grep cc1
 4471 olej      20   0 22252  16m 6032 R  100  0.8   0:01.31 cc1
 4477 olej      20   0 16468 8004 3132 R   71  0.4   0:00.38 cc1
 4485 olej      20   0 14376 5644 3004 R   19  0.3   0:00.10 cc1
 4471 olej      20   0 25804  20m 6588 R  100  1.0   0:04.34 cc1
 4501 olej      20   0 19244  13m 6184 R   35  0.7   0:01.05 cc1
 4517 olej      20   0 14248 5256 3004 R    2  0.3   0:00.07 cc1
...

Это, может быть, следствие того, что в этом Atom не 4 ядра (как думает Linux), а 2 с Hiper Threading, что даёт очень ограниченные возможности по параллельному использованию такой ветви. Хорошо видно на показанном выводе top (в таком синтаксисе), как:
а). строки "вываливаются" тройками, в соответствии с -j3
б). третья строка обычно имеет много меньше загрузку (19%, 2%, ...)
в). видно как изменяются (замещаются) PID - make запускает всё новые копии компилятора cc1 через fork().

6. в 4 процессора:

Код: Выделить всё

olej@atom:/usr/src/ntp-4.2.6p3$ time make -j4 2>&1 | tail -n3
make[2]: Вход в каталог `/usr/src/ntp-4.2.6p3'
make[2]: Выход из каталога `/usr/src/ntp-4.2.6p3'
make[1]: Выход из каталога `/usr/src/ntp-4.2.6p3'

real    1m1.568s
user    2m37.134s
sys     0m16.129s

olej@atom:~$ top | grep cc1
14092 olej      20   0 22504  16m 6392 R   83  0.8   0:02.51 cc1
14107 olej      20   0 17904  12m 6132 R   33  0.6   0:01.01 cc1
14111 olej      20   0 18680  10m 3748 R   23  0.5   0:00.70 cc1
14115 olej      20   0 17556 8408 3040 R   14  0.4   0:00.43 cc1
14111 olej      20   0 23460  18m 6632 R  100  0.9   0:03.74 cc1
14119 olej      20   0 23696  18m 6472 R   78  0.9   0:02.39 cc1
14135 olej      20   0 17748  11m 5796 R   20  0.6   0:00.60 cc1
14139 olej      20   0 14384 5864 3016 R    6  0.3   0:00.18 cc1

Вот вам и "параллелизм в действии" в простейшем его виде.

[Olej]

Вот вам и "параллелизм в действии" в простейшем его виде.

И уже здесь вылазит главная проблема параллельных реализаций, которая вообще не называлась даже при эквивалентной последовательной реализации - синхронизации.
В той же теме о сборке ядра: Как правильно собирать ядро? - мне попался (к счастью!) пример ... повторяю вывод:

Код: Выделить всё

[olej@nvidia linux-2.6.35.i686]$ time make -j bzImage
...
Can't fork, trying again in 5 seconds at /dev/shm/linux-2.6.35.i686/scripts/recordmcount.pl line 179.
make[2]: *** [drivers/md/dm-table.o] Ошибка 1
make[2]: *** Ожидание завершения заданий...
ccache: FATAL: Failed to fork
make[2]: *** [drivers/md/dm-uevent.o] Ошибка 1
Can't fork, trying again in 5 seconds at /dev/shm/linux-2.6.35.i686/scripts/recordmcount.pl line 179.
Can't fork, trying again in 5 seconds at /dev/shm/linux-2.6.35.i686/scripts/recordmcount.pl line 531, <IN> li
make[2]: scripts/Makefile.build:230: fork: Ресурс временно недоступен
make[2]: scripts/Makefile.build:230: fork: Ресурс временно недоступен
...
  LD      security/selinux/ss/built-in.o
make[1]: *** [security/selinux] Ошибка 2
make: *** [security] Ошибка 2
make[1]: *** [drivers/ata] Ошибка 2
make: *** [drivers] Ошибка 2
make: *** [kernel] Ошибка 2
make: *** wait: Нет дочерних процессов.  Останов.

Это сборка ядра, стандартного ... самого что ни есть ванильного, взятого с kernel.org, ядро 2.6.35.
Хорошо видно, что отказ от сборки происходит из-за не синхронизированности вызовов fork() ... каким-то образом.
Т.е., последовательно ядро замечательно собирается (как все вы знаете), а в 2 процессора - облом

Хотя, вот то же самое, на том же самом процессоре, сегодня:

Код: Выделить всё

[olej@nvidia linux-3.4.6]$ time make -j2 bzImage  > /dev/null
...
Succeed: decoded and checked 1722241 instructions
Setup is 17072 bytes (padded to 17408 bytes).
System is 4693 kB
CRC cb28295c

real    3m11.587s
user    3m32.140s
sys     0m38.655s
[olej@nvidia linux-3.4.6]$ ls -l *linux
-rwxrwxr-x. 1 olej olej 165637718 июля  28 12:56 vmlinux

Это уже весия 3.4.6 (последняя stable на сегодня), и здесь проблем нет никаких.

P.S. если кого смущает время сборки <4 мин., и кто подозревает обман , то:
1. сборка на весьма быстром процессоре и в 2 процессора:

Код: Выделить всё

[olej@nvidia linux-3.4.6]$ cat /proc/cpuinfo | grep 'model name'
model name	: Pentium(R) Dual-Core  CPU      E6600  @ 3.06GHz
model name	: Pentium(R) Dual-Core  CPU      E6600  @ 3.06GHz

2. сборка не на диске HDD, а в RAM (tmpfs):

Код: Выделить всё

[olej@nvidia linux-3.4.6]$ pwd
/dev/shm/build/linux-3.4.6

3. сборка только самого ядра (bzImage), а не всего (all) - а это обычно более чем в 2 раза меньше.

[Olej]

Но меня эти вопросы интересуют исключительно на удачных примерах кода.
Которые можно запустить и проверить...

Как оказалось, это не так просто

1. чтобы примеры были удачными:
- были насколько можно простыми (короткими по числу строк кода ), простыми и ясными для понимания
- достаточно гибкими (возможно за счёт параметров, опций), чтобы могли использоваться в разных конфигурациях для сравнения.

2. хотелось бы оттестировать на примерах параллельность:
- в процессах в юзерспейс (процессы, потоки ... это не так важно);
- в потоках ядра в ядре Linux;

Это много

[Olej]

Как оказалось, это не так просто

За болтовнёй (и на этом форуме) некогда было серьёзно сесть за этот проект.
Но вот 0-й вариант.

1. запускается T потоков (ключ -t) ...
2. которые должны "перелопатить" N порций данных (ключ -n), N порций делятся на каждый поток - N/T...
3. 1-на порция: это 100 мсек. работы, из которых в зависимости от ключа -a (процент активности) A мсек. поток активно накручивает пустые циклы, а (100-A) мсек. - пассивного ожидания в блокированном состоянии.
4. хотел (даже сделал, но потом убрал) переводить потоки в real-time диспетчирование с SCHED_FIFO или SCHED_FIFO, и управляемым (опцией) приоритетом ... но оказалось (показалось?), что это непотребно: а). и так повторяемые результаты весьма устойчивы, б). запуская с повышенным приоритетом (nice) в обычном диспетчировании (SCHED_SCHED_OTHER) делает их просто неубиенными.

Но что-то результаты у меня явно показывают не то, что ожидается:

Код: Выделить всё

bash-4.2$ sudo nice -n19 ./tspeed -n5000 -t50 -a100
threads number = 50, repeat in thread 100 times : full time was 13 sec. 332 msec.
bash-4.2$ sudo nice -n19 ./tspeed -n5000 -t50 -a10
threads number = 50, repeat in thread 100 times : full time was 12 sec. 312 msec.
bash-4.2$ sudo nice -n19 ./tspeed -n5000 -t5 -a100
threads number = 5, repeat in thread 1000 times : full time was 1 min. 48 sec. 287 msec.

Здесь явно есть ошибка ... я даже предполагаю, что не в коде, а в логике.
Буду искать.

Но интересующиеся параллельным программированием уже могут поиграться.

[Olej]

Ну вот это кажется веселее!

Вот как себя ведут 1, 2 и 3 потока, при загрузкой активной работой в потока на 99% (опция -v создаёт отладочный вывод):

Код: Выделить всё

bash-4.2$ sudo nice -n3 ./tspeed -t1 -n60 -a99 -v
calibrate: 9.97 cycles for one msec.
activ persent=99 repit on slice=987
33:452508 : main started<------>: pid=11087, tid=3077498560
33:452682 : pthread #0 started<>: pid=11087, tid=3077495616
39:497849 : pthread #0 finished>: pid=11087, tid=3077495616
39:497952 : main finished<----->: pid=11087, tid=3077498560
threads number = 1, repeat slices in thread 60 times : full time was 06 sec. 045 msec.

bash-4.2$ sudo nice -n3 ./tspeed -t2 -n60 -a99 -v
calibrate: 10.14 cycles for one msec.
activ persent=99 repit on slice=1004
28:420778 : main started<------>: pid=11078, tid=3078031040
28:420960 : pthread #1 started<>: pid=11078, tid=3069635392
28:420970 : pthread #0 started<>: pid=11078, tid=3078028096
31:485527 : pthread #0 finished>: pid=11078, tid=3078028096
32:361971 : pthread #1 finished>: pid=11078, tid=3069635392
32:362058 : main finished<----->: pid=11078, tid=3078031040
threads number = 2, repeat slices in thread 30 times : full time was 03 sec. 941 msec.

bash-4.2$ sudo nice -n3 ./tspeed -t3 -n60 -a99 -v
calibrate: 10.10 cycles for one msec.
activ persent=99 repit on slice=1000
55:958064 : main started<------>: pid=11082, tid=3078051520
55:958438 : pthread #2 started<>: pid=11082, tid=3061263168
55:961872 : pthread #1 started<>: pid=11082, tid=3069655872
55:965885 : pthread #0 started<>: pid=11082, tid=3078048576
58:940563 : pthread #0 finished>: pid=11082, tid=3078048576
59:394302 : pthread #1 finished>: pid=11082, tid=3069655872
59:665677 : pthread #2 finished>: pid=11082, tid=3061263168
59:665871 : main finished<----->: pid=11082, tid=3078051520
threads number = 3, repeat slices in thread 20 times : full time was 03 sec. 707 msec.

- в последнем случае интересно видеть порядок в котором потоки стартуют и завершаются: при каждом запуске они могут быть разными.

10 потоков, при загруженности их активной работой на 10%:

Код: Выделить всё

bash-4.2$ sudo nice -n3 ./tspeed -t10 -n60 -a10 -v
calibrate: 10.14 cycles for one msec.
activ persent=10 repit on slice=101
41:132665 : main started<------>: pid=11102, tid=3078403776
41:132919 : pthread #1 started<>: pid=11102, tid=3070008128
41:132951 : pthread #0 started<>: pid=11102, tid=3078400832
41:135001 : pthread #7 started<>: pid=11102, tid=3019651904
41:135031 : pthread #9 started<>: pid=11102, tid=3002866496
41:135045 : pthread #8 started<>: pid=11102, tid=3011259200
41:139816 : pthread #6 started<>: pid=11102, tid=3028044608
41:143818 : pthread #5 started<>: pid=11102, tid=3036437312
41:147822 : pthread #4 started<>: pid=11102, tid=3044830016
41:149820 : pthread #3 started<>: pid=11102, tid=3053222720
41:161826 : pthread #2 started<>: pid=11102, tid=3061615424
41:299008 : pthread #1 finished>: pid=11102, tid=3070008128
41:473469 : pthread #0 finished>: pid=11102, tid=3078400832
41:480813 : pthread #5 finished>: pid=11102, tid=3036437312
41:485115 : pthread #4 finished>: pid=11102, tid=3044830016
41:491726 : pthread #2 finished>: pid=11102, tid=3061615424
41:516893 : pthread #8 finished>: pid=11102, tid=3011259200
41:517358 : pthread #9 finished>: pid=11102, tid=3002866496
41:520215 : pthread #7 finished>: pid=11102, tid=3019651904
41:520631 : pthread #6 finished>: pid=11102, tid=3028044608
41:523687 : pthread #3 finished>: pid=11102, tid=3053222720
41:523842 : main finished<----->: pid=11102, tid=3078403776
threads number = 10, repeat slices in thread 6 times : full time was 00 sec. 391 msec.

- вот здесь порядок, о котором сказано выше, в котором стартуют потоки и завершаются.
При 10% активности (почти простаивают в блокировке) 10 потоков разгребаются почти мгновенно.

[Olej]

Возвращусь к вопросу параллельного выполнения ... в свете последних обсуждений здесь в форуме: Помогите поднять кластер и кластер PelicanHPC в VirtualBox :

На сегодня, как мне видится (IMHO) есть только 3 реальных (реализуемых) варианта организации параллельного выполнения задачи (для ускорения её просчёта):

1. использование сильносвязанных многопроцессорных систем, с общей памятью RAM, а реально - это SMP многоядерные реализации ... на сегодня совершенно не редкость архитектура с 2-мя процессорами по 4 ядра каждый;

2. использование слабосвязных многопроцессорных систем, когда прцессоры (хосты) связаны высокоскоростными каналами связи (на сегодня 1Gb/s или даже 10Gb/s это не такая уже экзотика), см. URL названные в начале сообщения.

3. специальные мультипроцессорные вычислители ... но из которых (не считая всяческих экспериментальных штучек) реально к использованию пригодны только вычислители на графических процессорах (GPU) NVIDIA или ATI, см. NVIDIA & CUDA.

Чем характерно отличаются?

Вариант 3 : достаточно дешёвое решение, легко получить несколько сот процессоров, программировать задачу нужно индивидуально, используя специфический API;

Вариант 2 : достаточно дорогой вариант, но можно использовать инфраструктуру существующих LAN на несколько десятков процессоров, программировать задачу нужно опять же индивидуально, используя специфический API стандарта MPI, но здесь API ближе к традиционному и попроще;

Вариант 1 : достаточно дешёвое решение, задействуются типовые рыночные изделия ... число ядер/процессоров (распараллелирвание) - несколько единиц (на сегодня 4-8, но эта граница повышается), в преимуществах то, что для распараллеливание происходит достаточно просто и естественно, на уровне отдельных процессов в SMP, или простой техники использования POSIX потоков pthread_*();

Вот этим, как мне видится, исчерпываются реальные возможности для параллельных вычислений.

[Olej]

Очень сходные вопросы выплыли в обсуждениях на форуме MINIX 3 : Сравнение скорости переключения процессов со скоростью переключения потоков.

Насколько медленнее переключение контекстов процессов чем у потоков, при прочих равных условиях?
Насколько легче реализация на потоках (pthread_t), чем на процессах (fork(), pid_t)?
(В учебниках пересказывается очень старое, лет 35 ему, утверждение, что реализация на потоках намного быстрее)

Сделал новые тесты (добавил к показанным раньше). Приложены архивом.
И вот что мы имеем:

И вот результаты:

- 5 потоков непрерывно "щёлкают" меж собой:

Код: Выделить всё

bash-4.2$ sudo nice -n18 ./shedt -n5 -s100000
число потоков = 5, общее число переключений = 500000,
число процессорных тактов = 645566850, тактов на переключение = 1291
bash-4.2$ sudo nice -n18 ./shedt -n5 -s100000
число потоков = 5, общее число переключений = 500000,
число процессорных тактов = 674795870, тактов на переключение = 1349

- 5 процессов

Код: Выделить всё

bash-4.2$ sudo nice -n18 ./shedp -n5 -s100000
число процессов = 5, общее число переключений = 500000,
число процессорных тактов = 747127810, тактов на переключение = 1494
bash-4.2$ sudo nice -n18 ./shedp -n5 -s100000
число процессов = 5, общее число переключений = 500000,
число процессорных тактов = 743315390, тактов на переключение = 1486

разница ~15%

- 15 потоков

Код: Выделить всё

bash-4.2$ sudo nice -n18 ./shedt -n15 -s100000
число потоков = 15, общее число переключений = 1500000,
число процессорных тактов = 2163560210, тактов на переключение = 1442
bash-4.2$ sudo nice -n18 ./shedt -n15 -s100000
число потоков = 15, общее число переключений = 1500000,
число процессорных тактов = 2168680620, тактов на переключение = 1445

- 15 процессов

Код: Выделить всё

bash-4.2$ sudo nice -n18 ./shedp -n15 -s100000
число процессов = 15, общее число переключений = 1500000,
число процессорных тактов = 2580788840, тактов на переключение = 1720
bash-4.2$ sudo nice -n18 ./shedp -n15 -s100000
число процессов = 15, общее число переключений = 1500000,
число процессорных тактов = 2610061690, тактов на переключение = 1740

разница ~20%

- 40 потоков

Код: Выделить всё

bash-4.2$ sudo nice -n18 ./shedt -n40 -s100000
число потоков = 40, общее число переключений = 4000000,
число процессорных тактов = 5885702820, тактов на переключение = 1471

- 40 процессов

Код: Выделить всё

bash-4.2$ sudo nice -n18 ./shedp -n40 -s100000
число процессов = 40, общее число переключений = 4000000,
число процессорных тактов = 7250384060, тактов на переключение = 1812
bash-4.2$ sudo nice -n18 ./shedp -n40 -s100000
число процессов = 40, общее число переключений = 4000000,
число процессорных тактов = 7301200350, тактов на переключение = 1825

здесь разница ~23%

Вот и вся разница в скорости переключений контекстов потоков vs процессов - в пределах 20%!
Вот вам и вся лёгкость.

P.S. Тесты очень несовершенные (для простоты): параллельные процессы, потоки - начинают непрерывно переключать контекст сразу после создания, т.е. пока создаются следующие параллельные ветки - без синхронизации начала своей работы.
Но при больших числе переключений (-s) и числе ветвей (-n) этот начальный этап нивелируется, что хорошо видно по сходимости и устойчивости результата.

[Olej]

Вот и вся разница в скорости переключений контекстов потоков vs процессов - в пределах 20%!
Вот вам и вся лёгкость.

Это весьма неожиданный результат. ... противоречащий "внутреннему голосу" и тому, что пишут в учебниках.

Ну так давайте обсудим.
Или давайте возражения...