Page 45 - 4868

43 Ошибка! Стиль не определен.

накопичення.В даному випадку зберігається (накопичується) максимальний з
переглянутих елементів, або, іншими словами, всі значення зводяться до їх
максимуму.Нехайm– змінна для зберігання максимального значення.Ціль
програми за допомогою логіки предикатів можна описати наступним чином.

j
 j  : 1  : n m a [ ],j

j
 j  : 1  : n m a [ ].j
Перший рядок говорить, що при завершенні програми значення змінної
mповинно бути не менше будь-якого значення в масиві a. Другий рядок

означає, що змінна повинна бути рівна деякому значенню з масиву a.
Для вирішення даної задачі можна використати наступну послідовну
програму.
int m = 0;
for [i = 0 to n-1] {
if (a[i] > m) m = a[i];
}

Ця програма ітеративно переглядає всі значення в масивіa.Якщо існує
деяке значення з масиву a яке більше поточного максимуму, то воно
присвоюєтьсяm.Оскільки передбачається, що значення елементів масиву
aдодатні, то можна виконати початкову ініціалізацію змінної mзначенням 0.
Тепер розглянемо способи розпаралелювання наведеної
програми.Припустимо, що цикл повністю розпаралелений шляхом
паралельної перевірки всіх елементів масиву.

int m = 0;
co [i = 0 to n-1]
if (a[i] > m) m = a[i];
У цій формі оператор co використовує один або декілька
квантифікаторів, які вказують, що набір операторів повинен виконуватися
паралельно для кожної комбінації значень параметрів циклу. Наприклад,

наступний тривіальний оператор ініціалізує масиви a[i] та b[i] нулями.
co [i = 0 to n-1] {
a[i] = 0;
b[i] = 0;
}

Даний оператор створює nпроцесів, по одному для кожного значення
змінної i.Область видимості лічильника – опис процесу, і в кожного процесу
своє, відмінне від інших, значення змінної i.Дві форми оператора co можна
змішувати. Наприклад, одна гілка може мати квантифікатор у квадратних
дужках, а інша оператор coпаралельного виконання.
Попередня програма пошуку максимального елемента масиву
некоректна, оскільки процеси не є незалежними: кожен з них і зчитує, і
записує змінну m. Зокрема, припустимо, що всі процеси виконуються з
однаковою швидкістю, і, отже, кожен з них порівнює свій елемент масиву