Page 55 - 6571

У програмі, представленій вище, зчитування і запис змінної m
є окремими операціями. Для роботи з таким рівнем паралельності
необхідно використати синхронізацію для поєднання окремих дій
в одній неподільній операції. Це демонструє наступна програма.

int m = 0;
co [i = 0 to n-1]
<if (a[i] > m) m = a[i];>

Кутові дужки в цьому фрагменті коду вказують, що кожен

оператор if виконується як неподільна операція, тобто перевіряє
поточне значення m і відповідно з умовою оновлює його в одній

неподільній дії.
На жаль, остання програма – це майже те ж саме, що і послі-
довне рішення. У послідовній програмі елементи масиву a пере-
віряються у встановленому порядку – від a[0] до a[n-1]. В

останній програмі елементи масиву a перевіряються в довільному
порядку, оскільки у довільному порядку виконуються процеси.

Але через синхронізацію перевірки все ще виконуються по одній.
Основне завдання – забезпечити, щоб оновлення змінної m
були неподільними операціями, а значення змінної m було дійсно
максимальним. Припустимо, що порівняння виконуються пара-

лельно, але оновлення даних виконуються по одному, як в насту-
пній програмі.

int m = 0;
co [i = 0 to n-1]
if (a[i]> m)
<m = a[i];>

Результат виконання даної програми насправді буде тим же,
що і першої паралельної програми. Кожен процес здатний порів-

няти своє значення елемента з масиву a із змінною m і потім об-
новити значення змінної m. І хоча оновлення m є неподільною
операцією, проте така неподільність фактично забезпечується на

апаратному рівні.
Отже, вихід полягає в поєднанні останніх двох програм. Мо-
жна безпечно виконувати паралельні порівняння, оскільки це дії,

які тільки зчитують змінні. Але необхідно забезпечити, щоб при
завершенні програми значення m дійсно було максимальним. Це
досягається в наступній програмі.

54