Системи, керовані потоком даних. Мова 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 à filter [2 * p +1]: arg
Даний запис означає, що вихід result р-ї копії процесу буде пов'язаний зі входом arg (2р +1)-й копії процесу filter.
Запис у рядку 17 означає, що вихід worker процесу Manager буде мати NW каналів. Причому, якщо значення NW менше 1, то все одно буде створено один канал. Всі канали нумеруються, номер каналу записується в константу С. У прикладі С-й канал виходу worker пов'язаний зі входом arg С-ої копії процесу Worker.
Написання тіла для кожного процесу
Для кожного процесу нунжно створити файл-шаблон. Ім'я такого файлу збігається з ім'ям процесу та має розширення frm (можна скористатися файлом Process.frm). У нашому випадку маємо три файли: Manager.frm, Worker.frm і Summer.frm. У кожному файлі є процедура, ім'я якої закінчується на Body. Всередині неї записується тіло процесу.
10 PROCEDURE ManagerBody;
11 VAR
12 Task: RECORD N: cardinal; a, b: real; END;
13 i, WrkId: cardinal;
14 CONST
15 N: cardinal = 10;
16 BEGIN
17 exportNumIter [0]. Send (N, SizeOf (N));
18 Task.N: = 10 * N;
19 Task.b: = 0;
20 FOR i: = 1 TO N DO BEGIN
21 Task.a: = Task.b;
22 Task.b: = i * 1.0 / N;
23 importDemandList.Receive (WrkId, SizeOf (WrkId));
24 exportWorker [WrkId]. Send (Task, SizeOf (Task));
25 END;
26 Task.N: = 0;
27 FOR i: = 1 TO exportWorker.NChannels DO
28 exportWorker [i-1]. Send (Task, SizeOf (Task));
29 END;
Файл Manager.frm: тіло процесу Manager
Змінна Task описує завдання для робочого процесу: a, b - межі, N - число інтервалів. Константа N, описана в рядку 15, дорівнює числу розбиття відрізка [0; 1].
На початку роботи посилаємо процесу Summer число розбиття N (рядок 17). У рядку 23 чекаємо запиту від одного з робочих процесів. Запит є ідентифікатор запитуючої процесу. Отримавши запит, відсилаємо чергове завдання відповідному робочому (рядок 24).
Після того, як завдання розподілені, потрібно повідомити про це всім робочим процесам. Для цього служать рядки 26-28: по всіх каналах порту exportWorker посилаємо завдання з нульовим числом інтервалів - сигнал про завершення роботи.
30 PROCEDURE WorkerBody;
31 VAR
32 Task: RECORD N: word; a, b: real; END;
33 S: real;
34 i: word;
35 FUNCTION f (x: real): real;
36 BEGIN
37 Result: = 4 / (1 + x * x);
38 END;
39 BEGIN
40 exportDemand [0]. Send (FloLib.CopyNumber, SizeOf (cardinal));
41 WHILE (true) DO WITH Task DO BEGIN
42 importArg.Receive (Task, SizeOf (Task));
43 IF (Task.N = 0) THEN EXIT;
44 h: = (ba) / N;
45 S: = 0;
46 FOR i: = 1 TO N DO
47 S: = S + f (a + (i-0.5) * h);
48 S: = h * S;
49 exportPartSum [0]. Send (S, SizeOf (S));
50 exportDemand [0]. Send (FloLib.CopyNumber, SizeOf (cardinal));
51 END;
52 END;
Файл Worker.frm: тіло процесу Worker
Нескінченний цикл 41-51 забезпечує роботу процесу до отримання сигналу завершення від розподільника робіт Manager.
У рядку 42 чекаємо чергове завдання Task. Якщо число інтервалів у завданні дорівнює 0, то завершуємо роботу. В іншому випадку обчислюємо часткову суму на інтервалі (Task.a; Task.b) і відсилаємо її суммирующем процесу (рядки 44-49). У рядку 50 звертаємося до розподільника робіт за черговим завданням.
53 PROCEDURE SummerBody;
54 VAR
55 N, i: cardinal;
56 F: TextFile;
57 TotalSum, S: real;
58 BEGIN
59 importNumIter.Receive (N, SizeOf (N));
60 TotalSum: = 0;
61 FOR i: = 1 TO N DO BEGIN
62 importPartSum.Receive (S, SizeOf (S));
63 TotalSum: = TotalSum + S;
64 END;
65 AssignFile (F, 'Pi.result');
66 Rewrite (F);
67 WriteLn (F, 'Pi =', TotalSum);
68 CloseFile (F);
69 END;
Файл Summer.frm: тіло процесу Summer
У рядках 61-64 збираються часткові суми від всіх робочих процесів і сумуються у змінній TotalSum. Число часткових сум записується в змінну N з порту importNumIter (рядок 59).
Компіляція вузлових процесів
Після того, як створені шаблони, потрібно отримати з них файли, придатні для компіляції. Для цього використовується компілятор з мови DGL:
dglc Pi.dgl
Компілятор, якщо немає помилок, згенерує наступні файли: Pi.dpr, Manager.pas, Worker.pas, Summer.pas.
Завантаження і виконання програми
Спочатку на комп'ютерах мережі потрібно запустити програму-монітор. Перепишемо откомпіліроанние файли і файл Pi.dgl з текстом графа потоку даних на мові DGL в один каталог і запустимо диспетчер, вказавши Pi.dgl як параметр. Після закінчення роботи диспетчера повинен з'явиться файл Pi.result, в якому записано наближене значення числа Pi.
Додаток А
Синтаксис мови DGL
DGL = ["DATAFLOW GRAPH" [identifier] ";"]
{Definitions}
{ProcessDecl}
Definitions = identifier "=" ConstExpr
ProcessDecl = "PROCESS" identifier ["AT" path]
["[" NumCopies "]"]
{"EXPORT:" {ExportDecl} |
"IMPORT:" {ImportDecl}
}
"END"
ExportDecl = identifier ["[" NumCopies "]"]
"-->"
identifier ["[" Exdivssion "]"]
":"
identifier ";"
ImportDecl = identifier ";"
NumCopies = ConstExpr
ConstExpr = Exdivssion
Exdivssion = Term [AddOp Term]
Term = Fact [MulOp Fact]
Fact = number | identifier | "(" Exdivssion ")"
AddOp = "+" | "-"
MulOp = "*" | "/"
Зауваження:
number - ціле позитивне число
всі операції мови цілочисельні
значення виразу NumCopies повинно бути більше нуля, в іншому випадку воно замінюється на число 1
у виразах можна використовувати наступні змінні: с - номер поточного каналу, р - номер поточної копії процесу
Список літератури
[1] Роберт Беб, «Програмування на паралельних обчислювальних системах» - Москва: Світ, 1991
[2] А. І. Водяхо, «Високопродуктивні системи обробки даних» - Москва: Вища школа, 1997