Параллельные вычисления. Баканов В.М. - 80 стр.

UptoLike

ВУЗ: 

МИРЭА | Москва

Составители: 

Рубрика: 

- 80 -
int k = N / N_P; // целое от деления N на N_NP
int k1 = N % N_P; // остаток от деления N на N_P
if ((I_AM > 0) && I_AM < N_P-1) { // для всех процессов кроме нулевого и последнего…
s = 0;
for (i=k
∗
(N_P-1); i<k
∗
N_P; i++) // суммируем k элементов массива A[ ]
s += A[i]; // s – локальная для каждого процесса переменная
послать s управляющему процессу // оператор не конкретизируется
}
// конец блока if ()
else
if (I_AM == N_P-1) { // для последнего процессора…
s = 0;
for (i= k
∗
(N_P-1); i< k
∗
N_P+k1; i++) // суммируем k+k1 элементов массива A[ ]
s += A[i]; // s – локальная для каждого процесса переменная
послать s управляющему процессу // оператор не конкретизируется
}
// конец блока if ()
Здесь каждый процессор (кроме нулевого и последнего) осуществляет сум-
мирование очередных
K
элементов массива
A[ ]
, последний процессор сумми-
рует оставшиеся
K+K1
элементов. Последним действием (выполняющимся
после всех приведенных – именно здесь необходима синхронизация) является
суммирование всех частичных сумм, полученных
N_P-1
процессорами:
if (I_AM == 0) { // выполняется управляющим процессом
sum = 0;
for (j=1; j<N_P; j++) { // по всем процессам 1
÷
N_P
принять значение s от процесса j // оператор не конкретизируется
sum += s; // готовое значение – в переменной sum
}
// конец блока for ()
}
// конец блока if ()
При излишне большом размере массива
A[ ]
процесс распределения его про
процессам может повторяться многократно (что способствует экономии ОП
каждого процессора), общее ускорение выполнения программы будет, конеч-
но, несколько меньше
N_P
(сетевой закон Амдаля, см. подраздел 1.5). При
разработке параллельной программы желательно использовать алгоритм, аб-
страгирующийся от количества процессоров (программа должна выполняться
на МВС с числом процессоров
≥
2).
Приведенный пример иллюстрирует блочное распределение итераций по
процессорам и является типовым для множества алгоритмов, основными
действиями в которых являются обладающие свойством ассоциативности
операций сложения/умножения (матричные операции, поиск экстремумов в
массивах, интегрирование и многие др.). Преимуществом его является сба-
лансированность загрузки ‘рабочих’ процессоров (все кроме одного выпол-
няют одинаковую работу,
последний ‘перерабатывает’ менее чем на
1-N_P
100%
).
Заметим, что условием сбалансированности загрузки процессоров является
приблизительно равноценные по времени исполнения распределяемые ите-
рации (рассматриваемый пример удовлетворяет этому условию). Таким ус-
                                                   - 80 -



  int k = N / N_P;                              // целое от деления N на N_NP
  int k1 = N % N_P;                             // остаток от деления N на N_P
   if ((I_AM > 0) && I_AM < N_P-1) {            // для всех процессов кроме нулевого и последнего…
    s = 0;
    for (i=k ∗ (N_P-1); i

Страницы