Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984, страница 9

Эта сеть Петри является моделью конечного автомата. На рнс. 3.13 изображена сеть Петри, соогветствующая автомату с рпс. 3.9. На рис. 3.14 — сеть 11етрн, соответствующая автомату с рис. 3.10. При сравнении сетей Петри на рис. 3.13, 3.14 с эквивалентными автоматами на рис. 3.9, 3 10 возникают некоторые вопросы. Прежде всего: почему модель сети Петри предпочтительнее описания конечным автоматом? Описание автоматом более понятно, чем описание сетью Петри, в которой б переходов, 24 дуги и 7 илн 8 позиций. Это верно.

Однако мы показали, что сети Петри могут представлять любую систему„представимую автоматом, и зто свидетельствует о больших возможностях сетей Петри. Кроме того, следует отметить, что модель сети Петри имеет опре- ,деленное преимущество при композиции автоматов. Например, Главе 8 Рис. 3.14.

Сеть Петри, эквивалентная автомату иа рнс. 3.10. заметим, что выходной алфавит автомата с рис. 3.9 идентичен входному алфавиту автомата с рис. 3.10. Передавая выход автомата с рис. 3.9 на вход автомата с рис. 3.10, можно построить композицию автоматов, вычислякяцуюдополнениедо двух и проверяю Рис.

3.15. Составнойтавтомат, прелставляющнй последовательную компови- пию автоматов, иэображен- имк иа рис. 3,0, 3.10. 110 Сети Петри длл лоделироапнил щую четность. Такая композиция является автоматом с составными состояниями, компоненты которых — зто состояния обоих подавтоматов. В сетях Петри такая композиция есть просто совмещение выходных позиций первой сети с входными позициями второй. Нз рис. 3.15 показана композиция автоматов, а на рис. 3.16 — составная сеть Петри. Другое преимущество представления сети Петри связано с иными формами компоэицин.

Например, параллельная композиции позволяет компонентам композиции автомилтав работать одновременно. В этом случае вновь получаем автомат с составными состояниями, в то время как для сети Петри — это просто дублирование фишек во входах, соответствующих вхсдиым символам, и использование их во всех компонентах сети Петри. Наконец, иа выходе мы просто выбираем соответствующие позиции выхода. Например, если мы хотим соединить параллельно две сети Петри (рис. 3.13 и 3.14), то в результате получим сеть Петри, подобную изображенной на рис.

3. 17, которая вычисляет дополнение числа до двух и его четность. Если на входе появляется символ сброса, то выходом явлнется четиасть. Упражнения К Покажите, что оса подхода к моделированию вэаимодействня между сетью Петри и ее окружением (с нспольэоваинем переходов или поенная) эквивалентны. ЗЗ.2. ЭВМ с конвейерной обработкой Возможность моделировать параллелизм и довольно простого объединения подсистем, представленных сетями Петри, делают сети Петри весыиа полезным инструментом моделирования сложной аппаратуры вычислительных систем.

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

Конвейер состоит из набора операций, которые могут выполняться одновременно. Когда операция й завершается, она передает свай результат операции (й + 1) и ожидает от операции (А — 1) нового задания. Если каждая операция занимает 1 единиц времени и всего существует п операций, то завершение обработки одного операнда потребует п1 единиц времени. Однако, если на конвейерную обработку продолжают поступать новые операнды, результаты могут выдаваться со скоростью один каждые г единиц времени. Глинки Л н О.

о ж д Ф 1" Я Ю Ф с а Я Ф н $ о с„2 Сети Петри для лвделидояаяия ! 1 Рис. 3.$7. Параллеяьяая колшозяция сетей Петри с рис. 3.!3, 3.!4. Необходимо обеспечивать дублирование входов дая обеих компонент с помощыо спепнальиай подсети. Глава 8 В качестве примера рассмотрим сложение двух чисел с плавающей точкой. Основные шаги этой операции предполагают: 1. Выделить экспоненты обоих чисел. 2.

Сравнить экспоненты и изменить, если необходимо, должным образом порядок большей и меньшей экспонент. 3. Сдвинуть точку в числе с меньшей экспонентой для их уравнения. 4. Сложить дроби. б. Нормализовать результат. 6. Проверить экспоненту на переполнение и сформировать экспоненту и дробь результата. Каждый из этих шагов может быть выполнен отдельным вычислительным блоком, где каждый отдельный операнд передается от блока к блоку для выполнения операции сложения.

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

В асинхронном конвейере в среднем процесс обработки может быть ускорен сигнализацией о завершении каждого шага конвейерной обработки и готовности передать свой операнд и получить новый. Результат шага й конвейерной обработки может быть послан на шаг (й + 1), как только шаг А выполнен, а блок (А + 1) свободен. Рассмотрим произвольный шаг конвейерной обработки.

Очевидно, нужно иметь место, куда можно поместить входы и выходы в то время, как они испопьзуются илн производятся. Обычно это предполагает наличие репктров: блок использует значение своего входного (буферного) регистра для вычисления значения выходного (буферного) регистра. После этого необходимо ждать, пока (1) — выходной регистр блока не будет очищен путем пересылки содержимого во входной регистр следующего блока и (2) — новое входное значение не появится в его входном регистре.

Таким образом, для управления блоком й конвейера необходимо знать, когда выполняются следующие условия: Сети Петри для моделирования ° входной регистр заполнен; ° входной регистр пуст; ° выходной регистр заполнен; ° выходной регистр пуст; ° блок занят; ° блок свободен; ° пересылка осуществлена. На рис. 3.18 н 3.19 показано, как можно промоделировать асинхронный конвейер такого типа. На рис. 3.18 приведена блок-схема конвейера, моделируемого сетью Петри на рис.

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

Блом Р дыкоднонреваснр донна д Бледной рееистр донна й+Ф Рис. 3.13. Блок-схема устройства управления асинхронной ЗБМ с конвейерной обработкой. Глава В Выгадай регистр Е-г' заполнен Выводной регис Е ! «уст Вгодной регистр * пуснг Внодной росист В гон«ложи Вгиодной регистр Н ге«аггее Выгодной регист В пуст Взодной регистр й г «уст Вгодавй регистр А ет заполнен у Рве. 3.19. Модель сета Петро устройства увравямшя асинхронной ЭВМ с конвейерной обработкой. ЗЗ.З. Кратные функциональные блоки Конвейерная структура управления, рассмотренная в~предыдущем разделе, — это один из подходов к построению очень больпщх быстродейств!нацих вычислительных систем.

Другой подход, использованный, например, в С!!С 6600 1291) и 1ВМ Зб(У91 1!О),. использует крлзлные функциональные блоки. В СВС 6600 нмеетси 10 функциональных блоков: блок ветвления (для условных переходов); булев блок (для булевых операций); блок сдвига; блок сложения с плавающей точкой; блок сложения с фиксированной точкой; 2 блока умножения; блок деления и 2 блока приращения (для индексирования). Кроме того, имеется несколько регистров для хранения входных и выходных значений функциональных блоков.