Разделы презентаций


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

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

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

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

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

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


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

План

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




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

Сумма последовательности значений

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


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

Походы к распараллеливанию суммирования

Конвейеризация последовательности операций
Векторизация
Разбиение цикла на блоки


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

Разбиение цикла на блоки

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

// p – кількість процесорів
// k – номер поточного процессора від 0 до p-1
// f() – підпрограма обчислення fi
sum=0;
for(i=k; i sum+=f(i);
}
reduce(0,sum);


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

Оценка количества операций

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


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

Эффективность распараллеливания суммирования

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


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

Конвейер

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

Процессор 1
Начал выполнять
Дальнейшую работу

Процессор 2
Получил результат
Процессора 1,
выполнил суммирование
Передал дальше

Процессор 3
Получил результат
Процессора 2,
выполнил суммирование
Передал дальше


Слайд 9
Графическая иллюстрацияКонвейер дает худшие результаты по ускорению, но не требует синхронизации между всеми процессорами и можно уменьшит
Текст слайда:

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


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


Слайд 10
Умножение матрицБлочное представление дает возможность вычислять блок результата параллельно с остальными блоками результатаРассмотрим пример для квадратной сетки
Текст слайда:

Умножение матриц

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


Слайд 11
Алгоритм ФоксаКаждый процессор pij вычисляет свой блок матрицы CijНа каждом процессоре выделяется место для хранения 4-х блоковCij
Текст слайда:

Алгоритм Фокса

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



Слайд 12
Алгоритм Фокса (продолжение)‏На каждой итерации алгоритма, номер l (l=1,k)‏Один процессор каждой строки отправляет свой блок матрицы A
Текст слайда:

Алгоритм Фокса (продолжение)‏

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

































Передача блоков
матрицы A

Передача блоков
матрицы B


Слайд 13
Оценка времени Алгоритма ФоксаВремя одной итерации равно Время рассылки блока матрицы A1Время отправки блоков матрицы B1	Время умножения
Текст слайда:

Оценка времени Алгоритма Фокса

Время одной итерации равно
Время рассылки блока матрицы A1
Время отправки блоков матрицы B1
Время умножения матриц A1 и B1

Время k итераций в k раз больше
Коэффициент ускорения


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

Характеристики

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


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

Решение систем линейных уравнений

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


Слайд 16
Методы последовательного исключения неизвестныхМетод ГауссаНад матрицами A и B выполняются элементарные преобразования, чтобы свести матрицу A к
Текст слайда:

Методы последовательного исключения неизвестных

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


Слайд 17
Последовательная программа// прямий хід//k- нумерує кроки виключення//i- нумеує рядки//j – нумерує стовпці матриці A//l – нумерує стовпці
Текст слайда:

Последовательная программа

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

