Сетевой закон Амдала. Недостатки закона Амдала

Сетевой закон Амдала

В сетевом законе Амдала учитывается время передачи сообщений

С_А – алгоритмическая составляющая коэффициента деградации.

С_{Т –} техническая составляющая, зависит от быстродействия процессора и аппаратуры сети.

Закон Амдала используется для начальной оценки ускорения, на практике чаще используется формула:

− Используются допущения, что самый лучший алгоритм – последовательный. Но некоторые проблемы имеют более эффективное параллельное решение

− Делается предположение, что возможности решения проблемы ограничены тактами процессора, Но в современных МВС каждое ядро имеет свой кэш, что позволяет хранить в памяти больше данных, и уменьшает потери времени

− Допущение, что при увеличении числа процессов ускорение будет расти, в больших системах с увеличением числа процессоров разрастается и решаемая проблема, поэтому ускорение увеличивается слабее, чем ожидается

− Закон Амдала не учитывает потери времени на передачу данных.

Решение уравнения теплопроводности на МВС. Постановка задачи. Расчетные формулы. Параллельный алгоритм. Распределение точек по процессам. Обработка стыков. Ускорение и точность вычислений.

Постановка задачи

Пусть дан тонкий однородный стержень длины L. Распространение тепла в стержне описывается уравнением:

(1),где u(t,x) – температура, t – время, x – координата, a>0

К уравнению задаются граничные условия, при которых u1(t) и u2(t) известны.

Во всех точках стержня известны начальные значения температур.

Найти u(t,x) для любого t>t⁰

Расчётные формулы

Воспользуемся методом сеток (методом конечных разностей)

Шаг по времени

Шаг по оси

Для решения будем использовать явную конечно-разностную схему:

,

Явная схема обладает достоинством, что решение на верхнем временном слое получается сразу (без решения СЛАУ) по значениям сеточных функций на нижнем временном слое t^k. Но эта же схема обладает существенным недостатком, поскольку она является условно устойчивой с условием:

, накладываем на сеточные характеристики τ и h.

Параллельный алгоритм MPI:

Воспользуемся геометрическим видом параллелизма, т.е. декомпозицией по пространству. Пусть будем использовать size-процессов. Введем шаг по оси x-h и шаг по времени – tau.

Определим кол-во точек на стержне длины L: int N = (int)L/h + 1; Распределим точки по процессам приблизительно одинаковыми частями, определим целое число точек.

Обработка стыков

1. Способ (простой)

На нулевом последнем процессе введем по одной дополнительной точке в конце и начале отрезка соответственно. На всех остальных процессах введем по две дополнительные точки в начале и конце отрезка.

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

Организованная таким образом обработка стыков выполняется за (size-1)*2 тактов по времени, выполняется последовательно.

+ легко программируется

− линейная зависимость от числа процессов

− последовательное выполнение передач

2. Способ (делим на четные и нечетные)

Разделим процессы на четные и нечетные, которые будут работать парами.

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

Решение систем обыкновенных дифференциальных уравнений на МВС методом Рунге-Кутта 4. Постановка задачи. Расчетные формулы. Параллельный алгоритм. Распределение заданий по процессам. Ускорение и точность вычислений.

Используем функциональный вид параллелизма при решении системы обыкновенных дифференциальных уравнений.

Постановка задачи

Дана задача Коши.

Расчётные формулы

Воспользуемся методом Рунге-Кутты 4

Каждый шаг по времени состоит из следующих этапов:

1)

2)

3)

4)

5)

6)

Параллельный алгоритм

Воспользуемся функциональным видом параллелизма (декомпозиция по задачам)
Определим функцию вычисления правых частей. Определим число параметров в системе.
Используем n+1 процессов. Организуем цикл t0 ->tmax с шагом tau.

Ускорение и точность вычислений

Ускорение достигается при одновременном вычислении.

В MPI программе будут потери за счёт передач, но передачи организованы оптимально. При правильном выборе шага tau не будет вычислительной неустойчивости, и значения во всех вариантах совпадают.