Page 48 - 6571

собів перемішати колод по m карт у кожній, за умови, що від-
n
носний порядок карт в кожній колоді зберігається.
Третій підхід полягає у застосуванні стверджувальних мірку-
вань (assertional reasoning). Його можна назвати «абстрактним

аналізом». У цьому методі формули логіки предикатів назива-
ються твердженнями і використовуються для опису наборів ста-
нів – наприклад, всіх станів, у яких x > 0. Неподільні дії розгля-

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

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

грамі.

6.2 Розпаралелювання (задача пошуку зразка у файлі)

Розглянемо задачу пошуку всіх екземплярів шаблону patte-
rn у файлі filename. Змінна pattern – це заданий рядок, а

змінна filename – ім’я файлу. Ця задача без значних зусиль ви-
рішується в ОС Unix на командному рівні за допомогою однієї із

команд сімейства grep, наприклад:
grep pattern filename

У результаті створюється один процес. Він виконує приблиз-

но наступну послідовну програму.
string line;
прочитати рядок вводу з stdin в line;

while (!EOF) { # EOF – це кінець файлу
шукати pattern в line;
if (pattern є в line) вивести line;
прочитати наступний рядок вводу;
}

Тепер бажано з’ясувати два основних питання: чи можна ро-
зпаралелити цю програму? Якщо так, то яким чином?
Основна вимога для можливості розпаралелювання будь-якої

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

47