//зворотній хід
for(i=n-1; i>=0; i--){
for(l=n;l for(j=i+1;j a[i][l]-=a[j][l]*a[i][j];
a[i][l]/=a[i][i];
}
}


Слайд 18
Распараллеливание прямого ходаСтроки распределяются по процессорам равномерно, каждый процессор содержит n/p строк, i-й процессор содержит строки с
Текст слайда:

Распараллеливание прямого хода

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










Процессор1
Ведущий элемент

Процессор1
Передача следующему

Процессор2






Процессор1
Исключение и передача

Процессор2



Слайд 19
Реализация// прямий хід//k- нумерує кроки виключення//i- нумерує рядки//j – нумерує стовпці матриці A//l – нумерує стовпці матриці
Текст слайда:

Реализация

// прямий хід
//k- нумерує кроки виключення
//i- нумерує рядки
//j – нумерує стовпці матриці A
//l – нумерує стовпці матриці B
//p - кількість процсорів
//c – номер поточного процесора
//cur – поточний рядок
for(k=0;kif(k%p == c){
// поточний рядок у нас
cur=a[k];
} else {
//прийняти поточний рядок від попереднього в кільці
recv(c>0?c-1:p-1,cur);
}
//передати поточний рядок наступному в кільці
if(ksend(c // кожен процесор містить n/p рядків
for(i=0;i //ділення на ведучий елемент
a[i][k]/=cur[k];
// виключення елементів матриць A і B
for(j=k+1;j a[i][j]-=a[i][k]*cur[j];
}
}

//зворотній хід
//кожен процессор має зберігати всі попередні
//значення x[i][l]
//кожен процесор виконує n/p виключень
for(i=n+c-p; i>=c; i-=p){
//отримуємо всі обраховані попередні значення x
for(j=(i+p)>(n-1)?(n-1):(i+p);j>i;j++){
//всі інші значення x вже отримані
recv(cif(i>0)‏
send(c>0?c-1:p-1,x[j]);
}
for(l=0;l for(j=i+1;j a[i][n+l]-=x[j][l]*a[i][j];
a[i][n+l]/=a[i][i];
x[i]=a[i]+n
// відправляємо обрахований рядок
if(i>0)‏
send(c>0?c-1:p-1,a[i]);
}
}


Слайд 20
Другие алгоритмы передачиОбычное кольцоМодифицированное кольцоДвойное кольцоМодифицированное двойноекольцо
Текст слайда:

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

Обычное кольцо

Модифицированное кольцо

Двойное кольцо

Модифицированное двойное
кольцо


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

Оценка времени передачи

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


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

Иллюстрация

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


Слайд 23
Сравнение разных методов передачи
Текст слайда:

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


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

Итеративные методы

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


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

Последовательный вариант

//xnew – наступне наближення
//xold – попереднє наближення
//eps – умова завершення ітераційного процесу
for(;;){
for(i=0;i xnew[i]=0;
for(j=0; j xnew[i]+=a[i][j]*xold[j];
}
for(j=i+1; j xnew[i]+=a[i][j]*xold[j]
}
xnew[i]=(b[i]-xnew[i])/a[i][i];
}
if(abs(abs(xnew)-abs(xold))< eps) break;
xold=xnew;
}


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

Распараллеливание

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


Слайд 27
Параллельная реализацияfor(;;){for(i=c*n/p;i
Текст слайда:

Параллельная реализация

for(;;){
for(i=c*n/p;i<(c+1)*n/p;i++){
xnew[i]=0;
for(j=0; j xnew[i]+=a[i][j]*xold[j];
}
for(j=i+1; j xnew[i]+=a[i][j]*xold[j]
}
xnew[i]=(b[i]-xnew[i])a[i][i];
allgather(xnew);
}
if(abs(abs(xnew)-abs(xold))< eps) break;
xold=xnew;
}


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

Оценка времени

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


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

Иллюстрация

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


Слайд 30
Сравнение различных матричных методов
Текст слайда:

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



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

Решение дифференциальных уравнений в частных производных

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



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

Дискретизация задачи

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


h

h

i

j


Слайд 33
Пример – уравнение ЛапласаВозникает в электротехнических задачахУравнение ЛапласаГраничные условияНайти потенциал электрического поля в области с цилиндрической симметриейНа
Текст слайда:

Пример – уравнение Лапласа

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


U(x,y)‏

F(x,y)‏


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

Решение уравнения

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

Выбираем начальное приближение в узле

Интеративно повторяем до сходимости


(I,j)‏

(I+1,j)‏

(I-1,j)‏

(I,j-1)‏

(I,j+1)‏


Слайд 35
РаспараллеливаниеНа сетку накладывается процессорная сеткаКаждому узлу процессорной сетки соответствует n/p узлов сетки дискретизацииДля каждого узла процессорной сетки
Текст слайда:

Распараллеливание

На сетку накладывается процессорная сетка
Каждому узлу процессорной сетки соответствует n/p узлов сетки дискретизации

Для каждого узла процессорной сетки итерации можно проводить параллельно
После итерации необходим обмен на границе сетки


2

4

3

Узел
процессорной
сетки

Узел сетки
дискретизации







Слайд 36
Реализация// px, py – координати процесора в процесорній сітці// u – старі наближення функції у вузлах сітки//
Текст слайда:

Реализация

// px, py – координати процесора в процесорній сітці
// u – старі наближення функції у вузлах сітки
// unew – нові наближення функції у вузлах сітки
for(;;){
if(px!=0) for(j=0;jif(px!=n-1) for(j=0;jif(py!=0) for(j=0;jif(py!=n-1) for(j=0;jif(px!=0) for(j=0;jif(px!=n-1) for(j=0;jif(py!=0) for(j=0;jif(py!=n-1) for(j=0;jfor(i=0,i for(j=0;j unew[i][j]=(u[i+1][j]+u[i-1][j]+u[i][j+1]+u[i],[j-1])/4;
}
}
//передати на всі процесори норму нового наближення
allreduce(abs(unew));
if(abs(abs(unew)-abs(u))< eps) break;
u=unew;
absu=abs(unew);
}


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

Оценка эффективности

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


Слайд 38
Вопросы
Текст слайда:

Вопросы



Слайд 39
Текст слайда:




Обратная связь

Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


Для правообладателей

Яндекс.Метрика