Машины обеспечивающие выполнение вычислений управляемых потоком данных
Машины, управляемые потоком данных
В вычислительных системах, управляемых потоками данных, машинах потоков данных, отсутствует понятие программы как последовательности команд, а следовательно, отсутствует понятие состояния процесса. Каждая инструкция передается на исполнение, как только создаются условия для ее реализации. При наличии достаточных аппаратных средств одновременно может обрабатываться произвольное число готовых к исполнению инструкций. В datafllow – модели параллелизм не задается явно и аппаратные средства обработки должны его выделять на этапе исполнения. Однако, следует отметить, что реализация принципа управления потоком данных вызывает ряд трудностей, часть из которых носит принципиальный характер. К их числу необходимо отнести громоздкость программы, трудность обработки итерационных циклов, трудность работы со структурами данных.
Граф потока данных и структура потоковых машин
Инструкциям на графе соответствуют вершины, а дуги, обозначенные стрелками, указывают на отношения предшествования. Точка вершины, в которую входит дуга, называется входным портом (или входом), а точка, из которой она выходит, выходным. По дугам передаются метки, называемые токенами данных (token). Срабатывание вершины означает выполнение инструкции. При этом срабатывание происходит в произвольный момент времени при выполнении условий, соответствующих правилу запуска. Обычно используется строгое правило запуска, согласно которому срабатывание вершины происходит при наличии хотя бы по одному токену во всех ее входных портах. Срабатывание вершины сопровождается удалением одного токена из каждого входного порта и размещением не более одного токена результата операции в выходные порты. В зависимости от конкретной архитектуры системы порты могут хранить один или несколько токенов, причем они могут использоваться по правилу FIFO или в произвольном порядке.
Вычислительные модели (системы) с управлением потоком данных (потоковые машины) и редукционные машины
Х. Классификация вычислительных моделей и механизмов обработки
Особенности RISС-архитектуры.
Развитие архитектур с полным набором команд (CISС-архитектур) столкнулось с рядом проблем.
Реализация большого количества сложных команд привела к необходимости использовать примерно 50% ресурсов кристалла для устройства управления.
Устройство управления реализуется на основе микропрограммного принципа, в основе которого – использование ПЗУ и сложных с логической точки зрения обрамляющих ПЗУ устройств.
В связи с отмеченным выше, оказываются длинными цепи прохождения сигнала в пределах такта. Это приводит к ограничению рабочей частоты, и сдерживает ее повышение даже при переходе к более высокочастотной базе.
В связи с этим, получили развитие RISС-архитектуры, т.е. архитектуры с ограниченным набором команд.
Их особенность: используются простейшие, но часто используемые команды (инструкции). Как правило, одна инструкция выполняется за такт. Сложные операции собираются из этих простейших команд с использованием подпрограмм. Ограничено количество способов адресации. Существует небольшое число форматов команд, преобладают фиксированные размеры и функциональное назначение команды. Широко используется жесткая логика (не используются принципы микропрограммного управления). Появляется возможность существенного сокращения ресурсов кристалла за счет уменьшения устройства управления. Обычно увеличивается количество регистров общего назначения.
Широко используются конвейерные принципы, как при выполнении команд, так и операций.
Главный недостаток такой архитектуры: возможно формирование программного кода существенно большей длины, т.е. увеличение количества инструкций.
С целью совершенствования архитектур в современных микропроцессорах используются комбинации CISС и RISС архитектур.
Примеры систем с RISС-архитектурой: TMS320C80 и другие сигнальные процессоры; рабочие станции SUN, DEC; процессоры компании Motorola, PowerPC, Hewlett Packard, Shpark фирмы SUN; Alpha фирмы DEC.
Выделяют 4 типа моделей:
Для каждой модели существует соответствующий метод управления (оценки организации вычислений, получения конечного результата):
1. Метод с потоком управления. Существует для вычислительного механизма неймановской машины. Механизм управления определяет, каким образом каждое вычисление запускает выполнение другого вычисления. Механизм данных определяет, как используются данные в различных вычислениях. Поток управления – это поток команд.
2. Метод с потоком данных. Применяется в потоковых машинах, ЭВМ.
3. Редукционные машины. Редукционная машина – это вычислительная машина, которая вычисляет арифметические выражения путем последовательного сокращения всех составляющих их подвыражений, пока не останутся просто значения данных.
Механизм управления определяет, каким образом каждое вычисление запускает выполнение другого вычисления.
Механизм данных определяет, как используются данные в различных вычислениях.
Императивная вычислительная модель соответствует неймановской архитектуре. Ей характерна последовательность команд, побочный эффект.
Описывают эту модель императивные языки – Паскаль, Фортран и т.д., т.е. процедурные языки.
Побочный эффект отображается в операторах присваивания.
Объектно-ориентированная вычислительная модель. В ней вычисления моделируются с помощью множества объектов, передающих друг другу запросы. Языки объектно-ориентированного направления описывают объектно-ориентированные модели.
Параллельные процессы представляются при параллельном описании и указании параллельного выполнения объектов.
Логическая вычислительная модель – это модель, в которой вычисления представляются с помощью логики предикатов. Язык программирования для описания вычислений – это логический язык (например, ПРОЛОГ). Распараллеливание процессов осуществляется на уровне И/ИЛИ.
Особенностью потоковых машин является то, что последовательность вычислений задается не последовательностью команд, что характерно для неймановской архитектуры, а по мере готовности данных для выполнения команд. Данные загружаются в операционное устройство, если оно свободно, и для определенной команды имеются все необходимые данные.
Принципиальным отличием от неймановских машин является то, что команды выполняются не в порядке их следования, а по готовности операндов. Как только на входе операционного блока появляются данные, соответствующая команда блока захватывает эти данные и выполняется соответствующая операция. Машины, основанные на модели с потоком данных, называются потоковыми:
— отсутствие побочного эффекта;
— эффективная реализация параллельных вычислений.
Пример. a = (b+c)*(b-c). Для отображения хода процесса используются специальные «фишки». Потоковые принципы описываются с помощью графов и сетей Петри.
Такой подход используется в параллельных системах: однородных вычислительных средах (однотипные архитектуры процессоров (процессорных элементов ПЭ), настаиваемых на выполнение определенных программ; передача данных с использованием средств коммутации.
Принцип управления вычислительным процессом на основе потока данных используется в современных микропроцессорах, в частности, в суперскалярных архитектурах (Рис.). Сущность этих процессов состоит в следующем. Команда имеет код операции, может содержать два операнда, а также имеет два разряда (теги) для идентификации наличия (готовности) операндов к вычислениям. Команды хранятся в ячейках команд. Устройство управления при обнаружении двух единиц (двух готовых операндов) в одной из команд анализирует наличие среди операционных устройств (ОУ) свободное, которое по функциональным возможностям может реализовать операцию данной команды. При наличии такого устройства код операции и коды операндов передаются через операционный компилятор в соответствующее выбранное операционное устройство. Полученный результат записывается в память по адресу, указанному в команде.
Механизм редукционных машин основан на принципе редукции, т.е. сокращения посредством перезаписи строк символов (формул) в программе или сокращения в графах.
Запуск вычислений осуществляется при необходимости получения данных.
Пример. Исходные данные: граф программы, находящийся в памяти. a = (b+c)*(b-c).
а)
b)
c) d)
Нет побочного эффекта. Реализуется последовательность решения математических выражений. Это направление удобно для параллельной реализации.
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет
Принцип действия машин потоков данных
2.1. Принцип действия машин потоков данных…………………………………………….6
2.4. Сети трактов передачи пакетов…………………………………………………………16
2.5. Переполнение и тупиковые ситуации………………………………………………….20
3.1. Постановка и реализация задачи……………………………………………………. 28
3.2. Реализация программы на машине потоков данных…………………………………..30
3.3. Принцип работы устройства…………………………………………………………….32
1. Введение
Появление машин потоков данных обусловлено тремя основными причинами: потребность в существенном увеличении вычислительной мощности, серьезным недостатком принципов построения современных языков программирования и наличием «узких мест» в физической структуре традиционных машин.
Первая причина – отсутствие достаточной вычислительной мощности – является значительным препятствием для применения машин при решении важных проблем. Хотя в наши дни ЭВМ с успехом применяют для экономических расчетов (подготовка платежных ведомостей, начисление страховых премий, бухгалтерский учет, ведение расчетов по кредитным карточкам), вычислительные машины плохо приспособлены для решения задач в области создания искусственного интеллекта, распознавание образов, обработки речевой информации, прогнозирование погоды, проектирование аэродинамических конструкций, перевода с одного иностранного языка на другой, сейсмического анализа и многих других.
Традиционным решением задачи увеличения мощности системы (после того как производительность единственного процессора доведена до максимального значения) является использование нескольких процессоров. Однако такой подход не является удовлетворительным в силу действия следующих обстоятельств. Во-первых, возникают проблемы программирования, обусловленные необходимостью для программиста «подгонять» структуру данных и программ под жесткую структуру многопроцессорной или распределенной вычислительной системы. Например, при работе с системой, содержащей 16 процессоров, программисту приходиться разбивать свою программу на 16 или более параллельных процессов. Задача далеко не тривиальная, и современные языки программирования, средства обслуживания и отладки едва ли могут здесь оказать какую-либо существенную помощь.
Во-вторых, в традиционных мультипроцессорных системах в режиме разделения памяти между процессорами возможны наложения обращений к памяти – так называемая интерференция обращения к памяти. Поскольку каждый отдельный процессор стремится захватить определенную часть памяти, подключение новых процессоров к памяти, уже разделяемой другими процессорами, может дать только ограниченную выгоду.
Интерференция обращения к памяти может быть уменьшена, если каждый процессор снабдить локальным кэш-буфером (кэш-памятью). Однако при этом возникает другая проблема: некоторая ячейка памяти может оказаться привязанной к нескольким кэш-буферам, т. е. операция записи одного процессора может повлечь за собой искажение информации в кэш-буферах других процессоров. Таким образом, хотя мультипроцессорные системы имеют определенные достоинства, повышая степень готовности системы для решения различных задач, они все же уступают однопроцессорным аналогам по такому критерию, как отношение стоимости к производительности.
Второй причиной появления машин потоков данных является недостатки, присущие самой природе современных языков программирования, и осознание того факта, что эти языки отражают в своей структуре основополагающие принципы архитектуры машин фон Неймана. Так же внутренняя организация современных машин предполагает использование пассивной памяти, процессора, выполняющего операции по изменению содержимого памяти, и устройства управления, воздействующего на процессор с помощью потока следующих одна за другой команд. Понятие «переменная» в языке программирования адекватно понятию «область пассивной памяти» в машине, понятие «передача управления» в языке (реализуемая, например, операторами GO TO, IF, DO, CALL) отражает устройство управления и счетчик команд в машине фон Неймана. Подобным же образом понятие «присваивание» является отображением определенной операции процессора (изменение содержимого области памяти машины). Использование потока данных для управления машиной позволило сделать выводы, с которыми согласились и специалисты в области теории языков
Третьей причиной появления машин потоков данных является осознание того фактора, что тракт, соединяющий процессор с памятью, является тем самым «узким местом», которое в основном и ограничивает эффективность системы. В современных вычислительных системах назначение программы заключается в изменении содержимого памяти, предоставляемой для данных этой программы. Достигается это путем «проталкивания» одиночных команд и данных через узкую магистраль, связывающую память и процессор.
В любом компьютере все основные параметры тесно связаны. Трудно себе представить универсальный компьютер, имеющий высокое быстродействие и мизерную оперативную память, либо огромную оперативную память и небольшой объем дисков. Следуя логике, делаем вывод: суперЭВМ это компьютеры, имеющие в настоящее время не только максимальную производительность, но и максимальный объем оперативной и дисковой памяти (вопрос о специализированном ПО, с помощью которого можно эффективно всем этим воспользоваться, пока оставим в стороне).
Так о чем же речь, и какие суперкомпьютеры существуют в настоящее время в мире? Вот лишь несколько параметров, дающих достаточно красноречивую характеристику машин этого класса. Компьютер ASCI WHITE, занимающий первое место в списке пятисот самых мощных компьютеров мира, объединяет 8192 процессора Power 3 с общей оперативной памятью в 4 терабайта и производительностью более 12 триллионов операций в секунду.
2.1. Принцип действия машин потоков данных
Машины потоков данных производят наиболее сильное впечатление тем, что принципы их проектирования не базируются на основных свойствах и характеристиках традиционных машин и языков программирования. В архитектуре машин потоков данных отсутствует понятие «пассивная память данных», а в языке потоков данных нет понятия «переменная»: данные перемещаются из команды в команду по мере выполнения программы.
Кроме того, в данном случае не используются понятия «передача управления», «счетчик команд» и «ветвление вычислительного процесса». Вместо этого команды (операторы) управляются данными. Считается, что команда готова к управлению (т. е. Ее выполнение разрешено), если данные присутствуют в каждом из ее входных портов и отсутствуют в выходном порте. Выполнение команды приводит к исчезновению данных в ее входных портах и появлению результата в выходном порте. Программа представляет собой направленный граф, образованный соединенными между собой командами: выходной порт одной команды соединен с входным портом другой команды. Таким образом, порядок выполнения команды определяется не счетчиком команд, а движением потока данных в командах.
Указанные принципы выполнения команд иллюстрируют рис. 1. здесь окружности обозначают команды, стрелки – линии связи между командами, а зачерненные круги – данные.
Команды не готовы к выполнению
 |  |  |
