Курсовая: Системы, управляемые потоком данных. Язык "Dataflow Graph Language" - текст курсовой. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Курсовая

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

Банк рефератов / Компьютерные сети

Рубрики  Рубрики реферат банка

закрыть
Категория: Курсовая работа
Язык курсовой: Русский
Дата добавления:   
 
Скачать
Архив Zip, 33 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникальной курсовой работы

Узнайте стоимость написания уникальной работы

8 Курсовая работа Тема : Системы , управляемые потоком данных. Язык Dataflow Graph Language . Автор : Андреев М.В. Группа : ПМ -42 Научный руководитель : Дулов Е.В. г . Ульяновск , 1999 Введение Одним из мето дов организации параллельных вычислений явл яется метод , основанный основанный на принцип е управления потоком данных . Обычно в вычи слительных системах , управляемых потоком данных , команды машинного уровня управляются доступнос тью данных , проходящих по ду гам графа потока данных (ГПД ) . Т акому принципу управления потоком данных на уровне операций можно противоп оставить принцип управления укрупненным потоком данных ( Large - Grain Data Flow ), в котором единица планирования вычислений крупнее (возмож но , намного крупнее ), чем одна машинная ком ан да . ГПД - одна из наиболее распространенных форм представления программы в данной моде ли вычислений . Вершины ГПД соответствуют отде льным процессам , а дуги задают отношения м ежду ними . Точка вершины , в которую входит дуга , называется входным по ртом ( порто м импорта или входом ), а точка , из ко торой она выходит , - выходным ( портом экспорта или выходом ). По дугам передаются данные из одного процесса в другой. Данный метод заставляет программиста прин ять поэтапный подход к программированию , но , с другой сторон ы , избавляет от слож ностей синхронизации , присущих большенству других моделей параллелизма. Программное обеспечение Система предназна чена для работы в сети , в которой любы е два компьютера могут обмениваться данными друг с другом . На любом компьютере мо же т быть запушенно несколько процессов . Каждый процесс получает данные через порты импорта и может отслать данные через порты экспорта по дугам данных другим процессам. Запуск программы осуществляется под управ лением диспетчера , который распределяет процесс ы по компьютерам и устанавливает связи между пр оцессами . Для нормальной работы диспетчера на всех компьютерах должна быть запущена сп ециальная программа - монитор . Монитор по запросу диспетчера запускает процесс , указанный в запросе , на своем компьютере. Порты импорта используются как очереди , и они , подобно каналам в ОС UNIX , буферизуют од но или неколько сообщений до тех пор , пока их не получит адресат . Объем буфера ограничен долько доступной емкостью памяти . Каждый порт импорта может быть связан с нескол ькими портами экспорта. Порты экспорта могут иметь несколько каналов , число которых определяется диспетчером после анализа графа данных на этапе за пуска процесса . Каждый канал обязательно связ ан только с одним портом импорта. Подготовка прикладной прог раммы к выполнению состоиз из следующих шагов : · конструирование графа п отока данных программы · запись графа потока данных на языке графов данных DGL · обработка записи на языке DGL · написание прикладных пр ограмм для узловых процессов · компиляция у зловых процессов в формат DLL · запуск узловых процессо в диспетчером на основе DGL Пример параллел ьной программы В качестве пр имера расмотрим задачу приближенного вычисления числа Пи с использованием правила прямоу гольников для вычисления определенного инте грала где Согласно правилу прямоугольников, где , а . Следует отметить , что это «процессорная» программа . Она не затрагивает многие проблемы параллельного пр ограммирования , например критическое влияние проц ессов ввода-вывода . Тем не менее эта задач а поможет ознакомится с основными принц ипами построения программ , работающих в соотв етствии с методом управления потоком данных. Существует множество подходов к решению контрольной задачи . Решение , приведенное ниже , иллюстрирует все основные шаги разработки программы. Констру ирование графа пот ока данных программы Граф потока данных программы (или граф данных ) определяет связи между процессами и дугами данных . Граф данных специфицирует все последуещее конструирование программы прикладной задачи . Его создание м ожет потребовать немало усилий для опре деления того , как разбить программу на акт ивизируемые данными процессы , чтобы достичь м аксимального увеличения скорости выполнения. В пределе разрабатываемая программа может быть создана в виде одного процесса , но при этом теряется п араллелелизм . Мо жно создать множество мелких процессов , таких как один оператор или даже одна ариф метическая операция , что приведет к резкому увеличению расходов , связанных с запуском к аждого процесса и обменом данных между ни ми . Следует отметить , что ст р уктур а решаемой задачи часто наводит на хороше е первое приближение. После того , как граф данных нарисован , каждый процесс , начало и конец каждой дуги помечаются буквенно-цифровым именем , котор ое используется в языке DGL . Если выход out имеет несколько кан алов , то его i -й канал обозначается на схеме строкой out [ i ]. Для подсчета числа Пи используется несколько рабочих проце ссов , которые вычисляют свои части интеграла и пересылают результат суммирующему процессу . Рабочие процессы обращаются за очередн ым заданием к процессу распределения работ . Вся работа не распределяется заранее равно мерно между процессами : один рабочий процесс , если он запущен на более быстрой маш ине , может выполнить львиную долю работы. Из входа num _ it er процесс 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 --> Summ er :part_sum; 27 IMPORT: 28 arg; 29 END 30 31 PROCESS Summ er 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 . После обработки графа программ ой dglc , на диске будут созданы следующие файлы : Manager . dpr , Worker . dpr , Summer . dpr , ManagerUnit . pas , WorkerUnit . pas , SummerUnit . pas . Очередная задача состоит в написании прикладных за дач для всех узловых про цессов . Для этого нужно создать файлы ManagerBody . pas , WorkerBody . pas , SummerBody . pas . Написание тела для каждого процесса Каждый процесс записывается в виде процедуры на языке Паскаль . Имя процедуры - Body - фиксировано и не мож ет быть изменено . Имя файла программы начинается с имени процесса и заканчивается словом Body . 10 PROCEDURE Body; 11 VAR 12 Task : RECORD N:word; a,b:real; END; 13 i,WrkId : word; 14 CONST 15 N : word = 10; 16 BEGIN 17 Send (exp ortNUM_ITER, 0, N, SizeOf(word)); 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/N; 23 Receive (importDEMAND_LIST, WrkId, SizeOf(word)); 24 Send (exportWORKER, WrkId, T ask, SizeOf(Task)); 25 END; 26 Task.N := 0; 27 FOR i := 1 TO exportWORKER.NChannels DO 28 Send (exportWORKER, i, Task, SizeOf(Task)); 29 END; Файл ManagerBody.pas : тело процесса Manager Переменная Task описыв ает задание для рабоче го процесса : a , b - границы, N - число интерва лов . Константа N , описанная в строке 15, равна числу разбиений отрезка [0;1] . В начале работы посылаем процессу Summer число р азбиений N (строка 17) . В строке 23 ждем запроса от одно го из рабочих процессов . З апрос предст авляет собой идентификатор запрашивающего процес са . Получив запрос , отсылаем очередное задание соответствующему рабочему (строка 24). После того , как задания распределены , нужно сообщить об этом всем рабочим проце ссам . Для этого служат строки 26-28: по всем каналам порта expWORKER посылаем задание с нулевым числом интервалов - сигнал о завершении рабо ты. 30 PROCEDURE Body; 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 Send (exportDEMAND, 0, GetProcessId, SizeOf(TProcessId)); 41 WHILE (true) DO WITH Task DO BEGIN 42 Receive (importARG, Task, SizeOf(Task)); 43 IF (Task.N = 0) THEN EX IT; 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 Send (exportPART_SUM, 0, S, SizeOf(S)); 50 Send (exportDEMAND, 0, GetProcessId, SizeOf(TProcessId)); 51 END; 52 END; Файл WorkerBody.pas : тело процесса Worker Бесконечный цикл 41-51 обеспечивает работу процесса до получения сигнала завер шения от распределителя работ Manager . В строке 42 ждем очередное задание Task . Если число интервалов в задании ра вно 0, то завершаем работу . В противном случае вычисляем частичную сумму на интерв але ( Task . a ; Task . b ) и отсылаем ее сумми рующему процессу (строки 44-49). В строке 50 обращаемс я к распределителю работ за очередным зад анием. 53 PROCEDURE Body ; 54 VAR 55 N : word; 56 i : word; 57 TotalSum, S : real; 58 BEGIN 59 Receive (importNUM_ITER, N, SizeOf(N)); 60 TotalSum := 0; 61 FOR i := 1 TO N DO BEGIN 62 Receive (importPART_SUM, S, SizeOf(S)); 63 TotalSum := TotalSum + S; 64 END; 65 END; Файл SummerBody.pas : тело процесса Summer В строках 61-64 собираются частичн ые суммы от всех рабочих процессов и суммируются в переменной TotalSum . Число частичных сумм записываем в переменну N из порта impNUM _ ITER (строка 59). Компиляция узловых процессов В среде Delphi необх одимо откомпилировать файлы Manager . dpr , Worker . dpr и Summer . dpr . После компиляции должны появитс я три новых файла : Manager . dll , Worker . dll , Summer . dll . Загрузка и выполнение програм мы Сначала на комп ьютерах сети нужно запустить программу-монитор . Перепиш ем откомпилироанные файлы и файл Pi . dgl с текстом графа потока данных на языке DGL в один каталог и запустим диспетчер , указав Pi . dgl в качестве параметра. Литература [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) все операции языка целочисленные 3) значение выражения NumCopies должно быть больше нуля , в противном случае он о заменяется на число 1 4) в выражениях можно использовать следующие переменные : с - номер текущего канала , р - номер текущей копии пр оцесса
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Настоящая подруга — это не та, что ползёт рядом, а та, что тащит тебя пьяную домой!
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, курсовая по компьютерным сетям "Системы, управляемые потоком данных. Язык "Dataflow Graph Language"", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru