Розділ 2
ФОРМАЛЬНЕ ПРЕДСТАВЛЕННЯ ТЕОРІЇ ПАРАЛЕЛЬНИХ ОБЧИСЛЕНЬ
2.1. Формальне представлення програми
В розділі вивчаються та формалізуються процеси розпаралелювання в системах
паралельної обробки інформації, які мають специфічний характер згідно
властивостей досліджуваного класу систем.
Однією з основних проблем сучасного паралельного програмування є така задача:
Розглядаються "складні" обчислювальні пристрої U, складені з декількох своїх
обчислювальних підпристроїв, не обов'язково з рівними за потужністю
характеристиками. Для кожної програми P і обчислювального пристрою U написати
алгоритм, який під час виконання програми P обчислювальним пристроєм U так
розподіляє виникаючі завдання між його підпристроями, щоб кількість тактів
виконання цієї програми була найменшою.
Ця задача має як самостійний математичний інтерес, оскільки для її розв'язання
необхідно формалізувати поняття "паралельного" обчислення, так і прикладний,
оскільки задачі розпаралелювання стали особливо актуальними з розвитком
мережевих технологій і різних форм мультипроцесорності.
В даної роботі проводиться теоретичне дослідження, направлене на рішення
поставленої задача (або на доказ, що у деякому сенсі такого рішення не існує).
Для того, щоб вирішити поставлену задачу, раніш за все, необхідно побудувати,
або обрати одну з можливих формалізацій [13-15, 24, 36, 42, 43, 45, 61, 101]
поняття програми і поняття складного обчислювального пристрою (будемо говорити
далі, складного обчислювача). Цей вибір буде проводитися у відповідності з
критеріями інтуїтивної ясності формалізації, що обирається, її зручності з
точки зору опису потрібного нам алгоритму.
Виходячи з цього, ми будемо дотримуватись формалізації поняття програми –
термінальна програма (ТП), яка найбільш близька до запропонованої Скоттом [101]
(діаграми), а також Редьком В.Н. та Буєм Д.Б. [13-15] (примітивна програмна
алгебра). ТП формалізація має ще одну перевагу: в ній явно виписуються всі
функціональні символи; при оцінці складності з фіксованою семантикою цих
символів, функціям, які їм відповідають, можуть бути явно приписані їх
коефіцієнти "складності". Окрім цього, оскільки у цієї формалізації явно
зафіксовані синтаксис і семантика, то цей підхід можна розглядати як логічний.
Пропонуючи цю формалізацію [35], ми будемо дотримуватись наступної
послідовності дій. Спочатку ми формально висловимо синтаксис (опишемо алфавіт і
деяку мову в ньому, слова якого ми будемо називати термами), далі – семантику
(покажемо, як при заданих значеннях символів в алфавіті обчислювати значення
терму), а потім ми приведемо взаємозв'язок між підходом ТП і підходом, що вже
давно став класичним – теорією частково рекурсивних функцій.
Синтаксис визначається таким чином. Спочатку фіксується алфавіт A; він у нашому
випадку завжди складається з множини символів, типізованих таким чином: f0, f1,
... – функціональні символи, p0, p1, ... – предикатні символи, символи S, C, *,
які ми будемо називати символами відповідно операції суперпозиції, операції
(умовного) розгалуження і операції (умовного) циклування, а також з допоміжних
символів: ( – лівою дужки, ) – правої дужки і , – звичайної коми. Взагалі
кажучи, ми не вважаємо сукупності функціональних і предикатних символів не
більш ніж зліченими; проте, для наочності ми, як правило, будемо при
індексуванні цих символів використовувати тільки натуральні числа.
Поняття терму (ТП-терму) в алфавіті A визначимо за індукцією:
1) кожен функціональний символ fi є терм;
2) якщо t, t1, ... , tn - терми, то слово S (t, t1, ..., tn) – терм;
3) якщо t0 і t1 – терми і pi – предикатний символ, то C(pi, t0, t1) – терм;
4) якщо t0 – терм і pi – предикатний символ, то *(pi, t0) – терм;
5) слово у алфавіті A є термом тоді і тільки тоді, коли воно може бути
побудовано за допомогою правил 1– 4 і тільки їх.
Фактично, терм – це синтаксична формалізація поняття "програми": фіксуючи
значення символів S, C і *, як деякі спеціальні та фіксуючи значення символів,
що входять у запис терму, тобто поставимо у відповідність функціональним
символам операції, предикатним символам – предикати і, нарешті, ми зможемо
одержувати конкретні приклади програм. Значення всіх цих символів створюють
семантику терму, що розглядається. Зараз ми більш детально покажемо, які
об'єкти можна обирати у якості значень цих символів і як обчислювати при цих
обраних значеннях символів значення самого терму.
Зафіксуємо деяку множину M. Задати інтерпретацію функціонального символу fi на
множині M – це означає поставити у відповідність йому деяку, можливо, часткову
операцію Fi довільної арності на множині M. Аналогічно, під інтерпретацією
предикатного символу pi на множині M будемо розуміти будь-який, можливо,
частковий предикат Pi довільної арності, заданий на M. Якщо t0 – терм у деякому
алфавіті A і {f , ..., f , p, ..., p} – множина всіх функціональних і
предикатних символів терму t0, то інтерпретацією терму t у множині M
називається будь-яке відображення , в якому кожному функціональному символу f ,
1 Ј j Ј m і предикатному символу p, 1 Ј k Ј n відповідають їх деякі
інтерпретації F і P у M.
Кожному ТП-терму буде поставлена у відповідність функція, арність якої істотно
вважати арністю терму (при фіксованій інтерпретації).
Нарешті, для кожною терму t0 індукцією по його побудові визначимо, що таке
значення терму t0 при його деякій фіксованій інтерпретації . Нехай t0 – терм у
алфавіті A і його інтерпретація у деякій множині M. Тоді:
1) якщо терм t0 має найпростіший вигляд, тт. fi, де fi – функціональний символ,
то значення терму t0 при інтерпретації визначається, як Fi, де Fi – зна
- Київ+380960830922