Распараллеливание некоторых численных методов - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Распараллеливание некоторых численных методов, слайд №1

Распараллеливание некоторых численных методов, слайд №2

Распараллеливание некоторых численных методов, слайд №3

Распараллеливание некоторых численных методов, слайд №4

Распараллеливание некоторых численных методов, слайд №5

Распараллеливание некоторых численных методов, слайд №6

Распараллеливание некоторых численных методов, слайд №7

Распараллеливание некоторых численных методов, слайд №8

Распараллеливание некоторых численных методов, слайд №9

Распараллеливание некоторых численных методов, слайд №10

Распараллеливание некоторых численных методов, слайд №11

Распараллеливание некоторых численных методов, слайд №12

Распараллеливание некоторых численных методов, слайд №13

Распараллеливание некоторых численных методов, слайд №14

Распараллеливание некоторых численных методов, слайд №15

Распараллеливание некоторых численных методов, слайд №16

Распараллеливание некоторых численных методов, слайд №17

Распараллеливание некоторых численных методов, слайд №18

Распараллеливание некоторых численных методов, слайд №19

Распараллеливание некоторых численных методов, слайд №20

Распараллеливание некоторых численных методов, слайд №21

Распараллеливание некоторых численных методов, слайд №22

Распараллеливание некоторых численных методов, слайд №23

Распараллеливание некоторых численных методов, слайд №24

Распараллеливание некоторых численных методов, слайд №25

Распараллеливание некоторых численных методов, слайд №26

Распараллеливание некоторых численных методов, слайд №27

Распараллеливание некоторых численных методов, слайд №28

Распараллеливание некоторых численных методов, слайд №29

Распараллеливание некоторых численных методов, слайд №30

Распараллеливание некоторых численных методов, слайд №31

Распараллеливание некоторых численных методов, слайд №32

Распараллеливание некоторых численных методов, слайд №33

Распараллеливание некоторых численных методов, слайд №34

Распараллеливание некоторых численных методов, слайд №35

Распараллеливание некоторых численных методов, слайд №36

Распараллеливание некоторых численных методов, слайд №37

Распараллеливание некоторых численных методов, слайд №38

Распараллеливание некоторых численных методов, слайд №39

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Распараллеливание некоторых численных методов. Доклад-сообщение содержит 39 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Распараллеливание некоторых численных методов Судаков А.А. “Параллельные и распределенные вычисления” Лекция 17

Слайд 2

Описание слайда:

План Нахождение суммы значений Умножение матриц Решение систем линейных уравнений

Слайд 3

Описание слайда:

Сумма последовательности значений Нахождение суммы большого количества слагаемых Численное интегрирование Суммирование рядов Умножение векторов Последовательный вариант // f() – підпрограма обчислення fi sum=0; for(i=0; i

Слайд 4

Описание слайда:

Походы к распараллеливанию суммирования Конвейеризация последовательности операций Векторизация Разбиение цикла на блоки

Слайд 5

Описание слайда:

Разбиение цикла на блоки Суммирование ассоциативно Цикл разбивается на блоки Каждый процессор выполняет свой блок цикла параллельно с остальными Результаты работы всех процессоров складываются

Слайд 6

Описание слайда:

Оценка количества операций Время выполнения последовательного алгоритма Nf – количество операций вычисления функции Время выполнения параллельного суммирования Время передачи данных Коэффициент ускорения

Слайд 7

Описание слайда:

Эффективность распараллеливания суммирования Коэффициент эффективности Ускорение при распараллеливании будет когда При большом количестве процессоров При увеличении количества процессоров эффективность падает При увеличении количества процессорных операций эффективность растет

Слайд 8

Описание слайда:

Конвейер Количество пересылок равно p-1 Эффективность ниже, чем при число параллельной обработке Существует возможность выполнения асинхронных операций Процессор, который закончил работу может сразу же приступить к выполнению дальнейшей работы

Слайд 9

Описание слайда:

Графическая иллюстрация

Слайд 10

Описание слайда:

Умножение матриц Блочное представление дает возможность вычислять блок результата параллельно с остальными блоками результата Рассмотрим пример для квадратной сетки размерности k, блоков размерности m и матрицы размерности n, количество процессоров p

Слайд 11

Описание слайда:

Алгоритм Фокса Каждый процессор pij вычисляет свой блок матрицы Cij На каждом процессоре выделяется место для хранения 4-х блоков Cij – блок результата Aij – блок матрицы A, который хранится на текущем процессоре A1ij – блок матрицы A, который получен с другого процессора B1ij – блок матрицы B, который получен с другого процессора (блоки правой матрицы все время перемещаются)‏ Выполняется инициализация C – обнуляется A – содержит блок матрицы A данного процессора B1 – содержит блок матрицы B данного процессора

Слайд 12

Описание слайда:

Алгоритм Фокса (продолжение)‏ На каждой итерации алгоритма, номер l (l=1,k)‏ Один процессор каждой строки отправляет свой блок матрицы A на все процессоры своей строки, номер столбца j для строки i=(i-l+1)mod(k)+1. Процессоры принимают эти данные в матрицу A1 Выполняется обычное матричное умножение C=C+A1*B1 Матрица B1 передается соседу сверху Повторяется для следующего l

Слайд 13

Описание слайда:

Оценка времени Алгоритма Фокса Время одной итерации равно Время рассылки блока матрицы A1 Время отправки блоков матрицы B1 Время умножения матриц A1 и B1 Время k итераций в k раз больше Коэффициент ускорения

