Автоматика и телемеханика, № 8, 2014
© 2014 г. Д.А. ЗАЙЦЕВ, д-р техн. наук (daze@acm.org) (Международный гуманитарный университет, Одесса, Украина)
ПАРАДИГМА ВЫЧИСЛЕНИЙ НА СЕТЯХ ПЕТРИ
Показано, что пардигма вычислений на сетях Петри обеспечит существенное ускорение вычислений и сокращение трудоемкости разработки программного обеспечения за счет массового параллелизма и асинхронного характера процессов обработки информации. Разработан язык программных сетей Петри, предложены альтернативные подходы реализации парадигмы на микро- и макроуровнях, уточнены оценки сложности ранее построенной универсальной сети Петри, являющейся прототипом соответствующего процессора. Указаны направления практической реализации парадигмы: разработка технологии программирования на нагруженных сетях Петри, технологии трансляции нагруженных сетей Петри в инги-биторные сети Петри и эффективных аппаратных процессоров, исполняющих программы на языке ингибиторных сетей Петри. Использование класса сетей Слепцова с кратным запуском перехода на шаге обеспечивает быстрые вычисления.
1. Введение
Сеть Петри [1-7] широко известна как средство моделирования дискретных параллельных процессов. Кроме того, сеть Петри все чаще применяют как язык программирования [8-13] параллельных вычислений [14]. С построением универсальной сети Петри в явном виде [15, 16] создаются объективные предпосылки для всесторонней разработки парадигмы вычислений на сетях Петри в замкнутом виде, не использующей других формализмов для организации вычислений; настоящая статья посвящена предварительной проработке основных направлений исследований.
2. Сети Петри и моделирование систем
Сеть Петри [1, 2] представляет собой двудольный ориентированный граф, на котором задан динамический процесс. Одна доля вершин, называемых позициями и изображаемых в виде окружностей, моделирует условия; вторая доля вершин, называемых переходами и изображаемых в виде прямоугольников, моделирует события. Динамические элементы, именуемые фишками, размещаются внутри позиций и перемещаются в сети в результате срабатывания переходов. Позиции, переходы, дуги и фишки рассматриваются либо как элементарные, либо как нагруженные дополнительными атрибутами и функциями, определяя множество различных классов сетей Петри [3, 5, 6].
Сети Петри традиционно применяют для моделирования систем в широком спектре приложений [3-7]. Элементарная сеть Петри располагается между конечным автоматом и машиной Тьюринга, позволяя применять аналитические методы исследования [1, 2]. Нагруженные сети Петри [3, 5] часто
рассматривают как графический язык систем имитационного моделирования и используют подход проверки модели (model-checking) либо статистический анализ.
Как правило, классические сети Петри применяют для доказательства корректности (верификации) систем, а нагруженные сети - для оценки эффективности систем.
3. Программирование на языке ингибиторных сетей Петри
Так как доказана полнота по Тьюрингу ингибиторной сети Петри [1, 2], то можно программировать на языке сетей Петри. Напомним, что в ингибиторной сети Петри (ИСП) добавлен специальный тип дуги, направленной из позиции в переход, для проверки маркировки позиции на ноль. Многие авторы рассматривают сеть Петри как графическую подложку асинхронных параллельных языков программирования [8-13]. Но язык сетей Петри достаточно часто используют как вспомогательный промежуточный язык, который, в конечном счете, транслируется в инструкции некоторого классического процессора.
На рис. 1 показана сеть Петри, реализующая операцию сложения целых чисел: а - исходные данные помещены в позиции x и у, попадание фишки в позицию s запускает вычисления; б - полученный результат наблюдается в позиции z когда позиция f маркирована. Ингибиторная дуга обозначена полым кругом на ее конце; дуга со сплошным кругом является проверочной и представляет собой аббревиатуру двух дуг противоположного направления. Позиции сети Петри обозначены буквами p, переходы - буквами t. Представленная в подрисуночной подписи последовательность срабатывания переходов не является единственной допустимой: порядок запуска переходов t2 и t3 допускает произвольные перестановки.
Современная управляемая моделью разработка (model-driven development) использует преимущество моделей в форме сетей Петри, которые трансформируются в спецификации систем в процессе проектирования. Однако заключительный этап предполагает трансляцию сети Петри в последовательность инструкций, что нивелирует многие преимущества.
Рис. 1. Ингибиторная сеть Петри сложения целых чисел ADD: а - начальное состояние; б - конечное состояние; последовательность срабатывания переходов tlt22t33t4.
operator 1
S operator 1 f/s operator 2 f
O—o-O—Ch-O
£K>
s //
f оси
OO IX
Рис. 2. Представление операторов языка программирования сетями Петри: а-последовательность; б - ветвление; в - цикл; г - параллельное выполнение.
Асинхронный подход противопоставляют традиционному параллельному подходу, в котором алгоритмы являются изначально последовательными и требуются методы их распараллеливания для исполнения на мультипроцессорных системах и кластерах. В асинхронном подходе алгоритмы разрабатывают, сохраняя естественный параллелизм предметной области таким образом, что их последующее распараллеливание не требуется.
На рис. 2 основные алгоритмические конструкции языка параллельного программирования представлены ингибиторной сетью Петри [15]: а - последовательность operator 1; operator 2; б -ветвление if (condition ) operator 1 else operator 2; в - цикл while (condition ) operator ; г - параллельное выполнение parbegin ... parend. Буквой c обозначен результат вычисления условия condition . Однако написание программ непосредственно на языке сетей Петри позволяет выполнять произвольные комбинации потоков данных и потоков управления; более того, потоки управления и данных могут быть настолько тесно интегрированы, что становятся неразличимыми по отдельности.
Сеть потока управления формируется путем композиции представленных на рис. 2 графических шаблонов для последовательности, ветвления, цикла и параллельного выполнения. Использованы две основные операции для композиции потока управления: последовательная композиция и подстановка перехода. Операторная сеть имеет входные и выходные контактные позиции вместе с обязательной парой позиций: входной - запуск (s) и выходной - завершение (f); другие контактные позиции используются для представления входных и выходных переменных. Последовательная композиция выполняется путем слияния позиции завершения (f ) предыдущего оператора с позицией запуска (s) следующего оператора, как показано на рис. 2,а.
4. Организация работы с переменными и вызова процедур
В [15-18] предложен ряд соглашений, позволяющих легко транслировать традиционные программы в ИСП, а также разрабатывать программы в виде ИСП непосредственно. Систему соглашений назовем программной инги-
б
a
в
г
to to
p3 p2
О
y = x
y = x
Рис. 3. Вспомогательные сети копирования значений переменных: а - CLEAN (x := 0); б - MOVE (y := x, x := 0); в - COPY
(y := x).
a
p8 p9
rl .1
»
ql
ADD б
q2
COPY
COPY
ADD
О-НЛ^Ю— HF
CLEAN
p26 p28 о—-Е^СН&О/
MOVE
б
а
x
x
x
s
s
s
b
a
c
c
a
Рис. 4. Пример использования оператора (подсети) - компиляция в низкоуровневую сеть: а - типовой вызов ADD (c := a+b); б - результирующая низкоуровневая сеть.
биторной сетью Петри (ПИСП). ПИСП получают в результате композиции сети, описывающей поток (потоки) управления и множества позиций, представляющих глобальные статические переменные. Использованы глобальные целочисленные переменные; каждая переменная представлена соответствующей позицией сети Петри. Кроме того, параметры операторов представлены входными и выходными контактными позициями. Перед запуском оператора переменные копируются в его входные позиции, а после завершения заменяются значениями из выходных позиций. В дальнейших реализациях возможно поразрядное хранение переменных.
Специфической особенностью ПИСП являются штриховые и пунктирные дуги, соединяющие позиции переменных с переходами операторов. Они обеспечивают присваивание значений переменным. На рис. 3 представлены основные вспомогательные сети копирования переменных. Эти сети могут использоваться либо независимо, либо как расширение штриховых (пунктирных) дуг.
Подстановка перехода представляет собой использование операторов (процедур). Переход замещается соответствующей подсетью; имя подсети записывается возле перехода. Как и в моделирующей системе CPN Tools [5], подстановка перехода требует указания:
а) имени подсети;
б) отображения контактных позиций.
Количество контактных позиций и их типы (входная, выходная, входная/выходная) должны совпадать. Например, подстановка, изображенная на рис. 4, задается следующим отображением: r1 — ADD, a — x, b — y, q1 — s, c — z, q2 — f. Буквами q на рис. 4 обозначены позиции потока управления сети высокого уровня. При композиции программы отображение контактных позиций может быть указано неявно, что в большинстве случаев не является неоднозначным.
ПИСП может быть полностью собрана с использованием функциональных подсетей (кланов) [7], содержащих только входные и выходные позиции. Для этого в таких вспомогательных сетях как COPY и MUL значение из входной позиции может быть предварительно скопировано в некоторую внутреннюю позицию.
Входные штриховые дуги оператора обозначают расширение в подсеть COPY; выходные - CLEAN и MOVE. На рис. 4 показан пример полной подстановки с копированием значений переменных: ПИСП, изображенная на рис. 4,а, компилируется в низкоуровневую сеть, представленную на рис. 4,б, с использованием подсетей рис. 1 и рис. 3,а-3,в. Для нескольких входных (выходных) переменных создаются цепочки подсетей COPY (CLEAN и MOVE).
Пунктирные линии используются в случае, когда значение переменной потребляется полностью оператором; они раскрываются как подсети MOVE. Когда переменная является как входной, так и выходной для некоторого оператора, используется двунаправленная штриховая ду
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.