Команда готова к выполнению
Рис. 1. Возможные состояния команд в машине потоков данных.
Первые три команды показаны в состоянии запрета на выполнение. У первой команды нет входных данных, у второй данные присутствуют не на всех входных линиях, а в третьей команде имеются данные – предыдущий результат – на выходной линии. Четвертая команда имеет все, что необходимо для получения разрешения на выполнение, т. е. готова к выполнению. Выполнение команды приводит к исчезновению данных со входных линий и появлению результата на выходной линии.
Также возникает необходимость ввести два дополнительных понятия. Первым является размножитель, который представляет собой операцию с одним входом и несколькими выходами. Он готов к работе, когда на входной линии данные присутствуют, а выходные линии пустые. Его функции – распределять входные данные по всем выходным линиям. Размножитель обозначается небольшим зачеркнутым кругом. Вторым новым понятием является бесконечный источник констант для команды.
2.2. Язык потоков данных
Один из языков для машин потоков данных был предложен Деннисом и его коллегами из Массачусетского технологического института, где проводятся наиболее серьезные исследования в области машин потоков данных.
Хотя язык Денниса является двумерного графического описания объектов программирования, существуют и другие предложения по построению подобных языков, предполагающие представление программ потоков данных в более привычном виде – в форме последовательности операндов, подчиняющихся определенному синтаксису такого языка.
Как упоминалось выше, в языке потоков данных не используются понятия «переменная» и «передача управления». Программа записывается в виде набора операторов, активируемых данными и соединенных однонаправленными линиями передачи. В основу языка Денниса положены следующие три основных понятия: исполнительный элемент, информация и линия связи.
Исполнительный элемент символизирует операцию, готовую к выполнению при поступлении информации на входные линии этого элемента и при отсутствии информации на его входных линиях. Существует два типа исполнительных элементов – блоки (actor) и размножители (link). Блок – это исполнительный элемент с одной выходной линией и одной или несколькими входными, размножитель – с одной входной линией и несколькими выходными.
Информация в языке Денниса представляется в виде токенов, которые передаются по линиям связи, обрабатываются и выдаются исполнительными элементами.
Различаются два вида информации: значение данных (например, числовые величины) и значения управляющих сигналов (логические величины TRUE – ИСТИННО или FALSE – ЛОЖНО). В описываемом языке отсутствуют средства для распознавания типов значений данных (целые, с фиксированной точкой, комплексные и т. д.).
Используемые в языке Денниса понятие линия связи (arc) символизирует однонаправленный тракт, по которому информация передается от одного исполнительного элемента к другому. Сигналы на линии связи могут отсутствовать либо на ней может находиться только 1 токен информации. Следовательно, линию связи можно рассматривать как определенный эквивалент традиционных понятий «переменная» и «область памяти».
В соответствии с классификацией информации на значения данных и значения управляющих сигналов линии также разделяются на линии данных (обозначены на рисунках сплошными стрелками) и управляющие линии (обозначены штриховыми стрелками).
Среди различных блоков рассматриваемого языка потоков данных блок типа «смеситель» является исключением: выполнение предписываемых им действий не вызывает уничтожения всех токенов на входных линиях, и для перехода его в состояние готовности к работе не требуется наличия всех входных токенов. Этот блок готов к работе при соблюдении одного из следующих условий: 1) одновременное присутствие управляющего токена TRUE и токена данных на линии с меткой Т; 2) одновременное присутствие управляющего токена FALSE и токена данных на линии с меткой F. В обоих случаях выходная линия должна быть пуста. Если присутствует управляющий токен TRUE, токен данных с входной линии Т пересылается на выходную линию. В результате эти два токена на входных линиях уничтожаются, но при наличии токена данных на линии F он сохраняется. Если присутствует управляющий токен FALSE, то токен данных на входной линии F пересылается на выходную линию. В результате этого два токена на входных линиях уничтожаются, но токен данных на линии Т, если он присутствовал, сохраняется.
Структура и архитектура типичной машины потоков данных была спроектирована в Массачусетском технологическом институте. Это наиболее распространенный проект машины. Структура этой машины представлена в приложении 1. здесь нет ни процессора, ни памяти в их традиционном смысле. Машина разделена на три главные секции. Первой из них является память, содержащая ячейки команд. Ячейка команды состоит из кода операции, одного или более входных портов и указателя ячеек команд, в которые должен быть направлен результат выполнения данной команды. Ячейки команд не являются пассивными запоминающими устройствами, они содержат некоторые логические схемы.
Вентиль-ный код