Слайд 2
Введение в параллельное программирование
“To put it quite bluntly:
as long as there were no
machines, programming was no
problem at all;
when we had a few weak computers,
programming became a mild problem, and now
we have gigantic computers, programming has
become an equally gigantic problem."
-- E. Dijkstra, 1972 Turing Award Lecture
Слайд 3
Знаменитый закон Мура
I Закон Мура (1965): каждые 2
года количество транзисторов в интегральной микросхеме удваивается.
Следствие Хауса: производительность
центрального процессора компьютера удваивается каждые 18 месяцев.
Мур, 2007: закономерности перестанут работать вследствие атомарной природы вещества и ограничения скорости света.
Слайд 4
Первый кризис ПО
60-70 годы 20 века
Проблема - язык
программирования ассемблер.
Компьютеры были готовы обрабатывать гораздо более сложные
программы, чем могли писать люди.
Для устранения была необходима абстракция над машинным кодом и переносимость программ между вычислителями.
Слайд 5
Первый кризис ПО
Решение
Появление языков высокого уровня С и
Фортран. Появление общих свойств у разных вычислителей. Модель ФонНеймана.
Единая память. Единственный поток управления.
Слайд 6
Второй кризис ПО
80-90 годы 20 века
Проблема: невозможность разработки
сложных программ, состоящих из миллионов строк кода, которые разрабатываются
сотнями людей. Компьютеры все еще готовы обрабатывать гораздо более сложные программы, чем могли писать люди.
Требовалась разработка стандартов по проектированию модульных, гибких и обслуживаемых программ. Скорость выполнения программ не была узким местом, вспоминаем закон Мура.
Слайд 7
Второй кризис ПО
Решение
Появление ООП и развитие языков высокого
уровня С#, Java, C++. Появление библиотек и инструментов для
написания, отладки и тестирования программ. Разработка различных методологий построения программного обеспечения. Появление методологий автоматического тестирования, ревью кода, XP программирования.
Слайд 8
Назревает третий кризис ПО
Особенности
Четкая граница между программой и
железом.
Программисты больше ничего не должны знать о процессорах
и их регистрах.
Высокоуровневые языки полностью абстрагируют программу от платформы исполнения.
Закон Мура все еще позволяет программистам получать хорошую скорость выполнения за счет мощных процессоров.
Программы одинаково хорошо работают на разных процессорах.
Такой подход развязывает руки программистам..
Слайд 9
Назревает третий кризис ПО
Проблема
Высокий уровень абстракции не дает
программистам достаточной мотивации писать оптимальные программы, которые работают максимально
быстро. Вместо этого скорость работы достигается путем появления новых процессоров.
Слайд 10
Шутка
- Скажи мне, Microsofе Office, почему ресурс моего
компьютера позволяет в онлайне управлять орбитальной группировкой из тысячи
боевых спутников, отслеживающих пролет тысяч баллистических ракет врага, но не в состоянии без лагов прогружать страницу в Excel когда там более двух вкладок?)))
- Потому что ваш компьютер не удовлетворяет минимальным системным требованиям для офиса, так как все ресурсы уходят на слежение за вами. Чем я еще могу вам помочь?
http://pikabu.ru/story/kakim_glazom_ya_seychas_morgnul_4423571
Слайд 11
Выводы из действия закона Мура
Раньше – производительность процессора
росла сама по себе, медленная программа с ходом времени
работала все быстрее.
Теперь – последовательная производительность процессора практически не растет, программист должен использовать параллельные вычисления, чтобы ускорить программу
Слайд 12
Алгоритм
Алгоритм – упорядоченная последовательность действий, приводящая к определенному
результату.
Задача: z = u∙x + v∙y
Слайд 13
Программа
Программа – способ выполнения алгоритма на определенном вычислителе.
По сути набор инструкций, приводящий к определенному результату.
1.load r1,
u
2.load r2, x
3.mul r3, r1,r2
4.load r1, v
5.load r2, y
6.mul r4, r1,r2
7.add r1, r3,r4
8.store z, r1
Слайд 14
Программа
1.load r1, u
2.load r2, x
3.mul r3, r1,r2
4.load r1,
v
5.load r2, y
6.mul r4, r1,r2
7.add r1, r3,r4
8.store z, r1
Слайд 15
Реализация
Реализация – способ реализации алгоритма при помощи программы.
Это множество путей выполнения алгоритма, часто неоптимальных.
Слайд 17
Компоненты вычислителя
• исполнительные устройства, ядра, процессоры, вычислительные узлы,
кластера, …
• блоки памяти - Оперативная память, кэш-память,
дисковая память …
• связи - Процессор-память, межпроцессорные, межузловые, межкластерные, …
Слайд 18
Системы с общей памятью
Многоядерные процессоры
Многопроцессорные узлы
…
Слайд 19
Системы с распределенной памятью
Сети рабочих станций
Кластера
Grid
…
Слайд 21
Меры качества параллельных программ
Производительность системы равняется
производительности ее
самого слабого звена..
Слайд 26
Меры качества параллельных программ
Время работы
Сколько времени программа
работает на N ядрах?
Ускорение
Во сколько раз программа стала быстрее
работать на N ядрах по сравнению с одним ядром / последовательной программой?
Эффективность распараллеливания
Какой процент времени работы программы идёт на полезную работу?
Масштабируемость
Как быстро эффективность падает с ростом числа ядер?
…
Слайд 27
Пример
Хорошо масштабируется
Плохо масштабируется
Слайд 28
Меры качества параллельных программ
Ускорение
Ускорение параллельной программы
при использовании N исполнительных устройств относительно…
•последовательной:
•параллельной
с использованием одного исполнительного устройства:
где:
Tseq – время работы последовательной программы,
T1 – время работы параллельной программы при использовании одного исполнительного устройства,
TN – время работы параллельной программы при использовании N исполнительных устройств.
Слайд 29
Пример
Хорошо масштабируется
Плохо масштабируется
Слайд 30
Меры качества параллельных программ
Эффективность распараллеливания
Эффективность использования N
исполнительных устройств относительно…
•последовательной программы:
•параллельной программы с использованием одного исполнительного
устройства:
где:
SseqN – ускорение параллельной программы при использовании N исполнительных устройств относительно последовательной,
S1N – ускорение параллельной программы при использовании N исполнительных устройств относительно параллельной при использовании одного исполнительного устройства.
Слайд 31
Пример
Хорошо масштабируется
Плохо масштабируется
Слайд 32
Предел ускорения: закон Амдала
α – доля последовательных
вычислений [0;1]
Слайд 33
Предел ускорения: закон Амдала
α – доля последовательных
вычислений [0;1]
1 - α – доля параллельных вычислений
Слайд 34
Предел ускорения: закон Амдала
α – доля последовательных
вычислений [0;1]
1 - α – доля параллельных вычислений
1 –
время выполнения последовательной программы
Слайд 35
Предел ускорения: закон Амдала
α – доля последовательных
вычислений [0;1]
1 - α – доля параллельных вычислений
1 –
время выполнения последовательной программы
α+(1- α)/p - время выполнения параллельной программы на p вычислителях
Слайд 36
Предел ускорения: закон Амдала
Ускорение, которое может быть
получено на вычислительной системе из p процессоров, по сравнению
с однопроцессорным решением не будет превышать величины:
Слайд 37
Предел ускорения: закон Амдала
Ускорение, которое может быть
получено на вычислительной системе из p процессоров, по сравнению
с однопроцессорным решением не будет превышать величины:
При каком значении α будет максимальное ускорение?
Слайд 38
Предел ускорения: закон Амдала
Если доля последовательных вычислений
в алгоритме равна 25 %, то увеличение числа процессоров
до 10 дает ускорение в 3,077 раза, а увеличение числа процессоров до 1000 даст ускорение в 3,988 раза.
Слайд 40
Способы реализация параллельных вычислений
Процесс (process) – работающий в
текущий момент экземпляр программы
Слайд 41
Способы реализация параллельных вычислений
Процесс (process) – работающий в
текущий момент экземпляр программы
Многозадачность (multitasking) – несколько процессов выполняются
условно одновременно за счет операционной системы
Вытесняющая многозадачность
Невытесняющая многозадачность
Слайд 42
Способы реализация параллельных вычислений
Процесс (process) – работающий в
текущий момент экземпляр программы
Многозадачность (multitasking) – несколько процессов выполняются
условно одновременно за счет операционной системы
Вытесняющая многозадачность
Невытесняющая многозадачность
Поток – последовательно выполняемая ветвь кода, для которой выделен отдельный стек и обеспечивается независимость использования регистров процессора.
Слайд 43
Способы реализация параллельных вычислений
Процесс (process) – работающий в
текущий момент экземпляр программы
Многозадачность (multitasking) – несколько процессов выполняются
условно одновременно за счет операционной системы
Вытесняющая многозадачность
Невытесняющая многозадачность
Поток – последовательно выполняемая ветвь кода, для которой выделен отдельный стек и обеспечивается независимость использования регистров процессора.
Многопоточность (multithreading) – несколько потоков выполнения кода работают внутри одной программы.
Слайд 44
Главный поток – поток, создаваемый для выполнения программы
по умолчанию.
Способы реализация параллельных вычислений
Слайд 45
Способы реализация параллельных вычислений
Слайд 46
Максимально нагруженная программа
Слайд 47
Максимально нагруженная программа
На сколько % будет загружен четырех-ядерный
процессор?
Слайд 48
Максимально нагруженная программа
Слайд 49
Асинхронные операции vs паралелльные вычисления
Слайд 50
Проблемы UI
Обрабатываются запросы пользователя.
Рисуется интерфейс.
Выполняется полезная работа.
Слайд 51
Многопоточность
Операции А1-А4 могут выполняться независимо, за их одновременное
выполнение отвечает планировщик Windows. Если одна задача подвиснет, то
после истечения определенного кванта времени ее сменит другая задача.
Слайд 53
Начальная ситуация
Повар готовит роллы == последовательная программа
Слайд 54
Параллельность
Много поваров готовит роллы == параллельная реализация
Слайд 55
Асинхронность
Повар готовит роллы, помощник варит рис == асинхронность
Слайд 56
Асинхронные операции vs паралелльные вычисления
Операции, которые выполняются не
прерывая основной поток выполнения программы, называются асинхронными. Эти операции
служат не для ускорения работы программы, а для удобства использования программы.
Ускорением занимаются параллельные вычисления – это решение какой-то задачи с разбиением задачи на подзадачи, выполняющиеся в разных потоках одновременно.
Слайд 57
Асинхронные операции
Примеры
Скачивание интернет-ресурса
Взаимодействие с сервером
Фоновое копирование файлов в
Total Commander
И т.д.
Слайд 59
Потоки
Стандарт POSIX.1c, Threads extensions (IEEE Std 1003.1c-1995) определяет
API для управления потоками, их синхронизации и планирования.
Слайд 60
Основные функции
Создание потока
Передача параметров в поток
Ожидание окончания потока
Установка
приоритета потока
Привязка потока к ядру
Окончание потока
Исключения, возникающие в потоке
Слайд 62
Пример 1. Результат
BBBBBBBBBBBBBBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAAAAAAAAAAAAAAAAAA
Слайд 63
Создание потока
CreateThread
lpThreadAttributes – указатель на SECURITY_ATTRIBUTES (чаще всего
NULL)
dwStackSize - размер стека в байтах
lpStartAddress - указатель на потоковую процедуру
lpParameter -
параметр потока (4 байта)
dwCreationFlags - параметры создания (чаще всего 0 – поток запускается сразу после создания)
Слайд 64
Удаление потока
Остановка выполнения
TerminateThread
hThread – хендл потока
dwExitCode – код
выхода потока
Удаление хендла
CloseHandle
hThread – хендл потока
Слайд 65
Изменение приоритета потока
Остановка выполнения
TerminateThread
hThread – хендл потока
dwExitCode –
код выхода потока
Удаление хендла
CloseHandle
hThread – хендл потока
Слайд 66
Другие операции
SetThreadPriority(handles[0], THREAD_PRIORITY_ABOVE_NORMAL);
SetThreadPriority(handles[1], THREAD_PRIORITY_BELOW_NORMAL);
Every thread has a base
priority level determined by the thread's priority value and
the priority class of its process. The system uses the base priority level of all executable threads to determine which thread gets the next slice of CPU time. Threads are scheduled in a round-robin fashion at each priority level, and only when there are no executable threads at a higher level does scheduling of threads at a lower level take place.
Слайд 67
Результат выполнения?
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB
Слайд 69
Привязка потоков к ядрам
SetThreadAffinityMask(HANDLE hThread, DWORD_PTR dwThreadAffinityMask)
dwThreadAffinityMask –
число, установленный i-ый бит (== 1), которого разрешают потоку
исполняться на i-ом ядре
Например, чтобы разрешить исполнение на 0 и 2 ядре:
0
0
0
0
0
0
1
0
1
= 5
Слайд 70
Привязка потоков к ядрам
SetThreadAffinityMask(handles[0], 1);
SetThreadAffinityMask(handles[1], 1);
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
Слайд 71
Исключения в потоках
if( i == 99) i = i
/ 0; // exception thrown
![Предел ускорения: закон Амдала α – доля последовательных вычислений [0;1]](/img/tmb/15/1452585/7b4fda4e59804ff94c9f16b2f6bc828c-720x.jpg "Асинхронные операции как часть параллельного программирования. Потоки, примитивы синхронизации в c+ +. Привязка к ядрам")
![Предел ускорения: закон Амдала α – доля последовательных вычислений [0;1]1](/img/tmb/15/1452585/9dcf1eb005ce73dbebe988a2f27fe157-720x.jpg "Асинхронные операции как часть параллельного программирования. Потоки, примитивы синхронизации в c+ +. Привязка к ядрам")
![Предел ускорения: закон Амдала α – доля последовательных вычислений [0;1]1](/img/tmb/15/1452585/1b3b81a4c0783f9cf0885d4e6a003b50-720x.jpg "Асинхронные операции как часть параллельного программирования. Потоки, примитивы синхронизации в c+ +. Привязка к ядрам")
![Предел ускорения: закон Амдала α – доля последовательных вычислений [0;1]1](/img/tmb/15/1452585/09f950a66651bb1f33dbd77ab72a192c-720x.jpg "Асинхронные операции как часть параллельного программирования. Потоки, примитивы синхронизации в c+ +. Привязка к ядрам")
![Другие операцииSetThreadPriority(handles[0], THREAD_PRIORITY_ABOVE_NORMAL);SetThreadPriority(handles[1], THREAD_PRIORITY_BELOW_NORMAL);Every thread has a base priority level determined by](/img/tmb/15/1452585/903f2206c192887368cdf56431b399f4-720x.jpg "Асинхронные операции как часть параллельного программирования. Потоки, примитивы синхронизации в c+ +. Привязка к ядрам")
![Привязка потоков к ядрамSetThreadAffinityMask(handles[0], 1);SetThreadAffinityMask(handles[1], 1);AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB](/img/tmb/15/1452585/277ad120dad904cb922e35dc58eee411-720x.jpg "Асинхронные операции как часть параллельного программирования. Потоки, примитивы синхронизации в c+ +. Привязка к ядрам")
