Управляющий автомат и dataflow парадигмы вычислительного процесса – необычный симбиоз

 САЛИБЕКЯН С.М., к.т.н., доцент Национального исследовательского университета «Высшая школа экономики», ssalibekyan@hse.ru

 ШИБАЕВ Р.В., Национальный исследовательский университет «Высшая школа экономики», rshibaev@hse.ru

Управляющий автомат и dataflow 
парадигмы вычислительного процесса – необычный симбиоз

Статья посвящена описанию реализации управляющего автомата на базе вычислительной системы с управлением потоком данных (dataflow). Структурный автомат обычно входит всостав автоматической системы управления: принимает сигналы с датчиков объекта управления по определенному алгоритму, выдает управляющие сигналы для него. Реализация такого автомата dataflow-базе позволяет, в частности, повысить его технологичность и снизить время его разработки и дает удобный механизм его имитационного моделирования

Введение

В данной статье пойдет речь о симбиозе управляющего (структурного) автомата [1] и dataflow парадигмы [2]. В автоматной парадигме вычислительный процесс описывается какпереход вычислительного процесса между выделенными состояниями под воздействием внешних сигналов. Dataflow же делает акцент на передаче данных между параллельно работающими вычислительными устройствами. Передаваемые данные оформляются в виде токена (совокупность операнда и служебной информации). Исполнительное устройство начинает вычисления после того, как к нему поступят все необходимые для операции данные. Результат вычислений в виде токена передается другим устройствам.

Почему же управляющий автомат и dataflow понадобилось объединять? Да по той причине, что в «чистом виде» автомат может быть реализован только схематехнически. Однако если автомат сложен (в нем большое количество состояний и возможных переходов между ними), то проектирование и изготовление специализированных микросхем или печатных плат становятся достаточно дорогими.

Удешевить автомат помогают программируемые логические схемы (ПЛИС или FPGA), однако их вычислительных ресурсов может не хватить для решения некоторых вычислительных задач. Поэтому весьма актуальна реализация автомата (в том числе и программная [3, 4]) на базе другой универсальной вычислительной системы (ВС), чтосущественно удешевляет и упрощает создание автоматной системы.

В данной статье внимание уделяется реализации структурного автомата (т.е. автомата, используемого в системах управления) на базе dataflow парадигмы (вычисления, управляемые потоком данных). Dataflow была выбрана в качестве базы, т.к. она обладает многими преимуществами:

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

Классическая (control-flow – управление потоком команд) парадигма такой совокупностью полезных свойств не обладает [5].

Автоматная и dataflow парадигмы – противоположности, что тянутся друг к другу

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

Dataflow – система асинхронная: токены могут передаваться в любой момент времени, вычисления на исполнительном устройстве активизируются в момент поступления полного комплекта данных (синхронизация по данным). Автомат же – устройство синхронное: он может поменять свое активное состояние только один раз в течение такта своей работы.

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

И, может быть, единственное, что их объединяет, – это имитационное моделирование, где эти парадигмы уже давно активно используются (F- (автоматная) и N- (сетевая) схемы моделирования) [6].

Однако в [7] была предложена методика реализации различных типов автоматов на базе объектно-атрибутной (ОА) архитектуры ВС [8], относящейся к классу dataflow. В частности, в вышеприведенной статье была предложена реализация управляющего автомата.

Симбиоз fd mkv парадигм

ОА-ВС представляет собой совокупность функциональных (исполнительных) устройств (ФУ), обменивающихся токенами простейшего формата, включающих два поля:

• нагрузка (данные или указатель);
• атрибут (идентификатор нагрузки).

Поэтому структурный автомат на базе ОА-ВС представляет собой множество ФУ, совместная работа которых обеспечивает функциональность автомата.

И задачей настоящего исследования является определение необходимых типов ФУ и алгоритмов работы как отдельных ФУ, так и их совместной работы.

Токены в ОА-ВС будем называть информационными парами (ИП), а ИП, служащую для управления ФУ, будем именовать милликомандой МК.

Итак, управляющая система состоят из двух основных компонент: устройство управления (в нашем случае автомат) и объект управления (ОУ). ОУ и его окружающая среда снабжены датчиками, показания с которых поступают на управляющий автомат в качестве входных (внешних) сигналов. Автомат, в свою очередь, может выдавать управляющие сигналы на ОУ, реализуя таким образом определенный алгоритм управления ОУ. Теперь необходимо определить состав автомата на базе ОА-архитектуры (ОА-автомата).

Во-первых, автомат должен принимать входные и выдавать выходные сигналы. Данный функционал будет возложен на ФУ ввода-вывода. Такое ФУ, например, может обслуживать аналогово-цифровой и/или цифро-аналоговый преобразователь, обеспечивающий общение ВС с «внешним миром».

ФУ ввода-вывода представляет входные сигналы в виде информационной пары и передает их для дальнейшей обработки другим ФУ, входящим в состав ОА-автомата. ФУ ввода-вывода может управлять несколькими каналами обмена информацией.

