Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 37
Текст из файла (страница 37)
Понятия эквивалентности и включения имеют в данном случае особую важность. Некоторые исследования по соотнесению различных моделей уже проведены Обзоры [20, 41, 197[ помогли собрать воедино описания нескольких моделей. В частности„в [41[ дано общее определение управляющей структуры„ которое позволяет определять единым образом различные модели. Это привело к рабатам [236, 240), в которых сравниваются различные модели для получения иерархии моделей, соотнесенных по их мощности моделирования. Независимый результат получен в [5), где сравнивается большое число моделей и с»роится другая иерархия с подобной структурой.
Оба результата — и в [240) и в [5) — получены с помощью использования языков моделей для их сравнения. Класс моделей А определяет класс языков 5(А). Два класса моделей, А и В, будут эквивалентны по определению, если ЦА) = — 14В). Это означает, что для любого определенного энземпляра а класса моделей А с языком 5(п) должен существовать экземпляр Ь класса В с идентичным языком 5(а) = 5(Ь). Если языки правильно характеризуют зги модели, то оин являются искомым средством для сравнения двух классов моделей. Однако.
как мы видслп, не вполне ясно, как определить язык для моделей параллельных вычислений. Исследования в области определення1языков сетей Петри привели к по меньшей мере 12 различным определениям языков, большинство из них, очевидно, различны. Различия в этик языках могут привести к различиям в соотношениях эквивалентности и включения между моделями. С другой стороны, если различия между моделями действительно существенны, то опи могут быть не чувствителы«ы к (незначительным) изменениям н определениях эквивалентности и включения. Таким образом, подобность результатов, полученных в [5) и [240[, весьма важна из-за того, что в этих работах попользовались различные определении эквивалентности и включения. Однако нельзя утверждать, что этн результаты бесспорны, »»вторы [175) также сравнили большое число моделей параллельных вычислений н пришли к другим выводам.
Их сравнение основывается на очень детальном анализе структуры н просшрансл«ва состояний отдельных представителей илассов моделей. Этим обьясняется значительное отличие результатов [178[ от резуль«атов [5) и [240[ ° Модели параллельных вычислений Итак, установлено, что существуют различия в мнениях исследователей по вопросам о том„ какие модели должны сравниваться, как их сравнивать? Сравнение, проводимое в этой главе, основано как на структурных характеристиках, так и на характеристиках поведения.
Мы будем говорить, что класс моделей А является меньшим илп равным по мощности моделирования (включается в) классу В, если для любого данного экземпляра а класса А существует алгоритм построения экземпляра Ь класса В, для которого верно, что: 1.
Каждая структурная компонента модели а представляется (небольшим) различимым множеством компонент моделе Ь. Размер модели Ь (чпсло элементов) отличается в худшем случае на мультиплнкативную константу от размера модели а, причем константа определяется классами моделей А н В.
а не конкретными экземплярамн а н Ь. 2. Любая последовательность действий в а может быть промоделирована последовательностью в Ь„с длиной последовательности в Ь, отличающейся не более чем на мультипликативную константу от длины последовательности в а. а. Модель Ь заходат в тупик только тогда, когда заходит в тупик модель ач Модель заходит в тупик, если все ее действия становятся невозможными. Цели введения этих ограничений очевидны. Первое ограничение устанавливает структурное подобие двух моделей; второе ограничение гарантирует, что две модели ведут себя одинаково. Однако мы не требуем абсолютного соответствия между. двумя моделямн.
Мы допускаем представление действия в одной модели (короткой) последовательностью действий в другой модели нли представление компоненты (подобной поникни нлн переходу) набором (небольшим) компонент. Следовательно, действие в одной модели может ьюделироваться последовательностью из двух действпй в другой модели. Последнее ограничение требует, чтобы более мощная модель не совершала ошибок, когда их не совершает менее мощная. Это исключает возможность построения модели, которая недетермннированно выбирает одно из нескольких действий и останавливается, если оказывается, что был сделан неверный выбор. Две модели эквивалентны, если они включают друг друга.
Это предполагает, что любой экземпляр какой-либо модели преобразуется в экземпляр другой. С учетом сказанного выше, рассмотрим соотношения между следующими моделями параллельных вычислений: 1. Конечные автоматы [42, 97, 1291. 2. Маркированные графы [54). 3. Графы вычислений [1471. 4. Р/Ч-системы 146, 791.
5. Сисгемы с сообщениями [258). 6. Графы ЦС1 Л [49, 50, 51, 1041. 7. Системы сложения векторов [1481. 8. Снстемы замещения векторов [1501. 9. Расширенные сети Петри (гл. 7). Для каждого класса моделей вначале определим модель и приведем пример. Затем обсудим связь ее с другими моделями параллельных вычислений.
В.1. Конечные автоматы В разд. 3.3.1 и 7.4.1 показано, что конечные автоматы легко преобразуются в сети Петри. Конечные автоматы использовались несколькими исследователями в качестве модели параллельных вычислений. Бредт [421 определил модель, основанную на концепциях, вложенных в аппаратуру ЭВй[. Каждый процессор модели- руется конечным автоматом с входными и выходными каналами, которые связывают один процессор с другим. Состоянием каждого входного и выходного канала является либо О, либо 1. Поскольку каждый выходной канал одного процессора является входным каналом другого процессора, и существует конечное число процессоров и конечное число каналов, каждый с конечным числом состояний, то и вся система имеет конечное число состояний.
Гильберт и Чандлер (971 использовали модель с общей памятью, а не каналы связи. Это означает, что их модель в большей степени, чем модель аппаратуры Бредта, направлена на моделирование программных процессов с совместно используемой памятью, но все же является не чем иным, как моделью с конечным числом состояний, и, следовательно, включена в модель сети Петри. 6.2. Маркированные графы Маргсараеаггпьгг графы были рассмотрены в равд.
7.4.2. Как подкласс сетей Петри маркированные графы, очевидно, обладают более ограниченной мощностью моделирования. Маркированные графы непосредственно не сопоставимы с конечными автоматами, но, по-видимому, являются двойственными к ним. Таким образом, мы получаем изображенное на рис. 8.1 соотношение между сетями Петри, конечными автоматами и маркированными графами. Сети /7етра Рнс. В.1. Соотношение межлу сетями Петри, маркированны- ми графами и конечными ав- томатами.
щеирайаниь е Конечные ерагры аототатаг 8.3. Графы вычмсненнй Одной из наиболее ранних моделей параллельных вычислеяий была модель графов еы«ислений 11471. Ее предложили главным образом для представления параллельного выполнения программ, вычисляющих 'арифметические выражения. Граф вычислений с1 определяется как ориентированный граф 6=- ()г, А), где 1'=- (иь о,, ..., и„) — — множество узлов; Л =- = (аы аа, ..., п ) — множество дуг. Каждая дуга аг е А есть упорядоченная пара узлов (о1, еа), пРедставлЯющан дУгУ из о1 к па.
Каждой дУге и; = (ау, оа) сопоставлена четверка(11.ы )г;,„, )Г'„, 7),,). Каждая дуга предсгавляет о«средь элементов данных, полученных процессором в узле ет и используемых процессором в узле пе. 11е есть число элементов данных, находящихся первоначально в очереди, соответствующей дуге из с у к па. Узел па подгот член, если на каждой дуге, напраз- Модели параллельмых вычивлемиа с1,0, О, 1) 13,0.1,11 Рис. В,2. Граф вычиспеиий. ленной к узлу оа из каждого узла оп присутствует не менее Тьл элементов данных.
Т;,а называется пороговььн значением. При выполнении операции, соответствующей узлу о,, удаляется %71ьь (Фда ~ Т;,4 элементов данных нз очереди, соответствующей дуге, направленной к оа. Когда операция, соответствукицая ию завершается, то она помещает $'м, элементов данных в очереди, соответствующие каждой дуге (оп, а,), направленной из узла оа к узлу ос. На рис. 8 2 изображен пример графа вычислений.
В начальном состоянии узел о, подготовлен, поскольку имеет один вход, и в очереди этого входа присутствуют три элемента данных. При выполнении ос он удаляет один элемент данных из этой очереди и по завершении операции помещает один элемент данных на дугу из о~ к ог один — на дугу из о, к оа. В этом новом состоянии может выполняться либо о„либо о„так как оба имеют достаточно элементов данных во входных очередях для удовлетворения пороговых условий. Граф вычислений легко моделируется сетью Петри. Каждая дуга представляется позицией, а каждый узел графа вычислений становится переходом.
Переход, соответствующий узлу рю имеет Т;.» входных дуг нз позиции, представляющей дугу из о; к оа. Это га- Рис. 8.3. Сеть Петри, эквивалентная графу вычислений, изображенному на рис. 8.2. рантирует то, что переход будет подготовленным только тогда, когда пороговое условие выполнено. Однако, когда переход запущен, он может удалить только ам» фишек, поэтому Т,,» — В'ты дуг направляются обратно от йерехода п» к позиции, представляющей дугу из пт к и». Кроме того, $~»„меток помещаются в позицию, представляющую дугу из иг к и,. Начальная маркировка определяется значениями 1,,~,.
На рис, 8.3 изображена сеть Петри, построенная описанным вы ше способом для графа вычислений на рис. 8,2. Легко показывается, что маркированные графы могут быть промоделированы графами вычислений, для которых ТП» = %'ь» для всех узлов и, и п». Однако графы вычислений являются более мощным средством, чем маркированные графы, благодаря возможности моделировать ситуации с Т,,» ) В',.». С другой стороны, графы вычислений и конечные автоматы ие сопоставимы, как маркированные графы и конечные автоматы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
