Функциональный (распараллеливание по процессам)

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

Достоинства:

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

Недостатки:

1. блоки не равноценны по затратам машинного времени, что приводит к простою некоторых процессов;

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

Область применения: системы нелинейных уравнений, задачи оптимизации, дифференциальные уравнения.

Конвейерный

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

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

Достоинства:

1. можно обсчитывать большие расчетные области;

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

3. нет стыков и нет проблем связанных с ними;

Недостатки:

Простой процессов в начале и в конце вычислений.

Область применения: решение уравнений математической физики.

Параллелизм типа принятия коллективного решения

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

Достоинства:

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

2. возможность обсчитывать большие расчетные области;

Недостатки:

узкая область применения.

Область применения: задачи оптимизации.

Ускорение и эффективность вычислений на мвс

Ускорение вычислений при использовании Р процессоров рассчитывается по формуле

Где S_P – ускорение при использовании Р процессоров;

T₁ – время которое затрачивает один процессор на выполнение задачи;

T_P - время которое затрачивают Р процессоров на выполнение той же задачи;

Эффективность вычислений:

Закон Амдала: , где α – число операций, не поддающихся распараллеливанию (число последовательных операций); 1 – количество всех операций.

α	1	3/4	1/2	1/4	0
S2 = SP	1	8/7 = 1.1	4/3 = 1.33	8/5 = 1.6	2

α	1	3/4	1/2	1/4	0
S4	1	16/13 = 1.2	8/5 = 1.6	16/7 = 2.2	4

Определение ускорения вычислений при решении системы из трёх уравнений методом Крамера:

1. Дано: A_X=b , где А =

a_ij

Найти x=(x_1,x_2,x₃)^T

2. Найти главный определитель системы Δ, если Δ≠0, то найдём Δx₁ , Δx₂ , Δx₃

3. Алгоритм распараллеливания. Воспользуемся функциональным видом параллелизма. Возьмём три процесса, которые никак не могут быть связаны друг с другом:

• все процессы вычисляют главный определитель системы;

• если главный определитель равен 0 то нулевой процесс печатает соответствующее сообщение и все процессы заканчивают работу;

• иначе все процессы вычисляют определители неизвестных, причём: процесс с номером 0 вычисляет , процесс с номером 1 вычисляет , процесс с номером 2 вычисляет

• все процессы одновременно вычисляют значения неизвестных, причём процесс с номером 0 вычисляет , процесс с номером 1 вычисляет , процесс с номером 2 вычисляет

• процессы печатают вычисленные значения

Действие Процесс	0	1	2
1	Δ	Δ	Δ
2
3

Действие Процесс	0
1	Δ
2
3
4
5
6
7

Δ≠0

α=1/7

4. Вычисление ускорения. Пусть определитель системы вычисляется за время t, а вычисление неизвестных за время t₂

T₁ = 4t₁ + 3t₂

T₃ = 2t₁ + t₂

пусть t₁ = t₂ = t

T₁=7t

T₂=3t

21/3

Закон Амдала: 21/3

Т.е. ускорение вычислений при использовании трёх процессоров = 2.33

Пример: топология «гиперкуб»

dim x = 4

dim x = 4

myx, myy

if (myx !=0)

PrevLink x = ConnectLink (MyID – 1, Reg, & error);

if (myx !=dim x-1)

NextLink x = ConnectLink (MyID + 1, Reg, & error);

if (myx ==0)

PrevLink x = ConnectLink (MyID – 1+ dim x, Reg, & error);

if (myx ==dim x-1)

NextLink x = ConnectLink (MyID + 1 - dimx, Reg, & error);

if (myy !=0)

PrevLink y = ConnectLink (MyID – dimx, Reg, & error);

if (myy !=dim y-1)

NextLink y = ConnectLink (MyID + dimx, Reg, & error);

if (myy ==0)

PrevLink y = ConnectLink (MyID + (dim y-1)*dimx, Reg, & error);

if (myy ==dim y-1)

NextLink y = ConnectLink (MyID – (dimy-1)*dimx, Reg, & error);