Также функциональность ФУ включается в себя и предварительный анализ сигналов. В частности, можно настроить канал обмена информацией таким образом, чтобы входные сигналы либо передавались в ОА-автомат регулярно через определенный промежуток времени, либо запрашивались другими ФУ по мере необходимости, а также чтобы ФУ ввода-вывода сам запускал определенные программы при изменении входного сигнала. В состав ОА-автомата может входит несколько ФУ ввода-вывода, которые совместно «поставляют» информацию в ОА-автомат.

Пространство состояний автомата, а также переходы из одного активного состояния в другое осуществляются с помощью ФУ двух типов: ФУ-менеджер (координатор) и ФУ-состояние.

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

Итак, алгоритм работы структурного автомата можно представить в виде графа, где узлы ассоциируются с состояниями ВС, а дуги – с возможными переходами между ними. Ккаждой дуге приписывается переходной предикат, аргументами которого являются как входные сигналы автомата, так и другие аргументы, например, номер активных состояний других автоматов в системе параллельно работающих автоматов. Если переходной предикат, приписанный к дуге, выходящей из узла графа, ассоциированного с активным состоянием, возвращает «правда», тогда ВС переходит в состояние, ассоциированное с инцидентной вершиной. В том случае, когда ни один из предикатов не возвращает «правда», ВС остается в том же состоянии.

ФУ-менеджер выполняет прием входных сигналов от ФУ ввода-вывода и их пересылку на активное ФУ-состояние (адрес активного ФУ-состояния хранится во внутреннем регистре ФУ-менеджера). В [7] было введено понятие переходной программы, которая запускается в момент перехода автомата из одного состояния в другое. Переходная программа может производить вывод выходных сигналов через ФУ ввода-вывода, а также записывать в регистр активного ФУ-состояния, входящего в состав ФУ-менеджера, адрес нового активного состояния (таким образом обеспечивается переход из одного состояния автомата в другое). На рис. 1 приведена функциональная схема ОА-автомата.

Рисунок 1. Управляющий ОА-автомат

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

• Первая – накопление значений сигналов, которые являются аргументами переходного предиката: сигналы поступают с ФУ ввода-вывода последовательно, и вычисление предиката должно начинаться только при приходе всех аргументов, но не раньше.
• Вторая – каким образом вычислять переходной предикат?
• Третья – каким образом передавать значения входных сигналов в переходной предикат?

Эти проблемы были решены с помощью введения в состав ОА-автомата двух информационных капсул (ИК), именуемых ИК шаблона и ИК переменных.

ИК – это совокупность ИП, служащая для хранения атрибутированных данных: атрибут ИП служит идентификатором данных или указателя на ячейку оперативной памяти, хранимых в нагрузке. ИК переменных формируется до запуска ОА-автомата.

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

При поступлении сигнала от ФУ ввода-вывода менеджер отыскивает в ИК переменных ИП с атрибутом сигнала и записывает значение сигнала в ячейку памяти по адресу, хранящемуся в нагрузке данной ИП.

Далее менеджер создает ИП с атрибутом сигнала и пустой нагрузкой и помещает ее в ИК шаблона, таким образом ОА-автомат запоминает факт поступления значения сигнала. Переменные же, в которые производилась запись значения сигнала, будут являться аргументами переходного предиката.

В качестве ФУ-состояния в структурном автомате применяется ФУ типа «список» (FUList) [9]. ОА-список (список ИК), управляемый данным ФУ, содержит описание условий перехода в другое состояние и действий, осуществляемых во время такого перехода. Условие перехода задается с помощью указателя на описание вычисления подпрограммы вычисления переходного предиката. Вычисления переходного предиката возлагаются на ФУ «арифметико-логическое устройство» (ФУ АЛУ) – ссылка на ФУ АЛУ хранится вовнутреннем регистре ФУ «список». В ИК ОА-списка также добавляются ИП с атрибутами входных сигналов, являющихся аргументами переходного предиката, а также ИП суказателем на переходную программу (см. рис. 2).

Рисунок 2. ФУ-состояние структурного ОА-автомата

На ФУ-состояние менеджер передает ИК шаблона, и ФУ начинает просматривать все ИК ОА-списка. Если обнаруживается, что в ИК списка присутствую все ИК со всеми атрибутами из шаблона (т.е. поступили все сигналы, являющиеся аргументами переходного предиката), ФУ передает ссылку на подпрограмму вычисления переходного предиката наФУ АЛУ. ФУ АЛУ возвращает значение предиката: если предикат «ложь», тогда ФУ «список» продолжает перебор ИК списка, иначе запускает выполнение переходного предиката.

Имитационная модель dataflow автоматной системы управления

Одним из преимуществ ОА-архитектуры является удобная методика имитационного моделирования работы ВС [10]. В частности, для моделирования ОА-автоматной системы можно применить технологию, когда модель объекта управления реализуется в виде ФУ. Тогда управляющие воздействия на модель управления поступают от ОА-автомата в виде милликоманд, а объект управления информирует автомат о своем состоянии также посредством милликоманд, которые передают эмулированные показания датчиков. Такая схема была применена для моделирования системы управления мобильным роботом YARP-2 [11].

