Нижегородский государственный университет им. Н.И.Лобачевского Факультет Вычислительной математики и кибернетики Лекция 3. Моделирование и анализ параллельных вычислений Образовательный комплекс Введение в методы параллельного программирования Гергель В.П., профессор, д.т.н. Кафедра математического обеспечения ЭВМ

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

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

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

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

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

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

Н.Новгород, 2005 г. Основы параллельных вычислений: Моделирование и анализ параллельных вычислений © Гергель В.П. 8 из 60 Пусть p есть количество процессоров, используемых для выполнения алгоритма. Тогда для параллельного выполнения вычислений необходимо задать множество (расписание): –i - есть номер операции, –P i - есть номер процессора, –t i - есть время начала выполнения i-ой операции. Должны выполняться условия: –один и тот же процессор не должен назначаться разным операциям в один и тот же момент времени: –к назначаемому моменту выполнения операции все необходимые данные уже должны быть вычислены: Схема параллельного выполнения алгоритма

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Н.Новгород, 2005 г. Основы параллельных вычислений: Моделирование и анализ параллельных вычислений © Гергель В.П. 24 из 60 Пример: Вычисление частных сумм… Каскадная схема суммирования –V 2 = { (v i1,…,v ili ), 0ik, 1l i 2 -i n } есть вершины графа, –(v 01,…, v 0n ) есть операции ввода, –(v 11,…,v 1n/2 ) есть операции первой итерации и т.д., –R 2 = { (v i-1,2j-1 v ij ),(v i-1,2j v ij ), 1ik, 1l i 2 -i n } есть множество дуг графа.

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

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

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

Н.Новгород, 2005 г. Основы параллельных вычислений: Моделирование и анализ параллельных вычислений © Гергель В.П. 28 из 60 Пример: Вычисление частных сумм… Для выполнения первого этапа требуется (log 2 n) выполнение параллельных операций при использовании p= (n/log 2 n) процессоров Для выполнения второго этапа необходимо log 2 (n/log 2 n)log 2 n параллельных операций для p=(n/log 2 n)/2 процессоров Время выполнения параллельного алгоритма составляет для p= (n/log 2 n) процессоров.

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

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

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

Н.Новгород, 2005 г. Основы параллельных вычислений: Моделирование и анализ параллельных вычислений © Гергель В.П. 32 из 60 Вычисление всех частных сумм… Пример: Вычисление частных сумм…

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

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

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

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

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

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

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

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

Н.Новгород, 2005 г. Основы параллельных вычислений: Моделирование и анализ параллельных вычислений © Гергель В.П. 41 из 60 Анализ масштабируемости параллельных вычислений… –Если сложность решаемой задачи является фиксированной (T 1 =const), то при росте числа процессоров эффективность, как правило, будет убывать за счет роста накладных расходов T 0, –При фиксации числа процессоров эффективность использования процессоров можно улучшить путем повышения сложности решаемой задачи T 1, –При увеличении числа процессоров в большинстве случаев можно обеспечить определенный уровень эффективности при помощи соответствующего повышения сложности решаемых задач.

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

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

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

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

Н.Новгород, 2005 г. Основы параллельных вычислений: Моделирование и анализ параллельных вычислений © Гергель В.П. 46 из 60 Пример: Вычисление числа Анализ эффективности Время параллельного решения задачи T p = 6n/p log 2 p Ускорение Sp = T 1 / T p = 6n / (6n/p log2p) Эффективность Ep = 6n / (6n + 6p + plog 2 p) Функция изоэффективности W = K(pT p - W) = K(6p + plog 2 p) n = [K(6p + plog 2 p)]/6, (K=E/(1–E)) Ex.: E=0.5 при p=8 n= 12 при p=64 n=128

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

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

Н.Новгород, 2005 г. Основы параллельных вычислений: Моделирование и анализ параллельных вычислений © Гергель В.П. 49 из 60 Анализ эффективности W = T 1 = 6n 2 M (M – количество итераций) T p = 6M + M log 2 p Ускорение S p = T 1 / T p = 6n 2 / (6n 2 /p + log 2 p) Функция изоэффективности W = K(pT p - W) = K(plog 2 p) n 2 = [K(plog 2 p)]/6, (K=E/(1-E)) Пример: Метод конечных разностей Метод конечных разностей является более масштабируемым, чем метод прямоугольников

