Машини, керовані потоком даних відносяться до класу dataflow architecture. Реалізація dataflow моделі обчислень може привести до найвищого ступеня паралелізму, так як в ній використовується альтернативний принцип управління - управління потоком даних, яка не накладає додаткових обмежень, властивих рас смотреніі вище командним принципом управління.
В обчислювальних системах, керованих потоками даних, машинах потоків даних відсутнє поняття програми як послідовності команд, а отже, відсутнє поняття стану процесу. Кожна інструкція передається на виконання, як тільки створюються умови для її реалізації. При наявності достатніх апаратних засобів одночасно може оброблятися довільне число готових до виконання інструкцій. У dataflow паралелізм не ставить явно, і апаратні засоби обробки повинні його виділяти на етапі виконання. Однак слід зазначити, що реалізація принципу управління потоком даних викликає ряд труднощів, частина з яких носить принциповий характер. До їх числа необхідно віднести громіздкість програми, труднощі обробки ітераційних циклів, труднощі роботи зі структурами даних.
Суть ідеї dataflow моделі в тому, що програма представляється графом потоку даних, приклад якого показаний на рис. 9.13.
Інструкцій на графі відповідають вершини, а дуги, позначені стрілками, вказують на відносини передування. Точка вершини, до якої входить дуга, називається вхідним портом (або входом), а точка, з якої вона виходить, вихідним. За дуг передаються мітки, звані токенами даних (token) Спрацювання вершини означає виконання інструкції. При цьому спрацьовування відбувається в довільний момент часу при виконанні умов, відповідних правилу запуску. Зазвичай використовується суворе правило запуску, згідно з яким спрацьовування вершини відбувається при наявності хоча б по одному токен у всіх її вхідних портах. Спрацювання вершини супроводжується видаленням одного токена з кожного вхідного порту і розміщенням не більше одного токена результату операції в вихідні порти. Залежно від конкретної архітектури системи порти можуть зберігати один або кілька токенов, причому вони можуть використовуватися за правилом FIFO або в довільному порядку.
Мал. 9.13. Граф потоку даних і структура потокових машин
Граф може бути поширений на довільну сукупність процесорів. У пре окремому випадку процесор в машині, керованої потоком даних, може виконувати операції як окремий кругової поплайн, як показано на рис. 9.13.
Всі архітектури машин, керованих потоком даних, з точки зору механізмів організації повторної входимость, прийнято ділити на статичні і динамічні. Іншими словами, в них використовується або статичний граф потоку даних, де кожна вершина представлена примітивної операцією, або динамічний граф, в якому вершина може бути представлена викликом довільної функції, яка сама може бути представлена графом. У динамічних архитектурах ефект динамічно розвивається графа на функцію, що викликається зазвичай досягається появою додаткового інформаційного контексту в тезі.
Було створено кілька машин, керованих потоком даних, як зі статичної, так і з динамічної архітектурою. Найбільш відомими є мультипроцессор Дениса (Массачусетський технологічний інститут), система DDP і LAU (дослідний центр СЕRТ), досить докладно описані в літературі.
Розробники систолических архітектур ставили перед собою завдання отримати систему, яка поєднувала б гідності конвеєрної і матричних обробок. Спочатку систолические архітектури розроблялися для вузькоспеціалізованих ви числівників систем. Однак в подальшому були знайдені відповідні алгоритми для досить широкого класу задач, що дозволяють реалізувати принципи систолічною обробки.
Основний принцип систолічною обробки полягає в тому, щоб виконати всі стадії обробки кожного елемента даних, витягнутого з пам'яті, перш ніж знову помістити в пам'ять результат цієї обробки. Цей принцип реалізується систолічною матрицею процесорних елементів, в якій окремі процесорні елементи об'єднані між собою прямими і регулярними зв'язками, що утворюють конвеєр. Таким чином, може формуватися кілька потоків операндів, кожен з яких утворений вихідними операндами (елементами структури даних, що зберігається в пам'яті), проміжними результатами, отриманими при виконанні елементарних операцій в кожному процесорному елементі, і елементами результуючої структури. За струми даних синхронізовані єдиної для всіх процесорних елементів системою тактових сигналів. Під час тактового інтервалу всі елементи виконують коротку незмінну послідовність команд (або одну команду).
Мал. 914 ілюструє систолическую систему для обчислення "згортки функції", що використовує просту лінійну область. Під час тактового інтервалу вхідні дані просуваються вправо, множаться на локальний вага і акумулюються на виході в порядку проходження.
Мал. 9.14. Приклад побудови систолічною структури
Систолічний архітектури володіють наступними перевагами:
• мінімізуються звернення до пам'яті, що дозволяє узгодити швидкість роботи пам'яті зі швидкістю обробки;
• спрощується рішення проблем введення / виведення внаслідок зменшення конфліктів при зверненні до пам'яті;
• ефективно використовуються технологічні можливості НВІС за рахунок регулярності структури систолічною матриці.
Однак для реалізації цих переваг необхідно знайти для кожного завдання з- Відповідаю систолические алгоритми, які можуть бути реалізовані на систолічною структурі системи. Такі алгоритми існують сьогодні для широкого кола завдань, серед яких завдання числової обробки, обробки сигналів і символів; множення і звернення матриць, рішення лінійних систем, дискретне перетворення Фур'є, кодування і декодування числових послідовностей і т. д. Більшість цих алгоритмів зводиться до рекурентних співвідношень того чи іншого виду. Залежно від виду систолічного алгоритму, т. Е. Числа операндів, що беруть участь в примітивних операціях, типу цих елементарних операцій, М-послідовності їх виконання вибираються тип процесорного елемента та структура локальних регулярних зв'язків між ними. До типових конфігурацій систолических матриць відносяться: лінійна (рис. 9.14), для реалізації алгоритмів фільтрації при обробці сигналів, порівняння ланцюжків літер при обробці баз даних; прямокутна, множення матриць, знаходження двомірних ДПФ; і гексагональна, для виконання операцій про рощення матриць, рішення лінійних систем рівнянь і т. д.
Однак не всі алгоритми можуть бути зведені до систолическим, і в багатьох випадках доводиться відмовлятися від алгоритмів з меншою складністю на користь більш складних, але регулярних алгоритмів, що відповідають вимогам систолічною обробки.