Курсова робота

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

Автор: Андреєв М.В.

Група: ПМ-42

Науковий керівник: Дулов Е.В.

р. Ульяновськ, 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: = (b-a)/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.

Література

[1] Роберт Беб, «Програмування на паралельних обчислювальних системах»
- Москва: Мир, 1991
[2] А. И. Водяхо, «Високопродуктивні системи обробки даних» -
Москва: Вища школа, 1997
Додаток А

Синтаксис мови 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 [ "[" Expression "]"]

":" identifier ";"

ImportDecl = identifier ";"

NumCopies = ConstExpr

ConstExpr = Expression

Expression = Term [AddOp Term]

Term = Fact [MulOp Fact]

Fact = number | identifier | "(" Expression ")"

AddOp = "+" | "-"

MulOp = "*" | "/"

Зауваження:

1) number - ціле позитивне число
2) всі операції мови цілочисельнізначення виразу NumCopies має бути більше нуля, у противному випадкувоно замінюється на число 1у виразах можна використовувати наступні змінні: с - номер поточногоканалу, р - номер цієї копії процесу