Системи, керовані потоком даних. Мова Dataflow Graph Language.

Курсова робота Андрєєва М.В.

р. Ульяновськ, 1999

Вступ

Одним з методів організації паралельних обчислень є метод, заснований заснований на принципі управління потоком даних. Зазвичай в обчислювальних системах, керованих потоком даних, команди машинного рівня управляються доступністю даних, що проходять по дуг графа потоку даних (ГПД). Такому принципом керування потоком даних на рівні операцій можна протиставити принцип управління укрупнених потоком даних (Large-Grain Data Flow), в якому одиниця планування обчислень крупніше (можливо, набагато більше), ніж один машинна команда.

ГПД - одна з найбільш поширених форм представлення програми в даній моделі обчислень. Вершини ГПД відповідають окремим процесам, а дуги задають відносини між ними. Точка вершини, до якої входить дуга, називається вхідним портом (портом імпорту або входом), а точка, з якої вона виходить, - вихідним (портом експорту або виходом). За дуг передаються дані з одного процесу в інший.

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

Програмне забезпечення

Система призначена для роботи в мережі, в якій будь-які два комп'ютери можуть обмінюватися даними один з одним. На будь-якому комп'ютері може бути запушенно кілька процесів. Кожен процес отримує дані через порти імпорту і може отслать дані через порти експорту по дугах даних іншим процесам.

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

Порти імпорту використовуються як черги, і вони, подібно до каналах в ОС UNIX, буферизує одне або неколько повідомлень до тих пір, поки їх не отримає адресат. Обсяг буфера обмежений часточки доступною ємністю пам'яті. Кожен порт імпорту може бути пов'язаний з декількома портами експорту.

Порти експорту можуть мати кілька каналів, число яких визначається диспетчером після аналізу графа даних на етапі запуску процесу. Кожен канал обов'язково пов'язаний тільки з одним портом імпорту.

Підготовка прикладної програми до виконання состоіз з наступних кроків:

конструювання графа потоку даних програми

запис графа потоку даних на мові графів даних DGL

обробка запису на мові DGL

написання прикладних програм для вузлових процесів

компіляція вузлових процесів у формат DLL

запуск вузлових процесів диспетчером на основі DGL

Приклад паралельної програми

Як прикладу розглянемо задачу наближеного обчислення числа Пі з використанням правила прямокутників для обчислення певного інтеграла

де

Згідно правилом прямокутників,

де , а .

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

Існує безліч підходів до розв'язання контрольної задачі. Рішення, наведене нижче, ілюструє всі основні кроки розробки програми.

Конструювання графа потоку даних програми

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

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

Після того, як граф даних намальований, кожен процес, початок і кінець кожної дуги позначаються буквено-цифровим ім'ям, яке використовується в мові DGL. Якщо вихід out має кілька каналів, то його i-й канал позначається на схемі рядком out [i].

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

З входу num_iter процес Summer зчитує число часткових сум, які він повинен підсумувати до завершення своєї роботи. На вхід arg процесу Worker надходить завдання: кордони і число інтервалів. Якщо число інтервалів у завданні дорівнює нулю, то процес завершує роботу. Пересилаючи свій ідентифікатор через вихід demand робочий процес звертається за черговим завданням.

Запис графа потоку даних на мові Data Graph Language

Переклад графа потоку даних у мову DGL здійснюється однозначним чином. У записі на DGL кожен процес представлений заголовком і списком вхідних та вихідних портів. При описі процесу можна використовувати числові константи, які визначаються на початку програми. Ряд констант задається диспетчером - константа nprocs, наприклад, дорівнює числу доступних процесорів в системі. Синтаксис мови DGL наведено в додатку А.

11 DATAFLOW GRAPH Pi;

12

13 NW = nprocs - 2

14

15 PROCESS Manager

16 EXPORT:

17 worker [NW] -> Worker [c]: arg;

18 num_iter -> Summer: num_iter;

19 IMPORT:

20 demand_list;

21 END

22

23 PROCESS Worker [NW]

24 EXPORT:

25 demand -> Manager: demand_list;

26 result -> Summer: part_sum;

27 IMPORT:

28 arg;

29 END

30

31 PROCESS Summer

32 IMPORT:

33 num_iter;

34 part_sum;

35 END

Запис програми обчислення Пі мовою DGL

У рядку 13 визначається константа NW - число робочих процесів. Її значення вибирається так, щоб використовувати для вирішення задачі всі комп'ютери мережі.

У рядку 23 описується процес Worker. Константа NW, розташована в квадратних дужках після імені процесу, дає вказівку диспетчеру створити NW копій даного процесу. Причому, якщо значення NW менше 1, то все одно створюється одна копія. Всі копії нумеруються, номер копії записується в константу p, яка може бути використана при описі виходів процесу. Розглянемо приклад.

result