1631124674-6a00ac47f208bd132d328527d69fe75d (848586), страница 5

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

Текст из файла (страница 5)

Итог: передавать данные нужно большими порциями; нужно придумывать алгоритмы, в которых коммуникаций меньше, чем операций.

f -- θ из вопроса 12 (относительная доля параллелизуемой части).

12.Законы Амдала и Густафсона (Добшик)

(Комментарии из видео-лекции 14.02)

Рассматривается распараллеливание фиксированной задачи А на разном количестве процессоров р.

Закон Амдаля

Закон Амдаля говорит о том, как изменяется ускорение вычислений на фиксированной задаче, если не все вычисления распараллеливаются.

(Напомню ускорение S_p(A)=T₁(A) / T_p(A), где А - какая-то решаемая задача или алгоритм, T_p(A) - время решения задачи А на р процессорах, T₁(A) - на одном).

S - итоговое ускорение - коэффициент ускорения времени решения всей задачи.

Если часть вычислений распараллеливается с ускорением S_p, а Ө (например равно 0.7 или 0.9) - относительная доля параллелизуемой части, то итоговое ускорение всей задачи можно вычислить с помощью формулы Амдаля: S = 1 / (1 - Ө - Ө/S_p)

Важное неравенство: итоговое ускорение S ≤ 1 / ( 1 - Ө ).

На графике показана функция Амдаля, по горизонтали - число процессоров p, по вертикали итоговое ускорение.

Видно, что число процессоров p может увеличиться в тысячи раз, но график S выходит на плато, значение которого зависит от Ө. Вывод: надо строить алгоритм так, чтобы в нем почти не было нераспараллеливаемых частей, то есть Ө было как можно больше.

Закон Густафсона

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

Итоговая формула S = 1 - Ө + ӨS_p.

S_p - число распараллеливаемых вычислений

Если ускорение S_p линейно (пропорционально количеству процессоров p), то функция ускорения S будет также линейна.

Важно отметить, что в этих законах рассматриваются "идеальные компьютеры", нет операций обмена (для упрощения анализа). Если учитывать операции обмена, то ситуация усложняется.

То же самое кратко на слайдах:

13.Параллельный метод сдваивания (Гуськова)

(Из видео-лекции 14.02)

Простейший пример: сумма N слагаемых: σ = или произведение N множителей: p = . С точки зрения распараллеливания эти операции одинаковые и имеют одинаковый принцип. Пусть есть восемь скалярных чисел. Их нужно сложить или перемножить. Как это делать параллельно: единственный способ - метод сдваивания. складываем по 2 числа, получаем 4 пары. (на каждую пару выделяем один процессор, все пары складываются одновременно). Теперь 4 числа складываем по два с помощью двух процессоров одновременно. Получаем 2 числа. Берем один процессор и получаем итоговый результат. Какой у этих алгоритмов коэф-т ускорения? Легко подсчитать , P = N/2 : * , . ( -- время 1 операции)

Например: N=1014, то ≈ 100, ≈ 0.2.

И для более общего случая: N = m*P (P - число процессоров), то

* (m + ), .

Слайд из лекций (есть ошибки в формулах, выше всё верно записано)

Почему * (m + ):

найдём k: P+P(k-1)/2 = N, => k=2m-1, => с точностью до констант получаем * (m + )

14.Умножение матрицы на вектор (Баушенко)

Пусть – матрица, – вектор.

Тогда их произведение: – каждый элемент можем считать независимо.

Поэтому, если есть = ядер или кратное число (=,∈ℕ), то время вычисления на всех будет – в раз меньше. Значит коэффициент ускорения (см. 11) =1=, эффективность использования ==1.

http://math.tsu.ru/sites/default/files/mmf2/e-resources/parallel_comp_meth.pdf (стр. 37)

15.Параллельное умножение матриц (Адоньева)

В записях лекций практически ничего не сказано по этому вопросу. Брала инфу отсюда (стр.53-66) : http://math.tsu.ru/sites/default/files/mmf2/e-resources/parallel_comp_meth.pdf

На 14 вопрос тоже есть ответ.

Не совсем поняла, что именно нужно, т.к. существуют разные алгоритмы.

