Содержание:
1.Введение…………………………………………………………………………………………….3
2.Теоретическийраздел………………………………………………………………………………6
2.1. Принцип действия машин потоков данных…………………………………………….6
2.2. Язык потоков данных…………………………………………………………………….9
2.3. Машина потоков данных………………………………………………………………..13
2.4. Сети трактов передачи пакетов…………………………………………………………16
2.5. Переполнение и тупиковые ситуации………………………………………………….20
2.6. Обработка структур данных…………………………………………………………….23
3.Практическаячасть…………………………………………………………………………………28
3.1. Постановка и реализация задачи……………………………………………………...28
3.2. Реализация программы на машине потоков данных…………………………………..30
3.3. Принцип работы устройства…………………………………………………………….32
3.4. Спецификация элементов………………………………………………………………..36
4.Заключение………………………………………………………………………………………….38
Списоклитературы…………………………………………………………………………………...40
5.Приложения…………………………………………………………………………………………41
ВСГТУ 622-1
Изм.
Лист
№ докум.
Подп.
Дата
Разраб.
Проверил
Литер.
Лист
Листов
Н.контр
Утв.
Д 630.1.05.00.039.ПЗ
ВВЕДЕНИЕ
1. Введение
Изм
Лист
№докум
Подпись.
Дата
Лист
4
Д 630.1.05.00.039.ПЗ
Первая причина – отсутствиедостаточной вычислительной мощности – является значительным препятствием дляприменения машин при решении важных проблем. Хотя в наши дни ЭВМ с успехомприменяют для экономических расчетов (подготовка платежных ведомостей, начислениестраховых премий, бухгалтерский учет, ведение расчетов по кредитным карточкам),вычислительные машины плохо приспособлены для решения задач в области созданияискусственного интеллекта, распознавание образов, обработки речевой информации,прогнозирование погоды, проектирование аэродинамических конструкций, перевода содного иностранного языка на другой, сейсмического анализа и многих других.
Традиционным решением задачи увеличения мощности системы (после того какпроизводительность единственного процессора доведена до максимального значения) являетсяиспользование нескольких процессоров. Однако такой подход не являетсяудовлетворительным в силу действия следующих обстоятельств. Во-первых, возникают проблемыпрограммирования, обусловленные необходимостью для программиста «подгонять»структуру данных и программ под жесткую структуру многопроцессорной илираспределенной вычислительной системы. Например, при работе с системой,содержащей 16 процессоров, программисту приходиться разбивать свою программу на16 или более параллельных процессов. Задача далеко не тривиальная, исовременные языки программирования, средства обслуживания и отладки едва лимогут здесь оказать какую-либо существенную помощь.
Во-вторых, в традиционныхмультипроцессорных системах в режиме разделения памяти между процессорамивозможны наложения обращений к памяти – так называемая интерференция обращения к памяти. Поскольку каждый отдельныйпроцессор стремится захватить определенную часть памяти, подключение новыхпроцессоров к памяти, уже разделяемой другими процессорами, может дать толькоограниченную выгоду.
Интерференция обращения к памяти может быть уменьшена, если каждыйпроцессор снабдить локальным кэш-буфером (кэш-памятью). Однако при этомвозникает другая проблема: некоторая ячейка памяти может оказаться привязаннойк нескольким кэш-буферам, т.е. операция записи одного процессора может повлечьза собой искажение информации в кэш-буферах других процессоров. Таким образом,хотя мультипроцессорные системы имеют определенные достоинства, повышая степеньготовности системы для решения различных задач, они все же уступаютоднопроцессорным аналогам по такому критерию, как отношение стоимости кпроизводительности.
Изм
Лист
№докум
Подпись.
Дата
Лист
5
Д 630.1.05.00.039.ПЗ Второй причиной появления машин потоковданных является недостатки, присущие самой природе современных языковпрограммирования, и осознание того факта, что эти языки отражают в своейструктуре основополагающие принципы архитектуры машин фон Неймана. Так жевнутренняя организация современных машин предполагает использование пассивнойпамяти, процессора, выполняющего операции по изменению содержимого памяти, иустройства управления, воздействующего на процессор с помощью потока следующиходна за другой команд. Понятие «переменная» в языке программирования адекватнопонятию «область пассивной памяти» в машине, понятие «передача управления» вязыке (реализуемая, например, операторами GOTO, IF, DO, CALL) отражает устройство управления исчетчик команд в машине фон Неймана. Подобным же образом понятие «присваивание»является отображением определенной операции процессора (изменение содержимогообласти памяти машины). Использование потока данных для управления машинойпозволило сделать выводы, с которыми согласились и специалисты в области теорииязыков
Третьей причиной появлениямашин потоков данных является осознание того фактора, что тракт,соединяющий процессор с памятью, является тем самым «узким местом», которое восновном и ограничивает эффективность системы. В современных вычислительныхсистемах назначение программы заключается в изменении содержимого памяти, предоставляемой дляданных этой программы. Достигается это путем «проталкивания» одиночных команд иданных через узкую магистраль, связывающую память и процессор.
Быстрое развитие компьютерной индустрииопределяет относительность понятия суперЭВМ — то, что десять лет назад можнобыло назвать суперкомпьютером, сегодня под это определение уже не попадает.Например, производительность персональных компьютеров Pentium-3/500MHz,сравнима с производительностью суперкомпьютеров начала 70-х годов, однако посегодняшним меркам суперкомпьютерами не являются ни те, ни другие.
В любом компьютере все основные параметрытесно связаны. Трудно себе представить универсальный компьютер, имеющий высокоебыстродействие и мизерную оперативную память, либо огромную оперативную памятьи небольшой объем дисков. Следуя логике, делаем вывод: суперЭВМ это компьютеры,имеющие в настоящее время не только максимальную производительность, но имаксимальный объем оперативной и дисковой памяти (вопрос о специализированномПО, с помощью которого можно эффективно всем этим воспользоваться, пока оставимв стороне).
Так о чем же речь, и какиесуперкомпьютеры существуют в настоящее время в мире? Вот лишь несколькопараметров, дающих достаточно красноречивую характеристику машин этого класса.Компьютер ASCI WHITE, занимающий первое место в списке пятисот самых мощныхкомпьютеров мира, объединяет 8192 процессора Power 3 с общей оперативнойпамятью в 4 терабайта и производительностью более 12 триллионов операций всекунду.
ВСГТУ 622-1
Изм.
Лист
№ докум.
Подп.
Дата
Разраб.
Проверил
Литер.
Лист
Листов
Н.контр
Утв.
Д 630.1.05.00.039.ПЗ
ПРИНЦИП ДЕЙСТВИЯ МАШИН ПОТОКОВ ДАННЫХ
2.1. Принцип действия машин потоков данных
Изм
Лист
№докум
Подпись.
Дата
Лист
7
Д 630.1.05.00.039.ПЗ данныеперемещаются из команды в команду по мере выполнения программы.
Кроме того, в данном случае не используются понятия «передача управления», «счетчик команд» и«ветвление вычислительного процесса». Вместо этого команды (операторы)управляются данными. Считается, что команда готова к управлению (т. е. Еевыполнение разрешено), если данные присутствуют в каждом из ее входных портов иотсутствуют в выходном порте. Выполнение команды приводит к исчезновению данныхв ее входных портах и появлению результата в выходном порте. Программа представляет собой направленный граф, образованныйсоединенными между собой командами: выходной порт одной команды соединен свходным портом другой команды. Такимобразом, порядок выполнения команды определяется не счетчиком команд, адвижением потока данных в командах.
Указанные принципы выполнения команд иллюстрируют рис. 1. здесьокружности обозначают команды,стрелки – линии связи междукомандами, а зачерненные круги – данные.
Ор
Ор
Ор
Ор
Ор Команды не готовы к выполнению
Команда готова к выполнению
Результат выполнения
Рис. 1. Возможные состояния команд в машине потоков данных.
Первые три команды показаныв состоянии запрета на выполнение. У первой команды нет входных данных, увторой данные присутствуют не на всех входных линиях, а в третьей командеимеются данные – предыдущий результат – на выходной линии. Четвертая командаимеет все, что необходимо для получения разрешения на выполнение, т. е. готовак выполнению. Выполнение команды приводит к исчезновению данных со входныхлиний и появлению результата на выходной линии.
Изм
Лист
№докум
Подпись.
Дата
Лист
8
Д 630.1.05.00.039.ПЗ размножитель, которыйпредставляет собой операцию с одним входом и несколькими выходами. Он готов к работе, когда на входной линии данныеприсутствуют, а выходные линии пустые. Его функции – распределять входныеданные по всем выходным линиям. Размножитель обозначается небольшим зачеркнутымкругом. Вторым новым понятием является бесконечныйисточник констант для команды.
ВСГТУ 622-1
Изм.
Лист
№ докум.
Подп.
Дата
Разраб.
Проверил
Литер.
Лист
Листов
Н.контр
Утв.
Д 630.1.05.00.039.ПЗ
ЯЗЫК ПОТОКОВ ДАННЫХ
2.2. Язык потоковданных
Изм
Лист
№докум
Подпись.
Дата
Лист
10
Д 630.1.05.00.039.ПЗ
Хотя язык Денниса является двумерного графического описания объектовпрограммирования, существуют и другие предложения по построению подобныхязыков, предполагающие представление программ потоков данных в более привычномвиде – в форме последовательности операндов, подчиняющихся определенномусинтаксису такого языка.
Как упоминалось выше, в языке потоков данных не используются понятия«переменная» и «передача управления». Программа записывается в виде набораоператоров, активируемых данными и соединенных однонаправленными линиямипередачи. В основу языка Денниса положены следующие три основных понятия:исполнительный элемент, информация и линия связи.
Исполнительный элемент символизируетоперацию, готовую к выполнению при поступлении информации на входные линииэтого элемента и при отсутствии информации на его входных линиях. Существуетдва типа исполнительных элементов – блоки (actor) и размножители (link). Блок – этоисполнительный элемент с одной выходной линией и одной или несколькими входными, размножитель– с одной входной линией и несколькими выходными.
Информация в языкеДенниса представляется в виде токенов, которые передаются по линиям связи,обрабатываются и выдаются исполнительными элементами.
Различаются два вида информации: значениеданных (например, числовые величины) и значения управляющих сигналов (логические величины TRUE – ИСТИННО или FALSE – ЛОЖНО). В описываемомязыке отсутствуют средства для распознавания типов значений данных (целые, сфиксированной точкой, комплексные и т. д.).
Используемые в языке Денниса понятие линия связи (arc)символизирует однонаправленный тракт, по которому информация передается от одного исполнительного элементак другому. Сигналы на линии связи могут отсутствовать либо на ней можетнаходиться только 1 токен информации. Следовательно, линию связи можнорассматривать как определенный эквивалент традиционных понятий «переменная» и«область памяти».
В соответствии с классификацией информации на значения данных и значенияуправляющих сигналов линии также разделяются на линии данных (обозначены на рисунках сплошными стрелками) и управляющие линии (обозначеныштриховыми стрелками).
Изм
Лист
№докум
Подпись.
Дата
Лист
11
Д 630.1.05.00.039.ПЗ
F T
P
f
Блок принятия решений
Вентиль Т
Размножитель данных
Размножитель
Блок выполнения операций
Вентиль F
T F
Рис. 2. Исполнительные элементы графического языка
Смеситель
На рис.2. изображены исполнительные элементы языка: сплошные стрелки показывают местаподсоединения линий данных, штриховые – управляющих линий. Операция размноженияготова к выполнению при появлении токена на единственной входной линииразмножителя и при условии, что все его выходные линии пусты. Размножительраспределяет полученный токен по выходным линиям. Блок выполнения операцииобычно имеет одну или две входных линии. Блок готов к работе при наличии токенов данных на всех еговходных линиях и при условии, что выходная линия пуста. Он принимает входныетокены, выполняет некоторые преобразования над полученными величинами ипомещает результирующий токен данных на свою выходную линию. Типичнымиоперациями таких блоков являются сложение, вычитание, умножение,инвертирование, извлечение квадратного корня и т. д.
Блок принятия решения функционирует аналогичным образом, однакорезультатом его работы является управляющий сигнал (логическая величина). Вэтом блоке вычисляется отношение, составленное из выходных данных, и формируется в результат в виде логическойвеличины TRUE (ИСТИННО)или FALSE (ЛОЖНО).Типичными операциями отношения являются операции сравнения двух величин поодному из критериев типа «равны», «не равны», «первая величина больше второй» ит. д.
Остальные три блока имеют на входе и данные, и управляющие сигналы. Блок типа вентиль Т (Т – от английскогослова TRUE) готов кработе при наличии на его входах как токена данных, так и токена управляющейинформации (при этом, как обычно, выходная линия должна быть пуста). Как и всеостальные исполнительные элементы, этотблок «поглощает» входную информацию вовремя выполнения. Если значение управляющего сигнала TRUE, то имеющийся на входе блока токенданных передается на выходную лини. Если значение управляющего сигнала FALSE, то сигнал на выходеблока не формируется. Таким образом, вентиль T либо пропускает входные данные на свой вход, либо просто«поглощает» их. Блок типа вентиль F (F – отанглийского слова FALSE)работает аналогичным образом, только для передачи токена данных на выходнуюлинию требуется управляющий сигнал, имеющий значение FALSE.
Изм
Лист
№докум
Подпись.
Дата
Лист
12
Д 630.1.05.00.039.ПЗ TRUEи токена данных на линии с меткой Т; 2) одновременное присутствие управляющеготокена FALSE и токенаданных на линии с меткой F.В обоих случаях выходная линия должна быть пуста. Если присутствует управляющийтокен TRUE, токенданных с входной линии Т пересылается на выходную линию. В результате эти дватокена на входных линиях уничтожаются, но при наличии токена данных на линии F он сохраняется. Еслиприсутствует управляющий токен FALSE,то токен данных на входной линии F пересылается на выходную линию. В результате этого два токенана входных линиях уничтожаются, но токен данных на линии Т, если онприсутствовал, сохраняется.
ВСГТУ 622-1
Изм.
Лист