uzluga.ru
добавить свой файл
1



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

  • Показатели эффективности параллельного алгоритма

  • Оценка максимально достижимого параллелизма

  • Анализ масштабируемости параллельных вычислений

  • Примеры

  • Заключение



Принципиальный момент при разработке параллельных алгоритмов - анализ эффективности использования параллелизма:

  • Принципиальный момент при разработке параллельных алгоритмов - анализ эффективности использования параллелизма:

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


Ускорение (speedup)

  • Ускорение (speedup)

  • получаемое при использовании параллельного алгоритма для p процессоров, по сравнению с последовательным вариантом выполнения вычислений, определяется величиной

  • (величина n используется для параметризации вычислительной сложности решаемой задачи и может пониматься, например, как количество входных данных задачи)



Эффективность (efficiency)

  • Эффективность (efficiency)

  • использования параллельным алгоритмом процессоров при решении задачи определяется соотношением:

  • (величина эффективности определяет среднюю долю времени выполнения параллельного алгоритма, в течение которого процессоры реально используются для решения задачи)



Замечания

  • Замечания

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


Стоимость (cost) вычислений

  • Стоимость (cost) вычислений

  • Стоимостно-оптимальный (cost-optimal) параллельный алгоритм - метод, стоимость которого является пропорциональной времени выполнения наилучшего последовательного алгоритма.



Оценка качества параллельных вычислений предполагает знание наилучших (максимально достижимых) значений показателей ускорения и эффективности

  • Оценка качества параллельных вычислений предполагает знание наилучших (максимально достижимых) значений показателей ускорения и эффективности

  • Получение идеальных величин Sp=p для ускорения и Ep=1 для эффективности может быть обеспечено не для всех вычислительно трудоемких задач



Закон Амдаля (Amdahl)

  • Закон Амдаля (Amdahl)



Закон Амдаля. Замечания

  • Закон Амдаля. Замечания

    • Доля последовательных вычислений может быть существенно снижена при выборе более подходящих для распараллеливания методов,
    • Эффект Амдаля


Закон Густавсона – Барсиса…

  • Закон Густавсона – Барсиса…



Закон Густавсона - Барсиса

  • Закон Густавсона - Барсиса





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

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

  • Новые выражения для времени параллельного решения задачи и получаемого при этом ускорения:

  • Тогда эффективность использования процессоров можно выразить как



Если сложность решаемой задачи является фиксированной (T1=const), то при росте числа процессоров эффективность, как правило, будет убывать за счет роста накладных расходов T0,

    • Если сложность решаемой задачи является фиксированной (T1=const), то при росте числа процессоров эффективность, как правило, будет убывать за счет роста накладных расходов T0,
    • При фиксации числа процессоров эффективность использования процессоров можно улучшить путем повышения сложности решаемой задачи T1,
    • При увеличении числа процессоров в большинстве случаев можно обеспечить определенный уровень эффективности при помощи соответствующего повышения сложности решаемых задач.


Пусть E=const есть желаемый уровень эффективности выполняемых вычислений. Из выражения для эффективности можно получить

    • Пусть E=const есть желаемый уровень эффективности выполняемых вычислений. Из выражения для эффективности можно получить
    • Порождаемую последним соотношением зависимость n=F(p) между сложностью решаемой задачи и числом процессоров обычно называют функцией изоэффективности (isoefficiency function).
















Для оценки оптимальности разрабатываемых методов параллельных вычислений в разделе приводятся основные показатели качества - ускорение (speedup), эффективность (efficiency), стоимость (cost) вычислений

  • Для оценки оптимальности разрабатываемых методов параллельных вычислений в разделе приводятся основные показатели качества - ускорение (speedup), эффективность (efficiency), стоимость (cost) вычислений

  • Рассматривается вопрос построения оценок максимально достижимых значений показателей эффективности. Для получения таких оценок может быть использован закон Амдаля (Amdahl) и закон Густавсона-Барсиса (Gustafson-Barsis's law)

  • Вводится понятие функции изоэффективности (isoefficiency function)

  • Получение описанных оценок иллюстрируется на примерах



Возможно ли достижение сверхлинейного ускорения?

  • Возможно ли достижение сверхлинейного ускорения?

  • В чем состоит противоречивость показателей ускорения и эффективности?

  • В чем состоит понятие стоимостно-оптимального алгоритма?

  • Как формулируется закон Амдаля? Какой аспект параллельных вычислений позволяет учесть данный закон?

  • Какие предположения используются для обоснования закона Густавсона-Барсиса?

  • Какой алгоритм является масштабируемым? Приведите примеры методов с разным уровнем масштабируемости.



Выполните в соответствии с законом Амдаля оценку максимально достижимого ускорения:

  • Выполните в соответствии с законом Амдаля оценку максимально достижимого ускорения:

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


Выполните оценку ускорения масштабирования для задач п.1.

  • Выполните оценку ускорения масштабирования для задач п.1.

  • Выполните построение функций изоэффективности для задач п. 1.

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



Гергель В.П. Теория и практика параллельных вычислений. - М.: Интернет-Университет, БИНОМ. Лаборатория знаний, 2007. – Лекция 2

  • Гергель В.П. Теория и практика параллельных вычислений. - М.: Интернет-Университет, БИНОМ. Лаборатория знаний, 2007. – Лекция 2

  • Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ-Петербург, 2002.

  • Дополнительные учебные курсы:

  • Барский А.Б. Параллельное программирование. — http://www.intuit.ru/department/se/parallprog/

  • Воеводин В.В. Вычислительная математика и структура алгоритмов. — http://www.intuit.ru/department/calculate/calcalgo/



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

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



Гергель В.П., профессор, д.т.н., декан факультета вычислительной математики и кибернетики

  • Гергель В.П., профессор, д.т.н., декан факультета вычислительной математики и кибернетики

  • Нижегородский университет

  • gergel@unn.ru

  • http://www.software.unn.ru/?dir=17