Аналитическое моделирование параллельных систем

Автор: Ananth Grama, Anshul Gupta, George Karypis, and Vipin Kumar

Источник: http://www-users.cs.umn.edu/~karypis/parbook/Lectures/AG/chap5_slides.pdf

Обзор тем

Источники накладных расходов в параллельных системах
Показатели эффективности параллельных систем
Влияние разбиения на производительность
Масштабируемость параллельных систем
Минимальное время исполнения и минимальное эффективное по стоимости время исполнения
Предельный анализ параллельных программ
Другие показатели масштабирования

Аналитическое моделирование - Основы

Последовательный алгоритм определяется временем его работы (в общем, предел времени работы – это функция от размера входных данных).
Предельное время работы последовательного алгоритма одинаково на любой последовательной платформе.
Время работы параллельной программы зависит от размера входных данных, числа процессоров и параметров межпроцессорного взаимодействия.
Поэтому параллельный алгоритм должен анализироваться в контексте платформы на которой он будет выполнятся.
Минимальное время исполнения и минимальное эффективное по стоимости время исполнения.
Пределы производительности – значение интуитивное.
Таймерное время – время от начала работы первого процессора до окончания работы последнего в согласованном параллельном выполнении. Но как это масштабируется , если число процессоров меняется при переносе системы на другую платформу?
На сколько параллельная версия программы быстрее? Отсюда напрашивается очевидный вопрос – что есть основа производительности с которой мы сравниваем? Можем ли мы использовать не самый оптимальный последовательный алгоритм, что бы представить параллельную программу в лучшем свете?
Число FLOP – Что хорошего в большом числе FLOP, если это не решает проблему?

Источники накладных расходов в параллельных программах

Если использовать два процессора , будет ли программа работать в два раза быстрее?
Нет – существует значительное количество накладных расходов, включая избыточные вычисления, межпроцессорное взимодействие, простой, и конкуренция, приводящая к снижению производительности.

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

Источники накладных расходов в параллельных программах

Межпроцессорное взаимодействие: Процессоры работающие над какой-либо нетривиальной задачей нуждаются в обмене данными друг с другом.
Простой: Процессоры могут простаивать из за несбалансированной нагрузки, процесса синхронизации, или последовательных компонентов программы.
Избыточные вычисления: Это вычисления, которые не производятся последовательным алгоритмом. Они могут появляться в следствии сложности распараллеливания последовательного алгоритма, либо это некоторые вычисления, которые производятся на каждом процессоре, что бы избежать дополнительного межпроцессорного взаимодействия.

Показатели эффективности для параллельных систем: Время исполнения

Время последовательного исполнения программы – это отрезок прошедший с начала работы алгоритма на последовательном компьютере до его окончания.
Параллельное исполнение это отрезок времени прошедший с момента, когда первый процессор начал работать до момента времени, когда последний процессор закончил исполнение программы.
Обозначим время исполнения последовательной программы, как Ts и время исполнения параллельной программы как Tp.

Показатели эффективности для параллельных систем : Совокупные параллельные накладные расходы

Пусть Tall будет общим временем затраченным коллективно всеми процессорами.
Ts это последовательное время исполнения.
Отметим что Tall - Ts это время потраченное всеми процессорами на «неполезную» работу. Это называется совокупными накладными расходами.
Общее время коллективно затраченное всеми процессорами Tall = p Tp (p – число процессоров).
Следовательно функция накладных расходов (To) будет To = p Tp - Ts (1)

Показатели эффективности для параллельных систем : Ускорение

Какие выгоды от распараллеливания?
Ускорение (S) коефицент, полученный отношением времени решения задачи на последовательном процессоре, к времени решения этой же проблемы на параллельном компьютере с p идентичными процессорами.

Показатели эффективности: Пример

Возьмём задачу сложения n чисел используя n процессоров.
Если n это степень двойки,мы сможем выполнить эту операцию за log n шагов распространяя частичные суммы по логическому дереву процессоров .

Вычисление общей суммы16 частичных сумм используя 16 процессоров. ?ji обозначает сумму чисел с последовательными индексами от i до j.

Если сложение занимает постоянное время, скажем tc, межпроцессорная передача слова занимает время ts + tw, мы получаем параллельное время Tp = (log n)
Мы знаем, что Ts = (n)
Ускорение S будет S = (n / log n)

Показатели эффективности : Ускорение

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

Показатели эффективности : Ускорение (Пример)

Возьмём задачу параллельной сортировки пузырьком.
Время сортировки пузырьком последовательного алгоритма 150 секунд.
Параллельное время сортировки чёт-нечёт(эффективное распараллеливание пузырька) 40 секунд.
Ускорение должно бы быть 150/40 = 3.75.
Но действительно ли это справедливая оценка ?
Что если последовательный алгоритм «быстрой» сортировки занимает 30 секунд? В этом случае ускорение 30/40 = 0.75. Это более справедливая оценка системы.

Показатели эффективности : Границы ускорения

Ускорение может быть равным 0 (параллельная программа не никогда не завершиться).
Ускорение,теоретически, должно быть ограничено p – мы можем ожидать только p-кратного ускорения.
Ускорение большее чем p возможно только, если каждый процессор тратит время меньшее чем TS / p на решение проблемы.
В этом случае, на одиночном процессоре можно достигнуть более быстрого решения задачи, что противоречит нашему решению брать лучший последовательный алгоритм за основу.

Показатели эффективности: Сверхлинейное ускорение

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

Поиск по неструктурированному дереву узла с заданной меткой `S', ну двух процессорах поиском в глубину. Двух процессорная система, где процессор 0 ищет в левом поддереве и процессор 1 ищет в правом поддереве обходя только затенённые узлы, пока решение не будет найдено. Соответствующая последовательная программа обходит всё дерево. Ясно, что последовательный алгоритм выполняет меньше работы чем параллельный.

Сверхлинейное ускорение основанное на ресурсах системы: Лучшая агрегация шины кеш/память, в результате даёт лучший коэфицент попадания в кеш, и следовательно сверхлинейное ускорение.

Например: Процессор с 64KB кеша достигает 80% попаданий. Если 2 процессора будут использоваться, то так как задача размер/процессор становиться менее важной, процент попаданий возрастает до 90%. Из оставшихся 10% доступа к памяти, 8% приходит из локальной памяти и 2% из удалённой памяти.

Если время доступа к DRAM 100 ns, время доступа к кэшу 2 ns, время доступа к удалённой памяти 400ns, это соответствует ускорению 2.43!

Показатели эффективности : Эффективность

Эффективность – это степень в которой процессор выполнял полезные вычисления в некий момент времени.
Математически это выражается E=S/P (2)
Следуя границам ускорения, эффективность может быть равной 0 и доходить до 1.