Слайд 14

Описание слайда:

Характеристики Алгоритм содержит как конвейерные так и параллельные операции Достаточно эффективен при больших размерностях матрицы Существуют другие алгоритмы с большим количество синхронных или асинхронных операций

Слайд 15

Описание слайда:

Решение систем линейных уравнений Есть система линейных уравнений Матрица A размерности nxn Матрицы B и x размерности nxm Матрица x - неизвестна

Слайд 16

Описание слайда:

Методы последовательного исключения неизвестных Метод Гаусса Над матрицами A и B выполняются элементарные преобразования, чтобы свести матрицу A к треугольному виду После чего решение находится с помощью обратного хода метода Гаусса Исключение неизвестных В каждой строке выбирается ведущий элемент – самый большой по модулю Текущая строка вычитается из всех расположенных ниже, нормированных на ведущий элемент При этом на месте ведущего элемента во всех ниже расположенных строках будут нули

Слайд 17

Описание слайда:

Последовательная программа // прямий хід //k- нумерує кроки виключення //i- нумеує рядки //j – нумерує стовпці матриці A //l – нумерує стовпці матриці B for(k=0;k

Слайд 18

Описание слайда:

Распараллеливание прямого хода Строки распределяются по процессорам равномерно, каждый процессор содержит n/p строк, i-й процессор содержит строки с номерами i+kp (k=1,n/p)‏ Передачу лучше выполнить конвейерно по принципу привилегированной передачи Первый процессор находит ведущий элемент, вычисляет результат деления своей строки на ведущий элемент Результат деления и номер ведущего элемента пересылается на следующий процессор Первый процессор продолжает исключение своих строк Второй процессор принимает данные от первого , выполняет исключение и тоже передает данные дальше

Слайд 19

Описание слайда:

Реализация // прямий хід //k- нумерує кроки виключення //i- нумерує рядки //j – нумерує стовпці матриці A //l – нумерує стовпці матриці B //p - кількість процсорів //c – номер поточного процесора //cur – поточний рядок for(k=0;k0?c-1:p-1,cur); } //передати поточний рядок наступному в кільці if(k

Слайд 20

Описание слайда:

Другие алгоритмы передачи

Слайд 21

Описание слайда:

Оценка времени передачи Последовательный алгоритм – порядка n3 операций Параллельный алгоритм Порядка n3/p последовательных операций Порядка n2 последовательных пересылок данных Порядка n устанослений связи

Слайд 22

Описание слайда:

Иллюстрация Эффективность растет при увеличении порядка матрицы Один из самых эффективных методов

Слайд 23

Описание слайда:

Сравнение разных методов передачи

Слайд 24

Описание слайда:

Итеративные методы Метод Якоби выражается значение неизвестного через значения других неизвестных Итеративно находятся все значения

Слайд 25

Описание слайда:

Последовательный вариант //xnew – наступне наближення //xold – попереднє наближення //eps – умова завершення ітераційного процесу for(;;){ for(i=0;i

Слайд 26

Описание слайда:

Распараллеливание Каждый элемент нового приближения может быть вычислен параллельно с другими элементами этого же приближения Каждый процессор содержит n/p=q строк матрицы A Каждый процессор вычисляет свою часть приближения Каждый процессор передает всем остальным свою часть приближения

Слайд 27

Описание слайда:

Параллельная реализация for(;;){ for(i=c*n/p;i

Слайд 28

Описание слайда:

Оценка времени Время параллельных вычислений складывается из времени работы процессора и времени выполнения передачи

Слайд 29

Описание слайда:

Иллюстрация Распараллеливается достаточно эффективно Требует синхронизации, что снижает эффективность

Слайд 30

Описание слайда:

Сравнение различных матричных методов

Слайд 31

Описание слайда:

Решение дифференциальных уравнений в частных производных Возникают в различных физических задачах Расчет прогноза погоды Расчет тепловых свойств Электричество Расчет прочности конструкция Аэродинамика

Слайд 32

Описание слайда:

Дискретизация задачи На область накладывается сетка с шагом h Производные заменяются разностными аппроксимациями Аналогично вторые производные Уравнение

Слайд 33

Описание слайда:

Пример – уравнение Лапласа Возникает в электротехнических задачах Уравнение Лапласа Граничные условия Найти потенциал электрического поля в области с цилиндрической симметрией На границе области потенциал равен f(x,y)‏

Слайд 34

Описание слайда:

Решение уравнения Метод Якоби Выражаем значение в узле сетки через 4 соседних значения Выбираем начальное приближение в узле Интеративно повторяем до сходимости

Слайд 35

Описание слайда:

Распараллеливание На сетку накладывается процессорная сетка Каждому узлу процессорной сетки соответствует n/p узлов сетки дискретизации Для каждого узла процессорной сетки итерации можно проводить параллельно После итерации необходим обмен на границе сетки

Слайд 36

Описание слайда:

Реализация // px, py – координати процесора в процесорній сітці // u – старі наближення функції у вузлах сітки // unew – нові наближення функції у вузлах сітки for(;;){ if(px!=0) for(j=0;j

Слайд 37

Описание слайда:

Оценка эффективности Для сетки n2 время выполнение последовательного алгоритма 4tn2 Для p2 процессоров время состоит из процессорной работы и обмена ускорение растет с увеличением количества данных задачи и падает с увеличением количества процессоров