Анализ сложности вычислений и оценка возможности распараллеливания

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Модель вычислений в виде графа "операции-операнды"
Схема параллельного выполнения алгоритма
Определение времени выполнения параллельного алгоритма
Пример: Вычисление частных сумм последовательности числовых значений
Пример: Умножение матриц
Заключение
Содержание

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Введение
Принципиальный момент при разработке параллельных алгоритмов - анализ эффективности использования параллелизма:
Оценка эффективности распараллеливания конкретных выбранных методов выполнения вычислений,
Оценка максимально возможного ускорения процесса решения рассматриваемой задачи (анализ всех возможных способов выполнения вычислений)

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Модель в виде графа "операции-операнды" используется для описания существующих информационных зависимостей в выбираемых алгоритмах
В наиболее простом виде модель основывается на предположениях:
время выполнения любых вычислительных операций является одинаковым и равняется 1,
передача данных между вычислительными устройствами выполняется мгновенно без каких-либо затрат времени.
Граф "операции-операнды"…

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Граф "операции-операнды"…
Множество операций, выполняемые в исследуемом алгоритме решения вычислительной задачи, и существующие между операциями информационные зависимости могут быть представлены в виде ациклического ориентированного графа
множество вершин графа, представляющих выполняемые операции алгоритма,
R
множество дуг графа; дуга r(i,j) принадлежит графу только если операция j использует результат выполнения операции i
Вершины без входных дуг могут использоваться для задания операций ввода, а вершины без выходных дуг – для операций вывода.
– множество вершин графа без вершин ввода,
– диаметр графа (длина максимального пути)

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Пример: граф алгоритма вычисления площади прямоугольника, заданного координатами двух противолежащих углов
Граф "операции-операнды"…

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Схемы вычислений обладают различными возможностями для распараллеливания, при построении модели вычислений может быть поставлена задача выбора наиболее подходящей для параллельного исполнения вычислительной схемы алгоритма
Операции алгоритма, между которыми нет пути в рамках выбранной схемы вычислений, могут быть выполнены параллельно
Граф "операции-операнды"

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Пусть p есть количество процессоров, используемых для выполнения алгоритма. Тогда для параллельного выполнения вычислений необходимо задать множество (расписание):
i - есть номер операции,
Pi - есть номер процессора,
ti - есть время начала выполнения i-ой операции.
Должны выполняться условия:
один и тот же процессор не должен назначаться разным операциям в один и тот же момент времени:
к назначаемому моменту выполнения операции все необходимые данные уже должны быть вычислены:
Схема параллельного выполнения алгоритма

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Модель параллельного алгоритма:
Время выполнения параллельного алгоритма с заданным расписанием:
Время выполнения параллельного алгоритма с оптимальным расписанием:
Определение времени выполнения параллельного алгоритма…

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Минимально возможное время решения задачи при заданном количестве процессоров (определение наилучшей вычислительной схемы):
Оценка наиболее быстрого исполнения алгоритма (при использовании паракомпьютера – системы с неограниченным числом процессоров):
Определение времени выполнения параллельного алгоритма…

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Время выполнения последовательного алгоритма для заданной вычислительной схемы:
Время выполнения последовательного алгоритма:
Время последовательного решения задачи:
Определение времени выполнения параллельного алгоритма…
Подобные оценки необходимы для определения эффекта использования параллелизма

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Теорема 1
Минимально возможное время выполнения параллельного алгоритма определяется длиной максимального пути вычислительной схемы алгоритма:
Определение времени выполнения параллельного алгоритма…

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Теорема 2
Пусть для некоторой вершины вывода в вычислительной схеме алгоритма существует путь из каждой вершины ввода. Кроме того, пусть входная степень вершин схемы (количество входящих дуг) не превышает 2. Тогда минимально возможное время выполнения параллельного алгоритма ограничено снизу значением:
где n есть количество вершин ввода в схеме алгоритма
Определение времени выполнения параллельного алгоритма…

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Теорема 3
При уменьшении числа используемых процессоров время выполнения алгоритма увеличивается пропорционально величине уменьшения количества процессоров, т.е. :
Определение времени выполнения параллельного алгоритма…

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Теорема 4
Для любого количества используемых процессоров справедлива следующая верхняя оценка для времени выполнения параллельного алгоритма:
Определение времени выполнения параллельного алгоритма…

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Теорема 5
Времени выполнения алгоритма, которое сопоставимо с минимально возможным временем T∞, можно достичь при количестве процессоров порядка p~T1/T∞, а именно:
При меньшем количестве процессоров время выполнения алгоритма не может превышать более, чем в 2 раза, наилучшее время вычислений при имеющемся числе процессоров, т.е.:
Определение времени выполнения параллельного алгоритма…

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Рекомендации
при выборе вычислительной схемы алгоритма должен использоваться граф с минимально возможным диаметром (теорема 1),
для параллельного выполнения целесообразное количество процессоров определяется величиной p~T1/T∞ (теорема 5),
время выполнения параллельного алгоритма ограничивается сверху величинами, приведенными в теоремах 4 и 5.
Определение времени выполнения параллельного алгоритма…

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Задача нахождения частных сумм последовательности числовых значений
(prefix sum problem):
Задача вычисления общей суммы имеющегося набора значений:
Пример: Вычисление частных сумм…

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Последовательный алгоритм суммирования элементов числового вектора
Пример: Вычисление частных сумм…
Данный "стандартный" алгоритм суммирования допускает только строго последовательное исполнение и не может быть распараллелен

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Пример: Вычисление частных сумм…
Каскадная схема суммирования
V2 = { (vi1,…,vili), 0≤i≤k, 1≤li≤2-in } есть вершины графа,
(v01,…, v0n) есть операции ввода,
(v11,…,v1n/2) есть операции первой итерации и т.д.,
R2 = { (vi-1,2j-1vij),(vi-1,2jvij), 1≤i≤k, 1≤li≤2-in } есть множество дуг графа.

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Пример: Вычисление частных сумм…
Количество итераций каскадной схемы суммирования:
Общее количество операций суммирования:
При параллельном исполнении отдельных итераций каскадной схемы общее количество параллельных операций суммирования является равным:

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Показатели ускорения и эффективности каскадной схемы алгоритма суммирования:
где p=n/2 есть необходимое для выполнения каскадной схемы количество процессоров.
время параллельного выполнения каскадной схемы совпадает с оценкой для паракомпьютера (теорема 2),
эффективность использования процессоров уменьшается при увеличении количества суммируемых значений:
Пример: Вычисление частных сумм…

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Пример: Вычисление частных сумм…
Модифицированная каскадная схема:
Все суммируемые значения подразделяются на (n/log2n) групп, в каждой из которых содержится (log2n) элементов; для каждой группы вычисляется сумма значений при помощи последовательного алгоритма суммирования;
На втором этапе для полученных (n/log2n) сумм отдельных групп применяется обычная каскадная схема:

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Пример: Вычисление частных сумм…
Для выполнения первого этапа требуется (log2n) выполнение параллельных операций при использовании p= (n/log2n) процессоров
Для выполнения второго этапа необходимо log2(n/log2n)≤log2n параллельных операций для p=(n/log2n)/2 процессоров
Время выполнения параллельного алгоритма составляет
для p= (n/log2n) процессоров.

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
С учетом полученных оценок показатели ускорения и эффективности модифицированной каскадной схемы определяются соотношениями:
Пример: Вычисление частных сумм…
По сравнению с обычной каскадной схемой ускорение уменьшилось в 2 раза,
Для эффективности нового метода суммирования можно получить асимптотически ненулевую оценку снизу:
Модифицированный каскадный алгоритм является стоимостно-оптимальным (стоимость вычислений пропорциональна времени выполнения последовательного алгоритма):

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Вычисление всех частных сумм…
Вычисление всех частных сумм на скалярном компьютере может быть получено при помощи обычного последовательного алгоритма суммирования при том же количестве операций
При параллельном исполнении применение каскадной схемы в явном виде не приводит к желаемым результатам.
Пример: Вычисление частных сумм…
Достижение эффективного распараллеливания требует привлечения новых подходов (может быть, даже не имеющих аналогов при последовательном программировании) для разработки новых параллельно-ориентированных алгоритмов решения задач

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Вычисление всех частных сумм…
Алгоритм, обеспечивающий получение результатов за log2n параллельных операций:
Перед началом вычислений создается копия S вектора суммируемых значений (S=x),
Далее на каждой итерации суммирования i, 1≤i≤log2n, формируется вспомогательный вектор Q путем сдвига вправо вектора S на 2i-1 позиций (освобождающиеся при сдвиге позиции слева устанавливаются в нулевые значения); итерация алгоритма завершается параллельной операцией суммирования векторов S и Q.
Пример: Вычисление частных сумм…

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Вычисление всех частных сумм…
Пример: Вычисление частных сумм…

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Вычисление всех частных сумм
Общее количество выполняемых алгоритмом скалярных операций определяется величиной:
Необходимое количество процессоров определяется количеством суммируемых значений:
Показатели ускорения и эффективности:
Пример: Вычисление частных сумм

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Пример: Умножение матриц…
Умножение матриц:
или
или

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Пример: Умножение матриц
Граф информационных зависимостей (до уровня операций умножения строк матрицы А и столбцов матрицы В):
⮲ Задача умножения матрицы на вектор может быть сведена к выполнению m·n независимых операций умножения строк матрицы A на столбцы матрицы B

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Заключение
Описывается модель вычислений в виде графа "операции-операнды", которая может использоваться для описания существующих информационных зависимостей в выбираемых алгоритмах решения задач
Приводятся теоретические оценки, которые могут быть использованы при определении максимального возможного распараллеливания
Для демонстрации применимости рассмотренных моделей и методов анализа параллельных алгоритмов в разделе рассматриваются задачи нахождения частных сумм последовательности числовых значений и умножения матриц

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Как определяется время выполнения параллельного алгоритма?
Как определить минимально возможное время решения задачи?
Какие оценки следует использовать в качестве характеристики времени последовательного решения задачи?
Как определить минимально возможное время параллельного решения задачи по графу "операнды – операции"?
При каком числе процессоров могут быть получены времена выполнения параллельного алгоритма, сопоставимые по порядку с оценками минимально возможного времени решения задачи?
Вопросы для обсуждения

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Разработайте модель и выполните оценку максимально возможных показателей ускорения и эффективности параллельных вычислений:
Для задачи скалярного произведения двух
векторов,
Для задачи поиска максимального и минимального
значений для заданного набора числовых данных,
Для задачи нахождения среднего значения для
заданного набора числовых данных,
Для задачи умножения матрицы на вектор,
Для задачи матричного умножения
Темы заданий для самостоятельной работы

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Гергель В.П. Теория и практика параллельных вычислений. - М.: Интернет-Университет, БИНОМ. Лаборатория знаний, 2007. – Лекция 2
Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ-Петербург, 2002.
Дополнительные учебные курсы:
Барский А.Б. Параллельное программирование. — http://www.intuit.ru/department/se/parallprog/
Воеводин В.В. Вычислительная математика и структура алгоритмов. — http://www.intuit.ru/department/calculate/calcalgo/
Литература…

Н.Новгород, 2008 г.
Основы параллельных вычислений: Оценка возможности распараллеливания
© Гергель В.П.
из 38
Общая схема разработки параллельных методов
Следующая тема