Н.Новгород, 2005 г. Основы параллельных вычислений: Моделирование и анализ параллельных вычислений © Гергель В.П. 50 из 60 Заключение… В разделе описывается модель вычислений в виде графа "операции-операнды", которая может использоваться для описания существующих информационных зависимостей в выбираемых алгоритмах решения задач. Рассматривается понятие паракомпьютера как параллельной системы с неограниченным количеством процессоров. Для оценки оптимальности разрабатываемых методов параллельных вычислений в разделе приводятся основные показатели качества - ускорение (speedup), эффективность (efficiency), стоимость (cost) вычислений.

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

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

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

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

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

Н.Новгород, 2005 г. Основы параллельных вычислений: Моделирование и анализ параллельных вычислений © Гергель В.П. 56 из 60 Гергель В.П. Теория и практика параллельных вычислений. - М.: Интернет-Университет, БИНОМ. Лаборатория знаний, Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ-Петербург, 2002.БХВ-Петербург Kumar V., Grama, A., Gupta, A., Karypis, G. (1994). Introduction to Parallel Computing. - The Benjamin/Cummings Publishing Company, Inc. (2nd edn., 2003) Quinn, M. J. (2004). Parallel Programming in C with MPI and OpenMP. – New York, NY: McGraw-Hill Bertsekas, D.P., Tsitsiklis, J.N. (1989). Parallel and distributed Computation. Numerical Methods. - Prentice Hall, Englewood Cliffs, New Jersey. Литература…

Н.Новгород, 2005 г. Основы параллельных вычислений: Моделирование и анализ параллельных вычислений © Гергель В.П. 57 из 60 Zomaya, A.Y. (Ed.) (1996). Parallel and Distributed Computing Handbook. - McGraw-Hill. Amdahl, G. (1967). Validity of the single processor approach to achieving large scale computing capabilities. In AFIPS Conference Proceedings, Vol. 30, pp , Washington, D.C.: Thompson Books. Grama, A.Y., Gupta, A. and Kumar, V. (1993). Isoefficiency: Measuring the scalability of parallel algorithms and architectures. IEEE Parallel and Distributed technology. 1 (3). pp Gustavson, J.L. (1988) Reevaluating Amdahl's law. Communications of the ACM. 31 (5). pp Литература

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

Н.Новгород, 2005 г. Основы параллельных вычислений: Моделирование и анализ параллельных вычислений © Гергель В.П. 59 из 60 Гергель В.П., профессор, д.т.н., руководитель Гришагин В.А., доцент, к.ф.м.н. Сысоев А.В., ассистент (раздел 1) Лабутин Д.Ю., ассистент (система ПараЛаб) Абросимова О.Н., ассистент (раздел 10) Гергель А.В., аспирант (раздел 12) Лабутина А.А., магистр (разделы 7,8,9, система ПараЛаб) Сенин А.В. (раздел 11) Авторский коллектив

Н.Новгород, 2005 г. Основы параллельных вычислений: Моделирование и анализ параллельных вычислений © Гергель В.П. 60 из 60 Целью проекта является создание образовательного комплекса "Многопроцессорные вычислительные системы и параллельное программирование", обеспечивающий рассмотрение вопросов параллельных вычислений, предусматриваемых рекомендациями Computing Curricula 2001 Международных организаций IEEE-CS и ACM. Данный образовательный комплекс может быть использован для обучения на начальном этапе подготовки специалистов в области информатики, вычислительной техники и информационных технологий. Образовательный комплекс включает учебный курс "Введение в методы параллельного программирования" и лабораторный практикум "Методы и технологии разработки параллельных программ", что позволяет органично сочетать фундаментальное образование в области программирования и практическое обучение методам разработки масштабного программного обеспечения для решения сложных вычислительно-трудоемких задач на высокопроизводительных вычислительных системах. Проект выполнялся в Нижегородском государственном университете им. Н.И. Лобачевского на кафедре математического обеспечения ЭВМ факультета вычислительной математики и кибернетики ( Выполнение проекта осуществлялось при поддержке компании Microsoft. О проекте