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



Модель вычислений в виде графа "операции-операнды"

  • Модель вычислений в виде графа "операции-операнды"

  • Схема параллельного выполнения алгоритма

  • Определение времени выполнения параллельного алгоритма

  • Пример: Вычисление частных сумм последовательности числовых значений

  • Пример: Умножение матриц

  • Заключение



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

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

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


Модель в виде графа "операции-операнды" используется для описания существующих информационных зависимостей в выбираемых алгоритмах

  • Модель в виде графа "операции-операнды" используется для описания существующих информационных зависимостей в выбираемых алгоритмах

  • В наиболее простом виде модель основывается на предположениях:

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






Схемы вычислений обладают различными возможностями для распараллеливания, при построении модели вычислений может быть поставлена задача выбора наиболее подходящей для параллельного исполнения вычислительной схемы алгоритма

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

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



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

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

    • i - есть номер операции,
    • Pi - есть номер процессора,
    • ti - есть время начала выполнения i-ой операции.
  • Должны выполняться условия:

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


Модель параллельного алгоритма:

  • Модель параллельного алгоритма:

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

  • Время выполнения параллельного алгоритма с оптимальным расписанием:



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

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

  • Оценка наиболее быстрого исполнения алгоритма (при использовании паракомпьютера – системы с неограниченным числом процессоров):



Время выполнения последовательного алгоритма для заданной вычислительной схемы:

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

  • Время выполнения последовательного алгоритма:

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



Теорема 1

  • Теорема 1

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



Теорема 2

  • Теорема 2

  • Пусть для некоторой вершины вывода в вычислительной схеме алгоритма существует путь из каждой вершины ввода. Кроме того, пусть входная степень вершин схемы (количество входящих дуг) не превышает 2. Тогда минимально возможное время выполнения параллельного алгоритма ограничено снизу значением:

  • где n есть количество вершин ввода в схеме алгоритма



Теорема 3

  • Теорема 3

  • При уменьшении числа используемых процессоров время выполнения алгоритма увеличивается пропорционально величине уменьшения количества процессоров, т.е. :



Теорема 4

  • Теорема 4

  • Для любого количества используемых процессоров справедлива следующая верхняя оценка для времени выполнения параллельного алгоритма:



Теорема 5

  • Теорема 5

  • Времени выполнения алгоритма, которое сопоставимо с минимально возможным временем T∞, можно достичь при количестве процессоров порядка p~T1/T∞, а именно:

  • При меньшем количестве процессоров время выполнения алгоритма не может превышать более, чем в 2 раза, наилучшее время вычислений при имеющемся числе процессоров, т.е.:



Рекомендации

  • Рекомендации

    • при выборе вычислительной схемы алгоритма должен использоваться граф с минимально возможным диаметром (теорема 1),
    • для параллельного выполнения целесообразное количество процессоров определяется величиной p~T1/T∞ (теорема 5),
    • время выполнения параллельного алгоритма ограничивается сверху величинами, приведенными в теоремах 4 и 5.


Задача нахождения частных сумм последовательности числовых значений

  • Задача нахождения частных сумм последовательности числовых значений

  • (prefix sum problem):

  • Задача вычисления общей суммы имеющегося набора значений:



Последовательный алгоритм суммирования элементов числового вектора

  • Последовательный алгоритм суммирования элементов числового вектора



Каскадная схема суммирования

  • Каскадная схема суммирования



Количество итераций каскадной схемы суммирования:

  • Количество итераций каскадной схемы суммирования:

  • Общее количество операций суммирования:

  • При параллельном исполнении отдельных итераций каскадной схемы общее количество параллельных операций суммирования является равным:



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

  • Показатели ускорения и эффективности каскадной схемы алгоритма суммирования:

  • где p=n/2 есть необходимое для выполнения каскадной схемы количество процессоров.

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


Модифицированная каскадная схема:

  • Модифицированная каскадная схема:

    • Все суммируемые значения подразделяются на (n/log2n) групп, в каждой из которых содержится (log2n) элементов; для каждой группы вычисляется сумма значений при помощи последовательного алгоритма суммирования;
    • На втором этапе для полученных (n/log2n) сумм отдельных групп применяется обычная каскадная схема:


Для выполнения первого этапа требуется (log2n) выполнение параллельных операций при использовании p= (n/log2n) процессоров

  • Для выполнения первого этапа требуется (log2n) выполнение параллельных операций при использовании p= (n/log2n) процессоров

  • Для выполнения второго этапа необходимо log2(n/log2n)≤log2n параллельных операций для p=(n/log2n)/2 процессоров

  • Время выполнения параллельного алгоритма составляет

  • для p= (n/log2n) процессоров.



С учетом полученных оценок показатели ускорения и эффективности модифицированной каскадной схемы определяются соотношениями:

  • С учетом полученных оценок показатели ускорения и эффективности модифицированной каскадной схемы определяются соотношениями:



Вычисление всех частных сумм…

  • Вычисление всех частных сумм…

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


Вычисление всех частных сумм…

  • Вычисление всех частных сумм…

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


Вычисление всех частных сумм…

  • Вычисление всех частных сумм…



Вычисление всех частных сумм

  • Вычисление всех частных сумм

    • Общее количество выполняемых алгоритмом скалярных операций определяется величиной:
    • Необходимое количество процессоров определяется количеством суммируемых значений:
    • Показатели ускорения и эффективности:






Описывается модель вычислений в виде графа "операции-операнды", которая может использоваться для описания существующих информационных зависимостей в выбираемых алгоритмах решения задач

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

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

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



Как определяется время выполнения параллельного алгоритма?

  • Как определяется время выполнения параллельного алгоритма?

  • Как определить минимально возможное время решения задачи?

  • Какие оценки следует использовать в качестве характеристики времени последовательного решения задачи?

  • Как определить минимально возможное время параллельного решения задачи по графу "операнды – операции"?

  • При каком числе процессоров могут быть получены времена выполнения параллельного алгоритма, сопоставимые по порядку с оценками минимально возможного времени решения задачи?



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

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

  • Для задачи скалярного произведения двух векторов,

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

  • Для задачи нахождения среднего значения для заданного набора числовых данных,

  • Для задачи умножения матрицы на вектор,

  • Для задачи матричного умножения



Гергель В.П. Теория и практика параллельных вычислений. - М.: Интернет-Университет, БИНОМ. Лаборатория знаний, 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