Стр. 47 - Параллельное программирование

ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ

45

Глобальная балансировка обычно приводит к высоким накладным расходам,

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

вычислительной нагрузки.

При использовании функционального способа декомпозиции процесса вычис-

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

операций по процессорам.

Возможные подходы

:

•

централизованная схема;

•

иерархическая схема;

•

децентрализованная схема (централизованная или распределенная очередь

заданий).

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

ные способы распределения данных (частей матриц) по процессорам:

•

ленточная или блочная схема распределения;

•

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

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

ные способы распределения данных (частей матриц) по процессорам:

•

ленточная или блочная схема распределения;

•

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

Рис. 5.3. Ленточная схема распределения n матриц по процессорам p

k

Рассмотрим задачу параллельного перемножения матриц. Над полем P заданы

матрицы:

,

. Требуется найти

матрицу

, где

.

{

}

P a,n,

j,n,

i: a

j,i

∈ = =

=

1 1

A

{

}

P b,n,

j,n,

i: b

j,i

∈ = =

=

1 1

B

{

}

P c,n,

j,n,

i: c

j,i

∈ = =

=

1 1

C

∑

=

⋅

=

n

k

j,k k,i

j,i

b a

c

1

0 1 2 3 4 ......n

0

1

2

3

.......

n

p

1

p

2

p

3

…….