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

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.


Нажми чтобы узнать.
скачати

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

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

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

Введення

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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;

Системи, керовані потоком даних. Мова Dataflow Graph Language. 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. Всередині неї записується тіло процесу.

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

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;

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

Файл Manager.frm: тіло процесу Manager

Змінна Task описує завдання для робочого процесу: a, b - межі, N - число інтервалів. Константа N, описана в рядку 15, дорівнює числу розбиття відрізка [0; 1].

На початку роботи посилаємо процесу Summer число розбиття N (рядок 17). У рядку 23 чекаємо запиту від одного з робочих процесів. Запит є ідентифікатор запитуючої процесу. Отримавши запит, відсилаємо чергове завдання відповідному робочому (рядок 24).

Після того, як завдання розподілені, потрібно повідомити про це всім робочим процесам. Для цього служать рядки 26-28: по всіх каналах порту exportWorker посилаємо завдання з нульовим числом інтервалів - сигнал про завершення роботи.

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

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;

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

Файл Worker.frm: тіло процесу Worker

Нескінченний цикл 41-51 забезпечує роботу процесу до отримання сигналу завершення від розподільника робіт Manager.

У рядку 42 чекаємо чергове завдання Task. Якщо число інтервалів у завданні дорівнює 0, то завершуємо роботу. В іншому випадку обчислюємо часткову суму на інтервалі (Task.a; Task.b) і відсилаємо її суммирующем процесу (рядки 44-49). У рядку 50 звертаємося до розподільника робіт за черговим завданням.

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

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;

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

Файл 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

Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Реферат
25.4кб. | скачати


Схожі роботи:
Некеровані і керовані випрямлячі
Редактор чисельних діаграм Microsoft Graph
Модуль Graph у програмі Turbo Pascal
English language for technical colleges
MathML Mathematical Markup Language
Вхідна мова системи MathCAD 7 0
Структура мови SQL Structured Query Language
Системи управління базами даних
Системи мережі передачі даних
© Усі права захищені
написати до нас
Рейтинг@Mail.ru