Реферат: Системы, управляемые потоком данных. Язык "Dataflow Graph Language"

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

Тема: Системы,управляемые потоком данных.

Язык Dataflow Graph Language.

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

Группа: ПМ-42

Научный руководитель: ДуловЕ.В.

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

[AK1] Введение

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

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

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

Программное обеспечение

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

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

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

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

Подготовка прикладной программы к выполнению состоизиз следующих шагов:

· конструирование графа потокаданных программы

· запись графа потока данныхна языке графов данных DGL

· обработка записи на языке DGL

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

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

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

Пример параллельной программы

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

где<img src="/cache/referats/11338/image004.gif" v:shapes="_x0000_i1026">

Согласноправилу прямоугольников,

где<img src="/cache/referats/11338/image008.gif" v:shapes="_x0000_i1028">, а <img src="/cache/referats/11338/image010.gif" v:shapes="_x0000_i1029">

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

Существует множество подходов к решению контрольнойзадачи. Решение, приведенное ниже, иллюстрирует все основные шаги разработкипрограммы.

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

Граф потокаданных программы(или граф данных) определяет связимежду процессами и дугами данных. Граф данных специфицирует все последуещееконструирование программы прикладной задачи. Его создание может потребоватьнемало усилий для определения того, как разбить программу на активизируемыеданными процессы, чтобы достичь максимального увеличения скорости выполнения.

В пределе разрабатываемая программа может бытьсоздана в виде одного процесса, но при этом теряется параллелелизм. Можносоздать множество мелких процессов, таких как один оператор или даже однаарифметическая операция, что приведет к резкому увеличению расходов, связанныхс запуском каждого процесса и обменом данных между ними. Следует отметить, что структура решаемойзадачи часто наводит на хорошее первое приближение.

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

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

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

Записьграфа потока данных на языке Data Graph Language

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

11 DATAFLOWGRAPH Pi;

13 NW = nprocs — 2

15 PROCESSManager

16 EXPORT:

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

18 num_iter --> Summer:num_iter;

19 IMPORT:

20 demand_list;

21 END

23 PROCESSWorker [NW]

24 EXPORT:

25 demand --> Manager:demand_list;

26 result --> Summer:part_sum;

27 IMPORT:

28 arg;

29 END

31 PROCESSSummer

32 IMPORT:

33 num_iter;

34 part_sum;

<img src="/cache/referats/11338/image013.gif" v:shapes="_x0000_s1029">35END

Записьпрограммы вычисления Пи на языке 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 FUNCTIONf(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 := 1TO 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}