События и условия

Простое представление системы сетью Петри основано на двух основополагающих понятиях: событиях и условиях. События – это действия, имеющие место в системе. Возникновением событий управляет состояние системы. Состояние системы может быть описано множеством условий. Условие – есть предикат или логическое описание состояния системы. Условие может принимать либо значение «истина», либо значение «ложь».

Так как события являются действиями, то они могут происходить. Для того чтобы событие произошло, необходимо выполнение соответствующих условий. Эти условия называются предусловиями события. Возникновение события может вызвать нарушение ; предусловий и может привести к выполнению других условий, постусловий.

В качестве примера рассмотрим задачу моделирования простого автомата–продавца. Автомат–продавец находится в состоянии ожидания до тех пор, пока не появится заказ, который он выполняет и посылает на доставку. Условиями для такой системы являются: а) автомат–продавец ждет; б) заказ прибыл и ждет; в) автомат–продавец выполняет заказ; г) заказ выполнен. Событиями будут: 1. Заказ поступил. 2. Автомат–продавец начинает выполнение заказа. 3. Автомат–продавец заканчивает выполнение заказа. 4. Заказ посылается на доставку. Предусловия события 2 (автомат–продавец начинает выполнение заказа) очевидны: (а) автомат–продавец ждет; (б) заказ прибыл и ждет. Постусловие для события 2: (в) автомат–продавец выполняет заказ. Аналогично мы можем определить предусловия и постусловия для других событий и составить следующую таблицу событий и их пред– и постусловий:

Событие	Предусловия	Постусловия
1	нет	б
2	а, б	в
3	в	г, а
4	г	нет

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

Сеть Петри на рис.6.6 иллюстрирует модель приведенного выше автомата–продавца.

Рис.5.6. Сеть Петри для простого автомата–продавца

Эвм с конвейерной обработкой

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

На протяжении ряда лет было предпринято много попыток увеличения производительности вычислительных систем путем параллельного выполнения нескольких функций. Примером такого подхода к построению высокопроизводительной ЭВМ является использование конвейерной обработки. Этот метод обработки подобен функционированию сборочного конвейера и особенно удобен для работы с векторами и массивами. Конвейер состоит из набора операций, которые могут выполняться одновременно. Когда операция k завершается, она передает свой результат операции (k + 1) и ожидает от операции (k — 1) нового задания. Если каждая операция занимает t единиц времени и всего существует n операций, то завершение обработки одного операнда потребует nt единиц времени. Однако, если на конвейерную обработку продолжают поступать новые операнды, результаты могут выдаваться со скоростью один каждые t единиц времени.

В качестве примера рассмотрим сложение двух чисел с плавающей точкой. Основные шаги этой операции предполагают:

1. Выделить экспоненты обоих чисел.

2. Сравнить экспоненты и изменить, если необходимо, должным образом порядок большей и меньшей экспонент.

3. Сдвинуть точку в числе с меньшей экспонентой для их уравнения.

4. Сложить дроби.

5. Нормализовать результат.

6. Проверить экспоненту на переполнение и сформировать экспоненту и дробь результата.

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

Координацию различных блоков можно осуществлять несколькими способами. Обычно управление конвейерной обработкой является синхронным: время, отпущенное на выполнение каждого шага конвейера t, постоянно и фиксировано. Каждые t единиц времени результат каждого блока перемещается по конвейеру, чтобы стать входом для следующего блока. Однако при синхронном подходе обработка может быть приостановлена без необходимости, так как требуемое время может изменяться от блока к блоку, а также внутри данного блока для различных входов. Например, для выполнения шага нормализации результата при сложении чисел с плавающей точкой может потребоваться различное количество времени в зависимости от того, на сколько разрядов необходимо произвести нормализующий сдвиг и в какую сторону: вправо или влево. В этом случае, поскольку время t должно быть выбрано максимальным, необходимым для самого медленного блока конвейера, может оказаться так, что большую часть времени все единицы будут пребывать незагруженными, ожидая окончания t единиц времени.

В асинхронном конвейере в среднем процесс обработки может быть ускорен сигнализацией о завершении каждого шага конвейерной обработки и готовности передать свой операнд и получить новый. Результат шага k конвейерной обработки может быть послан на шаг (k + 1), как только шаг k выполнен, а блок {k + 1) свободен. Рассмотрим произвольный шаг конвейерной обработки. Очевидно, нужно иметь место, куда можно поместить входы и выходы в то время, как они используются или производятся. Обычно это предполагает наличие регистров: блок использует значение своего входного (буферного) регистра для вычисления значения выходного (буферного) регистра. После этого необходимо ждать, пока (1) – выходной регистр блока не будет очищен путем пересылки содержимого во входной регистр следующего блока и (2) – новое входное значение не появится в его входном регистре. Таким образом, для управления блоком k конвейера необходимо знать, когда выполняются следующие условия:

• входной регистр заполнен; входной регистр пуст;

• выходной регистр заполнен; выходной регистр пуст;

• блок занят;

• блок свободен;

• пересылка осуществлена.

На рис.5.7 и 5.8 показано, как можно промоделировать асинхронный конвейер такого типа. На рис. 5.7 приведена блок-схема конвейера, моделируемого сетью Петри на рис. 5.8.

Рис.5.7

Отметим, что в этой модели мы промоделировали реальную работу блоков конвейера как непримитивных событий. Это позволяет нам игнорировать на этом уровне конкретные детали того, что делают блоки, и сосредоточиться на их правильном взаимодействии. Каждая операция также может быть промоделирована сетью Петри. Затем сети Петри для каждого блока можно внести в сеть Петри на рис. ???, получив более детальную сеть. Такая возможность моделирования системы на нескольких различных уровнях абстракции, т. е. иерархическим образом, может быть весьма полезна.

Рис.5.8.

Для введения параллелизма предлагается операциях parbegin и parend (рис.6.9). Структура управления была предложена Дейкстрой и имеет вид parbegin S₁; S₂; ...; S_n parend, где S_i – предложение. Смысл структуры parbegin/parend заключается в параллельном выполнении каждого из предложений S₁, S₂, ..., S_n.

Рис.5.9.