9.4. Поняття про паралельні обчислення
Модель машини Тьюринга передбачає послідовне виконання елементарних операцій. Такій моделі відповідає іноді використовувана модель "одного обчислювача", що має низьку швидкість обчислень при її технічній реалізації. Така модель реалізується Фон-Нейманівської структурою ЕОМ. Для моделювання процесів реалізації паралельного виконання елементарних операцій теорії алгоритмів використовується модель " колективу обчислювачів " . Кожне підзавдання вирішується обчислювачем, який за необхідності отримання чи передачі інформації інших подзадач обмінюється нею з іншими обчислювачами. Разом з тим, не виключається можливість вирішення одним обчислювачем одного простого завдання, не пов'язаного з іншими, наприклад, при обчисленні ав+сdе. Усі обчислювачі працюють одночасно у часі, паралельно виконуючи свої функції. Зручним засобом опису паралелізму взаємодіючих процесів є графові моделі особливого виду, які називаються мережами Петрі.
Мережа Петрі є дводольним графом (тобто таким графом, безліч вершин якого розпадається на дві неперетинаються підмножини таких, що кожне ребро графа має один кінець в одному підмножині, а інший - в іншому підмножині) і містить вершини двох типів - позиції та переходи , а також спрямовані ребра-дуги, які можуть з'єднувати вершини різних типів. На рис.9.7. наведено простий приклад мережі Петрі, де кружками позначені вершини, іменовані позиціями, а вертикальними лініями - вершини, звані переходами. Багато позицій, які з'єднані з певним переходом спрямованими до нього дугами, називаються вхідними позиціями даного переходу. Усі позиції, яких спрямовані дуги від переходу, утворюють безліч вихідних позицій цього переходу. Кожній вершині графа, що відповідаєпозиції мережі Петрі, може бути поставлено відповідно до невід'ємного числа міток, які на малюнку позначаються точками всередині гуртка. Початковий розподіл міток відповідає початковим умовам роботи мережі та називається початковим маркуванням.
Таким чином, мережа Петрі N може бути задана наступною четвіркою: N = 0, тут А і Т - кінцеві множини позицій і переходів відповідно: А = 1. ak>, T=1. tl>. У цьому АТ=, АТ. ФункціяF визначає зв'язок між позиціями та переходами так, що
F(a,t)=
F(t,a)=
М0 визначає початкове маркування мережі та є k-мірним вектором невід'ємних чисел, j-й елемент якого позначає число міток у позиції аj.
Для мережі Петрі рис.9.7 k=l=5, М0= і
F(a,t)=
Якщо всі вхідні позиції переходу ti містять мітки, такий перехід є активним. Активний перехід можна реалізувати. Іноді про активні переходи говорять як про займистість, а реалізацію переходу називають його згорянням. В результаті реалізації (згоряння) переходу видаляється одна мітка з кожної вхідної позиції та поміщається по одній мітці в кожну вихідну позицію. Таким чином, мітка позиції може бути використана для реалізації лише одного переходу. Реалізацію переходу можна розглядати як подію, що здійснюється при виконанні певних умов, у результаті старі умови зникають і створюються нові, при цьому загальна кількість міток у мережі може змінитися. Істотно, що не всі активні переходи мають бути реалізовані, але допустима реалізація лише активних переходів.
У мережі Петрі рис.9.7 початкове маркування, відповідно до якої є мітка позиції а1, робить активним перехідt1. Після реалізації цього переходу мітка з а1видаляється і поміщаються мітки впозиції а2і а3, що відповідає розпаралелювання процесу. Потім реалізуються переходиt2іt3і з'являються мітки а4і а5. Ці події можуть відбуватися в різні моменти часу, оскільки вони відносяться до різних процесів, що паралельно протікають. Однак ніt4ніt5не можуть бути реалізовані, поки обидва ці процеси не закінчаться. Потім реалізується якийсь із переходів t4 або t5 і мережа Петрі переходить у початковий стан.
Мережа Петрі є зручним та наочним засобом опису взаємодіючих процесів. Перебіг процесу відповідає послідовності реалізації переходів, що викликає переміщення міток мережею, тобто. зміна станів процесу.
У додатку 2 представлений додатковий матеріал про паралельні обчислення.