Книжка по сетям Петри, страница 36

вые выражения„задеощие сети на рис. 8.5, имеют следующий внд: (1) 1((е,Ы;+, (Ь,с);Х);+, (2) 1((а, Ы; +ы (с, г();+ г );+э, (3) 1 (((а, Ы;+ыс!;+т,Ф):+з. Если удалить из зтих потоковых выражений операции управления, скобки н доПолнительные индексы, то они примут вид; (1) еЬ + Ьс Х +, (2) аЬ +сг( + +, (3) аЬ+с+б+. Полученные выражения представляют собой обратную польскую запись выражений, которые в ннфиксной скобочной нотации имеет вид: (1) (а+Ы+ (Ь Х с), !2) (е ~ Ы + (с + т(), (3) ((в + Ь) + с) + т(). Формулы, задающие ястоксвые сети на рис. 8.6, и соответствующие потоковые выражения не содержат операций исключения и итерации.

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

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

ду с операциями-преобразователями "условные операции", н обеспечить конвейерное исполнение потоковых выражений за счет подходящей разметки мест-очередей. Например, для того чтобы запрограммировать условное вырахцние Из<отдел(е+с)е(зв (а-с) можно использовать условную операцию 0(х,у,г), в которой первый аргумент имеет тип "логический"; у, если х истина, л(т, у,г) = г, если к ложь. 1Зт Рис. 8.7. . в,в, Потоковое выражение для рассматриваемого условного выражения имеет вид: 1(((а, Ы;<, (а,с);+, (а,с1; — );В), где а, Ь, с — константные операции, бинарная операция.

< вырабатывает логическое значение. Простая потоковая сеть, задаваемая этой формулой, показана на рис. 8.6, а польская запись формулы выглядит следующим образом: аЬ < ас + ас — В. Недостатком введенного представления условного выражения в потоковой сети является необходимость вычисления обеих его альтернатив. Другой способ обеспечения функциональной полноты потоковых программ — использование регулярных сетей общего вида, т.е.

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

Если переход. фильтр может сработать, то он, как обычно. забирает фишку-данное и посыпает его без изменений во все свьн выходные места. рассмотренное выше условное выражение можно запрограммировать с применением фильтров < и > следующим образом: 1((а, Ы;((<;(а,с);+) ~ й",(а,с);-1))). Соответствующая потоковая сеть показана на рис. 8.7. На этом примере видно, что фильтры следует использовать в сочетании с операцией ис. ключения. э 83. Типы управления Для того чтобы в параллельных программах иметь воэможность в удобной форме задавать сложные структуры управления, все большее распространение получает идея выделения управляющих примитивов в отдельный подъяэык управления, который встроен в язык параллельного программирования.

Этот подъязык управления должен позволять описывать сложные улравляющие взаимодействия и в то же время он должен основыватьсл на относительно простом, формальном семантическом базисе, позволяющем достаточно строго и надежно задавать корректные структуры управления и/или верифицировать их автоматически. Так, в работе (60) предложена формальная методика описания структур управления с помощью управляющих выражений (26), семантика которых представля. (36 ется в терминах сетей Петри.

Алгебра регулярных и иерархических сетей, рассьютренная в главе 6, предназначена, в частности, для аналогичных целей. На ее основе предложен подъязык управления, являющийся частью базового языка параллельного программирования '[4) . Основной конструкцией подъязыка управления служит формула управления, составленная из операторов (модулей) языка как аргументов и из операций управления, Оператору соответствует атомарная сеть, состоящая из единственного перехода (простого в случае простого оператора и составного в случае составного оператора ипи модуля), Операции улравпения — зто операции над сетями, введенные в а 6.1. Таким образом, семам.

тика структу)хи управления, заданной формулой управления, представима регулярной или иерархической сетью. Формула управления задает некоторую конкретную структуру управления. Однако, наряду с операциями в алгебре сетей (и структур управления), можно рассматривать и функции нал множествами сетей (н структур управления) . Такие функции будем называть функциями управления нли типами управления [7), В контексте структур управления последний термин используется приблизительно в том же смысле, в котором используется понятие "тип данных" так как функция управления задает класс структур управления, обладающих некоторым общим свойством, например, семейство последовательных структур, конвейерных структур и т.п.

Тип управления может быть описан программистом, ему может быть присвоено имя (идентификатор), которое далее может использоваться в формулах управления. В денном параграфе мы обсудим принципиальную сторону использования типов управления и приведем примеры их описания и применения для конструирования параллельных программ. Функция (тип) управления может быть описана обычным образом по следующей схеме: функция.управления:: = нмя-функции-управления (список чЬормальных.параметров) = формула.управления. Формальный параметр — зто параметр. идентификатор, который при использованюч (вызове) функции управления заменяется фактическим оператором (именем оператора) или структурой из операторов (сетью) . Если в описании функции управления используются только скалярные параметры, то эта функция залает жесткий гоп управления, описывающий некоторую фиксированную абстрактную структуру управления, конкре.

тизация которой может осуществляться только путам непосредственной замены формальных параметров конкретными операторами (их именами) и сетями из операторов. Например, можно описать взаимное исключение исполнения двух операторов, введя тип управления птцтех 2 с помощью следующего описания: пютех 2 (а, Ы = 1 " (а |Ь) гле в и Ь вЂ” формальные параметры. Для описания параллельного исполнения двух пар последовательных операторов можно ввести тип рагзец 4 с помощью следующего описания; рагзец 4 (а, Ь, с, д) = 1((а; Ы, (с; гг) ) .

Семантика описанных типов управления изображается сетями на рис. 8.8,а иб. Наконец, можно описать еще один тип управления, используя ранее описанные типы управления: рагех 4 (а, Ь, с, 8, = (рагюц 4 (а, Ь, с, г)), птцтех 2 (а, с), пюьзх 2 (Ь, г()). 139 5 Рив Э.э ° а Сеть, иллюстрирующая последний тип управления, показана на формула алгебры сетей, описанной в главе 6, а формула, в которой использованы Функции управления точно таким же образом, как используются Функции в арифметических выражениях. Символы э, Ь, с, д в левой части описания типа рагех 4 являются фактическими параметрамм по отношению к типам (функциям), встречающимся в правой части.

В качестве фактических параметров могут, таким обрезом, выстугють формальные или конкретные операторы и структуры управления, в том числе задаваемые функциями управления. Везде далев мы будам применять термин "формула управления" в расширенном смысле, допуская использование как операций, так и функций управления. Введенные выше типы управления являются жасткими типами с фиксированным числом операторов или модулей. В общем случае желательно иметь типы управления, описывающие семейство подобных структур с "похожей" топологией управляющих связай, но с разным числом операторов, Если ограничиться только жесткими типами, то пришлосьбы описы. вать большой набор функций управления: например, взаимное исключение для 2, 3, 4 и т.д. операторов.

Чтобы избежать такой ситуации, наряду со скалярными объектами алгабры управления (операторами, сетями из операторов) необходимо рассматривать составные объекты — векторы и матрицы операторов и сетей из операторов. Другими словами, следует обобщить алгебру сетей на случай векторов и матриц сетей. Операции алгебры регулярных и иерархических сетей, введенные в главе 6 для "скалярных" сетей, распространяются на векторы и матрицы сатей следующим образом.