СРС №17 Архітектура потокових обчислювальних систем

       Існують труднощі, пов’язані з розв’язанням проблем автоматизації паралельного програмування, необхідного для забезпечення ефективного використання для широкого кола задач матричних (паралельних) ОС, тобто систем типу SIMD (ОКМД).
       Конвеєрні і конвеєрно-векторні  обчислювальні системи (ОС) найбільший ефект дають під час реалізації спеціалізованих систем з фіксованими алгоритмами, за яких  досягається оптимальна структура для задачі, яка розв’язується. В ОС універсального призначення склад позицій конвеєра є далеко не оптимальним  для кожної даної задачі, до того ж виникають витрати часу на комутацію позицій конвеєра під поточну команду.
      В таких умовах актуальними є дослідження нових шляхів побудови високопродуктивних ОС, одними з яких є ОС з управлінням потоком даних (операндів), або, іншими словами, потокові обчислювальні системи.

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

В усіх раніше розглянутих ЕОМ і обчислювальних системах порядок  виконання операцій над даними у ході розв’язання задачі суворо детермінований, він однозначно визначається послідовністю команд програми.

Детермінованість (determanancy) — властивість алгоритму, яка передбачає, що в ньому усі вказівки повинні бути чіткими й однозначними: значення величин, які отримуються в конкретний момент часу, повинні визначатися значеннями величин, отриманими в попередні моменти часу.

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

Розглянемо як приклад обчислення на потоковій ОС коренів квадратного рівняння:

Будемо вважати, що на вхід системи надходить група даних ai, bi, ci і за ними обчислюються корені рівняння. Розв’язання може бути отримане за допомогою операційних пристроїв, які виконують операції додавання, віднімання, множення, піднесення до степеня, ділення і вирахування квадратного кореня.
Процес розв’язання можна подати у такій послідовності:

У потокових обчислювальних моделях для описання обчислень використовують орієнтований граф, у якому вершини відображають операції, а дуги показують потоки даних між вершинами графа, які вони з’єднують На рисунку показаний граф потоку даних, які управляють розв’язанням задачі, що розглядається. Великими кружками показані операційні пристрої, а маленькими – мітки готовності даних. У початковому стані процесу готові всі вхідні дані.

Граф — це сукупність об’єктів із зв’язками між ними.
Об’єкти розглядаються як вершини, або вузли графу, а зв’язки — як дуги, або ребра. Для різних галузей види графів можуть відрізнятися орієнтованістю, обмеженнями на кількість зв’язків і додатковими даними про вершини або ребра.
Орієнтований граф (коротко орграф) — (мульти) граф, ребрам якого присвоєно напрямок.

Вершина графа активізується в довільному порядку у разі готовності їх операндів. Можна вважати, що активізація вершини супроводжується поглинанням міток готовності на їх входах. По закінченні операції міткою готовності позначається вихідна дуга вершини. Переміщення міток за графом потоку даних відображає проходження обчислювального процесу.

Граф потоків операндів


Контрольні питання:
  1. Що собою представляють системи з управлінням потоками даних (потокові ОС) ? Які задачі вони вирішують?
  2. У чому полягає принципова відмінність потокових машин ?
  3.  Що використовують для описання обчислень  в потокових обчислювальних моделях ?