Оценка эффективности параллельных вычислений

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

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

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

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

Н.Новгород, 2008 г.
Основы параллельных вычислений: Показатели эффективности параллельных вычислений © Гергель В.П. из 31
Замечания
Сверхлинейное (superlinear) ускорение Sp(n)>p может иметь место в силу следующего ряда причин:
неравноправность выполнения последовательной и параллельной программ (например, недостаток оперативной памяти),
нелинейный характер зависимости сложности решения задачи от объема обрабатываемых данных,
различие вычислительных схем последовательного и параллельного методов.
Показатели качества параллельных вычислений являются противоречивыми: попытки повышения качества параллельных вычислений по одному из показателей (ускорению или эффективности) может привести к ухудшению ситуации по другому показателю.
Показатели эффективности параллельного алгоритма…

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

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

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

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

Н.Новгород, 2008 г.
Основы параллельных вычислений: Показатели эффективности параллельных вычислений © Гергель В.П. из 31
Закон Густавсона – Барсиса…
Оценим максимально достижимое ускорение исходя из имеющейся доли последовательных расчетов в выполняемых параллельных вычислениях:
где τ(n) и π(n) есть времена последовательной и параллельной частей выполняемых вычислений соответственно, т.е.
С учетом введенной величины g можно получить
что позволяет построить оценку для ускорения
Оценка максимально достижимого параллелизма…

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

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

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

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

Н.Новгород, 2008 г.
Основы параллельных вычислений: Показатели эффективности параллельных вычислений © Гергель В.П. из 31
Анализ масштабируемости параллельных вычислений
Пусть E=const есть желаемый уровень эффективности выполняемых вычислений. Из выражения для эффективности можно получить
Порождаемую последним соотношением зависимость n=F(p) между сложностью решаемой задачи и числом процессоров обычно называют функцией изоэффективности (isoefficiency function).

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

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

Н.Новгород, 2008 г.
Основы параллельных вычислений: Показатели эффективности параллельных вычислений © Гергель В.П. из 31
Пример: Вычисление числа π…
Анализ эффективности…
n – количество разбиений отрезка [0,1]
Вычислительная сложность задачи
W = T1 = 6n
Количество узлов сетки на отдельном процессоре
m = ⎡n/p⎤ ≤ n/p + 1
Объем вычислений на отдельном процессоре
Wp = 6m = 6n/p + 6.

Н.Новгород, 2008 г.
Основы параллельных вычислений: Показатели эффективности параллельных вычислений © Гергель В.П. из 31
Пример: Вычисление числа π
Анализ эффективности
Время параллельного решения задачи
Tp = 6n/p + 6 + log2p
Ускорение
Sp = T1/ Tp = 6n / (6n/p + 6 + log2p)
Эффективность Ep = 6n / (6n + 6p + plog2p)
Функция изоэффективности
W = K(pTp - W) = K(6p + plog2p)
⇒ n = [K(6p + plog2p)]/6, (K=E/(1–E))
Ex.: E=0.5 при p=8 → n= 12
при p=64 → n=128

Н.Новгород, 2008 г.
Основы параллельных вычислений: Показатели эффективности параллельных вычислений © Гергель В.П. из 31
Пример: Метод конечных разностей…
Метод конечных разностей широко применяется для численного решения уравнений в частных производных (см. раздел 12)
Рассмотрим схему (N = 2)
Xi,j t+1=w(Xi,j-1t + Xi,j+1t+ Xi-1,jt+ Xi+1,j t)+(1–w) Xi,j t

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

Н.Новгород, 2008 г.
Основы параллельных вычислений: Показатели эффективности параллельных вычислений © Гергель В.П. из 31
Анализ эффективности
W = T1 = 6n2M (M – количество итераций)
Tp = 6n2M/p + M log2p
Ускорение
Sp = T1/ Tp = 6n2 / (6n2/p + log2p)
Функция изоэффективности
W = K(pTp - W) = K(plog2p)
⇒ n2 = [K(plog2p)]/6, (K=E/(1-E))
Пример: Метод конечных разностей
Метод конечных разностей является более масштабируемым, чем метод прямоугольников

Н.Новгород, 2008 г.
Основы параллельных вычислений: Показатели эффективности параллельных вычислений © Гергель В.П. из 31
Заключение
Для оценки оптимальности разрабатываемых методов параллельных вычислений в разделе приводятся основные показатели качества - ускорение (speedup), эффективность (efficiency), стоимость (cost) вычислений
Рассматривается вопрос построения оценок максимально достижимых значений показателей эффективности. Для получения таких оценок может быть использован закон Амдаля (Amdahl) и закон Густавсона-Барсиса (Gustafson-Barsis's law)
Вводится понятие функции изоэффективности (isoefficiency function)
Получение описанных оценок иллюстрируется на примерах

Н.Новгород, 2008 г.
Основы параллельных вычислений: Показатели эффективности параллельных вычислений © Гергель В.П. из 31
Возможно ли достижение сверхлинейного ускорения?
В чем состоит противоречивость показателей ускорения и эффективности?
В чем состоит понятие стоимостно-оптимального алгоритма?
Как формулируется закон Амдаля? Какой аспект параллельных вычислений позволяет учесть данный закон?
Какие предположения используются для обоснования закона Густавсона-Барсиса?
Какой алгоритм является масштабируемым? Приведите примеры методов с разным уровнем масштабируемости.
Вопросы для обсуждения

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

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

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

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