16.Классический и встречный методы прогонки (Добшик)

(Комментарии из видео-лекции 14.02 47:00)

Классический (обратный) метод прогонки

Рассмотрим трехдиагональную систему линейных уравнений:

Если решаем дифференциальную краевую задачу и учтем граничные условия, то a₁=c_N=0.

В методе прогонки искомое решение ищем в виде рекурсивной формулы:

индексы изменяются от N до 1 - справа налево - обратная прогонка.

Подставив уравнение (2) в (1) получим рекурсивные формулы прямой прогонки (i=1,...,N) для прогоночных коэффициентов z_i β_i:

Иллюстрация работы алгоритма:

В этом алгоритме количество действий пропорционально размерности системы.

Прямая прогонка

Можно v_i выразить через v_i-1 - прямая прогонка:

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

Это два эквивалентных алгоритма.

Метод встречных прогонок

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

Найдем средний узел i₀ и будем вычислять одновременно. Когда они встретятся, то найдем искомую величину v_i0 по формуле

и оставшиеся v_i будем также одновременно считать от центра к краям по формулам:

Такая комбинированная схема хорошо распараллеливается на двух процессорах.

17.Методы редукции трехдиагональных СЛАУ(Адоньева)

http://math.tsu.ru/sites/default/files/mmf2/e-resources/parallel_comp_meth.pdf

также инфа есть на слайдах 27-28

слайды 27-28:

18.Метод циклической редукции (Вербицкий)

по сути это предельный случай метода редукции

не нужен обратный ход! для n нужно log(n) редукций

https://clck.ru/UqjiG

Циклическая редукция, как и все варианты прогонки, заключается в исключении из уравнений неизвестных, однако, в отличие от них, в ней исключение ведут одновременно по всей СЛАУ. В принципе, её можно считать вариантом метода редукции, выполняемого максимально возможное для данной СЛАУ число раз.

19.Явные аппроксимации начально-краевых задач. Неявные аппроксимации начально-краевых задач (Агзямова) (комментарии взяты из видео-лекций)

Нам нужно уметь быстро решать начально-краевые задачи, причём многомерные.

(8) -- Стандартная общая постановка начально-краевой задачи через диф. уравнение (можно написать и интегральное уравнение, но в нашем курсе такие не будем рассматривать. Вообще, для распараллеливания диф-ые постановки лучше и чаще применяются).

Диф уравнение: взяли уравнение первого порядка по времени (можно было и второго, суть от этого не меняется), L(u) - оператор дифференцирования по пространственным переменным. x - вектор d-мерного пространства (нас интересует d=2,3), ᘯ - расчётная область, Г - её граница, их объединение - замкнутая область. Время t можно формально рассматривать как параметр. Рассматриваем задачу Коши, когда начальные данные заданы только в одной точке (t=0) -- это заданная функция координат. Также заданы условия на границе -- краевые, l(u) -- какой-то оператор краевых условий (например, если L(u) - оператор второго порядка, то это могут быть условия Дирихле, Неймана или 3 рода, на одном участке границы условия только одного типа).

u(x,t) может быть вектор-функцией, тогда будет система уравнений (более сложная междисциплинарная задача, т.е. будет объединять в себе разные задачи: теплопроводности, гидрогазодинамики и т.д.).

(9) -- Пример диф. задачи, с главной частью так называемого дивергентного вида. Первая сумма (с a_i,j) -- диффузионный член, вторая сумма -- конвективный член, cu -- можно назвать функцией источника (правая часть -- это тоже какой-то источник, но cu -- источник, зависящий от искомого решения). Решение -- это какая-то субстанция, это может быть скорость, плотность, температура.

(10) -- про эту систему на лекции ничего не сказал, видимо, она не очень важна.

Теперь эту исходную задачу мы аппроксимируем на какой-то сетке (2- или 3-мерной в зависимости от того, какая расчётная область). Сетки бывают простые, регулярные, нерегулярные. Для простоты считаем, что они квадратные или кубические.

Аппроксимировать можем конечными разностями, конечными элементами, конечными объёмами. Когда всё саппроксимировали по пространству (всякие вот эти пространственные производные), получаем матрицы.

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

Список файлов ответов (шпаргалок)