Модель робота и среды, в которой он осуществляет перемещение, была реализована программно в виде ФУ. ФУ-имитатор робота эмулирует среду передвижения робота, работу датчиков обнаружения объектов и дальномеров, определяющих расстояние до препятствия. Программы ФУ и управляющего ОА-автомата были интегрированы в среду ОА-программирования и моделирования. Среда позволяет производить моделирование вычислительного процесса в ОА-ВС, в ее состав входит компилятор специализированного языка программирования, предназначенного для управления виртуальными ФУ (ФУ выполненными в виде программы). Программирование ОА-автомата и настройка ФУ-эмулятора осуществлялись через консоль среды ОА-программирования и моделирования. Вывод результатов моделирования осуществлялся в другую консоль среды. Визуализация результатов моделирования осуществлялась в среде Matlab. Схема системы моделирования приведена на рис. 3.

Рисунок 3. Система имитационного моделирования управляющего ОА-автомата

Для удобства реализации системы управления была произведена декомпозиция автомата по четырем режимам управления: случайное блуждание до момента обнаружения цели, приближение к цели, объезд препятствия, экстренный отъезд от препятствия (если препятствие оказалось в опасной близости). Для каждого режима реализован отдельный автомат со своей программой управления. Переключение между различными режимами работы автомата происходит путем перенаправления потока информации от ФУ ввода на конкретный автомат: тот автомат, на который поступает входной поток данных, является активным в данный момент.

В заключение следует сказать, что управляющий ОА-автомат был успешно программно реализован в виде имитационной модели. Модель продемонстрировала возможность реализации автоматной декомпозиции задачи по режимам работы. Декомпозиция позволяет значительно упростить проектирование сложных автоматов. Отработанная методика имитационного моделирования автоматной системы на ОА-базисе также позволит значительно ускорить и удешевить создание систем управления. Это достигается благодаря кроссплатформенности ОА-программы: отлаженная на имитационной модели программа работы ОА-автомата без изменений переносится на реальную ВС, если на ней программно реализованы ФУ, аналогичные по функциональности применяемым в модели.

1. Савельев А.Я. Прикладная теория автоматов: Учеб. пособие для вузов по спец. ЭВМ. – М. Высшая школа, 1987. – 272 с.
2. Jurij Silk, Borut Robic and Theo Ungerer «Asynchrony in parallel computing: From dataflow to multithreading» Institut Jozef Stefan, Technical Report CDS-97-4, September 1997.
3. Поликарпова Н., Шалыто А. Автоматное программирование. – СПб: Питер, 2011.
4. Шалыто А. А. SWITCH-технология. Алгоритмизация и программирование задач логического управления. – СПб.: Наука, 1998. URL: http://is.ifmo.ru/books/switch/1.
5. Непейвода Н. Н. Стили и методы программирования. – М.: Интернет-университет информационных технологий, 2005.
6. Рябов О.А. Моделирование процессов и систем. Учебное пособие. – Красноярск, 2008. – 122 с.
7. Салибекян С.М. Реализация автоматного подхода к программированию на основе ОА-парадигмы // Объектные системы – 2016: материалы XII Международной научно-практической конференции (Ростов-на-Дону, 10-12 мая 2016 г.) / Под общ. ред. П.П. Олейника. – Ростов-на-Дону: ШИ (ф) ЮРГПУ (НПИ) им. М.И. Платова, 2016. – С. 54-61 – http://objectsystems.ru/files/2016/Object_Systems_2016_Proceedings.pdf.
8. Салибекян С.М., Панфилов П.Б. Объектно-атрибутная архитектура – новый подход к созданию объектных систем. // «Информационные технологии», № 2, 2012 г. – С. 8-14.
9. Салибекян С.М., Панфилов П.Б. Анализ языка с помощью объектно-атрибутного подхода к организации вычислений. // «Программная инженерия», № 1, 2013 г. – С. 9-16.
10. Салибекян С. М., Панфилов П. Б. Вопросы автоматно-сетевого моделирования вычислительных систем с управлением потоком данных. // «Информационные технологии ивычислительные системы», № 1, 2015 г. – С. 3-9.
11. Исследование методов организации коллектива роботов на основе моделирования эусоциальных сообществ // 2016. URL: http://robofob.ru/projects.

Ключевые слова: структурный автомат, вычислительный процесс с управлением потоком данных, объектно-атрибутный принцип организации вычислительного процесса и структур данных, программная реализация автомата.

Control automata and dataflow paradigm of computation process is unordinary symbiosis

Salibekyan S.M., Ph.D., Associate Professor of the National Research University «Higher School of Economics», ssalibekyan@hse.ru

Shibaev R.V., National Research University «Higher School of Economics», rshibaev@hse.ru

Abstract: The article is devoted to description of the implementation of the control automata based on a dataflow computing system. Structural machine usually is part of the automatic control system: it receives signals from the sensors of the control object and sends outputs control signals to him according to a specific algorithm. The implementation of such a machine on dataflow database allows, in particular, to increase the effectiveness of its designs, reduce its development time and provides a convenient mechanism for its simulation.

Keywords: control automata, dataflow, object-attribute principle of organization of the computational process and data structures, automata program realization.

Комментарии могут оставлять только зарегистрированные пользователи